search

invertedtomato / packing

Library for encoding integers in the minimal number of bits. Includes VLQ and Elias Omega encoding.
MIT License
76 stars 6 forks source link

Fast Fibonacci? #11

Open dzmitry-lahoda opened 5 years ago

dzmitry-lahoda commented 5 years ago

http://ceur-ws.org/Vol-567/paper14.pdf

invertedtomato commented 5 years ago

Gee, this is really interesting! I won't have time for a while to look into it seriously though. I'll leave this open and revisit it another day. Do let me know if you make something of this before me.

dzmitry-lahoda commented 5 years ago

I guess I will have something withing 2 month. I got integrated usual Fibonacci(it is good solution for small numbers like delta-prediction delta before going full blown huffman-zstandard-prediciton for compression), will look into fast so.

invertedtomato commented 5 years ago

While I haven't implemented fast yet, I have made some improvements. Have a look: https://github.com/invertedtomato/integer-compression/blob/master/Library/Compression/Integers/FibonacciCodec.cs#L45

invertedtomato commented 1 year ago

Hi @dzmitry-lahoda, are you still around? While I haven't yet implemented this "Faster Fibonacci", I have taken the next step and used pre-allocated UInt64 buffers to enhance writing speeds. On my test set I've reduced the write of 10m integers from ~8.0sec to ~3.4sec.

This came along with a re-write that enabled codecs to be bit-interleaved. Ie, you can use a VLQ codec adjacent to a Fibonacci codec. So long as you decode in the same order as you encode you're able to use the best codec for the type of integer you're storing.