Re: [RFC] Lock elision implementation guidelines

[Torvald Riegel <triegel at redhat dot com>]

On Thu, 2013-02-28 at 14:21 +0100, OndÅej BÃlka wrote:
> On Wed, Feb 27, 2013 at 03:18:30PM +0100, Torvald Riegel wrote:
> > On Fri, 2013-02-22 at 15:02 +0100, OndÅej BÃlka wrote:
> > > 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: 
> > > > > > 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.
> > 
> > I suppose you mean the atomic operations provided by current hardware.
> > But that has its limits, obviously: Either because those are
> > single-location, so you can't use them widely,
> 
> Single location is wide enough to cover most use cases where it matters.

Would be interested to hear where you got that data from...  I'm sure
this statement is based on data, isn't it?

> It is not that hard to fiddle with data layout until changes are done on
> single object. Then you need only to atomicaly change single pointer. 

There's a cost to indirection, both in terms of engineering costs and
performance costs.
And just have a look at some concurrent data structures and think about
whether those would have been publishable results if it were as easy as
adding indirection...

> > > Optimized programs would benefit 
> > > more from better optimized compare and swap.
> > 
> > I don't think current CAS is a problem; the best-case latency is already
> > pretty low compared to past implementations (on x86 at least).  But the
> > hardware implementation can't avoid the cache miss costs, so it's up to
> > programmers to synchronize in an efficient way.
> > 
> Of course hardware can avoid cache miss cost.

The point is that whenever you communicate with another piece of
hardware that is physically at a distance, you will have communication
costs.  Cache miss costs are just that.