TvStorage may not require a BitSet
Disclaimer: I have almost no knowledge in Rust! However I can read the code and understand what's going on.
Today I tried a little experiment: I ported TvStorage
to JavaScript and benchmarked the implementation. I was astonished by the results: it beats the native Map
implementation! I wanted to see if there was more room for optimisation and found out that the bit set wasn't required (at least in JavaScript).
Since ids
is compact, it is easy to figure out which storage is the least full when joining them together. Moreover, it is possible to compare data_indices
length to know if an ID has been stored at some point.
Note: The following are speculations since I don't know if it is feasible in Rust. However, in JavaScript, it has proven to be faster than the bit set implementation.
It should be possible to remove bits
and to mark empty data_indices
slots using a special value (let's say -1
). Then, join2
algorithm could be something like this:
function join2<A, B>(
// The storages
a: TvStorage<A>,
b: TvStorage<B>,
// A closure called for each match
fn: (a: A, b: B) => void
) {
// Finds the storages that contains the least entries.
// This expression should be macro-generated to support more than 2 storages.
let ids = a.ids.length < b.ids.length ? a.ids : b.ids
// Iterates over the stored IDs.
// Note: this is not the most performant way to iterate an array but at least
// it's readable.
for (let id of ids) {
// Tests if the ID may be stored.
// If the ID is out-of-bound we can ignore it.
if (
id < a.indices.length &&
id < b.indices.length
) {
// Great, the ID may be set.
let i = a.indices[id];
let j = b.indices[id];
if (i !== EMPTY && j !== EMPTY) {
// Extracts the components and calls the closure.
// Note: this is an implementation details.
fn(a.data[i], b.data[j]);
}
}
}
}
The above function could be generated using a macro.