7 ms·

Dashmap: Fast concurrent HashMap for Rust

132 points by indiv0 7y ago

jupp0r 7y ago
Some feedback: 1. Mind the difference between concurrency and parallelism. This is around safe parallel access. Concurrent access can happen on one thread without any synchronization. 2. It’s oftentimes an anti pattern to model thread safety around primitive data structures as opposed to higher level concerns. It forces all data that has to be consistent across thread boundaries to be in this one map. When circumstances change, you might want to have some of that data in different data structures and still provide consistent access to them. This change will be hard when you rely on data structure level thread safety.
- BubRoss 7y ago
  > This is around safe parallel access I'm not sold that this semantic game is usually worth playing, but here it is pointless. Concurrent access on the same threads or different threads isn't going to break. > It forces all data that has to be consistent across thread boundaries to be in this one map Why would it force that? There is no single technique for concurrency or parallelism and that silver bullet line of thinking is a dead end. Concurrent data structures are an important part of the puzzle, especially maps and queues. Fork join, data flow, message passing, copying, swapping buffers, read only data, etc. the list goes on. If it was simple it wouldn't be a problem.
  - jupp0r 7y ago
    > Why would it force that? Because you don’t get atomic writes across multiple data structures that are each thread safe unless you perform all writes while holding a mutex. If you do that, you don't need data structures to be thread safe on their own.
    - lcy 7y ago
      > unless you perform all writes while holding a mutex No. Maybe you are not familiar with the concurrency data structures community. Many techniques are invented and used in concurrency data structures, e.g., intrinsic CPU atomic instructions, like CAS, that make the data structures "lock-free". CAS: https://en.wikipedia.org/wiki/Compare-and-swap https://en.wikipedia.org/wiki/Compare-and-swap.
      - ahupp 7y ago
        From the comment: > you don’t get atomic writes across multiple data structures They're saying that lock-free approaches don't help when you have to ensure consistency across multiple datastructures.
    - viraptor 7y ago
      It depends how you structure your data. It's possible to have one "last pointer" log for example which is updated synchronously and points at new values in multiple structures which are updated independently/optimistically. This has different timing/properties than using a single mutex.
    - mirekrusin 7y ago
      You don't even need to say "atomic across multiple data structures", "atomic across multiple keys" in is enough as it's likely next level of atomicity you'll require after atomics over single keys. But if you require that you're in this higher level of transactional semantics that hashmaps don't try to solve (you can still use them as building blocks of course). I think the furthest hashmap api could go is to do: 1. CaS - simple compare-and-swap on single key 2. CaSS - compare-and-swap on one key and set other key + read two keys tuple Having 2. would be quite powerful already and you could solve a lot of tasks with it. Fancy locking over key ranges/key expressions would also be interesting but that starts to be more like database, not hashmap anymore.
    - deleted 7y ago
      [deleted]
- deleted 7y ago
  [deleted]
- joppy 7y ago
  “Concurrent data structure” is a well-established term (both in common use and in the academic literature) for a data structure which is safe to access from multiple threads of execution.
- chrisseaton 7y ago
  The 'concurrent' terminology is correct in this context - that's the term used in the literature.
- dkersten 7y ago
  I’ve always seen parallelism described as a special case of concurrency where the concurrent processing happens to run physically at the same time, while general case concurrency is about logically running at the same time (whether its actually at the same time or just appears that way). The use of the word concurrent here is consistent with that definition and the literature, where concurrent data structures are data structures designed to for safe concurrent access (whether they are accessed literally at the same time or not).
  - deleted 7y ago
    [deleted]
CameronNemo 7y ago
I am curious how this differs from chashmap: https://gitlab.redox-os.org/redox-os/chashmap https://gitlab.redox-os.org/redox-os/chashmap They provide benchmarks, but I would be more interested to know how the implementation differs.
- Jonhoo 7y ago
  I can't speak to the implementation differences between the two, but I know the author of dashmap is relatively active in responding online, so they may show up shortly to explain. In terms of performance comparisons, we're actually working on building a shared benchmarking tool for all of Rust's concurrent maps that you may find interesting: https://github.com/jonhoo/bustle https://github.com/jonhoo/bustle.
- xacrimon 7y ago
  Hi! I am the author of dashmap. CHashMap is essentially a table behind an rwlock where each slot is also behind its own rwlock. This is great in theory since it allows decently concurrent operations providing they don't need to lock the whole table for resizing. In practice this falls short quickly because of the contention on the outer lock and the large amount of locks and unlocks when traversing the map. dashmap works by splitting into an array of shards, each shard behind its own rwlock. The shard is decided from the keys hash. This will only lock and unlock once for any one shard and allows concurrent table locking operations provided they are on different shards. Further, there is no central rwlock each thread must go thru which improves performance significantly.
aratno 7y ago
If you’re interested in this, you might like this live-coding session implementing Java’s ConcurrentHashMap in Rust: https://youtu.be/yQFWmGaFBjk https://youtu.be/yQFWmGaFBjk
asdf-asdf-asdf 7y ago
11 uses of "unsafe". (this is not a critique of this specific library, it's more a look at the rust ecosystem as a whole) i keep looking at Rust, but at the end it seems it is not a language for me. Rust developers just seem to use more "unsafe" than what i am comfortable with. generally, if there could be a choice between using "unsafe", and taking a 2% performance penalty,i personally would go with the performance-penalty. of course, i can understand others have different priorities. the question is, what are the priorities of the rust ecosystem? i mean, can i find libraries that go with as-safe-as-possible or are most libraries as-fast-as-possible? also, the claim that the rust language is fast and safe becomes harder to accept when the fast libraries use unsafe :) (i do understand code using "unsafe" can be safe if the developer does not make mistakes. the problem is, developers do make mistakes.)
- unlinked_dll 7y ago
  I'll critique the language. Unsafe is a bad name. It doesn't mean "not safe" it means "cannot be verified by the compiler to be memory safe." Some things are inherently unsafe by that definition, including things necessary for software development. It may be better than other names, but frankly - it's too scary. In particular, the implementation of data structures. Raw memory allocation, usage of pointers, low level concurrency primitives - none of that can be done without the programmer manually enforcing invariants. But unsafe isn't wanton abandon. You still have to obey the type system and ownership rules. As for the goal, it depends on the author. Some prioritize one over the other. In general the Rust community these days tries to optimize the balance of safety and speed with as few compromises as possible - which is fundamentally why the language exists.
  - rat9988 7y ago
    unsafe doesn't mean dangerous or hazardous. If we cannot verify safety then it's unsafe. The word's choice seems correct to me. I agree with the rest of your comment though.
    - atoav 7y ago
      Another name that came to my mind was trustme as you as the programmer have to uphold certain garantuees that outside an unsafe block the compiler would enforce.
barnyfried 7y ago
The github readme is content free. I personally have no interest in porting concurrent hashmap in a world where thread based models are going the way of the DODO. The synchronization wars are over and we all lost.
amelius 7y ago
Nice! But a bit disappointing that read speed doesn't increase with number of threads. Curious what the bottleneck is here (first thought is it can't be the memory because CHT shows higher performance for reads in the graph). A comparison with a read-only hashmap would be nice here.
- xacrimon 7y ago
  Hey! I do know what the issue is I think and it is something that will be resolved with v4 releasing later this year. It's an atomic architecture specific thing.
tombert 7y ago
I know this is a bit out of date, but I remember there was a port of the Scala Ctrie data structure to Rust using Hazard pointers. I would be quite interested in seeing how the performance of a snapshotable lock-free structure compares to this https://github.com/ballard26/concurrent-hamt https://github.com/ballard26/concurrent-hamt
- xacrimon 7y ago
  The Contrie library is in the benchmarks and is a port. That said referring the note in the repo the benchmarks arent 100% scientific atm and will be revamped later this year.
phibz 7y ago
I see Jon G referenced in the readme. Is this work based on his livestream series where he ported Java's concurrent Hashmap to Rust? I love his youtube streams. He's extremely patient and thoughtfully thinks through problems in a similar way to me, making it easy to follow. Regardless, kudos and great work. I'm sure I'll find a use for this in some of my tokio projects.
- Jonhoo 7y ago
  Nope, Dashmap is all xacrimon, and came on the scene long before my port. We've been collaborating on writing a shared benchmarking suite over at https://github.com/jonhoo/bustle/ https://github.com/jonhoo/bustle/ though. For the time being, it looks like Dashmap outperforms the port of ConcurrentHashMap (called "flurry"), often by a significant amount. It seems to be mainly due to the garbage collection scheme flurry uses, but we're still digging into it (maybe you want to come help?). In any case, I'm glad you enjoy the videos!
  - phibz 7y ago
    Ha "straight from the horse's mouth." I'd love to help out if I can.
    - Jonhoo 7y ago
      Awesome! Some good places to read up on and join the discussion are https://github.com/jonhoo/bustle/issues/2 https://github.com/jonhoo/bustle/issues/2, https://github.com/jonhoo/flurry/issues/50 https://github.com/jonhoo/flurry/issues/50, and https://github.com/jonhoo/flurry/issues/80 https://github.com/jonhoo/flurry/issues/80. Happy to guide you further there!

132 points by indiv0 7y ago

Some feedback: 1. Mind the difference between concurrency and parallelism. This is around safe parallel access. Concurrent access can happen on one thread without any synchronization. 2. It’s oftentimes an anti pattern to model thread safety around primitive data structures as opposed to higher level concerns. It forces all data that has to be consistent across thread boundaries to be in this one map. When circumstances change, you might want to have some of that data in different data structures and still provide consistent access to them. This change will be hard when you rely on data structure level thread safety.

BubRoss 7y ago
> This is around safe parallel access I'm not sold that this semantic game is usually worth playing, but here it is pointless. Concurrent access on the same threads or different threads isn't going to break. > It forces all data that has to be consistent across thread boundaries to be in this one map Why would it force that? There is no single technique for concurrency or parallelism and that silver bullet line of thinking is a dead end. Concurrent data structures are an important part of the puzzle, especially maps and queues. Fork join, data flow, message passing, copying, swapping buffers, read only data, etc. the list goes on. If it was simple it wouldn't be a problem.
- jupp0r 7y ago
  > Why would it force that? Because you don’t get atomic writes across multiple data structures that are each thread safe unless you perform all writes while holding a mutex. If you do that, you don't need data structures to be thread safe on their own.
  - lcy 7y ago
    > unless you perform all writes while holding a mutex No. Maybe you are not familiar with the concurrency data structures community. Many techniques are invented and used in concurrency data structures, e.g., intrinsic CPU atomic instructions, like CAS, that make the data structures "lock-free". CAS: https://en.wikipedia.org/wiki/Compare-and-swap https://en.wikipedia.org/wiki/Compare-and-swap.
    - ahupp 7y ago
      From the comment: > you don’t get atomic writes across multiple data structures They're saying that lock-free approaches don't help when you have to ensure consistency across multiple datastructures.
  - viraptor 7y ago
    It depends how you structure your data. It's possible to have one "last pointer" log for example which is updated synchronously and points at new values in multiple structures which are updated independently/optimistically. This has different timing/properties than using a single mutex.
  - mirekrusin 7y ago
    You don't even need to say "atomic across multiple data structures", "atomic across multiple keys" in is enough as it's likely next level of atomicity you'll require after atomics over single keys. But if you require that you're in this higher level of transactional semantics that hashmaps don't try to solve (you can still use them as building blocks of course). I think the furthest hashmap api could go is to do: 1. CaS - simple compare-and-swap on single key 2. CaSS - compare-and-swap on one key and set other key + read two keys tuple Having 2. would be quite powerful already and you could solve a lot of tasks with it. Fancy locking over key ranges/key expressions would also be interesting but that starts to be more like database, not hashmap anymore.
  - deleted 7y ago
    [deleted]
deleted 7y ago
[deleted]
joppy 7y ago
“Concurrent data structure” is a well-established term (both in common use and in the academic literature) for a data structure which is safe to access from multiple threads of execution.
chrisseaton 7y ago
The 'concurrent' terminology is correct in this context - that's the term used in the literature.
dkersten 7y ago
I’ve always seen parallelism described as a special case of concurrency where the concurrent processing happens to run physically at the same time, while general case concurrency is about logically running at the same time (whether its actually at the same time or just appears that way). The use of the word concurrent here is consistent with that definition and the literature, where concurrent data structures are data structures designed to for safe concurrent access (whether they are accessed literally at the same time or not).
- deleted 7y ago
  [deleted]

CameronNemo 7y ago

I am curious how this differs from chashmap: https://gitlab.redox-os.org/redox-os/chashmap https://gitlab.redox-os.org/redox-os/chashmap They provide benchmarks, but I would be more interested to know how the implementation differs.

Jonhoo 7y ago
I can't speak to the implementation differences between the two, but I know the author of dashmap is relatively active in responding online, so they may show up shortly to explain. In terms of performance comparisons, we're actually working on building a shared benchmarking tool for all of Rust's concurrent maps that you may find interesting: https://github.com/jonhoo/bustle https://github.com/jonhoo/bustle.
xacrimon 7y ago
Hi! I am the author of dashmap. CHashMap is essentially a table behind an rwlock where each slot is also behind its own rwlock. This is great in theory since it allows decently concurrent operations providing they don't need to lock the whole table for resizing. In practice this falls short quickly because of the contention on the outer lock and the large amount of locks and unlocks when traversing the map. dashmap works by splitting into an array of shards, each shard behind its own rwlock. The shard is decided from the keys hash. This will only lock and unlock once for any one shard and allows concurrent table locking operations provided they are on different shards. Further, there is no central rwlock each thread must go thru which improves performance significantly.

aratno 7y ago

If you’re interested in this, you might like this live-coding session implementing Java’s ConcurrentHashMap in Rust: https://youtu.be/yQFWmGaFBjk https://youtu.be/yQFWmGaFBjk

asdf-asdf-asdf 7y ago

11 uses of "unsafe". (this is not a critique of this specific library, it's more a look at the rust ecosystem as a whole) i keep looking at Rust, but at the end it seems it is not a language for me. Rust developers just seem to use more "unsafe" than what i am comfortable with. generally, if there could be a choice between using "unsafe", and taking a 2% performance penalty,i personally would go with the performance-penalty. of course, i can understand others have different priorities. the question is, what are the priorities of the rust ecosystem? i mean, can i find libraries that go with as-safe-as-possible or are most libraries as-fast-as-possible? also, the claim that the rust language is fast and safe becomes harder to accept when the fast libraries use unsafe :) (i do understand code using "unsafe" can be safe if the developer does not make mistakes. the problem is, developers do make mistakes.)

unlinked_dll 7y ago
I'll critique the language. Unsafe is a bad name. It doesn't mean "not safe" it means "cannot be verified by the compiler to be memory safe." Some things are inherently unsafe by that definition, including things necessary for software development. It may be better than other names, but frankly - it's too scary. In particular, the implementation of data structures. Raw memory allocation, usage of pointers, low level concurrency primitives - none of that can be done without the programmer manually enforcing invariants. But unsafe isn't wanton abandon. You still have to obey the type system and ownership rules. As for the goal, it depends on the author. Some prioritize one over the other. In general the Rust community these days tries to optimize the balance of safety and speed with as few compromises as possible - which is fundamentally why the language exists.
- rat9988 7y ago
  unsafe doesn't mean dangerous or hazardous. If we cannot verify safety then it's unsafe. The word's choice seems correct to me. I agree with the rest of your comment though.
  - atoav 7y ago
    Another name that came to my mind was trustme as you as the programmer have to uphold certain garantuees that outside an unsafe block the compiler would enforce.

barnyfried 7y ago

The github readme is content free. I personally have no interest in porting concurrent hashmap in a world where thread based models are going the way of the DODO. The synchronization wars are over and we all lost.

amelius 7y ago

Nice! But a bit disappointing that read speed doesn't increase with number of threads. Curious what the bottleneck is here (first thought is it can't be the memory because CHT shows higher performance for reads in the graph). A comparison with a read-only hashmap would be nice here.

xacrimon 7y ago
Hey! I do know what the issue is I think and it is something that will be resolved with v4 releasing later this year. It's an atomic architecture specific thing.

tombert 7y ago

I know this is a bit out of date, but I remember there was a port of the Scala Ctrie data structure to Rust using Hazard pointers. I would be quite interested in seeing how the performance of a snapshotable lock-free structure compares to this https://github.com/ballard26/concurrent-hamt https://github.com/ballard26/concurrent-hamt

xacrimon 7y ago
The Contrie library is in the benchmarks and is a port. That said referring the note in the repo the benchmarks arent 100% scientific atm and will be revamped later this year.

phibz 7y ago

I see Jon G referenced in the readme. Is this work based on his livestream series where he ported Java's concurrent Hashmap to Rust? I love his youtube streams. He's extremely patient and thoughtfully thinks through problems in a similar way to me, making it easy to follow. Regardless, kudos and great work. I'm sure I'll find a use for this in some of my tokio projects.

Jonhoo 7y ago
Nope, Dashmap is all xacrimon, and came on the scene long before my port. We've been collaborating on writing a shared benchmarking suite over at https://github.com/jonhoo/bustle/ https://github.com/jonhoo/bustle/ though. For the time being, it looks like Dashmap outperforms the port of ConcurrentHashMap (called "flurry"), often by a significant amount. It seems to be mainly due to the garbage collection scheme flurry uses, but we're still digging into it (maybe you want to come help?). In any case, I'm glad you enjoy the videos!
- phibz 7y ago
  Ha "straight from the horse's mouth." I'd love to help out if I can.
  - Jonhoo 7y ago
    Awesome! Some good places to read up on and join the discussion are https://github.com/jonhoo/bustle/issues/2 https://github.com/jonhoo/bustle/issues/2, https://github.com/jonhoo/flurry/issues/50 https://github.com/jonhoo/flurry/issues/50, and https://github.com/jonhoo/flurry/issues/80 https://github.com/jonhoo/flurry/issues/80. Happy to guide you further there!