[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sun, 18 Jun 2017 11:01:32 -0400
From: Rich Felker <dalias@...c.org>
To: musl@...ts.openwall.com
Subject: Re: [PATCH] a new lock algorithm with lock value and CS
counts in the same atomic int
On Fri, Jun 16, 2017 at 09:11:35AM +0200, Jens Gustedt wrote:
> A variant of this new lock algorithm has been presented at SAC'16, see
> https://hal.inria.fr/hal-01304108. A full version of that paper is
> available at https://hal.inria.fr/hal-01236734.
>
> The main motivation of this is to improve on the safety of the basic lock
> implementation in musl. This is achieved by squeezing lock value and
> "waiter" count into a single int. Thereby an unlock operation does
> exactly one memory transfer (a_fetch_add) and never touches the value
> again, but still detects if a waiter has to be woken up.
Thanks! In the process of reviewing.
> Another effect could be improved performance, but don't take this too
> seriously, these lock/unlock functions are probably never used in
> performance critical parts of libc.
An equivalent inlined/open-coded version of the lock is used in
malloc, which is the only place I see where it's performance-critical.
If it really does perform significantly better it would make sense to
see if we can get the benefit in malloc too; that may be harder
because it would sacrifice the inlining unless we wanted to try to get
the larger new code inlined (which the compiler may not want to do, or
which may affect other levels of inlining in the same file).
> Depending on the architecture, the performance of the previous lock
> strategy was not always so great under no or medium congestion. Now, in
> case of no congestion, there are exactly two memory operations, one to
> lock an one to unlock. So if we would start to use this same new strategy
> also for user locks such as mutexes, semaphores or the locks used for
> lockfull atomics, we might see a performance improvement.
It definitely can't be used for mutexes that have to record an owner
(recursive, error-checking, and/or robust), or for semaphores, unless
we wanted to depend on double-word atomics. There's just too much
state in all these cases to fit in 32 bits. Normal mutexes could do it
though. Another case that would be very nice to optimize, but where I
don't see a way, is stdio FILE locks. They're recursive and thus need
to record an owner. The current implementation works more like an
errorchecking mutex abused as a recursive one (see also: an old SO
question on that topic), having the caller be responsible for knowing
whether it needs to unlock from whether it was already owned by the
calling thread at lock time.
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.
