C11 Lock-free Stack | Hacker News Reader

C11 Lock-free Stack

nullprogram.com

80 pointssigna1111 comments

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.

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

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);

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.

There 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/

While 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!

In 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.

But you're still burning more cycles, this isn't just about spinning read threads without input.

Even 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.

If you are on Windows I highly recommend Pelles C http://www.smorgasbordet.com/pellesc/

>C11 hasn't received anywhere near the same amount of fanfare as C++11

Well did C11 add lambdas? Didn't think so.

Reply on news.ycombinator.com