Choosing a concurrent map

[maxcountryman]

Hi,

First, thank you for this fantastic crate! I particularly appreciate how well-documented things are.

On that note, I'm working on a crate that provides HTTP sessions as a tower service and am trying to find more information about potential overhead introduced by various crates, such as this one and e.g. dashmap.

I'm currently using dashmap but I'm unsure it's an ideal fit for my use case (both the session data itself as well as an in-memory cache of active/loaded sessions). Because sessions are loaded per request (either from the backing store or the in-memory cache) performance can be impacted when using overly coarse locking strategies.

For that last reason, it seems scc might be a better fit because as I understand it dashmap will lock an entire shard, which in turn could mean requests bearing unrelated sessions might block one another unnecessarily. However, my concern with scc is that it might introduce more overhead than is warranted, in particular its garbage collection facility.

That said, I'm even less sure about what overhead dashmap introduces.

I'm curious if someone might be able to shed some light on an overhead comparison between dashmap and scc?

[wvwwvwwv]

Hi!

Nice to hear that you're considering this crate for your project.

So, first and foremost, I'd like to start with dashmap's sharding vs the fine-grained locking mechanism in scc::HashMap. From my understanding, the number of shards in a dashmap instance is determined at runtime by querying the number of cores in the system; say, if the system has 32 CPU cores, the number of shards will be 32, and the number of locks in the dashmap instance is fixed to 32. On the other hand, the number of locks in a scc::HashMap instance is not fixed, and relates to the number of entries in it; you can approximate it by expected number of entries * 2 / 32 where 2 comes from the fact that the average load factor is 0.5 (empirically, it is very true for most hash maps), and 32 is the size of a bucket (where, entries share the same lock).

There, you'll have to measure the expected number of sessions in the in-memory cache. For instance, if the system has 32 CPU cores, and the expected number of cached sessions is 2048, scc::HashMap will perform better. On the other hand, if the system only serves a small number of sessions, like 128, dashmap will be a better choice.

In short, I'd say that which concurrent hash map implementation is better is totally dependent on the type of workloads and the system that the service is aimed at.

Now, the second topic, garbage collection, you really don't need to care about it unless you're considering scc::HashIndex or scc::TreeIndex. scc::HashMap immediately removes/drops an entry as soon as it was removed from it; the only heap memory allocations that will be garbage-collected later are internal hash table instances, however the operation is not expensive - during garbage collection, fn drop does almost nothing but invoking free for the memory chunks it holds.

To be specific, the EBR garbage collector will kick in after an instance of scc::HashMap got resized, e.g., capacity=64 -> capacity=128. When an scc::HashMap is resized, the old hash table (of capacity=64) is retained in it, and existing entries will be incrementally relocated to the new hash table (of capacity=128). Once the old hash table becomes empty, the old hash table is passed to the EBR garbage collector, and the old hash table will be dropped when there is no potential reader of it. Dropping the old hash table should be quite cheap (it's O(1) - no iteration over entries whatsoever), but of course, it depends on the memory allocator implementation.

-> Here, one significant difference between dashmap and scc::HashMap; the memory occupied by the old hash table will be lazily deallocated; it is usually pretty fast for the EBR garage collector to kick in, but still when exactly the memory is deallocated is not deterministic. Note that the EBR garbage collector is only triggered when scc::ebr::Guard is used; if a thread keeping garbage memory stays dormant, the garbage memory won't be deallocated at all until scc::ebr::Guard is instantiated or scc::ebr::suspend is called.

In summary, in terms of 'latency', the overhead of garbage collection should not be observable, however, in terms of memory usage, due to the nature of garbage collection, unreachable memory chunks may reside in memory for a longer time.

[x1957]

Thanks, version 2.0.17 seems to have slowed down memory growth, but it has not completely resolved the issue. I will continue testing it.

[wvwwvwwv]

Your observation is correct, it won’t fix the issue completely - a complete fix needs more thorough changes to the Entry data structure and its API. I’ll try this approach soon!

[x1957]

Thanks for your work, please notify me if new version is released.

[wvwwvwwv]

@x1957 Hi, note that you can try the SCC2.1 branch. I've uploaded several fixes to the branch that shall greatly improve the garbage collection performance. I cannot upload it to crates.io yet as the branch has yet to be fully tested.

[x1957]

Thanks, the problem has been solved.