Fast lookup of bits types using dispatch

General Usage
1

I am playing with this problem for my own education only, to learn more about dispatch and computations on the type system. Questions at the end.

Objective: implement something like findfirst((:a, :b, :c), x) that would be compiled to very efficient code, using just the type system and dispatch, not generated functions. The first sequence is always a tuple of bits types so they can be type parameters.

What I have so far: a type

struct IX{T} end

IX(names::Symbol...) = IX{names}() # convenience constructor

ix1 = IX(:a, :b, :c)

A complicated system of dispatch using various levels:

# utility functions
_splitfirst(car, cdr...) = car
_splitrest(car, cdr...) = cdr

# no match, check rest
function _gx1{key,i,name,namerest}(::Type{Val{key}}, ::Type{Val{i}}, ::Type{Val{name}},
                                   ::Type{Val{namerest}})
    _gx1(Val{key}, Val{i+1}, Val{_splitfirst(namerest...)}, Val{_splitrest(namerest...)})
end

# no match, no more items, return 0
_gx1{key,i,name}(::Type{Val{key}}, ::Type{Val{i}}, ::Type{Val{name}}, ::Type{Val{()}}) = 0

# match
_gx1{key,i}(::Type{Val{key}}, ::Type{Val{i}}, ::Type{Val{key}}, ::Type{Val{()}}) = i

# match, no more items -- BUT WHY DO I NEED THIS METHOD?
_gx1{key,i,namerest}(::Type{Val{key}}, ::Type{Val{i}}, ::Type{Val{key}},
                     ::Type{Val{namerest}}) = i

# this just calls _gx1
_gx2{key}(::Type{Val{key}}, ::Type{Val{()}}) = 0

function _gx2{key,names}(::Type{Val{key}}, ::Type{Val{names}})
    _gx1(Val{key}, Val{1}, Val{_splitfirst(names...)}, Val{_splitrest(names...)})
end

getindex{names}(::IX{names}, key) = _gx2(Val{key}, Val{names})

And some tests:

ix1[:a]                         # 1
ix1[:b]                         # 2
ix1[:c]                         # 3
ix1[:d]                         # 0

Using v0.6-rc1.

Questions:

  1. why do I need the fourth _gx1 method? I thought the third one would apply. Is this a bug?
  2. can I do this in a simpler way?
  3. related: how can I check that it compiles to optimal code? inspecting
f(ix) = ix[:b]
@code_llvm f(ix1)

seems to suggest it is compiled to quite complex code.

2

No don’t do that. It’s impossible.

3

And ref Dispatch time using `Val` is an order of magnitude slower than looking up with `Dict` - #2 by yuyichao You are trying to express something simple using something fundamentally more complex and this will never make things faster.

4

Thanks. I was just curious if the mechanism of NamedTuples.jl could be implemented without generated functions.

Why is is impossible? It this an inherent limitation in the type system, or just something that has not been optimized yet? My (apparently naive) expectation was that once I am in the type space, the type system would just grind through the code and produce an efficient version.

5

Because you did not start in the type domain. If you do, it can probably be implemented.

6 
Base.@pure @noinline Getindex{T <: Tuple, N}(::Type{T}, ::Val{N}) = T.parameters[N]
Base.@pure Next{N}(::Val{N}) = Val{N - 1}()
findfirst(syms, x, n::Val{0}) = error("$x not found in $syms")
@inline function findfirst{T <: Tuple, TX, N}(t::Type{T}, x::Val{TX}, n::Val{N})
    Getindex(T, Val{N}()) === TX && return N
    findfirst(T, Val{TX}(), Next(Val{N}()))::Int
end

Compiles to:

return 2

It needed a bit of unintuitive tricks, like repacking Val{N}() and noinline to make constant propagation actually work!

3 Likes