# Ntuple aggressive specialisation and boxed values

**URL:** <https://discourse.julialang.org/t/ntuple-aggressive-specialisation-and-boxed-values/40450>\
**Category:** General Usage\
**Tags:** question, ntuple\
**Created:** [May 30, 2020, 1:36am UTC](https://discourse.julialang.org/t/ntuple-aggressive-specialisation-and-boxed-values/40450 "2020-05-30T01:36:27Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Ward9250](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ward9250/32/42768_2.png) [@Ward9250](https://discourse.julialang.org/u/Ward9250)\
**Post date:** [May 30, 2020, 1:36am UTC](https://discourse.julialang.org/t/ntuple-aggressive-specialisation-and-boxed-values/40450/1 "2020-05-30T01:36:28Z")

</div>

Hi,

Further to my questions on the General slack today I decided to do an experiment, pitting an NTuple based kmer type, against the existing BioSequences Mer types which are based on primitive types.

Valentin advised me to use ntuple to generate “tail” in the code, and to use ntuple in a way that it aggressively specialised.

Anyway I did and the results are here: [https://gist.github.com/BenJWard/4e06c5c4f4648c594fdb1a886cf5042d](https://gist.github.com/BenJWard/4e06c5c4f4648c594fdb1a886cf5042d)

When I benchmarked I found v. bad performance:

```julia
julia> @benchmark DNAKmer{63,2}($dnaseq)
BenchmarkTools.Trial: 
  memory estimate: 1.36 KiB
  allocs estimate: 87
  --------------
  minimum time: 24.255 μs (0.00% GC)
  median time: 24.460 μs (0.00% GC)
  mean time: 25.328 μs (0.00% GC)
  maximum time: 307.687 μs (0.00% GC)
  --------------
  samples: 10000
  evals/sample: 1

```

Vs the primitive type:

```julia
julia> @benchmark BigDNAMer{63}($dnaseq)
BenchmarkTools.Trial: 
  memory estimate: 0 bytes
  allocs estimate: 0
  --------------
  minimum time: 126.889 ns (0.00% GC)
  median time: 126.991 ns (0.00% GC)
  mean time: 130.191 ns (0.00% GC)
  maximum time: 303.371 ns (0.00% GC)
  --------------
  samples: 10000
  evals/sample: 883

```

But looking at the code warntype of the function I could see the variable idx was boxed, and the tuple “tail” had an element type of any.

I wasnt sure why the boxin occured, but changing idx to a Ref fixed the issue, and it beats the primitive type performance!

```julia
julia> @benchmark DNAKmer{63,2}($dnaseq)
BenchmarkTools.Trial: 
  memory estimate: 0 bytes
  allocs estimate: 0
  --------------
  minimum time: 91.087 ns (0.00% GC)
  median time: 91.181 ns (0.00% GC)
  mean time: 92.795 ns (0.00% GC)
  maximum time: 243.353 ns (0.00% GC)
  --------------
  samples: 10000
  evals/sample: 952

```

On Julia 1.5

Why did the boxing occur, and why was it Ref fixed it - in both cases the idx is just an int.

---

<div class="post-metadata">

**Author:** ![Ward9250](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ward9250/32/42768_2.png) [@Ward9250](https://discourse.julialang.org/u/Ward9250)\
**Post date:** [May 30, 2020, 3:29pm UTC](https://discourse.julialang.org/t/ntuple-aggressive-specialisation-and-boxed-values/40450/2 "2020-05-30T15:29:42Z")

</div>

```julia
@inline shiftright(x::BigDNAMer{K}) where {K} = BigDNAMer{K}(reinterpret(UInt128, x) >> 2)

@inline function shiftright(x::Kmer{A,K,N}) where {A,K,N}
    head = @inbounds x.data[1] >> 2
    tail = ntuple(Val{N - 1}()) do i
        Base.@_inline_meta
        j = i + 1
        @inbounds begin
            return (x.data[j] >> 2) | ((x.data[i] & UInt64(3)) << 62)
        end
    end
    return Kmer{A,K,N}((head, tail...))
end

```

@benchmark shiftright($m)  
@benchmark shiftright($oldm)

I tried to implement a good rightshift of all the nucleotides stored in a ntuple based Kmer.  
Performance is almost as good a the UInt128 based kmer `oldm`. But not quite. Any way I could get it even quicker?

---

<div class="post-metadata">

**Author:** ![Ward9250](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ward9250/32/42768_2.png) [@Ward9250](https://discourse.julialang.org/u/Ward9250)\
**Post date:** [May 30, 2020, 3:47pm UTC](https://discourse.julialang.org/t/ntuple-aggressive-specialisation-and-boxed-values/40450/3 "2020-05-30T15:47:27Z")

</div>

Turns out you can get faster:

```julia
    return _shiftright(zero(UInt64), x.data...)
end

@inline function _shiftright(carry::UInt64, head::UInt64, tail...)
    Base.@_inline_meta
    return ((head >> 2) | carry, _shiftright((head & UInt64(3)) << 62, tail...)...)
end

@inline _shiftright(carry::UInt64) = ()

```

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [May 30, 2020, 4:00pm UTC](https://discourse.julialang.org/t/ntuple-aggressive-specialisation-and-boxed-values/40450/4 "2020-05-30T16:00:44Z")

</div>

The `Base.@_inline_meta` should be redundant here, since it is equivalent to the `@inline` already in front of the function definition.

---

<div class="post-metadata">

**Author:** ![Ward9250](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ward9250/32/42768_2.png) [@Ward9250](https://discourse.julialang.org/u/Ward9250)\
**Post date:** [May 30, 2020, 5:28pm UTC](https://discourse.julialang.org/t/ntuple-aggressive-specialisation-and-boxed-values/40450/5 "2020-05-30T17:28:48Z")

</div>

So I tried to introduce a similar shiftleft function:

```julia
@inline function shiftleft(x::Kmer{A,K,N}) where {A,K,N}
    _, newbits = _shiftleft(x.data...)
    return Kmer{A,K,N}(_cliphead(64N - 2K, newbits...))
end

@inline function _cliphead(by::Integer, head::UInt64, tail...)
    return (head & (typemax(UInt64) >> by), tail...)
end

@inline function _shiftleft(head::UInt64, tail...)
    carry, newtail = _shiftleft(tail...)
    return head >> 62, ((head << 2) | carry, newtail...)
end

@inline _shiftleft(head::UInt64) = (head & 0xC000000000000000) >> 62, head << 2

```

Which does similar to shiftright, but with clipping of the tuple’s head element at the end.

Benchmarking this I get allocations and slower times:

```julia
julia> @benchmark shiftleft($m)
BenchmarkTools.Trial: 
  memory estimate: 112 bytes
  allocs estimate: 6
  --------------
  minimum time: 227.321 ns (0.00% GC)
  median time: 229.827 ns (0.00% GC)
  mean time: 241.572 ns (1.41% GC)
  maximum time: 3.747 μs (93.68% GC)
  --------------
  samples: 10000
  evals/sample: 442

```

```julia
julia> @code_warntype shiftleft(m)
Variables
  #self#::Core.Compiler.Const(shiftleft, false)
  x::Kmer{DNAAlphabet{2},63,2}
  @_3::Int64
  newbits::Tuple{UInt64,UInt64}

Body::Kmer{DNAAlphabet{2},63,2}
1 ─ nothing
│ %2 = Base.getproperty(x, :data)::Tuple{UInt64,UInt64}
│ %3 = Core._apply_iterate(Base.iterate, Main._shiftleft, %2)::Tuple{UInt64,Tuple{UInt64,UInt64}}
│ %4 = Base.indexed_iterate(%3, 1)::Core.Compiler.PartialStruct(Tuple{UInt64,Int64}, Any[UInt64, Core.Compiler.Const(2, false)])
│ Core.getfield(%4, 1)
│ (@_3 = Core.getfield(%4, 2))
│ %7 = Base.indexed_iterate(%3, 2, @_3::Core.Compiler.Const(2, false))::Core.Compiler.PartialStruct(Tuple{Tuple{UInt64,UInt64},Int64}, Any[Tuple{UInt64,UInt64}, Core.Compiler.Const(3, false)])
│ (newbits = Core.getfield(%7, 1))
│ %9 = Core.apply_type(Main.Kmer, $(Expr(:static_parameter, 1)), $(Expr(:static_parameter, 2)), $(Expr(:static_parameter, 3)))::Core.Compiler.Const(Kmer{DNAAlphabet{2},63,2}, false)
│ %10 = (%9)(newbits)::Kmer{DNAAlphabet{2},63,2}
└── return %10

```