Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date: Mon, 18 Aug 2014 00:04:37 -0400
From: Rich Felker <>
Subject: Re: New private cond var design

On Fri, Aug 15, 2014 at 03:35:36PM -0400, Rich Felker wrote:
> Jens' proposed solution tracked "instances" via dynamically allocated,
> reference-counted objects. I finally think I have a solution which
> avoids dynamic allocation: representing the "instance" as a
> doubly-linked-list of automatic objects on the stack of each waiter.
> [...]
> Option 2: Each waiter can wait on a separate futex on its own stack,
> so that sequence numbers are totally unneeded. This eliminates all
> spurious wakes; signal can precisely control exactly which waiter
> wakes (e.g. choosing the oldest), thereby waking only one waiter.
> Broadcast then becomes much more expensive: the broadcasting thread
> has to make one requeue syscall per waiter. But this still might be a
> good design.

I ended up implementing option 2. It doesn't avoid O(n) operations in
broadcast like Jens seems to have had in mind (although it only makes
O(1) syscalls); avoiding the need for waiters to access the cv object
after waiting (which would require round-trip synchronization with all
waiters at broadcast time) necessitates writing to each waiter node
object. I have some improvements in mind that might further reduce the
time spent in broadcast and make the wake order more predictable (and
reduce code size) to look into soon, though.

So far I'm really happy with the performance -- it's much better than
before, sometimes even 2-3x. The benchmark by Timo Teräs that showed
the benefit of private futexes particularly benefits. My cvb2.c test
benefits much less: roughly 15% improvement for private mutex and ~33%
improvement with process-shared mutex.

I'd still like to look into whether it's possible to improve
process-shared cond vars (even at the expense of some performance) to
get rid of the synchronization in the destroy function (and thereby
make them unmapping-safe too).


Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.