FastFibonacci
Rust library implementing the FastFibonacci integer compression/decompression algorithm. Besides, the crate also supplies regular fibonacci compression/decompression.
Introduction
Fibonacci encoding is a variable-length encoding of integers, with the special property that any encoding of an interger ends in 1
(binary) and no encoding contains 11
. Hence one can use 11
as a separator in a stream of Fibonacci encoded integers.
Regular Fibonacci en/decoding works decoding bit by bit, which can be quite slow. FastFibonacci encoding and decoding looks at n
bits at once, decoding this chunk in a single operation which can be faster.
Performance
Regular Fibonacci encoding is up to speed with other rust implementations, e.g. fibonnaci_codec crate (which I took some code from):
- Fibonacci encoding:
- this crate: 75ms/ 1M integers
- fibonnaci_codec: 88ms / 1M integers
Regular fibonacci decoding (iterator based) is up to speed with the fibonnaci_codec crate. The FastFibonacci decoding functions are ~2x faster, but have some constant overhead (i.e. only pays off when decoding many integers):
- Fibonacci decoding:
- regular decoding: 92ms/ 1M integers
- fibonnaci_codec: 108ms / 1M integers
- fast decoding (u8 segments): 40ms / 1M integers
- fast decoding (u16 segments): 30ms / 1M integers
- fast decoding (using an iterator): 54ms / 1M integers
Examples
Regular encoding and decoding:
use ;
let encoded = encode ;
// Decoding
let decoded = decode; // 2nd argument: shift all values by -1 (in case we wanted to encode 0 in the fibonacci encoding)
assert_eq!;
// Alternatively, we can also create an iterator (yields one decoded int at a time)
let f = new;
assert_eq!
Fast decoding:
use ;
use prelude as bv;
let bits = bits!.to_bitvec;
// using a u8 lookup table
let table: = new;
let r = fast_decode;
assert_eq!;
// using a u16 table
let table: = new;
let r = fast_decode;
assert_eq!;
// using an iterator
let dec8 = get_u8_decoder;
assert_eq!;