# Inference on field types?

**URL:** <https://discourse.julialang.org/t/inference-on-field-types/53448>\
**Category:** Performance\
**Tags:** inference\
**Created:** [January 16, 2021, 7:55pm UTC](https://discourse.julialang.org/t/inference-on-field-types/53448 "2021-01-16T19:55:12Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![tamasgal](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamasgal/32/27946_2.png) [@tamasgal](https://discourse.julialang.org/u/tamasgal)\
**Post date:** [January 16, 2021, 7:55pm UTC](https://discourse.julialang.org/t/inference-on-field-types/53448/1 "2021-01-16T19:55:12Z")

</div>

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:

```julia
struct Hit
    dom_id::Int16
    time::Float64
end

```

The hardcoded version:

```julia
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()`:

```julia
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`):

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

```

Gives:

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

```

And the benchmark results:

```julia
@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)]

```

```julia
@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)]

```

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [January 17, 2021, 12:14am UTC](https://discourse.julialang.org/t/inference-on-field-types/53448/2 "2021-01-17T00:14:15Z")

</div>

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

```julia
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:

```julia
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)

```

---

<div class="post-metadata">

**Author:** ![tamasgal](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamasgal/32/27946_2.png) [@tamasgal](https://discourse.julialang.org/u/tamasgal)\
**Post date:** [January 17, 2021, 8:17am UTC](https://discourse.julialang.org/t/inference-on-field-types/53448/3 "2021-01-17T08:17:15Z")

</div>

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 `:)`

---

<div class="post-metadata">

**Author:** ![tamasgal](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamasgal/32/27946_2.png) [@tamasgal](https://discourse.julialang.org/u/tamasgal)\
**Post date:** [January 17, 2021, 8:28am UTC](https://discourse.julialang.org/t/inference-on-field-types/53448/4 "2021-01-17T08:28:13Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![tamasgal](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamasgal/32/27946_2.png) [@tamasgal](https://discourse.julialang.org/u/tamasgal)\
**Post date:** [January 17, 2021, 8:34am UTC](https://discourse.julialang.org/t/inference-on-field-types/53448/5 "2021-01-17T08:34:51Z")

</div>

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

```julia
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:

```julia
"""
$(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

```

```julia
"""
$(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

```

---

<div class="post-metadata">

**Author:** ![aplavin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aplavin/32/222056_2.png) [@aplavin](https://discourse.julialang.org/u/aplavin)\
**Post date:** [January 17, 2021, 12:12pm UTC](https://discourse.julialang.org/t/inference-on-field-types/53448/6 "2021-01-17T12:12:57Z")

</div>

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) ...`

---

<div class="post-metadata">

**Author:** ![Raf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/raf/32/3383_2.png) [@Raf](https://discourse.julialang.org/u/Raf)\
**Post date:** [January 17, 2021, 12:27pm UTC](https://discourse.julialang.org/t/inference-on-field-types/53448/7 "2021-01-17T12:27:48Z")

</div>

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:

```julia
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)…

```

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [January 17, 2021, 1:39pm UTC](https://discourse.julialang.org/t/inference-on-field-types/53448/8 "2021-01-17T13:39:13Z")

</div>

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:

```julia
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
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
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
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.

---

<div class="post-metadata">

**Author:** ![tamasgal](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamasgal/32/27946_2.png) [@tamasgal](https://discourse.julialang.org/u/tamasgal)\
**Post date:** [January 17, 2021, 2:17pm UTC](https://discourse.julialang.org/t/inference-on-field-types/53448/9 "2021-01-17T14:17:56Z")

</div>

@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! `:)`

---

<div class="post-metadata">

**Author:** ![tamasgal](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamasgal/32/27946_2.png) [@tamasgal](https://discourse.julialang.org/u/tamasgal)\
**Post date:** [January 17, 2021, 2:24pm UTC](https://discourse.julialang.org/t/inference-on-field-types/53448/10 "2021-01-17T14:24:39Z")

</div>

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…

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [January 18, 2021, 12:47am UTC](https://discourse.julialang.org/t/inference-on-field-types/53448/11 "2021-01-18T00:47:38Z")

</div>

I looked it up, [`Symbol` and `Tuple`s of `Symbol`s are](https://discourse.julialang.org/t/how-to-use-a-type-wrapping-a-symbol-as-a-type-parameter/19628/6) [_hard-coded exceptions_ to the isbitstype parameter rule](https://github.com/JuliaLang/julia/blob/7772486a6942c9a9b52849b6ffe690a7da5861cd/src/builtins.c#L825-L843), very interesting.