-
Notifications
You must be signed in to change notification settings - Fork 55
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
Reduce allocations in BytesEncode
#257
Comments
Thank you for this proposal @nolanderc, very appreciated 😃 However, there is one minor issue with the I am pretty sure we can apply this optimization to the Meilisearch codebase and see the performance gains 🤩 |
The
BytesEncode
trait is currently defined as follows:heed/heed-traits/src/lib.rs
Lines 20 to 26 in 3406383
There are some issues with this definition:
str
,[u8]
,U32<NativeEndian>
, ...) we have to allocate a temporary buffer where the value is written.For example, most architectures in use are Little-Endian (x86, Arm), however, for lexicographic ordering to correctly sort integers, we have to store them in Big-Endian. Since this incurs a byte-swap on Little-Endian architectures we cannot simply return a pointer to the integer itself, instead we have to allocate a temporary buffer where we store the byte-swapped result. That's one heap allocation for each integer, something which could have been done trivially on the stack or in a CPU register.
Optimizations
In most cases we know a-priori the maximum size of the needed allocation:
In some cases it may be preferable to run serialization in two phases:
MDB_RESERVE
).A new trait
With the above in mind, we can make a few changes to the
BytesEncode
trait (naming TBD):Based on the value of
ZERO_COPY
we can decide between either callingbytes_encode
and directly get our slice, or using a pre-allocated buffer withencode_writer
. (If the )We could also consider making
encode_writer
the required method, and definebytes_encode
in terms ofencode_writer
withVec
as ourWrite
r. However, this would be a breaking change.Example Usage
Let's look at how we might implement
Database::put
with the above definition (pseudocode):Note that we can avoid all temporary allocations and intermediate memory copies in all cases except one: if the resulting size of
value
is unknown.The text was updated successfully, but these errors were encountered: