Efficient get key/value by index in OrdMap/OrdSet

[alexforencich]

Ordering is useful for iteration, but if there is a defined order then being able to efficiently jump into the middle of that at a defined point is vital. Think use cases like pagination and such. Unfortunately, OrdMap and OrdSet do not seem to support this natively. The only option seems to be iter().skip() or iter().nth(), which I think are O(n) as as far as I can tell they work by visiting every node in sequence. Seems to me like it should be possible to speed this up significantly. Potentially both iter.skip and iter.nth could be accelerated, as well as providing APIs to convert a key to an index and get a key/value by index.

[jneem]

In principle this would be possible, but it would require adding some extra bookkeeping to intermediate nodes to keep track of subtree sizes. It would therefore add an extra (probably small, but non-zero) performance cost to users that don't care about indices.

[alexforencich]

Flip side, for the users that do need lookup by index faster than o(n), they have to use a different library. Or follow the AI recommendation of using both an OrdMap and a vector, which has significantly higher overhead.

Perhaps another option is to add an IndexedOrdMap type that adds this capability without adding any overhead to OrdMap itself.

[jplatte]

I'm pretty sure that I've wanted an imbl::IndexMap or something like it too, back when I was working on matrix-rust-sdk. I always found other solutions in the end, but it might be a useful type in general (just like indexmap is a widely-used crate).

Actually, that would be different right? You're just talking about being able to access things by index, but with indexmap you have control over how things are ordered.

[alexforencich]

Yes, indexmap preserves insert order, I want the sorting of OrdMap but the ability to efficiently extract items from the list based on the position in the sorted list. And these lists could be in the millions or billions of elements, so efficiency is key here, both for storage as well as lookup complexity.

Honestly it's probably a better idea for my application to make a custom data structure that's more like a rope that's set up to be indexed by index and by x value (fastnum D128) and can also store the x values in a compressed form (they are super high resolution time tags so there is a lot of redundancy). But I have not had time to do that yet, so I am making do with OrdMap.

[alexforencich]

Actually, I guess from a functional perspective, indexmap would be a better fit for what I need. Except, I also need efficient multithreading, and indexmap doesn't provide that. With OrdMap, I can avoid locks completely with arcswap. With indexmap, I would probably need rwlock, which would block readers during updates.

[arthurprs]

That tree variation is often referred to as "Counted". E.g. https://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html

[Dorumin]

I'm pretty sure that I've wanted an imbl::IndexMap or something like it too, back when I was working on matrix-rust-sdk. I always found other solutions in the end, but it might be a useful type in general (just like indexmap is a widely-used crate).

@jplatte I've found myself wanting a persistent insertion-order hashmap too, which isn't provided in this crate. What alternatives did you find?

[jplatte]

None, I ended up with different solutions altogether 😅