search

mozilla / rkv

A simple, humane, typed key-value storage solution.
https://crates.io/crates/rkv
Apache License 2.0
307 stars 52 forks source link

Prevent needless key/value copies in database methods #163

Closed victorporof closed 4 years ago

victorporof commented 4 years ago

Signed-off-by: Victor Porof victor.porof@gmail.com

We're using std::collections::HashMap's Entry API to store keys/values in our safe mode database implementation. This is more ergonomic than using an imperative API, and more performant in the ideal case.

However, the real world isn't ideal, and we end up needlessly reallocating keys and values when interacting with the database. For example, using the Entry API to insert a key/value pair into the database results in a copy of the key when the value was already added. Similarly (in an even worse case scenario), deleting all values matching a key copies the key, and attempts clearing an already empty BTreeSet representing our values.

The Entry API is long known for having poor performance in those situations, with many attempts to fix it. We could opt into using the imperative API instead, but that just makes us less performant in other situations. Luckily, we now have a new RawEntry API, added in https://github.com/rust-lang/rust/pull/54043 giving us the tools required to deal with this problem elegantly.

The RawEntry API is available in nightlies at the moment; however, we can use it in stable via std::collections::HashMap's backing store rust-lang/hashbrown.

victorporof commented 4 years ago

@ncloudioj Yes, sounds good!