Designing APIs. defining new methods versus passing in functions

General Usage
1

I have previously been conflicted on what I think are two general kinds of APIs in julia. For the sake of an example, take the sort function:

sort(v; alg::Algorithm=defalg(v), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

I will focus on the lt and by arguments. Another possible API would be to not have those keyword arguments, and just define the appropriate methods on some user-defined type. As a generic example:

struct SortWrap{By, IsLess, T}
  value::T
end

function Base.isless(a::S, b::S) where {T, By, IsLess, S <: SortWrap{By, IsLess, T}}
  return IsLess(By(a.value), By(b.value))
end

# allow SortWrap{By, IsLess}(value)
function (::Type{SortWrap{By, IsLess, T} where T})(value) where {By, IsLess}
  T = typeof(value)
  SortWrap{By, IsLess, T}(value)
end

Then we can use a custom “by” and “isless” as follows:

data = rand(1:10, 10)

sort(SortWrap{identity, isless}.(data))

sort(SortWrap{Base.:-, isless}.(data))

I have not benchmarked to see if there is any performance penalty. But assuming there isn’t a significant performance difference, is there any reason to prefer one approach over the other?

One vague sense I have is driven by the recognition that there is no matrix multiplication function in julia that takes in add and multiply arguments. Instead, you define a new number type with the appropriate scalar + and * methods. There also isn’t much sense in defining a MatMulWrap struct with parametrizable + and * operations.

2

Requiring the user to create an instance of some custom parametric type seems much more complicated than just passing the functions as arguments. What’s the benefit of the 2nd API?

I saw a blog post recently describing an approach to library design where you think about

  1. what are the things the library operates on
  2. what are the operations on those things

I think this approach maps nicely into Julia’s types and functions (sometimes your library introduces new functions, sometimes it extends some other library’s functions).

Generally I think you should avoid the user needing to use types that don’t represent “things” that they care about.

-s

4 Likes
3

I don’t have a concrete answer to your question about benefits, but I do fear that my example didn’t illustrate what I actually had in mind. So if I may try again.

What business do you have trying to sort a “thing” that doesn’t have isless defined on it? Shouldn’t it just have an isless method? If it has the wrong islessmethod defined on it, then you can introduce a new thing that has the desired behavior. That’s what the wrapper was meant to illustrate.

The arguments to the sort function feel to me out of place, actually (I know there is a history in other languages of sorting functions taking in these kinds of arguments). Why doesn’t the maximum function take in an lt argument too? Or for that matter, any function that calls isless, why doesn’t that function take an lt argument? That’s what the first API would do.

Once you define isless on your type (your thing), then you can use min, minimum, sort, you can use the lexicographic ordering induced by isless on NTuple{Thing}, and so forth. (So, here’s a benefit of the second API)

I understand that sort has this interface almost as a convenience. Sometimes you want to introduce a very context-specific notion of isless that you don’t want anywhere else in your program. And it could be a pain to define a new type with the appropriate behavior. (This is a benefit of the first API)

On the other hand, defining new types with new methods is favored in other contexts, e.g. defining new Number types with different arithmetic behavior.

4

One reason is of course performance: it is costly both in memory and CPU to wrap and then unwrap every single element. And how would you do sort! with a wrapper?

Another reason is convenience. IMO, it can be a more pleasant and efficient coding experience to use these arguments than requiring the developer to define isless.

Finally, it seems to me that the current approach offers the best of both worlds, since you can still define isless or wrap your elements, and then use sort without these arguments.

5

There are trade-offs between the two approaches, and both have their place.

Accepting a callable (which can be a function/closure, or a composite type value which is callable) does not require (but optionally allows) the user to define a type. The disadvantage is that if multiple such functions are required, it may be tedious to keep them in sync and pass all of them around to called functions.

Requiring that an interface (ie a collection of methods) is defined can remedy all these, with the downside that it makes one-off (potentially parametric) constructs like closures more difficult.

My (continuously evolving) rules of thumb are:

  1. if I flexibility is needed, or the API is used for parametric/one-off constructs, accept callables. Eg

    sort(xs, by = x -> f(x, a))

    where a is a parameter in the caller.

  2. If the problems are sufficiently complex, it is better to require an interface with the relevant methods. Setting up a composite type is not that much of an overhead, and it will be useful in unit testing etc.

  3. If multiple, more or less orthogonal functionalities are required, again go for the interface.

  4. It is fine to accept both, eg provide an API function which takes functions, and wraps them in a simple type, which provides the interface, but allow for the interface directly. You may want to look at base/ordering.jl for a WIP example.

4 Likes
6

One other aspect not mentioned yet is locality - with the option to give a custom lt for sorting only, you can change the sorting behaviour for this call only, without impacting anything else as is the case with overwriting isless or wrapping the thing in a new type. This is useful because (in my experience) the vast majority of the time when passing that custom function you only want to get a different sorting that one time, not have it impact different parts of your code.

1 Like
7

@Sukera, this is what I meant when I wrote

8

I actually wouldn’t expect this to be much of a problem, if the code is type-stable, the wrapper is immutable, and any pass-through access is inlined then you can probably do this sort of thing with zero overhead. i.e. an Array{MyWrapper{T}} could take the same space as an Array{T}, and accesses could be just as fast.

Ah, I see your point, thanks for clarifying. I think it depends on whether you see isless as a property of the object or a way to customize the behavior of the function you’re applying (sort in this case).

This case seems like a grey area, but I see what you mean that isless seems like a property of the input type. by seems like something that you might commonly want to customize, e.g. you might want to sort by absolute value so give by=abs. Needing to wrap that in some kind of wrapper type seems needlessly complicated.

So I don’t think there’s a clear answer - it depends on your expected use cases. I think if you envision the caller of the function wrapping the input in a separate type just to change the behavior of this function then I’d rethink that design (as you mentioned).

2 Likes
9

For fun, I decided to benchmark SortWrap. I wanted to avoid allocating a temporary array via the broadcasted SortWrap{...}.(data), so I added a wrapper type:

extract_value(x) = x
extract_value(x::SortWrap) = x.value
struct SortWrapVector{By, IsLess, T, AV <: AbstractVector{T}} <: AbstractVector{SortWrap{By,IsLess,T}}
    data::AV
end
function SortWrapVector{By,IsLess}(data::AV) where {By,IsLess,T,AV <: AbstractVector{T}}
    SortWrapVector{By, IsLess, T, AV}(data)
end
Base.size(swv::SortWrapVector) = size(swv.data)
Base.length(swv::SortWrapVector) = length(swv.data)
function Base.getindex(swv::SortWrapVector{By, IsLess, T}, i) where {By, IsLess, T}
    SortWrap{By, IsLess, T}(swv.data[i])
end
Base.setindex!(swv::SortWrapVector, v, i) = swv.data[i] = extract_value(v)
Base.IndexStyle(::Type{SortWrapVector{By,IsLess,T,AV}}) where {By,IsLess,T,AV} = IndexStyle(AV)

the results:

julia> using Random, BenchmarkTools

julia> data = randn(2048);

julia> @benchmark sort!($data, by = identity, lt = isless, alg = QuickSort) setup = randn!($data)
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     66.836 ÎĽs (0.00% GC)
  median time:      71.364 ÎĽs (0.00% GC)
  mean time:        72.014 ÎĽs (0.00% GC)
  maximum time:     97.413 ÎĽs (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     1

julia> @benchmark sort!(SortWrapVector{identity,isless}($data), alg = QuickSort) setup = randn!($data)
BenchmarkTools.Trial: 
  memory estimate:  16 bytes
  allocs estimate:  1
  --------------
  minimum time:     149.802 ÎĽs (0.00% GC)
  median time:      157.055 ÎĽs (0.00% GC)
  mean time:        159.133 ÎĽs (0.00% GC)
  maximum time:     185.620 ÎĽs (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     1

That is quite the performance overhead. The vector-wrapper is actually worse than the broadcast:

julia> @benchmark sort!(SortWrap{identity,isless}.($data), alg = QuickSort) setup = randn!($data)
BenchmarkTools.Trial: 
  memory estimate:  16.13 KiB
  allocs estimate:  1
  --------------
  minimum time:     137.217 ÎĽs (0.00% GC)
  median time:      144.902 ÎĽs (0.00% GC)
  mean time:        145.877 ÎĽs (0.00% GC)
  maximum time:     200.958 ÎĽs (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     1

Any chance I am missing something obvious?

EDIT:
If isless seems like a property of the input type T, I would define an appropriate isless(a::T, b::T) method (so long as that isn’t committing type piracy).

EDIT:
and this performs even worse:

julia> @benchmark sort!(reinterpret(SortWrap{identity,isless,Float64}, $data), alg = QuickSort) setup = randn!($data)
BenchmarkTools.Trial: 
  memory estimate:  32 bytes
  allocs estimate:  1
  --------------
  minimum time:     166.313 ÎĽs (0.00% GC)
  median time:      173.687 ÎĽs (0.00% GC)
  mean time:        175.342 ÎĽs (0.00% GC)
  maximum time:     225.484 ÎĽs (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     1
10

Yes but the creation of that array, and conversion back to the original format, will likely take longer than the sorting itself. Or did you mean to do something similar to @Elrod’s example of reusing the same memory?

11

Re-using the memory. I’m not trying to get too into the weeds on this, just making the point that simple wrapper types used just for dispatch behavior are often zero-overhead, but I even so they’re often not the right API choice if there’s something simpler available. Julia’s type system is very expressive, I often get nerd-sniped into using it even when there’s a more direct way.

1 Like