Persistent IndexMap support?

[Dorumin]

Would it be considered within the scope of the crate to have an insertion-ordered persistent HashMap implementation? I was reminded of it by a comment by jplatte (who I do not want to ping twice in one day!) in issue #158, and because I've personally wanted this in the past.

Taking the approach that indexmap uses, a way of designing this struct in userland could be:

struct IndexMap<K, V> {
    indices: imbl::HashMap<K, usize>,
    entries: imbl::Vector<Bucket<K, V>>
}

where Bucket is effectively a tuple of the hash, key, and value; I'm not entirely certain that storing the hash is necessary though. The key is stored in the Vector to be able to scan the matching hashes in the HashMap while also comparing equality with the key until a match, if any, is found.

This approach, however, has fairly atrocious time complexity in the case of shift_removing a key/index.

• Not only can you not memcpy the Buckets inside the entries Vector, since it's no longer a dense Vec, but you'll also either have to fully scan the indices table to subtract one from the stored mapped indices or do a lookup for each key (the decrement_indices in the indexmap Core does this).
  • At the very least we'd preserve structural sharing and you could mutate in place if you have your own copy that's yet to be cloned
• It looks pretty bad unless it also implements:
  • some sort of tombstone system
  • or having some sort of globally-incrementing index for insertions and a value we can use to iterate live indices. This could probably be done with an OrdMap and keeping a sequence_id (probably u64 and not usize; we're not constrained by memory in this case but rather how many times you can insert + remove)
    • Thinking about this approach some more, I think it would perform rather well in nearly all cases, but it could not offer a get_index(usize) -> Option<(&K, &V)> like indexmap does unless the issue 158 were implemented in order to have O(log n) access by index. This is not a use case I personally care about for an indexmap, where insertion ordered iteration is more important than getting a property by index

This library seems to try and offer decent-perf for the most common use cases, and worrying about whether to shift or swap does not quite match with that idea.

[jneem]

Would it be considered within the scope of the crate to have an insertion-ordered persistent HashMap implementation?

Maybe. I'm not too keen to enlarge this crate because I'm only "lightly" maintaining it (in the sense of responding to stuff, but not actually doing much work myself). One thing that might convince me is if the implementation of IndexMap benefits from internal imbl code, so that there's a real advantage to having it in-crate instead of as a separate crate.

Not only can you not memcpy the Buckets inside the entries Vector, since it's no longer a dense Vec

I don't think you'd have to shift the entries vector down, because Vector already supports efficient removal in the middle.

you'll also either have to fully scan the indices table to subtract one from the stored mapped indices or do a lookup for each key

This is the same as the indexmap crate, right? Which is why their remove defaults to swapping instead of shifting. But yes, if you want fast removal that preserves the order, I think either of your approaches should work. One disadvantage of the globally-incrementing index is that I expect lookups to become slower: you need a hashmap lookup and an ordmap lookup and a vector lookup. But in exchange you don't need to worry about periodically compacting tombstones...

[Dorumin]

Maybe. I'm not too keen to enlarge this crate
One thing that might convince me is if [...] there's a real advantage to having it in-crate instead of as a separate crate.

Fair. Nothing's stopping it from being done in a separate crate - I've put an implementation up here and on crates. It would really just help avoid code duplication, like with the Entry API structs.

I based it off of the OrdMap approach, being the least surprising in performance and potentially getting index access if that other issue gets picked up.

I don't think you'd have to shift the entries vector down, because Vector already supports efficient removal in the middle.

Brain fart. Just the indices map update was the concern.

This is the same as the indexmap crate, right? Which is why their remove defaults to swapping instead of shifting.

Yep.

One disadvantage of the globally-incrementing index is that I expect lookups to become slower: you need a hashmap lookup and an ordmap lookup and a vector lookup. But in exchange you don't need to worry about periodically compacting tombstones...

I haven't actually conjured up a tombstone implementation in my head yet due to the added complexity, but the OrdMap approach doesn't actually require a vector lookup. It can just do hashmap->key->seq_id, and then ordmap->seq_id->value.

A vector implementation might actually be faster in a lot of cases though, but it would have that concerning shift problem without some engineering behind it. I'd rather wait on an OrdMap with a generic type parameter like TrackedSubtree = Untracked/Tracked to keep track of subtree sizes.

Ultimately, the benchmarks in my imbl-index experiment don't point to an all too terrible performance degradation for the double tiered access. I think the worst relative score is 7.1x slower than ordmap... because hashmap was also 7.1x slower than ordmap in that particular test. get_index() is the big hole that I haven't personally needed