Overhead of std::mutex depends a lot on contention patterns. Assuming one x86 CPU socket, usually you can take + release an ideally optimized contended mutex about 10M-25M times per second, if that's all you do, 100% CPU usage on all cores. That's simply limited by how many times you can run contested LOCK XADD (x86 atomic fetch-and-add) / LOCK CMPXCHG* (x86 atomic compare-and-swap) instructions per second.

Mutex generates a lot of cache coherency traffic and saturates the CPU internal ring bus. NUMA case it'll of course quickly saturate lower bandwidth CPU external QPI link(s).

Contested mutexes perform a lot better on a typical laptop than on a server.

good analysis, but you probably meant "ideally optimized uncontended mutex".

edit: spelling

To be exact, I meant code that just repeatedly locks and releases same mutex on all CPU cores.

(Counting is a bit tricky, atomic counter on each lock would invalidate the results. Best to only update the counter, say, on every 1000th result or to use some parallel counting library.)

  for(;;) { 
    mutex.lock(); 
    mutex.unlock();
  }

OK, now I see what you are saying. It would certainly be true for a spin lock, but it seems to me that, for std::mutex, the kernel transition required to arbitrate contention would dominate even on the coherency traffic, right?

Yeah, I was talking about spinlocks.

You're right that context switches would dominate std::mutex. For some reason I was thinking std::mutex uses spinlocks, even though I knew better. Too much kernel side coding lately - context switches are often not possible there, so mutexes are often not possible as potential synchronization mechanisms.

You might still be right. The implementation of std::mutex is unspecified, and real world implementations will probably spin a bit before going into the kernel, so for your test case with a tiny critical section it might behave like a spinlock.

std::map is a RB tree, not a hash map.

I'd be interested in the answer for std::unordered_map, then.

ANSI C++, section 23.4.2 and 23.4.4, doesn't specify the implementation only the complexity requirements.

Any C++ implementation is free to choose their std::map implementation as long as it meets the requirements, it doesn't say anywhere that a RB Tree is required.

libstdc++, libc++, and MSVC's STL all implement it as a red-black tree.

Even if it's not required to be a red-black tree, it is de facto a red-black tree on every major compiler.

Moreover, this doesn't really change the parent's point. It must be some sort of ordered associative container, meaning that it's not going to have the performance characteristics of a hash table.

Clang, gcc and MSVC are hardly "every major compiler", as there are many others to choose from specially in the embedded systems, real time OSes, classical commercial UNIX and mainframes.

We don't have always the luxury of choosing which compiler to use.

Relying on implementation details of the compiler or provided library is the first trap to writing portable code across OSes and compiler vendors.

I recall hearing/reading that there are sections of the standard which mostly suggest that a tree is the only valid map data structure. I think something to do with iterators and was mentioned in a CppCon talk or blog article. I will try to dig this up.

Sure, it might be that only a tree based structure is able to fulfill the required complexity, but it doesn't need to be a RB one necessarly.

On programming languages with ISO/ANSI specifications, relying on implementation details is a trap for writing portable code.