# Fast lookup of bits types using dispatch

**URL:** <https://discourse.julialang.org/t/fast-lookup-of-bits-types-using-dispatch/3809>\
**Category:** General Usage\
**Tags:** question\
**Created:** [May 19, 2017, 3:31pm UTC](https://discourse.julialang.org/t/fast-lookup-of-bits-types-using-dispatch/3809 "2017-05-19T15:31:28Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [May 19, 2017, 3:31pm UTC](https://discourse.julialang.org/t/fast-lookup-of-bits-types-using-dispatch/3809/1 "2017-05-19T15:31:28Z")

</div>

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

```julia
struct IX{T} end

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

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

```

A complicated system of dispatch using various levels:

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

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

```julia
f(ix) = ix[:b]
@code_llvm f(ix1)

```

seems to suggest it is compiled to quite complex code.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [May 19, 2017, 3:51pm UTC](https://discourse.julialang.org/t/fast-lookup-of-bits-types-using-dispatch/3809/2 "2017-05-19T15:51:51Z")

</div>

> [@Tamas\_Papp](#):
>
> 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.

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

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [May 19, 2017, 3:53pm UTC](https://discourse.julialang.org/t/fast-lookup-of-bits-types-using-dispatch/3809/3 "2017-05-19T15:53:31Z")

</div>

And ref [Dispatch time using `Val` is an order of magnitude slower than looking up with `Dict` - #2 by yuyichao](https://discourse.julialang.org/t/dispatch-time-using-val-is-an-order-of-magnitude-slower-than-looking-up-with-dict/3543/2) You are trying to express something simple using something fundamentally more complex and this will never make things faster.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [May 19, 2017, 3:58pm UTC](https://discourse.julialang.org/t/fast-lookup-of-bits-types-using-dispatch/3809/4 "2017-05-19T15:58:32Z")

</div>

Thanks. I was just curious if the mechanism of [NamedTuples.jl](https://github.com/blackrock/NamedTuples.jl/blob/master/src/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.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [May 19, 2017, 5:10pm UTC](https://discourse.julialang.org/t/fast-lookup-of-bits-types-using-dispatch/3809/5 "2017-05-19T17:10:46Z")

</div>

> [@Tamas\_Papp](#):
>
> Why is is impossible?

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

---

<div class="post-metadata">

**Author:** ![sdanisch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sdanisch/32/1406_2.png) [@sdanisch](https://discourse.julialang.org/u/sdanisch)\
**Post date:** [May 21, 2017, 9:55am UTC](https://discourse.julialang.org/t/fast-lookup-of-bits-types-using-dispatch/3809/6 "2017-05-21T09:55:02Z")

</div>

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

```nohighlight
return 2

```

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