Inference on field types?

I often have to “categorise” a vector of struct elements by a specific field and I wanted to get rid of some duplicated logic and generalise the categorisation, however I hit the penalty of runtime (dynamic) lookup of the field type, which I need to create the output dictionary. I though the inference would somehow magically figure it out but I was wrong :) and understand the reason.

Obviously if the type is known at compile time, the compiler should be able to figure out the field types either since structs cannot be redefined but it’s the call to fieldtype() which is not pure, and prevents that.

So my (probably dumb) question is something like: is there any way to somehow tell Julia that fieldtype() is pure and if not, are there any other approaches than parametrising the field type into the struct’s definition (at least that’s the only way I found so far but it’s a bit annoying since I have many fields I want to categorise on involving a couple of different struct definitions).

Here is an example:

struct Hit
    dom_id::Int16
    time::Float64
end

The hardcoded version:

function domhits(hits::Vector{T}) where T
    hit_map = Dict{Int16, Vector{T}}()
    for hit ∈ hits
        dom_id = hit.dom_id
        if !haskey(hit_map, dom_id)
            hit_map[dom_id] = T[]
        end
        push!(hit_map[hit.dom_id], hit)
    end
    hit_map
end

The general version which is dynamically determining the type via fieldtype():

function categorize(field::Symbol, elements::Vector{T}) where T
    out = Dict{fieldtype(T, field), Vector{T}}()
    for el ∈ elements
        key = getfield(el, field)
        if !haskey(out, key)
            out[key] = T[]
        end
        push!(out[key], el)
    end
    out
end

Here is some test data (a couple of hits which we will sort by dom_id):

n = 20
dom_ids = Int16.(rand(1:4, n))
times = rand(n);
hits = [Hit(dt...) for dt in zip(dom_ids, times)]

Gives:

20-element Array{Hit,1}:
 Hit(3, 0.44280682173150687)
 ...
 Hit(4, 0.9483316068868308)
 Hit(4, 0.874216680644536)

And the benchmark results:

@btime domhits($hits)  #  625.762 ns (14 allocations: 1.41 KiB)

Dict{Int16,Array{Hit,1}} with 4 entries:
  4 => Hit[Hit(4, 0.257824), Hit(4, 0.948332), Hit(4, 0.874217), Hit(4, 0.46145…
  2 => Hit[Hit(2, 0.147367), Hit(2, 0.124529), Hit(2, 0.973964), Hit(2, 0.39077…
  3 => Hit[Hit(3, 0.442807), Hit(3, 0.995658), Hit(3, 0.332106), Hit(3, 0.50589…
  1 => Hit[Hit(1, 0.292101)]
@btime categorize(:dom_id, $hits)  # 5.061 μs (34 allocations: 2.03 KiB)

Dict{Int16,Array{Hit,1}} with 4 entries:
  4 => Hit[Hit(4, 0.257824), Hit(4, 0.948332), Hit(4, 0.874217), Hit(4, 0.46145…
  2 => Hit[Hit(2, 0.147367), Hit(2, 0.124529), Hit(2, 0.973964), Hit(2, 0.39077…
  3 => Hit[Hit(3, 0.442807), Hit(3, 0.995658), Hit(3, 0.332106), Hit(3, 0.50589…
  1 => Hit[Hit(1, 0.292101)]
3 Likes

It looks like an inherently run time computation to me. At compile time, you ideally know the type of a variable, but you never assume the value. Well, fieldtype's answer varies by the value of the argument field; :dom_id and :time would give different answers. All that is known at compile time is that field is a Symbol. You can make categorize type-stable by pulling the fieldtype call out and giving the type as an argument categorize(thetype::Type, elements::Vector{T}), but that doesn’t really solve anything because the fieldtype call still happens somewhere.

The only remaining suggestion I have depends on if you actually need to check all the fields of the Hit struct. See, if you only need to check a field named dom_id, you could do

function domhits(hits::Vector{T}) where T
  hit_map = Dict{fieldtype(T, :dom_id), Vector{T}}()
  #yada yada yada
end

T is known at compile time. :dom_id is a constant Symbol, not a variable, so it is also known at compile-time. Therefore, the type from the fieldtype call is known at compile time, and dom_hits is type-stable (check with @code_warntype). I’m also sort of sure that the call is done at compile-time; in the @code_warntype printout, there is a line for the call, but it is tagged Core.Compiler.Const which I think means “this call was done at compile time and the answer was stored”. It’s worth asking someone who knows the compiler better than I do.

If you want to make it a bit more extensible, make a method that maps structs like Hit to the type of a specific field:

function domhits(hits::Vector{T}) where T
  hit_map = Dict{innertype(T), Vector{T}}()
  #yada yada yada
end

innertype(x::Type{Hit}) = fieldtype(x, :dom_id)
innertype(x::Type{Blah}) = fieldtype(x, :blah_id)
2 Likes

Thanks @Benny, that’s a nice, detailed explanation!

The innertype solution is unfortunately not feasible since often I need to use more than one field for sorting.

Anyways that gave me more inspiration and we’ll see where it goes :)

Btw. I also tried exploiting Val but a Symbol is unfortunately not an isbits value :see_no_evil:

Here is a probably better example which shows the actual code duplication, which I am trying to get rid off:

abstract type AbstractHit end

struct DAQHit <: AbstractHit
    dom_id::Int16
    du::Int8
    time::Float64
end

struct MCHit <: AbstractHit
    dom_id::Int16
    du::Int8
    origin::Int32
    time::Float64
    phe::UInt8
end

and the current implementation of the categorisation hardcoded to dom_id and du. As you can see, only the field = ... lines differ:

"""
$(SIGNATURES)

Categorise hits by DOM ID and put them into a dictionary of DOM ID=>Vector{Hit}.
"""
function domhits(hits::Vector{T}) where {T<:AbstractHit}
    field = :dom_id
    hit_map = Dict{fieldtype(T, field), Vector{T}}()
    for hit ∈ hits
        key = hit.dom_id
        if !haskey(hit_map, key)
            hit_map[key] = T[]
        end
        push!(hit_map[key], hit)
    end
    hit_map
end
"""
$(SIGNATURES)

Categorise hits by DU and put them into a dictionary of DU=>Vector{Hit}.
"""
function duhits(hits::Vector{T}) where {T<:AbstractHit}
    field = :du
    hit_map = Dict{fieldtype(T, field), Vector{T}}()
    for hit ∈ hits
        key = getfield(hit, key)
        if !haskey(hit_map, key)
            hit_map[key] = T[]
        end
        push!(hit_map[key], hit)
    end
    hit_map
end

Can you pass a function like in groupby(h -> h.dom_id, hits)? Or, if you want to be fancy, there is Setfields.jl with l = @lens _.dom_id; ... get(hit, l), set(hit, l) ...

It should help if you make the compiler compile functions for every fieldname, and it wont for Symbol. But you can force multiple versions using Val{:x}(). Have a wrapper function that will constant propagate the symbol (i.e. @inline), then wrap it with Val and call the method again.

Oh I see you tried that - but it does work, I use it everywhere for this kind of thing:

struct Hit
    dom_id::Int16
    time::Float64
end
@inline function categorize_val(field::Symbol, elements::Vector)
    categorize_val(Val{field}(), elements) 
end
@inline function categorize_val(field::Val{F}, elements::Vector{T}) where {T,F}
    out = Dict{fieldtype(T, F), Vector{T}}()
    for el ∈ elements
        key = getfield(el, F)
        if !haskey(out, key)
            out[key] = T[]
        end
        push!(out[key], el)
    end
    out
end

n = 20
dom_ids = Int16.(rand(1:4, n))
times = rand(n);
hits = [Hit(dt...) for dt in zip(dom_ids, times)]

using BenchmarkTools

julia> @btime categorize_val(:dom_id, $hits)
  853.000 ns (14 allocations: 1.41 KiB)
Dict{Int16,Array{Hit,1}} with 4 entries:
  4 => Hit[Hit(4, 0.642627), Hit(4, 0.491384), Hit(4, 0.981954)…
  2 => Hit[Hit(2, 0.211748), Hit(2, 0.000746403), Hit(2, 0.7723…
  3 => Hit[Hit(3, 0.511963), Hit(3, 0.386519), Hit(3, 0.207365)…
  1 => Hit[Hit(1, 0.908978), Hit(1, 0.768637), Hit(1, 0.449042)…
3 Likes

So I played around with your code, and I spotted an odd timing discrepancy on the order of ns-μs in initializing the dictionary, similar to your original example. At first I figured it was type-instability from dynamically computing the field type, but the discrepancy is still there after I stripped out any computation of the field type and made the calls type-stable:

hits = Int16[1,2,3]

# similar timings to just specifying the field name and thus the type, 80-90 ns
domhits(hits::Vector{T}) where T = Dict{Int16, Vector{T}}()

# similar timings to dynamically computing the field type, 2.3 us, almost half the original 5 us
maphits(hits::Vector{T}, intype) where T = Dict{intype, Vector{T}}()

And the timings:

julia> @btime domhits(hits)
  80.165 ns (4 allocations: 512 bytes)
Dict{Int16,Array{Int16,1}}()

julia> @btime maphits(hits, Int16)
  2.311 μs (4 allocations: 512 bytes)
Dict{Int16,Array{Int16,1}}()

I can’t really read LLVM, but it looks nearly identical. I can’t spot anything that would explain the large discrepancy in timing.

julia> @code_llvm domhits(hits)

;  @ C:\Users\benm1\Downloads\script.jl:7 within `domhits'
; Function Attrs: uwtable
define nonnull %jl_value_t* @japi1_domhits_715(%jl_value_t*, %jl_value_t**, i32) #0 {
top:
  %3 = alloca %jl_value_t**, align 8
  store volatile %jl_value_t** %1, %jl_value_t*** %3, align 8
  %4 = call nonnull %jl_value_t* @j1_Dict_716(%jl_value_t* inttoptr (i64 340996880 to %jl_value_t*), %jl_value_t** null, i32 0)
  ret %jl_value_t* %4
}
julia> @code_llvm maphits(hits, Int16)

;  @ C:\Users\benm1\Downloads\script.jl:9 within `maphits'
; Function Attrs: uwtable
define nonnull %jl_value_t* @japi1_maphits_719(%jl_value_t*, %jl_value_t**, i32) #0 {
top:
  %3 = alloca %jl_value_t**, align 8
  store volatile %jl_value_t** %1, %jl_value_t*** %3, align 8
  %4 = call nonnull %jl_value_t* @j1_Dict_720(%jl_value_t* inttoptr (i64 340996880 to %jl_value_t*), %jl_value_t** null, i32 0)
  ret %jl_value_t* %4
}

This is genuinely odd to me.
UPDATE: this discrepancy vanishes when I declare const hits in my example, so this is really just a case of evil globals. Declaring const in the original post’s example does not change the timings, so it really was just down to the type instability stemming from the value-parameter of the dictionary’s type.

1 Like

@Raf Oh dear, I probably messed up something with Val since I quickly switched to the docs and read that it only works with isbits values so I thought that’s the reason. Thanks for the working example, this is exactly what I was looking for! :)

1 Like

I can reproduce it and I have really no idea, it’s strange for sure! I remember however some peculiarities when passing types to functions, don’t remember exactly…

I looked it up, Symbol and Tuples of Symbols are hard-coded exceptions to the isbitstype parameter rule, very interesting.

2 Likes