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

21–30 of 31 posts

Re: New Concurrent Hash Maps for C++

#21

Post by pjmlp »

daemin wrote: post #17
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.

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.

Re: New Concurrent Hash Maps for C++

#23

Post by vardump »

exDM69 wrote: post #18
vardump wrote: post #13

Earlier quoted context omitted.

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

> ... Instrumented code or sampling profilers?

A sampling profiler would be helpful. Although most hash map related samples would likely fall on atomic ops it presumably uses for synchronization. On the other hand, you'd know whether you need to optimize this in the first place.

Instrumented profiler would yield garbage data for a lot of reasons, I wouldn't use that, except maybe over a large group of hash map operations.

> ... I'd first reach for the CPU performance counters

I count CPU performance counters as profiling.

Re: New Concurrent Hash Maps for C++

#24

Post by vardump »

gpderetta wrote: post #19
vardump wrote: post #10

Earlier quoted context omitted.

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 un contended 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();
  }

Re: New Concurrent Hash Maps for C++

#25

Post by preshing »

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…

I think you might be right. Maybe I should edit the post and not call it "more scalable", since I only have six cores to test on. But if it does top out at a higher core count, there are several ways it could be optimized.

Either way, Junction is BSD-licensed while TBB is GPL/$, so I hope it'll find a use somewhere.

Re: New Concurrent Hash Maps for C++

#26

Post by preshing »

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?

Threads are not required to call QSBR::update at the same time. They can call it anytime, but they do need to call it.

Re: New Concurrent Hash Maps for C++

#27

Post by thrownaway2424 »

preshing wrote: post #26
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?

Threads are not required to call QSBR::update at the same time. They can call it anytime, but they do need to call it.

OK. That's not really clear from the article. It makes the strange statement that the update function must be called "at a moment when each thread is quiescent – that is, not doing anything else." I don't believe there is any way in C++ to have a thread be doing more than one thing at a time, so if a C++ thread calls update it must by inspection be not doing anything else. Maybe you could restate this. I assumed since this had been stated this way it must really mean that all threads must have reached this state, and one thread must call update.

Re: New Concurrent Hash Maps for C++

#28

Post by preshing »

thrownaway2424 wrote: post #27
preshing wrote: post #26

Earlier quoted context omitted.

Threads are not required to call QSBR::update at the same time. They can call it anytime, but they do need to call it.

OK. That's not really clear from the article. It makes the strange statement that the update function must be called "at a moment when each thread is quiescent – that is, not doing anything else." I don't believe there is any way in C++ to have a thread be doing more than one thing at a time, so if a C++ thread calls update it must by inspection be not doing anything else. Maybe you could restate this. I assumed sinc…

OK, I tweaked it a little bit.

Re: New Concurrent Hash Maps for C++

#29

Post by gpderetta »

vardump wrote: post #24
gpderetta wrote: post #19

Earlier quoted context omitted.

good analysis, but you probably meant "ideally optimized un contended 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?

Re: New Concurrent Hash Maps for C++

#30

Post by vardump »

gpderetta wrote: post #29
vardump wrote: post #24

Earlier quoted context omitted.

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.

Post reply on HN