Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sat, 29 Aug 2015 13:16:12 -0400
From: Rich Felker <dalias@...c.org>
To: musl@...ts.openwall.com
Subject: Re: [PATCH 1/2] let them spin

On Sat, Aug 29, 2015 at 10:50:44AM +0200, Jens Gustedt wrote:
> Remove a test in __wait that looked if other threads already attempted to
> go to sleep in futex_wait.
> 
> This has no impact on the fast path. But other than one might think at a
> first glance, this slows down if there is congestion.
> 
> Applying this patch shows no difference in behavior in a mono-core
> setting, so it seems that this shortcut is just superfluous.

The purpose of this code is is twofold: improving fairness of the lock
and avoiding burning cpu time that's _known_ to be a waste.

If you spin on a lock that already has waiters, the thread that spins
has a much better chance to get the lock than any of the existing
waiters which are in futex_wait. Assuming sufficiently many cores that
all threads that are not sleeping don't get preempted, the spinning
thread is basically guaranteed to get the lock unless it spins so long
to make it futex_wait. This is simply because returning from
futex_wake (which all the other waiters have to do) takes a lot more
time than one spin. I suspect there are common loads under which many
of the waiters will NEVER get the lock.

The other issue is simply wasted cpu time. Unlike in the no-waiters
case where spinning _can_ save a lot of cpu time (no futex_wait or
futex_wake syscall), spinning in the with-waiters case always wastes
cpu time. If the spinning thread gets the lock when the old owner
unlocks it, the old owner has already determined that it has to send a
futex_wake. So now you have (1) the wasted futex_wake syscall in the
old owner thread and (2) a "spurious" wake in one of the waiters,
which wakes up only to find that the lock was already stolen, and
therefore has to call futex_wait again and start the whole process
over.

Rich

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.