Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bijou64: A variable-length integer encoding

inkandswitch.com

Post reply on HN
Print view View original

71–80 of 93 posts

Re: Bijou64: A variable-length integer encoding

#71

Post by hansvm »

nine_k wrote: post #36
kstenerud wrote: post #20

The problem is that this breaks down once you try to use SIMD instructions. I'd developed a similar kind of approach to encoding integers (and ieee774 floats) a couple of years ago (first byte encodes length and first bit of data: https://github.com/kstenerud/bonjson/blob/05b91f6fe7d6b07186... ). It was very clever and used compiler intrinsics to get the length in 1 instruction, so 2 instructions got you the final va…

I think these are different use cases. If you talk about SIMD, you talk about the CPU and efficient processing of large numbers of integers. I think that when a solution like this crops up, it's about storage or transmission, and dense packing at the cost of non-uniformity. It's more like time-series databases pack numbers by delta encoding.

I dunno. Varints in the wild tend to be misused, and there are external proto schemas at work we have to integrate with which would literally be both faster and smaller as gzipped json. They're misused because they have an API encouraging misuse -- compressing scalars rather than sequences. Varints are used because they can have reasonable developer ergonomics while sometimes improving computer metrics a twidge.

On top of that, for the vast majority of performance/cost parameter spaces, you're better off both in developer ergonomics and speed/space slapping zstd across a flatter binary format, supposing no better tool fits your use case better. Especially if your messages aren't exceptionally tiny. You're not using them in a raw DB or doing raw bulk analysis on varints (else basically zero choices of parameters make varints win out), so you're transferring them somewhere and decoding them. That decoding step, even for highly optimized solutions like bijou64, is on par with (slightly better than, if you have an older datacenter link) your raw network. If you spend 1s on networking, you spend 1s on parsing. That's a bad tradeoff almost always, and that assumes a good varint solution.

Even when varints make sense for some set of perf/cost parameters, it's still only for developer ergonomics 99.9999% of the time. Even simple changes like operating on a sequence of values rather than a single scalar enable vastly better CPU/space tradeoffs, and being willing to craft a proper data layout usually offers huge gains on top of that.

It's interesting that you pick delta encoding (or, its natural extension, double-delta encoding often being valuable) for time-series databases as an example. That's an obvious case where you have a solution which is extremely cheap in storage/network/CPU. Varints suck comparatively, almost always.

Not to rip on them too much, especially since it's nice to have primitives available which let you not have to do hard thinking for literally every problem, but they're not amazing and not a great default.

Re: Bijou64: A variable-length integer encoding

#72

Post by stebalien »

b_fiive wrote: post #24
stebalien wrote: post #5

I've used LEB128 (with canonicalisation) extensively and... this looks so much nicer for most use-cases (length prefixed, supports the full uint64 range without that extra 10th byte). The downside is the encoding size. LEB128 quickly grows to 2 bytes, but stays at 2 bytes all the way to 2^14. This is important if you're using these numbers as tags/identifiers as we were in the multicodec [1] project, or for network m…

sup steb, this is expede's work!

Sup b5! I always look forward to new work by expede (and n0).

Re: Bijou64: A variable-length integer encoding

#73

Post by NooneAtAll3 »

kstenerud wrote: post #57
jaen wrote: post #54

Earlier quoted context omitted.

Right, I think we have a slightly different definition of SIMD: You mean byte-parallel, I mean "doable with SIMD instructions". I also didn't imply the performance would be better than other methods... Even though decoding the lengths must be serial (since's there's no unambiguous way to differentiate a tag and data byte), it's still doable within the wider SIMD registers, so there's some theoretical efficiency gain…

Yeah, sorry, I didn't say that very well. Single value decoding of Bijou values is of course trivial in SIMD, but the performance benefits of SIMD come from deterministic boundaries across a window. ULEB128's continuation bit is fixed position, so it's data independent. One pmovmskb gives you every boundary in the window. Interleaved Bijou has no such signal (tag and payload bytes both span 0x00–0xFF), so finding the…

would vector instruction be of any help? (variable length simd)

Re: Bijou64: A variable-length integer encoding

#74

Post by juancn »

I like the denormalization of VLE ints (with or without zig-zag encoding of negatives), it helps support out of band information, such as nulls and other signals in serialization protocols with minimal overhead.

For example you can use a denormalized zero to signal null.

You can still define a canonical encoding where denormalizations have specific meaning or signal an error.

Re: Bijou64: A variable-length integer encoding

#76

Post by dzaima »

Kinda surprised that there's no discussion on that this basically just does not solve the non-canonicality problem.

Forgetting to do the range check on the first_byte==255 case and just letting it do 64-bit wraparound is exactly as much of a plausible bug as missing range checks on LEB128. Any test suite with the goal of covering canonicality will trivially cover both properly; and a programmer that implements things by reading 7 words into the spec, saying "oh yeah I got this" and goes to implement what seems simple, will write a broken version of both.

Perhaps the biggest benefit is just not being associated with a format that tolerates non-canonicality in other places (though, if bijou64 gains traction, it'll only be a matter of time for wraparound-check-less versions to start appearing in places where the wraparound is fine); and I guess also it being less annoying to implement the canonicality check, though hopefully people writing security-sensitive software aren't ones to skip out on correctness checks due to annoyingness.

In a sense, bijou64 could perhaps even be more problematic - it invites not doing any range checks for the smaller inputs because they obviously don't need it, and so you can just forget to special-case the max length case; whereas LEB128 makes you already care about it at the first point it is actually LEB128.

(of course, the format does still have other benefits; enforced canonicality is just...not one of them)

Re: Bijou64: A variable-length integer encoding

#77

Post by apitman »

raphlinus wrote: post #68
apitman wrote: post #64

This reminds me of the varint encoding used by QUIC, but I've never implemented it. Anyone know the differences?

Similar, in that it encodes length in the first byte. The differences are: * It does not require canonicality, it allows multiple encodings of the same value. To make things even more fun, the QUIC spec requires shortest encoding in some uses but not others. * It uses 2 bits rather than cutting out a range. * It only encodes values up to 62 bits long. So, some similarities but also some differences. [1]: https://www.…

Perfect, thanks!

Re: Bijou64: A variable-length integer encoding

#78

Post by restalis »

dzaima wrote: post #76

Kinda surprised that there's no discussion on that this basically just does not solve the non-canonicality problem. Forgetting to do the range check on the first_byte==255 case and just letting it do 64-bit wraparound is exactly as much of a plausible bug as missing range checks on LEB128. Any test suite with the goal of covering canonicality will trivially cover both properly; and a programmer that implements things…

Your range checking requirement is just one of many things that may or may not be necessary to someone using this. Taking them all into account (besides the fact that may be unfeasible, if there happen to be some conflicting requirements) would render the solution to be unnecessarily complex. It's better to focus on the minimal set of viable requirements and thus have a base design as simple as possible. For additional requirements, just go and complicate your design (and be the only one having to pay the costs that come out of that complication), hopefully only when and only for as long it makes sense to do so. For the need you mention, some kind of container wrapper may do, with the amount of number's words specified in it. A good thing is that you'd be able to limit the use of such container-wrapped numbers only to some situations (like the exchange of data to and from unsanitized areas).

Re: Bijou64: A variable-length integer encoding

#80

Post by teo_zero »

pkulak wrote: post #27
billpg wrote: post #26

I forget where I encountered it, but I've seen similar encodings that eliminated the possibility of many possible encodings for the same number by making the length part of the value. Values 0-127 are a single byte, but if that first byte has the continuation bit set, not only does that indicate the next byte has 7 more bits to contribute, it also moves the base up to the next window. 10000000 00000000 is the only wa…

UTF-8?

UTF-8 notoriously doesn't prevent ambiguous encoding by construction, but only prohibiting it in the specs. It's known as overlong encoding. It's up to the encoder/decoder to prevent, correct, or reject it. This burden on the software is exactly what TFA tries to eliminate with the bijou64 format (unfortunately replacing it with another burden: overflow check).
Post reply on HN