Re:Stream VByte: breaking new speed records for integer comp...
by frankmcsherry on Wednesday September 27, 2017 @03:44PM
(#15351563)
!#$!@# I was going to go try that out. ;) When doing the Chaos/Order stuff, the decompression was about half the CPU cycles, so thinning that could help.
Fwiw, the encoding I used wasn't VByte; because I was doing strict increments, I knew `0` wasn't a valid value to see, and used it to encode variable byte lengths (number of zeros: number of valid data bytes). Not smart, but easy to hack up, and gave me back 128-255 in one byte. I'm curious to check this out, now!
In one of the linked prior blog posts[2] of his he linked to in the beginning of that article, he said this:
Using the Hilbert curve layout leads to a very simple compressed representation: having sorted the u64 values it uses to represent edges, one can simply delta-encode them (writing the differences between adjacent values). Because the Hilbert curve teases out locality, the gaps are often quite small, and therefore compress nicely. When I combined a variable-length integer encoding with gzip, the resulting file was only 45GB; about 2.8 bits per edge). Decompressed (with just the variable-length delta encoding), it is 154GB, which is the representation I used to get the measurements above.
He then goes on in his posts to comically trounce some large distributed systems.
1: https://news.ycombinator.com/item?id=15332051
2: https://github.com/frankmcsherry/blog/blob/master/posts/2015...