Fast Fibonacci?

[dzmitry-lahoda]

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

[invertedtomato]

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]

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]

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]

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.