Friday, February 17, 2017

Two posters at PPoPP 2016

We got two posters accepted at PPoPP 2016, yupiii!!!

One was for "Poor Man's URCU" which we talked about on a post long ago.
It's a very simple way to implement a Userspace RCU using reader-writer locks, in a lock-free way. Yes, you can use the trylock() API in reader-writer locks to build lock-free constructs, with URCU being an example.

The other one was the Turn Queue, the world's fastest (so far) wait-free linearizable MPMC queue with wait-free memory reclamation, which we talked about on a post a couple months ago.
The full paper is called "A Wait-Free Queue with Wait-Free Memory Reclamation" and you can get a draft here if you want to.

1 comment:

  1. Hello. I'm facing a challenge with a queue-like structure you might have tips on for me. The situation is as follows:

    Thread 1 offers items into a bounded "queue". Thread 2 traverses the queue from time to time, occasionally removing items at non-deterministic places (no need for FIFO actually). Thread 3 may come in and remove all items from the queue and signal Thread 1 to stop trying to offer any more items.

    The extended problem is when the "queue" is unbounded and may need to grow.

    My current solution is in the form of a copy-on-write array with a special terminal indicator array instance. If removals were not part of the requirement, this could be just the ordinary and cheap single-producer single-consumer bounded queue.