5 ms·

The biggest bummer of lock-free data structures from my perspective is the reclamation problem. Hazard pointers solve the problem but they are API-intrusive. N

The 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 ago
As 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.)
throwawayaway 12y ago
maybe i'm a clown(i certainly haven't written any libraries). but with pthreads for example you you put the new()and free() into a wrapper around the function you want to call? void wrapper() { new(); job(); free(); } pthread_t thread; int yes = 0; pthread_create(&thread, NULL, wrapper, (void *) &yes);
- haberman 12y ago
  That works if you are the application, or a framework that is in control of all thread creation. If you are just trying to be a thread-safe library though, you aren't at liberty to do that. For example, say someone wrote a thread-safe stack, like the article author. As the user of that thread-safe, lock-free stack, you don't want to put it in charge of all your threading, it's just one little library you're using.

swift 12y ago

As 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.)

throwawayaway 12y ago

maybe i'm a clown(i certainly haven't written any libraries). but with pthreads for example you you put the new()and free() into a wrapper around the function you want to call? void wrapper() { new(); job(); free(); } pthread_t thread; int yes = 0; pthread_create(&thread, NULL, wrapper, (void *) &yes);

haberman 12y ago
That works if you are the application, or a framework that is in control of all thread creation. If you are just trying to be a thread-safe library though, you aren't at liberty to do that. For example, say someone wrote a thread-safe stack, like the article author. As the user of that thread-safe, lock-free stack, you don't want to put it in charge of all your threading, it's just one little library you're using.