“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.

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).

The 'concurrent' terminology is correct in this context - that's the term used in the literature.

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

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

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.

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.

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

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.