How does Any actually work?

New to Julia
1

Earlier I posted an example function which has very poor runtime performance.

function demo(
    dict::Dict{Symbol, Vector},
    datetime_first::DateTime,
    datetime_last::DateTime,
)
    time = dict[:time]
    data = dict[:data]

    sum_value = 0.0f0
    sum_count = 0

    for ii in 1:length(time)
        if time[ii] >= datetime_first
            if time[ii] < datetime_last
                sum_value += data[ii]
                sum_count += 1
            end
        end
    end

    average_value = sum_value / sum_count

    return average_value
end

For an input of length 10^8 this should run in a few ms, instead it takes nearly a second.

The reason for the poor performance is all the variables in this function are inferred to have the type Any.

For me, this raised two questions.

  • Firstly, what actually is Any? I understand that it is not a concrete type, so there is no memory representation for an Any type. So, if sum_value and sum_count are of type Any, what sense can be made of this? In reality they are of type Float32 and Int64 respectively. So why does the machine code produce inefficient code?
  • Secondly, when the input data dict contains the following elements, what does the compiler actually do when it generates the code for function demo?
time::Vector{Float32} = ...
data::Vector{Float32} = ...
dict = Dict(:time => time, :data => data)
2

The variable dict has the type Dict{Symbol, DataType}, which would cause an error if passed as the first argument to your function demo. To construct an empty vector, use DateTime[] rather than Vector{DateTime}.

In any case, the compiler generates code for the argument type dict::Dict{Symbol, Vector} and won’t re-generate more performant code (i.e. specialization) depending on the actual dict argument you supplied. The compiler skips specialization because Dict{Symbol, Vector} is actually a concrete type, but it’s still a performance liability because it defines a container with non-concrete type Vector for the values in the dictionary. The consequence is that the compiler cannot infer the type of the actual elements in the vector.

An object of type Any is represented in memory as a label of the actual concrete type and a memory address which points to a variable-length chunk of memory (the length depends on the exact concrete type) that holds the data. Since the length is unpredictable, the memory is allocated in unpredictable non-contiguous locations, making performance bad.

1 Like
3

I’ve slightly re-formatted that line of code to better express what I was intending.

It’s just a dictionary with Symbol as the key, and two Vectors as the values. The Vectors are different types; Vector{Float32} and Vector{DateTime}.

4

Your re-worked code triggers a syntax error (just type it into the REPL to see). You could use this instead:

dict = Dict(:time => DateTime[], :data => Float32[])
5

This is what I don’t understand. If I pass in this object

time::Vector{DateTime}
data::Vector{Float32}
dict = Dict(:time=>time, :data=>data)

why does that result in poor performance.

Take for example the Vector{Float32}. Its in memory representation does not change when added to this dict object, or when that dict is passed to the function, or when the function de-structures the dict into a pair of Vectors.

So, each element (type Any) is not a pointer to a memory location containing (sizeof(Float32), value::Float32). It’s just an array of Float32.

Hence my confusion - hope that makes sense?

2 Likes
6

This is not intended to be code which compiles, please do not be distracted by that. It’s just pseudocode to show what the type is.

I have edited it to make it clearer.

7

Try inspecting the type of dict:

julia> typeof(Dict(:time => DateTime[], :data => Float32[]))
Dict{Symbol, Vector}

You’re getting a Dict with a non-concrete Vector type for the values. This is because you mixed two vectors with different element types.

1 Like
8

Is it a really stupid comment if I say the following?

  • If a function takes an argument of type Vector (which is abstract) then it will generate code for every possible concrete type of Vector{T} which could be passed to it?

It seems like such a function would be infinitely long because of the infinite possibilities in the argument types - but perhaps not?

For example, if the function body just added all the elements

function example(v::Vector)
    accum = 0.0f0
    for i in eachindex(v)
        value = v[i]
        accum += value
    end
end

then I suppose there are two (three) functions which need to exist

  • a function to get an element by index from v
  • a function to convert value to Float32
  • (the add function for two Float32 arguments - but this one isn’t as important since the types are concrete by this point)
9

Any matches any Julia type. You can think of it similar to what a void pointer might be in C. This pointer may then point to something that has a type tag. We can only figure out what the type of the pointed to object is by deferencing the pointer. Additionally, the type of the pointed to memory could change.

As a contrived example, I will use references below which are similar to pointers. I will then compile the functions to LLVM IR.

The example using Int compiles to a few simple LLVM instructions. In fact, it figured out that I’m just multiplying the value by 2, meaning we can just do a left shift.

The example using Any results in many more LLVM instructions. Here we have to carefully dereference the pointers, figure out the types, and then apply a generic add function, dynamically dispatching at runtime. As you can see this is considerably less efficient than the Int example. It becomes similar to what an untyped language like Python might do in its default execution model.

julia> r_int = Ref{Int}(1)
Base.RefValue{Int64}(1)

julia> r_any = Ref{Any}(1)
Base.RefValue{Any}(1)

julia> f(r) = r[] + r[]
f (generic function with 3 methods)

julia> @code_llvm f(r_int)
;  @ REPL[82]:1 within `f`
define i64 @julia_f_832({}* noundef nonnull align 8 dereferenceable(8) %0) #0 {
top:
; ┌ @ refvalue.jl:59 within `getindex`
; │┌ @ Base.jl:37 within `getproperty`
    %1 = bitcast {}* %0 to i64*
    %2 = load i64, i64* %1, align 8
; └└
; ┌ @ int.jl:87 within `+`
   %3 = shl i64 %2, 1
; â””
  ret i64 %3
}

julia> @code_llvm f(r_any)
;  @ REPL[82]:1 within `f`
define nonnull {}* @julia_f_834({}* noundef nonnull align 8 dereferenceable(8) %0) #0 {
top:
  %1 = alloca [2 x {}*], align 8
  %gcframe8 = alloca [3 x {}*], align 16
  %gcframe8.sub = getelementptr inbounds [3 x {}*], [3 x {}*]* %gcframe8, i64 0, i64 0
  %2 = bitcast [3 x {}*]* %gcframe8 to i8*
  call void @llvm.memset.p0i8.i64(i8* align 16 %2, i8 0, i64 24, i1 true)
  %thread_ptr = call i8* asm "mrs $0, tpidr_el0", "=r"() #7
  %tls_ppgcstack = getelementptr i8, i8* %thread_ptr, i64 16
  %3 = bitcast i8* %tls_ppgcstack to {}****
  %tls_pgcstack = load {}***, {}**** %3, align 8
; ┌ @ refvalue.jl:59 within `getindex`
; │┌ @ Base.jl:37 within `getproperty`
    %4 = bitcast [3 x {}*]* %gcframe8 to i64*
    store i64 4, i64* %4, align 16
    %5 = load {}**, {}*** %tls_pgcstack, align 8
    %6 = getelementptr inbounds [3 x {}*], [3 x {}*]* %gcframe8, i64 0, i64 1
    %7 = bitcast {}** %6 to {}***
    store {}** %5, {}*** %7, align 8
    %8 = bitcast {}*** %tls_pgcstack to {}***
    store {}** %gcframe8.sub, {}*** %8, align 8
    %9 = bitcast {}* %0 to {}**
    %getfield = load atomic {}*, {}** %9 unordered, align 8
    %.not = icmp eq {}* %getfield, null
    br i1 %.not, label %fail, label %pass4

fail:                                             ; preds = %top
    call void @ijl_throw({}* inttoptr (i64 530752553744 to {}*))
    unreachable

pass4:                                            ; preds = %top
    %.sub = getelementptr inbounds [2 x {}*], [2 x {}*]* %1, i64 0, i64 0
    %10 = getelementptr inbounds [3 x {}*], [3 x {}*]* %gcframe8, i64 0, i64 2
    store {}* %getfield, {}** %10, align 16
; └└
  store {}* %getfield, {}** %.sub, align 8
  %11 = getelementptr inbounds [2 x {}*], [2 x {}*]* %1, i64 0, i64 1
  store {}* %getfield, {}** %11, align 8
  %12 = call nonnull {}* @ijl_apply_generic({}* inttoptr (i64 530685332464 to {}*), {}** nonnull %.sub, i32 2)
  %13 = load {}*, {}** %6, align 8
  %14 = bitcast {}*** %tls_pgcstack to {}**
  store {}* %13, {}** %14, align 8
  ret {}* %12
}

To summarize, if the type is known we can compile to a succint set of instructions that we can determine at compile time. Any represents a wildcard unknown type, forcing us to figure out what needs to be done at run time.

5 Likes
10

Not necessarily, the following function will have good performance:

function example(v::Vector)
    accum = zero(eltype(v))
    for a in v
        accum += a
    end
    return accum
end

This is because the function argument v is annotated with an abstract type Vector, and the compiler will generate the code for the actual type of the argument passed to the function, e.g. Vector{Float64}. However, the following function will have poor performance:

function example(dict::Dict{String, Vector})
    v = dict["data"]
    accum = zero(eltype(v))
    for a in v
        accum += a
    end
    return accum
end

This is because the function argument dict is annotated with a concrete type Dict{String, Vector}, in which case the compiler will not further specialize for user-supplied arguments, and the generated code is not aware of the type of the elements in the vector. (In Julia’s type system, Dicts with non-concrete key/value types can still have concrete types themselves.)

11

You’re just giving me surface level details and telling me information I already know which is pointless, distracts from the thread, and gives the impression to other readers that the question has been answered because of the long series of posts which focus on irrelevant nit-picking pedanticities.

We just don’t speak the same language. I am sorry.

12

There are several levels of issues to unpack here. The exact example you gave lacks the nesting issue that was present with Dict making this a different situation.

Here Vector will match any of Vector, Vector{Int}, or Vector{Any}. Once matched for the purposes of method dispatch. Then, Julia will generate and specialize the code. In this case, Julia can infer the type and thus generate code Just-In-Time.

julia> f(v::Vector) = v[1] + v[1]
f (generic function with 1 method)

julia> f(Int[1,2])
2

julia> @code_llvm f(Int[1,2])
....
; ┌ @ int.jl:87 within `+`
   %3 = shl i64 %arrayref, 1
; â””
  ret i64 %3
}

julia> @code_warntype f(Int[1,2])
MethodInstance for f(::Vector{Int64})
  from f(v::Vector) @ Main REPL[1]:1
Arguments
  #self#::Core.Const(f)
  v::Vector{Int64}
Body::Int64
1 ─ %1 = Base.getindex(v, 1)::Int64
│   %2 = Base.getindex(v, 1)::Int64
│   %3 = (%1 + %2)::Int64
└──      return %3

julia> methods(f, Tuple{Vector{Int}}).ms[1].specializations
MethodInstance for f(::Vector{Int64})

The difference between this example and the original example with Dict{Symbol, Vector} issue is that the Dict{Symbol, Vector} has an explicitly abstract value type and thus cannot be specialialized. In contrast Dict{Symbol, <: Vector} and Vector can be specialialized by Julia just-in-time.

  • Dict{Symbol, Vector} means a dictionary with key type Symbol and explicitly value type of an unparameterized Vector.
  • Dict{Symbol, <: Vector} means a dixtionary with key type Symbol and any subtype of Vector. Subtypes of Vector include both an unparameterized Vector itself and parameterized types such as Vector{Int}.
  • Vector by itself is equivalent to Vector{ <: Any}, meaning it will match any or no parameter.
  • Vector{Any} without the subtyping operator is distinct from Vector or Vector{ <: Any}. Like Dict{Symbol, Vector} it explicitly says that the parameter is specifically Any, not a subtype of it.

it will generate code for every possible concrete type of Vector{T} which could be passed to it

I hesitate to agree with this. I initially thought that you meant that Julia would generate code eagerly for every single concrete type of Vector{T}. Julia will not eagerly do so. With the current execution model, Julia will only generate this code when a concrete type of Vector{T} would be passed to it. In other words, Julia is lazy about code generation.

One major caveat to the above statement is that there is a new experimental mode of Julia compilation where Julia will attempt to eagerly determine all possible types when the juliac driver is used. This again is experimental and requires one to get into the nightly development builds. This mode is meant for static compilation where the set of “every possible concrete type of Vector{T} which could be passed to it” can be constrained under the assumption that no new code will be added. This assumption is not valid meant for the primary execution mode of Julia since Julia’s current execution model does allow new code to be added.

3 Likes
13

Here’s a few additional resources:

  1. Julia Type System Explained (from JuliaCon 2024 sponsor Great Lakes Consulting) - "Just like Abstract types, if you leave off a supertype when you declare the primitive, the primitive will have “Any” as its direct supertype. "
  2. [2310.16866] A Type System for Julia (A PhD Thesis by Benjamin Chung) - “The type Any is the root of the type hierarchy, or the greatest
    supertype (top).”
  3. https://dl.acm.org/doi/pdf/10.1145/3485527. " Type stability in Julia: avoiding performance pathologies in JIT compilation", Julia Belyakova.
2 Likes
14

It seems like people are quoting and adequately answering several of your questions; I myself had asked similar questions before and gotten similar answers. People can’t know what you know or don’t know, so it’s not their fault if they don’t happen to offer entirely new information. It’s your responsibility to clarify what pieces of Julia’s type inference and compilation implementation you’re missing.

11 Likes
15

Argument type annotations do not affect performance*.

They just define the dispatch table and constrain the possible types that the method accepts. It just so happens that ::Dict{String, Vector} will only accept a type unstable collection. And that’s the crux of the problem here.

* except when they change specialization heuristics, but these are not that case

This is correct — but Julia will only generate that code if and when it sees that particular argument type. This is precisely why the time to first X is a problem — if Julia hasn’t seen some type yet it’ll need to pause and compile the method.

6 Likes
16

I suppose I was hoping someone who works with the compiler could provide an in-depth explanation.

To say “type is not concrete so slow” is just repeating what the documentation pages say. It’s unhelpful because it does not offer any explanation as to what output the compiler produces.

Only by knowing that information can we understand why it is slow.

The problem is, I am not an expert in LLVM. So I cannot read the LLVM output.

I should perhaps add the context to this that as well as Julia, I also have a deep understanding of how C++ behaves. I can read the machine code the compiler generates (although again it is not easy to do so, and it takes me a long time) so I would not suggest reading the machine code generated by the Julia compiler is a realistic starting point.

Since C++ is statically typed, you can’t accidentally tank your code performance by not fully specifying the types to the compiler.

So trying to understand what Julia does with types like Dict{:Symbol, :Vector} is my main focus here.

To put a different angle on it, understanding why Python performance is poor is relatively simple. All types are effectively Any. At runtime, when a function is called with some arguments, Python has to go to the location of each argument, figure out what (runtime) type it has, then follow a pointer to a VTable. The VTable tells Python what instructions to execute to perform the operations of the function.

It is the repeated querying of “what type are you” which contributes significantly to the performance hit. If a function is implemented in Python code rather than at the C level, the effect is compounded for each variable and operation inside the function.

2 Likes
17

See this doesn’t make sense to me. Consider the example argument type of

data::Vector{Float32}
time::Vector{DateTime}
dict(:data=>data, :time=>time)

Sorry to keep repeating myself. This has type

Dict{Symbol, Vector}

which happens to match the function argument type, which is the same.

When the compiler first sees this function call, it will generate machine code for the function with argument of type Dict{Symbol, Vector}.

This doesn’t make sense to me, because as was already pointed out, Vector is an abstract type, and therefore it can be infinitely many possible things.

  • I guess a better way to phrase the question here is what does the Julia compiler do to constrain Dict{Symbol, Vector} further when it generates code for a function with this argument type?
18

Thanks for your comments, this looks useful. Allow me some time to read through this.

19

This is a subtle point, but while Vector is not a concrete type, Vector{Vector} is (and same for Dict{Symbol, Vector}). A concrete type is something you can instantiate. It’s the type of some object. There’s no object whose typeof(x) is Vector, but typeof(Vector[]) is Vector{Vector}. The compiler specializes on the concrete type of the arguments, and you have to think of what information it has. If v is known to be Vector{Vector}, then v[3] = some_vector will be efficient code, but sin(v[3][1]) will be inefficient, because the compiler won’t know which method of sin to call (is v[3][1] an Int? A float?) so it has to look it up at runtime. Whereas if v is a Vector{Vector{Int}}, then it’ll know exactly which code to run to compute sin(::Int), so it can be much faster.

4 Likes
20

Ok so what you have shown here is that the example with Vector does not produce any warnings with @warn_type and is therefore not representative of the original problem. I agree with that.

Yes, this is what I intended to say but as you pointed out, and I had already realized, this would be logically impossible because there are an infinite number of possible types.