# Bijou64 varint encoding

**URL:** <https://discourse.julialang.org/t/bijou64-varint-encoding/137654>\
**Category:** Performance\
**Created:** [June 16, 2026, 3:42pm UTC](https://discourse.julialang.org/t/bijou64-varint-encoding/137654 "2026-06-16T15:42:18Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![KyleSJohnston](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kylesjohnston/32/12674_2.png) [@KyleSJohnston](https://discourse.julialang.org/u/KyleSJohnston)\
**Post date:** [June 16, 2026, 3:42pm UTC](https://discourse.julialang.org/t/bijou64-varint-encoding/137654/1 "2026-06-16T15:42:18Z")

</div>

I recently discovered the [bijou64 variable-length integer encoding](https://github.com/inkandswitch/bijou/blob/main/bijou64/SPEC.md). The reference implementation is in Rust, and it appears to outperform LEB128 for most encoding and decoding. While I don’t have any need for bijou64 in my own work, I saw it as a tractable challenge to learn about profiling, benchmarking, etc.\[1\]

I put together a [small package](https://github.com/KyleSJohnston/Bijou64.jl) to implement the specification.\[2\] I have been reading the [performance tips](https://docs.julialang.org/en/v1/manual/performance-tips/) and experimenting with variations to get closer to the Rust performance.

I noticed clear improvement by reducing the number of allocations (see [this](https://github.com/KyleSJohnston/Bijou64.jl/pull/2)), but it’s not obvious to me where to look next. Type instability seems to be limited to `Base.iterate` and pretty [minor](https://discourse.julialang.org/t/understanding-the-output-of-code-warntype/123191/4) situations. I added `@inbounds` in a few places to little effect. Without any supporting data, I was about to explore replacing `reinterpret` with bit operations when I decided I might have better luck reaching out to the discourse community for suggestions.

> **Source Code**
>
> The full source is here: [Bijou64.jl/src/Bijou64.jl at main · KyleSJohnston/Bijou64.jl · GitHub](https://github.com/KyleSJohnston/Bijou64.jl/blob/main/src/Bijou64.jl).
> 
> The function in question:
> 
> ```julia
> """
> encode(values)
> 
> Encode `values` using the bijou64 variable-length integer encoding into a Vector{UInt8}
> 
> `values` must be a `Vector{T}`, where `T` may be UInt8, UInt16, UInt32, or UInt64.
> """
> function encode(values::Vector{T})::Vector{UInt8} where {T <: UNSIGNED}
> if length(values) == 0
> return UInt8[]
> end
> 
> # Pre-allocate an array for the results and fill it.
> # `maxbytes` inspired by https://github.com/davidssmith/LittleEndianBase128.jl/blob/85f2c1e6b8041e9bcfbab897e673a0a45186d3db/src/LittleEndianBase128.jl#L38
> # Because `bytes` will always be large enough for all of `values`, `@inbounds` can be
> # used when indexing into `bytes`.
> maxbytes = length(values) * (0x01 + value2tier(typemax(T)))
> bytes = Vector{UInt8}(undef, maxbytes)
> 
> # Pre-allocate payload array for `reinterpret` in the loop.
> # This avoids incurring the cost of temporary array construction
> # during each iteration.
> # The eltype is UInt64 because `tier2offset` always returns a UInt64.
> payload = Vector{UInt64}(undef, 1)
> 
> i = firstindex(bytes)
> for v in values
> if v < 248 # T(248)
> @inbounds bytes[i] = v
> else
> tier = value2tier(v)
> @inbounds bytes[i] = tier2tag(tier)
> payload[1] = hton(v - tier2offset(tier)) # big-endian unsigned integer
> payload_bytes = @views reinterpret(UInt8, payload)[end-tier+1 : end]
> for pb in payload_bytes
> i = nextind(bytes, i)
> @inbounds bytes[i] = pb
> end
> end
> i = nextind(bytes, i)
> end
> return bytes[begin:prevind(bytes, i)]
> end
> 
> ```

> **Type Stability**
>
> ```julia
> (Bijou64) pkg> precompile
> 
> julia> using Bijou64
> 
> julia> const x = rand(UInt64(248):UInt64(65_535), 4086);
> 
> julia> @time Bijou64.encode(x);
> 0.000020 seconds (8 allocations: 48.141 KiB)
> 
> julia> @code_warntype Bijou64.encode(x);
> MethodInstance for Bijou64.encode(::Vector{UInt64})
> from encode(values::Vector{T}) where T<:Union{UInt16, UInt32, UInt64, UInt8} @ Bijou64 ~/vcs/Bijou64.jl/src/Bijou64.jl:143
> Static Parameters
> T = UInt64
> Arguments
> #self#::Core.Const(Bijou64.encode)
> values::Vector{UInt64}
> Locals
> @_3::Union{Nothing, Tuple{UInt64, Int64}}
> i::Int64
> payload::Vector{UInt64}
> bytes::Vector{UInt8}
> maxbytes::Int64
> @_8::Union{Nothing, Tuple{UInt8, Tuple{Base.OneTo{Int64}, Int64}}}
> val@_9::UInt8
> val@_10::UInt64
> v::UInt64
> payload_bytes::SubArray{UInt8, 1, Base.ReinterpretArray{UInt8, 1, UInt64, Vector{UInt64}, false}, Tuple{UnitRange{Int64}}, true}
> tier::UInt8
> S#277::Base.ReinterpretArray{UInt8, 1, UInt64, Vector{UInt64}, false}
> val@_15::UInt8
> pb::UInt8
> @_17::Vector{UInt8}
> @_18::Vector{UInt8}
> Body::Vector{UInt8}
> 1 ── Core.NewvarNode(:(@_3))
> │ Core.NewvarNode(:(i))
> │ Core.NewvarNode(:(payload))
> │ Core.NewvarNode(:(bytes))
> │ Core.NewvarNode(:(maxbytes))
> │ %6 = Bijou64.Vector::Core.Const(Vector)
> │ %7 = Bijou64.UInt8::Core.Const(UInt8)
> │ %8 = Core.apply_type(%6, %7)::Core.Const(Vector{UInt8})
> │ %9 = Bijou64.:(==)::Core.Const(==)
> │ %10 = Bijou64.length::Core.Const(length)
> │ %11 = (%10)(values)::Int64
> │ %12 = (%9)(%11, 0)::Bool
> └─── goto #6 if not %12
> 2 ── %14 = Bijou64.UInt8::Core.Const(UInt8)
> │ %15 = Base.getindex(%14)::Vector{UInt8}
> │ (@_17 = %15)
> │ %17 = @_17::Vector{UInt8}
> │ %18 = (%17 isa %8)::Core.Const(true)
> └─── goto #4 if not %18
> 3 ── goto #5
> 4 ── Core.Const(:(@_17))
> │ Core.Const(:(Base.convert(%8, %21)))
> └─── Core.Const(:(@_17 = Core.typeassert(%22, %8)))
> 5 ┄─ %24 = @_17::Vector{UInt8}
> └─── return %24
> 6 ── %26 = Bijou64.:*::Core.Const(*)
> │ %27 = Bijou64.length::Core.Const(length)
> │ %28 = (%27)(values)::Int64
> │ %29 = Bijou64.:+::Core.Const(+)
> │ %30 = Bijou64.value2tier::Core.Const(Bijou64.value2tier)
> │ %31 = Bijou64.typemax::Core.Const(typemax)
> │ %32 = $(Expr(:static_parameter, 1))::Core.Const(UInt64)
> │ %33 = (%31)(%32)::Core.Const(0xffffffffffffffff)
> │ %34 = (%30)(%33)::Core.Const(0x08)
> │ %35 = (%29)(0x01, %34)::Core.Const(0x09)
> │ (maxbytes = (%26)(%28, %35))
> │ %37 = Bijou64.Vector::Core.Const(Vector)
> │ %38 = Bijou64.UInt8::Core.Const(UInt8)
> │ %39 = Core.apply_type(%37, %38)::Core.Const(Vector{UInt8})
> │ %40 = Bijou64.undef::Core.Const(UndefInitializer())
> │ %41 = maxbytes::Int64
> │ (bytes = (%39)(%40, %41))
> │ %43 = Bijou64.Vector::Core.Const(Vector)
> │ %44 = Bijou64.UInt64::Core.Const(UInt64)
> │ %45 = Core.apply_type(%43, %44)::Core.Const(Vector{UInt64})
> │ %46 = Bijou64.undef::Core.Const(UndefInitializer())
> │ (payload = (%45)(%46, 1))
> │ %48 = Bijou64.firstindex::Core.Const(firstindex)
> │ %49 = bytes::Vector{UInt8}
> │ (i = (%48)(%49))
> │ %51 = values::Vector{UInt64}
> │ (@_3 = Base.iterate(%51))
> │ %53 = @_3::Union{Nothing, Tuple{UInt64, Int64}}
> │ %54 = (%53 === nothing)::Bool
> │ %55 = Base.not_int(%54)::Bool
> └─── goto #14 if not %55
> 7 ┄─ Core.NewvarNode(:(@_8))
> │ Core.NewvarNode(:(val@_9))
> │ Core.NewvarNode(:(val@_10))
> │ Core.NewvarNode(:(payload_bytes))
> │ Core.NewvarNode(:(tier))
> │ %62 = @_3::Tuple{UInt64, Int64}
> │ (v = Core.getfield(%62, 1))
> │ %64 = Core.getfield(%62, 2)::Int64
> │ %65 = Bijou64.:<::Core.Const(<)
> │ %66 = v::UInt64
> │ %67 = (%65)(%66, 248)::Bool
> └─── goto #9 if not %67
> 8 ── nothing
> │ %70 = bytes::Vector{UInt8}
> │ %71 = v::UInt64
> │ %72 = i::Int64
> │ Base.setindex!(%70, %71, %72)
> │ %74 = v::UInt64
> │ (val@_10 = %74)
> │ nothing
> │ val@_10
> └─── goto #12
> 9 ── %79 = Bijou64.value2tier::Core.Const(Bijou64.value2tier)
> │ %80 = v::UInt64
> │ (tier = (%79)(%80))
> │ nothing
> │ %83 = Bijou64.tier2tag::Core.Const(Bijou64.tier2tag)
> │ %84 = tier::UInt8
> │ %85 = (%83)(%84)::UInt8
> │ %86 = bytes::Vector{UInt8}
> │ %87 = i::Int64
> │ Base.setindex!(%86, %85, %87)
> │ (val@_9 = %85)
> │ nothing
> │ val@_9
> │ %92 = Bijou64.hton::Core.Const(hton)
> │ %93 = Bijou64.:-::Core.Const(-)
> │ %94 = v::UInt64
> │ %95 = Bijou64.tier2offset::Core.Const(Bijou64.tier2offset)
> │ %96 = tier::UInt8
> │ %97 = (%95)(%96)::UInt64
> │ %98 = (%93)(%94, %97)::UInt64
> │ %99 = (%92)(%98)::UInt64
> │ %100 = payload::Vector{UInt64}
> │ Base.setindex!(%100, %99, 1)
> │ %102 = Bijou64.reinterpret::Core.Const(reinterpret)
> │ %103 = Bijou64.UInt8::Core.Const(UInt8)
> │ %104 = payload::Vector{UInt64}
> │ %105 = (%102)(%103, %104)::Core.PartialStruct(Base.ReinterpretArray{UInt8, 1, UInt64, Vector{UInt64}, false}, Any[Vector{UInt64}, Core.Const(true), Core.Const(true)])
> │ (S#277 = %105)
> │ %107 = S#277::Core.PartialStruct(Base.ReinterpretArray{UInt8, 1, UInt64, Vector{UInt64}, false}, Any[Vector{UInt64}, Core.Const(true), Core.Const(true)])
> │ %108 = Bijou64.:(:)::Core.Const(Colon())
> │ %109 = Bijou64.:+::Core.Const(+)
> │ %110 = Bijou64.:-::Core.Const(-)
> │ %111 = S#277::Core.PartialStruct(Base.ReinterpretArray{UInt8, 1, UInt64, Vector{UInt64}, false}, Any[Vector{UInt64}, Core.Const(true), Core.Const(true)])
> │ %112 = (lastindex)(%111)::Int64
> │ %113 = tier::UInt8
> │ %114 = (%110)(%112, %113)::Int64
> │ %115 = (%109)(%114, 1)::Int64
> │ %116 = S#277::Core.PartialStruct(Base.ReinterpretArray{UInt8, 1, UInt64, Vector{UInt64}, false}, Any[Vector{UInt64}, Core.Const(true), Core.Const(true)])
> │ %117 = (lastindex)(%116)::Int64
> │ %118 = (%108)(%115, %117)::UnitRange{Int64}
> │ (payload_bytes = (Base.maybeview)(%107, %118))
> │ %120 = payload_bytes::Core.PartialStruct(SubArray{UInt8, 1, Base.ReinterpretArray{UInt8, 1, UInt64, Vector{UInt64}, false}, Tuple{UnitRange{Int64}}, true}, Any[Core.PartialStruct(Base.ReinterpretArray{UInt8, 1, UInt64, Vector{UInt64}, false}, Any[Vector{UInt64}, Core.Const(true), Core.Const(true)]), Tuple{UnitRange{Int64}}, Int64, Core.Const(1)])
> │ (@_8 = Base.iterate(%120))
> │ %122 = @_8::Union{Nothing, Tuple{UInt8, Tuple{Base.OneTo{Int64}, Int64}}}
> │ %123 = (%122 === nothing)::Bool
> │ %124 = Base.not_int(%123)::Bool
> └─── goto #12 if not %124
> 10 ┄ %126 = @_8::Tuple{UInt8, Tuple{Base.OneTo{Int64}, Int64}}
> │ (pb = Core.getfield(%126, 1))
> │ %128 = Core.getfield(%126, 2)::Tuple{Base.OneTo{Int64}, Int64}
> │ %129 = Bijou64.nextind::Core.Const(nextind)
> │ %130 = bytes::Vector{UInt8}
> │ %131 = i::Int64
> │ (i = (%129)(%130, %131))
> │ nothing
> │ %134 = bytes::Vector{UInt8}
> │ %135 = pb::UInt8
> │ %136 = i::Int64
> │ Base.setindex!(%134, %135, %136)
> │ %138 = pb::UInt8
> │ (val@_15 = %138)
> │ nothing
> │ val@_15
> │ (@_8 = Base.iterate(%120, %128))
> │ %143 = @_8::Union{Nothing, Tuple{UInt8, Tuple{Base.OneTo{Int64}, Int64}}}
> │ %144 = (%143 === nothing)::Bool
> │ %145 = Base.not_int(%144)::Bool
> └─── goto #12 if not %145
> 11 ─ goto #10
> 12 ┄ %148 = Bijou64.nextind::Core.Const(nextind)
> │ %149 = bytes::Vector{UInt8}
> │ %150 = i::Int64
> │ (i = (%148)(%149, %150))
> │ (@_3 = Base.iterate(%51, %64))
> │ %153 = @_3::Union{Nothing, Tuple{UInt64, Int64}}
> │ %154 = (%153 === nothing)::Bool
> │ %155 = Base.not_int(%154)::Bool
> └─── goto #14 if not %155
> 13 ─ goto #7
> 14 ┄ %158 = bytes::Vector{UInt8}
> │ %159 = Bijou64.:(:)::Core.Const(Colon())
> │ %160 = bytes::Vector{UInt8}
> │ %161 = Base.firstindex(%160)::Core.Const(1)
> │ %162 = Bijou64.prevind::Core.Const(prevind)
> │ %163 = bytes::Vector{UInt8}
> │ %164 = i::Int64
> │ %165 = (%162)(%163, %164)::Int64
> │ %166 = (%159)(%161, %165)::Core.PartialStruct(UnitRange{Int64}, Any[Core.Const(1), Int64])
> │ %167 = Base.getindex(%158, %166)::Vector{UInt8}
> │ (@_18 = %167)
> │ %169 = @_18::Vector{UInt8}
> │ %170 = (%169 isa %8)::Core.Const(true)
> └─── goto #16 if not %170
> 15 ─ goto #17
> 16 ─ Core.Const(:(@_18))
> │ Core.Const(:(Base.convert(%8, %173)))
> └─── Core.Const(:(@_18 = Core.typeassert(%174, %8)))
> 17 ┄ %176 = @_18::Vector{UInt8}
> └─── return %176
> 
> ```

_What are the next tools or evaluations you would recommend? Are there good heuristics for knowing when further optimization is unlikely to be helpful?_

I’d appreciate any pointers or suggestions, and thanks in advance for your thoughts/links/suggestions/etc.

* * *

1. With a few guidelines, I find it pretty easy to write Julia code that’s as performant as I need. I mostly try to avoid the obvious problems, and I end up mostly happy with the results. 

2. The package is not current registered, but if I would submit it to the general registry if there were interest.

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [June 16, 2026, 4:22pm UTC](https://discourse.julialang.org/t/bijou64-varint-encoding/137654/2 "2026-06-16T16:22:03Z")

</div>

Cool project! I suspect lots of your next optimizations could come from avoiding/limiting the temporary array use. For example:

> [@KyleSJohnston](#):
>
> ```julia-auto
> payload = Vector{UInt64}(undef, 1)
> # ...
> payload[1] = hton(v - tier2offset(tier)) # big-endian unsigned integer
> payload_bytes = @views reinterpret(UInt8, payload)[end-tier+1 : end]
> for pb in payload_bytes
> i = nextind(bytes, i)
> @inbounds bytes[i] = pb
> end
> # ...
> 
> ```

There’s a lot of overhead here to do what you really want, which is just accessing a _subset_ of bytes within an `Int64`. What you could do instead is reinterpret the _bare_ `UInt64` directly into a tuple of bytes. In other words, ditch the one-element array entirely and instead do something like (untested):

```julia-auto
            payload = hton(v - tier2offset(tier)) # big-endian unsigned integer
            payload_bytes = reinterpret(NTuple{8, UInt8}, payload)
            for pi in tier:8
                i = nextind(bytes, i)
                @inbounds bytes[i] = payload_bytes[pi]
            end

```

The next things I’d look towards would be the `bytes` scratch space itself and looking into SIMD-ability if at all possible… but those are both more challenging.

---

<div class="post-metadata">

**Author:** ![matthias314](https://avatars.discourse-cdn.com/v4/letter/m/a88e4f/32.png) [@matthias314](https://discourse.julialang.org/u/matthias314)\
**Post date:** [June 16, 2026, 11:34pm UTC](https://discourse.julialang.org/t/bijou64-varint-encoding/137654/3 "2026-06-16T23:34:10Z")

</div>

The last line of `encode` is

```julia-auto
return bytes[begin:prevind(bytes, i)]

```

which allocates a new vector. This can be avoided with

```julia-auto
return resize!(bytes, prevind(bytes, i))

```

maybe combined with `sizehint!` to shrink the capacity.

Here is another version of `value2tier`:

```julia-auto
function value2tier_new(v::T) where T <: UNSIGNED
    t::NTuple{8,UInt64} = (0xF8, 0x01F8, 0x0101F8, 0x010101F8,
        0x01_010101F8, 0x0101_010101F8, 0x010101_010101F8, 0x01010101_010101F8)
    something(findlast(v .>= t), 0) % UInt8
end

```

It does not vectorize on my machine, but it’s still faster:

```julia-auto
julia> using Chairmarks

julia> p = rand(UInt64, 1000);

julia> @b similar(p, UInt8) map!(value2tier, _, $p), map!(value2tier_new, _, $p)
(2.913 μs, 657.857 ns)

```

(Mapping the function over a vector without doing anything else is not what you want to do, so the absolute numbers are not realistic.)

EDIT: On a machine with AVX512 the new function does _not_ do better in the benchmark above.

You insist that the argument `values` be a `Vector`. With an `AbstractVector` you would be more flexible. For example, you could say

```julia-auto
encode(v::UNSIGNED) = encode(v:v)

```

which avoids allocating the vector `[v]`.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [June 17, 2026, 9:45am UTC](https://discourse.julialang.org/t/bijou64-varint-encoding/137654/4 "2026-06-17T09:45:54Z")

</div>

I think you (and possibly the bijou original authors) are under a misapprehension that basic julia or rust or C can ever reach competitive performance (as measured by the benchmarks on the page).

This problem almost surely has the shape where you need to basically write in assembly / intrinsics; where you need to spend some time poring over avx2, avx512, arm neon and arm sve manuals, and use different algorithms for each.

Once you have the instruction sequence you want, figuring out a way of writing portable julia / rust / C that the compiler optimizes to that instruction sequence is a nontrivial (and optional) second step.

As an example, consider e.g. [GitHub - simdjson/simdjson: Parsing gigabytes of JSON per second : used by Facebook/Meta Velox, the Node.js runtime, ClickHouse, WatermelonDB, Apache Doris, Milvus, StarRocks · GitHub](https://github.com/simdjson/simdjson)

Attempting to write a json parser in portable C / rust / julia / java and expecting competitive performance would be pretty futile.

That being said, I don’t want to spoil the fun too much, just temper your expecations, and don’t believe that the rust reference implementation is competitive with “ideal” code.

---

<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:** [June 17, 2026, 9:22pm UTC](https://discourse.julialang.org/t/bijou64-varint-encoding/137654/5 "2026-06-17T21:22:07Z")

</div>

I don’t really have optimization advice, just 2 cents. I can’t really estimate the impact, but the temporary arrays and reinterpreted arrays have stubborn overheads. Heap-allocated arrays take more work to handle, and even when you need the heap, it’s better to stay away as long as possible. That’s more annoying in languages that don’t map as conveniently to the heap/not-heap distinction, but Julia has some options. On top of using heap-allocated memory, reinterpreted arrays add overhead to work around the strict aliasing rule; to enable type-aliased alias analysis, the (LLVM part of the) compiler assumes pointers of different types never share memory. `@views reinterpret(UInt8, payload)[end-tier+1 : end]` cannot simply pluck a couple bytes from `payload`’s memory without jumping through hoops at runtime.

I usually would suggest looking at the reference implementation, but the API is different enough that I wouldn’t know where to start. For example, the Rust API for `encode` apparently encodes a single `u64` value into 1-9 bytes appended to a preexisting `Vec<u8>`, and the parallel to `Bijou64.encode` encoding a vector of unsigned integers isn’t obvious to me. The reference implementation’s benchmark appears to loop its `encode` over the 4096 test inputs into the one `Vec<u8>` per sample, but I’m not good at Rust so take that with a grain of salt.

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [June 18, 2026, 5:53am UTC](https://discourse.julialang.org/t/bijou64-varint-encoding/137654/6 "2026-06-18T05:53:04Z")

</div>

It’s unlikely to help you with your optimization but [GitHub - GunnarFarneback/UniversalIntegerCodes.jl: Universal Codes for Integers · GitHub](https://github.com/GunnarFarneback/UniversalIntegerCodes.jl) might be of some interest as another view on variable-length integer encodings.