fanum tax 64-bit integers with LEB128

Matthew Kim

Last update: May 22, 2024

Related tags

Overview

rizz64

Fanum* tax 64-bit integers.

_{* Fanum is a popular streamer who taxes his friends by taking bites of their food.}

This crate provides an efficient and powerful variable-length integer codec using LEB128 compression.

Why rizz64 is helpful

It's super efficient in representing smaller numbers with fewer bytes. Instead of a fixed-size solution like u64, this form of encoding can store values using less space or memory.

Basic metrics:

Decimal	Powers of 2	# of Bytes Needed
0..127	`2^0-1`..`2^7-1`	1
128..16383	`2^7`..`2^14-1`	2
16384..2097151	`2^14`..`2^21-1`	3
2097152..268435455	`2^21`..`2^28-1`	4

and so on... to compute the number of bytes required, you can use the following:

The upper bound of log2(max(x, 1)) / 7, where x is your number. This is derived from the fact that each byte can represent 7 bits. rizz64 uses a base-2 logarithm to determine the magnitude in bits. We call max(x, 1) to ensure this value could never be 0. We take the upper bound and round to the nearest whole number.

How encoding works

For a given u64, we process the number by groups of 7 bits. For every group, if there are more than 7 bits still to be encoded, we loop.

In the loop, the least significant 7 bits are extracted and packed into a buffer. The 8th bit is the most significant bit (MSB); we set the MSB to 1 to indicate there are more groups ahead. Then, we shift right (>>=) by 7 bits and we process the next group.

After looping, the remaining bits of the number are packed into the buffer. This is the last byte and since we're halting, we don't set the MSB to 1.

Literature

LEB128
sqlite variable-length ints
varint.go

Todo

Go outside

Comments

feat: skip bound checks by iterating

Instead of running:

loop {
     unsafe { *buf.get_mut_unchecked(i) = .... } 
}

The rust compiler seems to skip this bound check when shoving this into an iterator that is:

for i in 0..buf.len() {
     // same stuff here
}

compiler explorer: https://godbolt.org/z/49P653o9j

Performance

Running benchmarks indicate significantly faster execution times.

Benchmarking Log/write_u64 1152921504606846976: Collecting 10
Log/write_u64 1152921504606846976
                        time:   [321.67 ps 325.25 ps 329.86 ps]
                        change: [-91.933% -91.871% -91.799%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 12 outliers among 100 measurements (12.00%)

It also seems to beat out the leb128 crate by significant measures:

Benchmarking Log/leb128::write::unsigned 1152921504606846976:
Log/leb128::write::unsigned 1152921504606846976
                        time:   [1.6255 ns 1.6417 ns 1.6615 ns]
Found 11 outliers among 100 measurements (11.00%)
  5 (5.00%) high mild
  6 (6.00%) high severe

Note a more robust benchmarking report is needed to fully assert these claims

opened by friendlymatthew 0

fanum tax 64-bit integers with LEB128

Related tags

Overview

rizz64

Why rizz64 is helpful

How encoding works

Literature

Todo

You might also like...

Rust implementations of finite-field arithmetic based on big integers with configurable limb sizes

A tiny 32 bit kernel written in Rust

A bit-packed k-mer representation (and relevant utilities) for rust

Fast conversion between linear float and 8-bit sRGB

A little bit fast and modern Ruby version manager written in Rust

Tiny Rust crate to iterate bit combinations

Controls the RGB on the keyboard for the Legion 5 Pro from Lenovo. Mostly used for learning a bit of rust.

kani - 64 bit multiboot toy OS written in Rust

A naive native 128-bit cityhash v102 implementation

Advent of Code 2021, also an attempt to practice a bit of Rust.

StdFuzzer - StdFuzzer is the reference implementation of a generic bit-level fuzzer with LibAFL

A bit vector with the Rust standard library's portable SIMD API

Isn't it time to be a bit nicer to rustc?

An Intel HAXM powered, protected mode, 32 bit, hypervisor addition calculator, written in Rust.

wait-free 4-level 64-bit pagetable for contiguous low-contention concurrent metadata

Bit fields and masks for rust!

Steggy CLI Tool - hides data within the least significant bit of an image

Fast encoder/decoder for the lossless DTM 16 bit image format

Bitpack a boolean into a pointer using bit magic.

Comments

feat: skip bound checks by iterating

Performance

Owner

Matthew Kim

📈 The fastest map possible in Rust, where keys are integers and the capacity is fixed (faster than Vec!)

Rust implementations of finite-field arithmetic based on big integers with configurable limb sizes

A bit-packed k-mer representation (and relevant utilities) for rust

Isn't it time to be a bit nicer to rustc?

Bitpack a boolean into a pointer using bit magic.

Simple bit-level protocol definitions in Rust.

Rust library of custom number malarkey, including variable-bit-width integers

Rust library to convert RGB 24-bit colors into ANSI 256 (8-bit) color codes with zero dependencies and at compile-time.

A bit like tee, a bit like script, but all with a fake tty. Lets you remote control and watch a process

📈 The fastest map possible in Rust, where keys are integers and the capacity is fixed (faster than Vec!)