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

Type safe Fibonacci #13

Closed dzmitry-lahoda closed 5 years ago

dzmitry-lahoda commented 5 years ago

As of now Fibonacci will throw on int64.max. It is possible to make it not to throw (so it will reduce performance a little), but will be type safe. I.e. handle +1 out of band of number. But this reduction will be same as already reduced by error handling https://gitlab.com/dzmitry-lahoda/dotnet-system-except

Alternative is to introduce int63(or like), but that also will reduce perf, may be substantially and do intrusive into API of users. I have tested for floats https://gitlab.com/dotnet-fun/dotnet-system-numerics-algebra/blob/master/benchmarks/UnsafeRefFloat.cs .

I am trying to replace 7bit with fib for u8 and u16, but avoid surprises.

So may be avoid these in integer-compression could be good too.

dzmitry-lahoda commented 5 years ago

As example https://github.com/dzmitry-lahoda/NetStack/commit/17eba5c3f31682d5dc9fdd57839ccde91238f5a0.

invertedtomato commented 5 years ago

There are some really interesting optimizations in your code in general there!

I couldn't think of a possible desire to support precisely UInt64.MaxValue - but to be explicitly correct you are right.

dzmitry-lahoda commented 5 years ago

In my case, I could have deployed a game which uses fib for u8 and u16 (byte and ushort) and may be u32. I works fine for a month. Then some people start to get errors because some numbers reach limit sometimes which was miss during testing. Than we need wold wide redeploy.

I guess https://en.wikipedia.org/wiki/Principle_of_least_astonishment may apply.

Same for deploy e.g. onto car measurement data analytics onto ARM hardware or whatever large scale number storage.

About u64(ulong). I do not know, for purposes of symmetry of all numbers.

If some people will need optimal version, than provide them with u63Encode method or EncodeUnsafe and just reduce max into max - 1. I may be better solution than exception either overall.

My desire to allow juniors developers to use the code and make code absolutely safe to use without dropping perf to much.

invertedtomato commented 5 years ago

I hear you. I've attempted to be clear that it supports only UInt64.MaxValue-1. (See the MaxValue property). I'll see if it comes up in the real world though.