Denser length encoding as an option

[tv42]

We could encode field lengths at <1byte per field.

This could be enabled on a {message,version}-basis in the schema with e.g.

message Person v1 {
    wire format: v1
    options {
        align: 4
        # switches field lengths from varuint to exponential golomb coding
        field length encoding: exp-golomb
    }

    slots {
        ...

• they're not sorted, so can't delta-compress, but could bit pack

Resources

• fastpfor et al
• https://github.com/surge/encoding
• http://godoc.org/j4k.co/exp/varintrle
• http://godoc.org/github.com/Yawning/ntru/bitpack
• https://github.com/robskie/bit
• https://github.com/robskie/fibvec
  and https://en.wikipedia.org/wiki/Fibonacci_coding
• https://github.com/crazy2be/birdie
• https://github.com/Smerity/govarint

self-delimiting number sequences

• goal: "Field lengths are densely encoded, typically at less than 1 byte per field."

Elias δ-coding needs

math.floor(math.log(x, 2)) + 2 * math.floor(math.log(1 + math.floor(math.log(x, 2)), 2)) + 1

bits to encode x

• https://en.wikipedia.org/wiki/Prefix_code
• https://en.wikipedia.org/wiki/Variable-length_code#Uniquely_decodable_codes
• rice/golomb looks promising
  https://en.wikipedia.org/wiki/Golomb_coding
  https://github.com/dave-andersen/deltagolomb

Results from my experiments so far

• varuint is hard to beat
• exponential golomb is smaller for fields predominantly <30
  https://github.com/dave-andersen/deltagolomb
  https://en.wikipedia.org/wiki/Exponential-Golomb_coding
• everything more complex than varuint is 10x slower
• make benchmarks reproducible

[tv42]

Also https://github.com/jwilder/encoding/blob/master/simple8b/encoding.go