5 ms·
C11 Lock-free Stack
- justincormack 12y agoThere is a C11 threads implementation, in Musl libc[1]. It is not committed yet, but looks like it will be in the next release - there are patches on the mailing list. [1] http://www.musl-libc.org/ http://www.musl-libc.org/
- voidlogic 12y agoWhile it is true that lock free data structures provide much better throughput in highly contended environments people forget that in the many reads/few writers situations they often are slower the Read/Write mutexes. Maybe some of the upcoming transactional memory instructions will improve this, but for the time being, and probably always- benchmark your code!
- readerrrr 12y agoIn that case you can add signals and send threads to sleep if there is not enough elements on the stack, and wake them up if the stack starts growing faster.
- jacquesm 12y agoBut you're still burning more cycles, this isn't just about spinning read threads without input.
- davidtgoldblatt 12y agoEven if you're read mostly, R/W locks often do a very bad job. If your critical sections are short (say, in a hash map, or fine-grained locks in a linked list or tree, or even a whole structure lock on a small tree or array), then contention on the R/W lock internals will be a bottleneck, since readers still have to update the reader count, so the count field is a shared location all the readers are doing writes to. You could have this by e.g. having a "fat" R/W lock that's made up of num_cpus primitive R/W locks (and each reader only reader-locks the lock associated with its CPU), but none of the common R/W locks actually do this (and it's not always even the right call if you're worried about node size). Then again, lots of lock-free structures often try to handle memory management using reference counts or hazard pointers, which have their own performance issues.
- haberman 12y agoThe biggest bummer of lock-free data structures from my perspective is the reclamation problem. Hazard pointers solve the problem but they are API-intrusive. Notably, hazard pointers require thread-local state, as well as some global structure that contains the entire list of threads. That means you have to register/deregister threads when when they are created/destroyed. So essentially your API needs to look like this: mylib_perthread_t *perthread = mythread_perthread_new(); // Later: mylib_lockfreestack_push(obj, perthread, val); // When the thread shuts down: mylib_perthread_free(perthread); But this is API-intrusive: 1. each thread must call mylib_perthread_new() 2. the thread needs thread-local storage for "perthread" 3. the thread must call mylib_perthread_free() before exiting C11 and C++11 have thread-local storage, which solves (2), but (1) and (3) are still API-intrusive. Having to explicitly initialize/uninitialize a library per-thread resource is very uncommon. Worse, it doesn't compose well. Until this problem has a convenient and idiomatic solution, it's hard to imagine hazard pointers being very useful in idiomatic C and C++ APIs. Without hazard pointers, your only real options are: 1. use a fixed-size structure (specify up front its max size) 2. don't free any nodes until the structure itself is deleted The first is what this article does. The second is what boost.lockfree does. But without hazard pointers, you also need to solve the ABA problem, which requires either DCAS (double compare-and-swap), or a fixed-size structure that you index by offset instead of by pointer. It just occurred to me that a flow-chart of all these options and variations could be interesting.
- swift 12y agoAs someone who spent some significant time in a previous life working on a parallel programming framework that involved lock-free data structures, you've really hit the nail on the head here. The whole experience totally changed my views on garbage collection, because without GC problems like this can be so painful to solve. The only thing I really have to add is that, while we had to do pretty much what you describe here, I didn't think it felt that bad for the end user in the context of a framework built on top of C++11's features. A combination of RAII and lambdas can allow you to solve (1) and (3) pretty elegantly. (As you say, though, it's not very cleanly composable. This is one of many reasons why we were creating a framework in the first place and not a set of independent libraries.)
- verroq 12y ago>C11 hasn't received anywhere near the same amount of fanfare as C++11 Well did C11 add lambdas? Didn't think so.
- bithush 12y agoIf you are on Windows I highly recommend Pelles C http://www.smorgasbordet.com/pellesc/ http://www.smorgasbordet.com/pellesc/