3 ms·

> 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 ho

by 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]

by jupp0r 7y ago

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]