svbyte
| Crates.io | svbyte |
| lib.rs | svbyte |
| version | 0.1.1 |
| source | src |
| created_at | 2023-05-22 08:55:06.062751 |
| updated_at | 2023-05-22 11:39:19.599377 |
| description | Fast Stream VByte implementation |
| homepage | https://github.com/bazhenov/svbyte |
| repository | https://github.com/bazhenov/svbyte |
| max_upload_size | |
| id | 870470 |
| size | 55,164 |
Denis Bazhenov (bazhenov)
documentation
README
Rust Stream VByte encoder/decoder
This library provides encoding/decoding primitives for Stream VByte encoding.
Stream VByte encoding is a SIMD accelerated algorithm of VarInt decompression. It is used in a search and database systems as a way of efficiently store and stream large number of VarInts from a disk or main memory.
Benchmarking results:
| CPU | Base Freq. (GHz) | Turbo Freq. (GHz) | Result (GElem/s) |
|---|---|---|---|
| Xeon E3-1245 v5 | 3.5 | 3.9 | 5.0 |
| Core i7-1068NG7 | 2.3 | 4.1 | 5.5 |
The idea behind VarInt is not to store leading zero bytes of the number. This way large amount of relatively small numbers can be stored in a much more compact way. VarInt encoding is frequently used with delta-encoding if numbers are stored in the ascending order. This way all the numbers are smaller by magnitude, hence better compression.
Stream VByte working using two data streams: control stream and data stream. Control stream contains control words (1
byte each). Each control word describe length of 4 numbers in the data stream (2 bits per number, 00 - length 1,
01 - length 2 and so on).
Links
- Stream VByte: Faster Byte-Oriented Integer Compression by Daniel Lemire and Leonid Boytsov.
- Stream VByte: breaking new speed records for integer compression by Daniel Lemire
- Compress-a-Palooza: Unpacking 5 Billion Varints in only 4 Billion CPU Cycles