Re: [RFC] Lock elision implementation guidelines

[OndÅej BÃlka <neleai at seznam dot cz>]

On Wed, Feb 20, 2013 at 09:42:56PM +0100, Torvald Riegel wrote:
> 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.
> > >
This is not quite true. 
For libraries often even for single thread apps significant time is spend 
on locking when workload consist of many small updates.
Take malloc for example.

Of course most of time when they care about performance they simply do
no locking and say it is user responsibility.

This overhead can be perhaps decreased by teaching gcc to eliminate
unlock(x) lock(x) pairs. I do not know how to do in way to prevent
starvation yet.
 
> > > 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.
> 
When you optimize programs first thing you look for is what locks can be
eliminated by using atomic primitives. Optimized programs would benefit 
more from better optimized compare and swap.