Julia Version 1.5.0-beta1.0
Commit 6443f6c95a (2020-05-28 17:42 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin19.4.0)
  CPU: Intel(R) Core(TM) i7-6920HQ CPU @ 2.90GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, skylake)

using BioSequences, BenchmarkTools
# In BioSequences.jl kmers are called Mer, not Kmer so there is no name clash.
struct Kmer{A<:NucleicAcidAlphabet{2},K,N}
    data::NTuple{N,UInt64}
end
# Shortcut
const DNAKmer{K,N} = Kmer{DNAAlphabet{2},K,N}

@inline capacity(::Type{Kmer{A,K,N}}) where {A,K,N} = div(64N, 2)

function (::Type{Kmer{A,K,N}})(seq::LongSequence{A}) where {A<:NucleicAcidAlphabet{2},K,N}
    seqlen = length(seq)
    if seqlen != K
        throw(ArgumentError("seq does not contain the correct number of nucleotides ($seqlen ≠ $K)"))
    end
    if seqlen > capacity(Kmer{A,K,N})
        throw(ArgumentError("Cannot build a mer longer than $(capacity(Kmer{A,K,N}))bp long"))
    end

    # Construct the head.
    bases_in_head = div(64 - (64N - 2K), 2)
    head = zero(UInt64)
    @inbounds for i in 1:bases_in_head
        nt = convert(eltype(typeof(seq)), seq[i])
        head = (head << 2) | UInt64(BioSequences.twobitnucs[reinterpret(UInt8, nt) + 0x01])
    end
    
    # And the rest of the sequence
    idx = Ref(bases_in_head + 1)
    
    tail = ntuple(Val{N - 1}()) do i
        Base.@_inline_meta
        body = zero(UInt64)
        @inbounds for i in 1:32
            nt = convert(eltype(typeof(seq)), seq[idx[]])
            body = (body << 2) | UInt64(BioSequences.twobitnucs[reinterpret(UInt8, nt) + 0x01])
            idx[] += 1
        end
        return body
    end

    return Kmer{A,K,N}((head, tail...))
end

# For old primitive type based kmer.
@inline shiftright(x::BigDNAMer{K}) where {K} = BigDNAMer{K}(reinterpret(UInt128, x) >> 2)

# For NTuple based kmer.
@inline function shiftright(x::Kmer{A,K,N}) where {A,K,N}
    return _shiftright(zero(UInt64), x.data...)
end
@inline function _shiftright(carry::UInt64, head::UInt64, tail...)
    return ((head >> 2) | carry, _shiftright((head & UInt64(3)) << 62, tail...)...)
end
@inline _shiftright(carry::UInt64) = ()
dnaseq = LongSequence{DNAAlphabet{2}}(randdnaseq(63))
m = DNAKmer{63, 2}(dnaseq)
oldm = BigDNAMer{63}(dnaseq)
@benchmark shiftright($m)
@benchmark shiftright($oldm)

# For old primitive type based kmer.
@inline shiftleft(x::BigDNAMer{K}) where {K} = BigDNAMer{K}(reinterpret(UInt128, x) << 2)

# For new NTuple based kmer.
@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

julia> @benchmark shiftleft($m)
BenchmarkTools.Trial: 
  memory estimate:  112 bytes
  allocs estimate:  6
  --------------
  minimum time:     228.094 ns (0.00% GC)
  median time:      230.368 ns (0.00% GC)
  mean time:        241.913 ns (1.64% GC)
  maximum time:     4.400 μs (94.66% GC)
  --------------
  samples:          10000
  evals/sample:     438

julia> @benchmark shiftleft($oldm)
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     0.039 ns (0.00% GC)
  median time:      0.043 ns (0.00% GC)
  mean time:        0.043 ns (0.00% GC)
  maximum time:     0.051 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     1000

julia> @code_typed shiftleft(m)
CodeInfo(
1 ─ %1  = Base.getfield(x, :data)::Tuple{UInt64,UInt64}
│   %2  = (getfield)(%1, 1)::UInt64
│   %3  = (getfield)(%1, 2)::UInt64
│   %4  = Base.and_int(%3, 0xc000000000000000)::UInt64
│   %5  = Base.sle_int(0, 62)::Bool
│   %6  = Base.bitcast(UInt64, 62)::UInt64
│   %7  = Base.lshr_int(%4, %6)::UInt64
│   %8  = Base.neg_int(62)::Int64
│   %9  = Base.bitcast(UInt64, %8)::UInt64
│   %10 = Base.shl_int(%4, %9)::UInt64
│   %11 = Base.ifelse(%5, %7, %10)::UInt64
│   %12 = Base.sle_int(0, 2)::Bool
│   %13 = Base.bitcast(UInt64, 2)::UInt64
│   %14 = Base.shl_int(%3, %13)::UInt64
│   %15 = Base.neg_int(2)::Int64
│   %16 = Base.bitcast(UInt64, %15)::UInt64
│   %17 = Base.lshr_int(%3, %16)::UInt64
│   %18 = Base.ifelse(%12, %14, %17)::UInt64
│   %19 = Base.sle_int(0, 2)::Bool
│   %20 = Base.bitcast(UInt64, 2)::UInt64
│   %21 = Base.shl_int(%2, %20)::UInt64
│   %22 = Base.neg_int(2)::Int64
│   %23 = Base.bitcast(UInt64, %22)::UInt64
│   %24 = Base.lshr_int(%2, %23)::UInt64
│   %25 = Base.ifelse(%19, %21, %24)::UInt64
│   %26 = Base.or_int(%25, %11)::UInt64
│   %27 = Core.tuple(%26)::Tuple{UInt64}
│   %28 = Core._apply_iterate(Base.iterate, Core.tuple, %27, %18)::Tuple{UInt64,UInt64}
│   %29 = (getfield)(%28, 1)::UInt64
│   %30 = (getfield)(%28, 2)::UInt64
│   %31 = Base.and_int(%29, 0x3fffffffffffffff)::UInt64
│   %32 = Core.tuple(%31, %30)::Tuple{UInt64,UInt64}
│   %33 = %new(Kmer{DNAAlphabet{2},63,2}, %32)::Kmer{DNAAlphabet{2},63,2}
└──       return %33
) => Kmer{DNAAlphabet{2},63,2}

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 = (64 * $(Expr(:static_parameter, 3)))::Core.Compiler.Const(128, false)
│   %11 = (2 * $(Expr(:static_parameter, 2)))::Core.Compiler.Const(126, false)
│   %12 = (%10 - %11)::Core.Compiler.Const(2, false)
│   %13 = Core.tuple(%12)::Core.Compiler.Const((2,), false)
│   %14 = Core._apply_iterate(Base.iterate, Main._cliphead, %13, newbits)::Tuple{UInt64,UInt64}
│   %15 = (%9)(%14)::Kmer{DNAAlphabet{2},63,2}
└──       return %15