Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

New Concurrent Hash Maps for C++

preshing.com

Post reply on HN
Print view View original

11–20 of 31 posts

Re: New Concurrent Hash Maps for C++

#11

Post by vardump »

eps wrote: post #9

Uhm... The absolute Y-position of the curve on the graph is secondary to its shape. Also, the scalability discussion is largely pointless if the sample set covers only 6 CPUs. Intel TBB scales proportionally, which is precisely what you'd want here. Junction starts to flatten out on 6th CPU, which implies that it has fundamental design issues that crop up at higher CPU counts. Chances are that its performance not onl…

Based on the information available, you might be right and you might be wrong.

Before one can say anything either way, one needs to profile. Assumptions rarely work when it comes to extracting high runtime performance.

So unless you did profile, your comment didn't really add anything.

Re: New Concurrent Hash Maps for C++

#12

Post by vog »

vardump wrote: post #11
eps wrote: post #9

Uhm... The absolute Y-position of the curve on the graph is secondary to its shape. Also, the scalability discussion is largely pointless if the sample set covers only 6 CPUs. Intel TBB scales proportionally, which is precisely what you'd want here. Junction starts to flatten out on 6th CPU, which implies that it has fundamental design issues that crop up at higher CPU counts. Chances are that its performance not onl…

Based on the information available, you might be right and you might be wrong. Before one can say anything either way, one needs to profile. Assumptions rarely work when it comes to extracting high runtime performance. So unless you did profile, your comment didn't really add anything.

> So unless you did profile, your comment didn't really add anything.

The previous comment explained why and how the author's analysis is flawed. Then it goes over top by speculating exactly into the opposite direction. But that doesn't reduce the quality of the first part of the comment. That part was still valuable to me.

Re: New Concurrent Hash Maps for C++

#13

Post by vardump »

vog wrote: post #12
vardump wrote: post #11

Earlier quoted context omitted.

Based on the information available, you might be right and you might be wrong. Before one can say anything either way, one needs to profile. Assumptions rarely work when it comes to extracting high runtime performance. So unless you did profile, your comment didn't really add anything.

> So unless you did profile, your comment didn't really add anything. The previous comment explained why and how the author's analysis is flawed. Then it goes over top by speculating exactly into the opposite direction. But that doesn't reduce the quality of the first part of the comment. That part was still valuable to me.

Ok, you have a point.

Original author's analysis is flawed, it doesn't extend to multi-socket systems.

What we don't know is how thing scales beyond a single socket. The graph is not going to tell us anything about that. Profiling will.

Experience has shown to me assumptions are bad.

So now I don't assume a certain call will succeed or even work the way I think it does. Instead I check return value of every call and test it against my assumptions.

I never assume much about performance either. I might occasionally use microbenchmarks as a hint. But the main mode of operation is measuring as big of a piece of functionality as possible. Many different size, but realistic, workloads. Preferably on multiple different systems as well.

If performance is the goal, I'd advocate one trying out different concurrent hash map implementations in the system one is building.

Never assume.

Re: New Concurrent Hash Maps for C++

#14

Post by pjmlp »

berkut wrote: post #4
zokier wrote: post #3

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.

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

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.

Re: New Concurrent Hash Maps for C++

#15

Post by tlipcon »

lsr0 wrote: post #7
thrownaway2424 wrote: post #2

Interesting and impressive performance. The requirement to periodically halt every thread seemed like a bit of a downer though. Am I reading that wrong?

That seems to be the case, I do wish they'd made this requirement clear up front. There is no getting around sychronised quiescence being a blocking event, but in this case they essentially hope that either 1) you're already using a kind of scatter gather thread model like the mentioned game example - which implies an iterative discrete world, or 2) the set of threads (or tasks) interacting with the collection is sim…

Typically QSBR algorithms don't require blocking the world, or even blocking any single thread. They just require each thread to periodically check in and run a bounded amount of code which amounts to "hey, I'm not currently looking at the map".

Some other background collector thread (which is going to actually delete removed objects) just has to wait until it sees every mutator thread cross a safepoint, at which point it knows that none of those threads could be hanging onto references that have been unlinked from the data structure.

I'd recommend reading some surveys of RCU and SMR algorithms if this stuff is interesting to you.

Re: New Concurrent Hash Maps for C++

#16

Post by skystrife »

pjmlp wrote: post #14
berkut wrote: post #4

Earlier quoted context omitted.

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

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.

Re: New Concurrent Hash Maps for C++

#17

Post by daemin »

pjmlp wrote: post #14
berkut wrote: post #4

Earlier quoted context omitted.

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

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.

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.

Re: New Concurrent Hash Maps for C++

#18

Post by exDM69 »

vardump wrote: post #13
vog wrote: post #12

Earlier quoted context omitted.

> So unless you did profile, your comment didn't really add anything. The previous comment explained why and how the author's analysis is flawed. Then it goes over top by speculating exactly into the opposite direction. But that doesn't reduce the quality of the first part of the comment. That part was still valuable to me.

Ok, you have a point. Original author's analysis is flawed, it doesn't extend to multi-socket systems. What we don't know is how thing scales beyond a single socket. The graph is not going to tell us anything about that. Profiling will. Experience has shown to me assumptions are bad. So now I don't assume a certain call will succeed or even work the way I think it does. Instead I check return value of every call and…

> The graph is not going to tell us anything about that. Profiling will.

What kind of profiling would you employ for a concurrent data structure like the hash map here? Instrumented code or sampling profilers?

I'm afraid both kinds of profiling would yield quite meaningless information, because the individual operations are quite fast and the runtime may vary depending on e.g. cache utilization and contention. Profiling is good for bigger applications but it's not super useful for "primitive" operations like hash map inserts.

If I were to optimize something like this, I'd first reach for the CPU performance counters trying to understand what aspect is the bottle neck.

Re: New Concurrent Hash Maps for C++

#19

Post by gpderetta »

vardump wrote: post #10
zokier wrote: post #3

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.

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 gen…

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

edit: spelling

Re: New Concurrent Hash Maps for C++

#20

Post by pjmlp »

skystrife wrote: post #16
pjmlp wrote: post #14

Earlier quoted context omitted.

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.

Post reply on HN