Non-Arc iterators / Interior iteration.

[XAMPPRocky]

Hello 👋 I've been benchmarking https://github.com/googleforgames/quilkin and while benchmarking I noticed that we spend a significant amount of CPU time just allocating and dropping the Arc in GuardIter (~5–10%). Because we need to iterate over the map in every packet. In our case the use of the Arc is not really needed because we're immediately consuming the iterator.

I was wondering if there's any interest in providing support for iterators that don't use Arc, or providing a way to map/reduce that doesn't involve Arc? I think this would provide significant performance benefits for those who are trying to perform an operation over the whole map immediately over the current implementation.

Code

# DashMap<String, BTreeSet<SocketAddr>
map.iter().map(|entry| entry.value().len()).sum()

Flamegraph

[XAMPPRocky]

I should note this is with a single entry in the map, it gets worse as the map gets larger.

[xacrimon]

The raw-api features exposes the underlying shards as a slice, allowing you to iterate over those and then iterate over the entries as raw std maps. The amount of arc ops is very small and the overhead of them very low compared to other costs in involved in iterating over a dashmap in normal intended use, as the number of shards is fixed relative to processor cores. I took a look at quilkin code and it seems like you're using it for not frequently changing data that is frequently iterated and the amount of entries per map is relatively low. This is like one of the least beneficial applications for something like dashmap.

If my understanding of quilkin is correct it really looks like the proper solution for your needs is a plan and simple std HashMap with a custom hasher to fit your key type. You'd implement updates to the map by RCU, completely replacing the map each time. Unless need to process hundreds of thousands to millions of key lookups concurrently with equal numbers of insertions/removals/value updates, something like dashmap which pays significant syncronisation cost on every nonmutable access and isn't optimised for iteration (the core assumption behind the design is that 99.9% of operations are single-key ops.

For implementing this kind of atomic update, I suggest using arcswap to wrap a std hashmap with a suitable custom hasher for your key type and other parameters. This allows you to clone and swap the map to implement modifications and makes reads wait-free and incredibly fast. You'd need to use ArcSwap::compare_and_swap or ArcSwap::rcu to avoid loosing updates if you have concurrent modification operations.

Closing as not a bug.