Re: [RFC] Lock elision implementation guidelines

[Torvald Riegel <triegel at redhat dot com>]

On Wed, 2013-02-20 at 11:58 -0500, Rich Felker wrote:
> On Wed, Feb 20, 2013 at 12:21:35PM +0100, Torvald Riegel wrote:
> > On Tue, 2013-02-19 at 20:23 -0500, Rich Felker wrote:
> > > On Tue, Feb 19, 2013 at 09:52:28PM +0100, Torvald Riegel wrote:
> > > > > > > No. You cannot ignore any requirements. That's why they're called
> > > > > > > requirements and not recommendations.
> > > > > > 
> > > > > > Usually, I wouldn't reconsider any requirements.  But this case is
> > > > > > special enough to warrant thinking about this.
> > > > > 
> > > > > Everybody's pet feature is "special enough" to warrant breaking the
> > > > > requirements -- to them. The problem is that this doesn't scale. You
> > > > > end up breaking all the requirements because everybody wants to break
> > > > > a different one.
> > > > 
> > > > Just a quick comment because this seems to be off-topic: The
> > > > requirements themselves don't come out of thin air either;  Some
> > > > features are considered to be more important than others when deciding
> > > > on the requirements too.  So there is a way to scale such decisions, and
> > > > lock elision has enough potential to be quite a bit more than a pet
> > > > feature.
> > > 
> > > At present, this feature is only interesting to less than 1% of glibc
> > > users. I doubt that will increase significantly even if the hardware
> > > becomes widespread, simply because locking already costs virtually
> > > nothing for most normal usage cases.
> > 
> > While it's true that the lock acquisition latency for locks that are
> > already in the cache has been substantially decreased in the past, once
> > you use the same locks concurrently with other threads, you get cache
> > misses, and these are costly.  Typically, when you use locks, you use
> > them because you need to synchronize and there can be concurrent actions
> > by other threads.  You can hope that those other threads are not too far
> > away from yourself in terms of the memory hierarchy (i.e., hope for
> > locality), but that's not simple.  But we won't get less concurrency.
> 
> First of all, 99% of users of glibc are using it for LAMP stacks or
> desktop-oriented Linux distributions. High-end computational
> parallelism is in itself a 1% niche. This is the basis for my claim
> that lock elision is a "pet feature".

We'll likely get even more parallelism in hardware in the future, so
likely also more parallelism in programs, and this usually results in
more synchronization too.  In fact, the "high-end computational
parallelism" programs (I assume this means well-optimized programs) will
likely often have less synchronization than the average parallel or
concurrent program, I believe.  So lock elision is the more important
the less optimized the synchronization in the program is, I think.

> It doesn't mean it's unimportant
> to the people who care about it, but it does mean you can't attempt to
> justify breaking other requirements for its sake. There are other
> application which are much less niche (think graphics, gaming, etc.)
> that could benefit from breaking IEEE requirements in the math
> library, but glibc is moving in the direction of better conformance,
> not more non-conforming performance hacks, because it's the right
> thing to do.

Whether lock elision is a "pet feature" or not is orthogonal to which
semantics we want it to provide, and I've been arguing that it's not a
pet feature.

> > > > However, is a deadlocked thread actually *required* by POSIX to make
> > > > progress handling signals?
> > > 
> > > This is a good question -- I'll have to research it. I believe the
> > > general forward progress requirements cover this case: for example if
> > > a signal has been sent to thread A, and thread B is waiting for an
> > > event that would happen from the signal handler running in thread A,
> > > and no other threads exist, then I believe it's required that the
> > > signal handler run. However I can look into this in more detail.
> > 
> > Thanks.
> > 
> > Both C11 and C++11 give very limited progress guarantees, so I wouldn't
> > be surprised if POSIX doesn't guarantee much either.
> 
> POSIX makes some forward progress guarantees, such as XSH 2.9.3:
> 
>     A thread that has blocked shall not prevent any unblocked thread
>     that is eligible to use the same processing resources from
>     eventually making forward progress in its execution. Eligibility
>     for processing resources is determined by the scheduling policy.
> 
> The question here is just whether it makes a guarantee of signal
> delivery at the time in question.

And also delivering the signal "via" this OS thread (the above is about
one block threads vs. other threads AFAIU).


Torvald