How much overhead does std::mutex add in the single-threaded case for std::map? Because its kinda curious that this new map is more than twice as fast as std::map even on single thread.
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.
edit: spelling
(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();
}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.
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.
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.
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.
On programming languages with ISO/ANSI specifications, relying on implementation details is a trap for writing portable code.