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

Create lookup for u32 as this is used frequently either. #7

Closed dzmitry-lahoda closed 2 years ago

dzmitry-lahoda commented 5 years ago

https://github.com/invertedtomato/integer-compression/blob/8b0b80f1e74340b90cc9726c1bf944dbca93b24d/Library/Compression/Integers/Wave3/FibonacciCodec.cs#L26

invertedtomato commented 5 years ago

I like this idea. Haven't justified the effort yet though!

dzmitry-lahoda commented 5 years ago

If I have generator of u32 (uint). Than having 1B of values in memory will take 4GB and perf of fib these will be optimal.

If I have u64(ulong) API only, than I have to case 4GB into 8GB (these will take time and space - 12GB at once in memory). And fib each number may appear to be non optimal.

So u32 version is must for production API.

invertedtomato commented 5 years ago

Ok, so the lookup table will always have just 92 entries (~ 736b RAM), but are you meaning the values to be encoded? Those could be casted as required to do the same with a little more overhead. At this stage it's a bit much to optimize this project that far.

dzmitry-lahoda commented 5 years ago

  1. Each integer type would have its own lookup table inlined via ReadOnlySpan and has different count of entries and avoid cast from 64 bit to 32 16 and 8, and not consume time during calculation on start. It look like sane optimization for game networking, not sure that it is the case for other case. I.e. for games the overhead could be not so acceptable.

  2. Having encoded map another issues. I will do that for 8 bit integers. I doubt will do that that for 16 bit integers. But it is another topic.

invertedtomato commented 2 years ago

I'm going to close this issue in favour of https://github.com/invertedtomato/integer-compression/issues/11. I think that's a better approach that can work at scale. Thanks @dzmitry-lahoda