Skip to content
The methodOpen data
Back to the collection

Decoding billions of integers per second through vectorization

Daniel Lemire, Leonid Boytsov

2012 · arXiv

DatabasesComputer systems
Read the paper
HN score
0
Mentions
4
Readers
4
Months
4
What’s in a score?

From the abstract

In many important applications -- such as search engines and relational database systems -- data is stored in the form of arrays of integers. Encoding and, most importantly, decoding of these arrays consumes considerable CPU time. Therefore, substantial effort has been made to reduce costs associated with compression and decompression. In particular, researchers have exploited the superscalar nature of modern processors and SIMD instructions. Nevertheless, we introduce a novel vectorized scheme called SIMD-BP128 that improves over previously proposed vectorized approaches. It is nearly twice as fast as the previously fastest schemes on desktop processors (varint-G8IU and PFOR). At the same time, SIMD-BP128 saves up to 2 bits per integer. For even better compression, we propose another new vectorized scheme (SIMD-FastPFOR) that has a compression ratio within 10% of a state-of-the-art scheme (Simple-8b) while being two times faster during decoding.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

4 selected excerpts · 4 total mentions

ashtonsix
Neutral mention · rule
Thank you so much for attempting a reproduction! (I posted this on Reddit and most commenters didn't even click the link) For the baseline you need SIMDe headers: https://github.com/simd-everywhere/simde/tree/master/simde. These alias x86 intrinsics to ARM intrinsics. The baseline is based on the previous State-of-The-Art (https://arxiv.org/abs/1209.2137) which happens to be x86-based; using SIMDe to compile was the highest-integrity way I could think of to compare with the previous SOTA. Note: M1 chips specifically have notoriously bad small-shift performance, so the benchmark results will be very bad on your machine. M3 partially fixed this, M4 fixed completely. My…
Read the full comment
primary target is server-class rather than consumer-class hardware so I'm not too worried about this. The benchmark results were cpy-pasted from the terminal. The README prose was AI generated from my rough notes (I'm confident when communicating with other experts/researchers, but less-so with communication to a general audience).
Original comment 86 GB/s bitpacking with ARM SIMD (single thread)
ot
Neutral mention · rule
> For my purpose, I want to get as high a compression rate as possible, and I need to store just the list of integers Then PFor(Delta) is not the best option, that class of algorithms is intentionally a trade-off between compression rate and decoding speed, as it's meant to store posting lists in inverted indexes. If you want higher compression, a better option would be Binary Interpolative Coding [1], which has some of the highest compression rate among the schemes that are relatively simple to implement. Then you can go down the rabbit hole and start to use entropy compression, complex modeling, etc... But there are diminishing returns. > The problem with PFor,…
Read the full comment
however, is that if you have a single large outlier, you’ll waste a lot of bits unnecessarily. This is not true, the author is describing binary packing of deltas, and mistaking it for PFor. What PForDelta means is - P -> Patched: Outliers are stored separately in a list of "exceptions", so that does not affect the bit size of the rest of the block - For -> Frame of Reference: the min value of the block is subtracted from the values in block, which are then encoded with the minimum number of bits necessary for the adjusted maximum (this is just binary packing) - Delta -> Deltas are encoded instead of values, only used if your sequence is monotonic. If it is strictly monotonic, you can encode v[i+1] - v[i] - 1 and save a little more. > This encoder will [...] Then we check the top and bottom halves of the batch, to see if we’ll get a benefit from recording them separately. What this is describing is an algorithm for partitioning lists in order to optimize for the overall binary packing compression rate; but it is greedy, and optimal algorithms exist based on dynamic programming [2] EDIT: Forgot to mention that everything I wrote above is also explained in the paper cited in the post [3], which is indeed a very good survey of this stuff. [1] https://link.springer.com/article/10.1023/A:1013002601898 [2] https://dl.acm.org/doi/10.1145/1871437.1871592 [3] https://arxiv.org/pdf/1209.2137.pdf
Original comment Sorted Integer Compression
DannyBee
Neutral mention · rule
IMHO: Using varint for this is silly, and just wastes decoding time. (Doing because proto/etc did it, when they have wildly different use cases, it a bad idea.) The example they purport to give even proves it: " For example, a 100 TB file in IPFS may have as many as 400 million subobjects, which would mean 400 million hashes. 400,000,000 hashes * (7 - 2) bytes = 2 GB" Right, so uh, that's 0.002% of that 100tb. (IE who cares) (This already appears to be the difference between what it would normally take, at 7 bytes, and what it takes with varint, which is ~17 bits per int) But assume we go crazy, and use 8 bytes per hash. we have 3.2 gigabytes there. vs 800 megabytes for…
Read the full comment
your varint encoding. Or, for our 100 terabyte file, approximately, "who cares" vs "who cares". if you could transfer at a gigabyte per second, the version with varint would take ~28 hours. The version with fixed-size 8 bytes would take ... 2 seconds longer. Remind me again how this is showing it's a good idea? Also, if you really wanted to use variable size integers, variable byte encoding is pretty much the slowest way to do it. See, e.g, https://arxiv.org/pdf/1209.2137.pdf Using variable sized integers here doesn't save space, precisely because th , but it does make it more annoying to splat these in and out of memory.
Original comment Multihash – self-describing hashes

Keep following the thread.

More in Databases

More from the same topics.

2017arXiv

The Case for Learned Index Structures

Tim Kraska, Alex Beutel, Ed H. Chi +2

Indexes are models: a B-Tree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record within an unsorted array, and a BitMap-Index as a model to indicate if a data record exists or not.

Databases
19 mentions14 months
5HN score