-
Notifications
You must be signed in to change notification settings - Fork 21
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Support varint to have a better list size encoding #408
Comments
There's a clear advantage in proto-buf to support the greater length of integers. |
Hey team! Please add your planning poker estimate with ZenHub @apoorv-2204 @imnik11 @Neylix @prix-uniris |
Tasks/Actions
|
* Added VarInt Utility Module * Added new VarInt Scheme for all lists inside transaction chain folder * VarInt Implemented for transaction_chain, tests passing for transaction_chain * Fixed with new VarInt in BeaconChain Lists and DocTests * Fixed Test in Election and Mining Fees and Transaction Controller since changes in Serialization. * Chore: Credo Fix * Review Modification and Addition of VarInt in message.ex * Added VarInt in db/encoding.ex for storage * Review Changes and Modifications * Review Changes: Remove VarInt from nb_validations and nb_cross_validations
Is your feature request related to a problem?
We are using some fixed int sizing for the encoding, for example in the list or binary encoding from estimation or approximation. (ex: 1 byte = 256 elements in a list)
However, this approach is not scalable and inefficient as it can either limit the number of items or use too big encoding and useless bytes.
Describe the solution you'd like
To tackle this problem, we can leverage Variable length integers (varint): an encoding format which compress down integers into a smaller space than is normally needed. So we can save bandwidth. The idea is smaller numbers are more common in than larger ones.
So the trade-off is to spend more bits on larger numbers, and fewer bits on smaller numbers.
Example: a 64-bit integer that is almost always less than 256 would be wasting the top 56 bits of a fixed width representation.
There are several approaches of this problem:
While Protobuf's approach seems interesting, it's still quite complex using bits manipulation.
The benefit of length prefixed is the simplicity of understanding and fast decoding.
So we can leverage such technique as length prefixed but we can simplify it a bit using a simple byte to identify how many bytes the following integer is encoded:
<<1::8, x::8>>
-> 1 byte<<2::8, x::16>>
-> 3 bytes3::8, x::32>>
-> 5 bytes<<4::8, x::64>>
-> 9 bytesAdditional context
Should be implemented for the infinite sizes (input list, etc...)
The text was updated successfully, but these errors were encountered: