Question: Double-Ended IndexMap

[emkw]

Question to someone familiar with the codebase:

I am probably oversimplyfing things, but I imagine currently the IndexMap is backed by "something like a Vec", would changing it to "something like a VecDeque" allow popping first key-value pairs in O(1) time, same as popping last key-value pairs?

Basically my use case is that I could use a FIFO with random access by keys; as I understand currently IndexMap would allow for LIFO in O(1) time and FIFO in O(n) time.

How difficult do you think would be such modification of existing codebase?

[cuviper]

It's an interesting question!

I am probably oversimplyfing things, but I imagine currently the IndexMap is backed by "something like a Vec",

The core is literally a Vec, and a hashbrown::raw::RawTable of indices into that Vec:

indexmap/src/map/core.rs

Lines 27 to 33 in 15518f3

	/// Core of the map that does not depend on S
	pub(crate) struct IndexMapCore<K, V> {
	/// indices mapping from the entry hash to its index.
	indices: RawTable<usize>,
	/// entries is a dense vec of entries in their order.
	entries: Vec<Bucket<K, V>>,
	}

Right now, a pop_front implemented as shift_remove(0) would be O(n) on two counts, both to move all the 1.. items down in the Vec and to decrement all of those indices in the RawTable.

If we simply changed the Vec to VecDeque, that would avoid the O(n) move, but we would still have the O(n) index updates. A more advanced change could add a field tracking a rolling base offset for all indices, so pop_front wouldn't need to change the RawTable at all, apart from the single O(1) removal. You could have push_front (like shift_insert(0)) benefit as well.

There are other parts of the IndexMap API that are closely tied with being Vec-like though. For example, VecDeque doesn't support sorting at all, and our Slice API also assumes a single contiguous memory range. But if you were interested in creating a new crate with the incompatible APIs removed, I think a "DequeMap" would be feasible on its own.

If you decide to pursue this idea as a fork, I suggest starting from #343 where most of the unsafe code is gone.

Alternatively, hashlink is also based on hashbrown, with LinkedHashMap that is tracked as a linked list, so that also supports O(1) pop_front. There's no usize indexing like IndexMap though. :)

[cuviper]

I think you've nerd-sniped me, because I'm still thinking about this, and I may go ahead and try a fork based on VecDeque myself. Let me know if you're already considering or working on that yourself though. :)

[emkw]

At the moment I don't have any plans to go ahead with it, unless I run into hard performance issues with current setup - I'm mostly a user of HashMaps, never fiddled with implementing any, so it may be beyond my ability to complete it in reasonable time.

Sorry for maybe exploring too broad.

[cuviper]

No worries! I think I will explore this, and I'll share it here if I do.