Sections of strings or arrays and concrete types

General Usage Performance
1

I’m starting to wade into the wonderful world of SnoopCompile and the many insights it gives (and realising along the way that my understanding of types, inference etc, is shallow to say the least). One thing I got from reading the docs (and getting excellent comments by @tim.holy) was that it’s better, where possible, to use concrete types to reduce the time to first call.

In my code, I often have to repeatedly work on sections of arrays: either a subset of a String or a subset of a Vector say to simplify a Vector{Int}. Intuitively, it seemed to me to be a good idea to not create new objects for these, so I often basically do:

subset = SubString(original_string, range)
do_thing(subset)

and the same with @view of vectors. This is often in a recursive function so the signature of do_thing in my code is typically something like:

do_thing(obj::Union{SubString{String}, String})

or

do_thing(obj::AbstractVector{Int})

but these are not concrete types and from a discussion with @tim.holy ; I believe that this is not ideal.

My question is then, am I better off making the original objects into a sub-version of themselves before processing them? i.e.:

processed_original_string = SubString(original_string)
do_thing(processed_original_string)

and

processed_original_array = @view original_array[eachindex(original_array)]
do_thing(processed_original_array)

?

A subsidiary question is about returned types, does concreteness matter here as well? For instance let’s say I have a function which returns a vector with objects of type either A or B or both, does something like:

return_vector(args)::Vector{Union{A,B}}

cause issues? Thanks a lot!

1 Like
2

A lot of it comes down to the tradeoff among costs. As you say, creating a String from a SubString{String} does have a cost:

julia> str = SubString("hello", 2:4)
"ell"

julia> using BenchmarkTools

julia> @btime String($str)
  11.030 ns (1 allocation: 32 bytes)
"ell"

If that’s in the inner loop of your program, you might come to hate that 11ns—you’d be better off if you didn’t need to convert.

In contrast, suppose you have

function somebigfunction(filename::AbstractString)
    # this takes 300ms to compile and 1ms to execute
end

In terms of runtime performance, if somebigfunction takes 1ms to execute, you’ll never notice the 11ns it would take to convert the filename to a String. So from a runtime performance standpoint, it’s completely, utterly irrelevant whether you convert to a String before calling it. But you might notice paying 300ms each time you compile it for:

  • filename::String
  • filename::SubString{String}
  • filename::AbstractString (for those cases where you’re calling this with poor inferrability of filename)

If you have to compile it for all 3 types, you might have to wait a full second, whereas it’s only a third of a second if you could get away with compiling it only once.

A way to standardize on filename::String and ensure that you never pay that 300ms for any other type is to define your methods like this:

function somebigfunction(filename::String)
    # this takes 300ms to compile and 1ms to execute
end
somebigfunction(filename::AbstractString) = somebigfunction(String(filename)::String)

Now, you can’t always do this: part of Julia’s power is the ability to write generic functions that can handle “anything.” But you don’t always need that power, and that power comes with the cost of pretty bad latencies. Fortunately, Julia is flexible enough that you don’t have to use that power if you don’t want to.

As is hopefully clear, these are not black vs white issues: it requires understanding where the costs of a package are coming from, and you might do one thing in one circumstance and the exact opposite in a different circumstance. It comes down to understanding the tradeoffs in each case.

7 Likes
3

There is no runtime performance problem with using abstract types in function signatures. You don’t even need to declare a type at all — do_thing(obj) = ... is perfectly fine with rare exceptions for Type and Function arguments.

The compiler will generate specialized versions of your functions based on the concrete types inferred wherever it is called. For example, if you define f(x)=x+1 and then write f(3) + f(2.5), the compiler will generate (and inline, in this case) specialized versions of f for Int and Float64 overhead.

The only reasons to declare argument types are usually dispatch (to have different methods of the function for different types), correctness (to prevent an invalid argument from being passed by accident), or clarity (to indicate to the caller what type is expected). You should generally make your argument declarations as abstract as possible for correctness, so that your code is more generic/extensible.

e.g. use obj::AbstractString or obj::AbstractVector{<:Integer} rather than Union{SubString{String}, String} or obj::AbstractVector{Int}.

  • This is an entirely separate from the question what argument types you should pass, e.g. passing a view vs. making a copy.

  • As @timholy points out, compile-time performance may be worse if you have to compile more specializations of a function. But that’s more about what argument types you pass than what you declare in the function definition.

3 Likes
4

All that’s true, but anyone playing with SnoopCompile has a goal to reduce latency. In such cases, there are reasons to limit signatures. This is just a glorified version of this style guide tip and one of many tricks for reducing latency.

When you need Julia’s specialization, the last thing you want to do is get in its way. But when you don’t need the specialization (e.g., there’s nothing in somebigfunction that cares one whit about how filename is actually represented), then there’s every reason to try to eliminate unhelpful and latency-costly type-diversity.

4 Likes
5

But as you point out in the style guide, this is a function of what arguments you pass, not of what arguments you declare in the method definition, though narrowing the definition temporarily could help you catch such call sites.

I generally consider overly narrow declarations to be an anti-pattern in Julia that most new Julia programmers fall prey to instinctively; writing generic code is hard but extremely useful.

4 Likes
6

Thanks both, I think in my context the answer is pretty clear in that the functions I’m talking about are not exposed to the user (“backend functions”) and are exactly of the type that Tim Holy describes. So in that respect I could “afford” to make them pretty specific if it helps fight noticeable latency.

For a package providing functions that I could expect users to extend, then I think @stevengj 's advice holds and it’s not a good idea to over-specialise.

PS: if I understood both your answers correctly, specifying the return type has no impact on inference latency?

1 Like
7

The return type declaration of a function wouldn’t affect its compilation latency, but can affect the compilation of its callers. If your function’s return value is used within a callee but its type is hard to infer, then declaring it would help the compiler a lot. We can’t tell whether it’s best to do that without its usage context.

3 Likes
8

Learning the virtues of generic code should indeed be the first step. But once that lesson is absorbed, ambitious developers can go on to understand how their design choices affect latency. Good tools for identifying the source of latency have been a long time coming, but now that we’re mostly there we should encourage experimentation and innovation in this space, just as we coach people through how to improve the runtime performance of their code. For better or for worse, declaring argument types is sometimes an effective way to reduce latency.

3 Likes
9

Sorry if I missed something, but what about:

function somebigfunction(@nospecialize filename_ :: AbstractString)
    filename = String(filename_)::String
    # ... rest of your code here
end

as a compromise?

10

That also reduces compile-cost, but there are tradeoffs:

  • @nospecialize doesn’t prevent specialization in inference, only codegen (the logic being that it’s useful for callers who know the type concretely to know what kind of type will be returned)
  • if you trigger non-inferrability in the call graph from somebigfunction, it might hurt runtime performance or make you more vulnerable to invalidation.

From the standpoint of latency the ideal situation, when you can achieve it, is concrete inference with low diversity of argument types.

Again, all these considerations are for when it doesn’t cost you in some other way that matters more to you. If you need Julia’s specialization wizardry, by all means one should embrace it.

3 Likes