[RFC] Lock elision implementation guidelines

[Dominik Vogt]

On Mon, Jun 10, 2013 at 08:49:19PM +0200, Torvald Riegel wrote:
> On Mon, 2013-06-10 at 13:43 +0200, Dominik Vogt wrote:
> > thread 1:
> > ---------
> > 
> > for (...)
> >   lock A
> >   lock B
> >   increment a counter 1
> >   unlock A
> >   handle big workload
> >   increment counter 3
> >   unlock B
> > 
> > thread 2:
> > ---------
> > 
> > forever
> >   lock A
> >   increment a counter 2
> >   lock B
> 
> unlock A, I assume

Of course.

> > In a real life test, the runtime of the program with elision is
> > almost identical to the runtime without elision and just locks.
> 
> So, "big workload" executes for a long time (i.e., significantly longer
> than one would need for trying to acquire a lock for a couple of times)?

The test was made with a loop that increments a volatile global
variable 100,000 times as a workload.  (If the workload becomes
too big, the abort ratio will increase and dilute the result.)

> > But in the same time I get 1247 million increments of counter 2
> > without elision but just 660 million increments _with_ elision.
> 
> It's surprising that the difference is so large.  If "big workload" runs
> for most of the time in thread 1, A should be free most of the time.
> Does anything else in "big workload" conflict with what thread 2 does?

Some more testing:

1. With all globals in the program aligned to cache lines, the
   result is roughly the same.  So there were no hidden aborts due
   to variables stored in the same cache lines.

2. With a modified thread 1:

   for (...)
     lock A
     increment counter 1
     unlock A
     lock B
     handle big workload
     increment counter 3
     unlock B

   Performance with lock elision does _not_ improve.  This comes
   as a surprise to me because I specifically wrote the test
   program to demonstrate bad performance with elision, and this
   looks like my theory _why_ performance is bad was wrong.

> Do you have any performance counter data for how often you can run
> transactions successfully?

At the moment I only have performance counters recorded with
hardware sampling (we're working on a transaction profiling patch
for gcc, but that will take some more weeks).  Almost all samples
of thread 1 user code are inside transactions, and I see no aborts
at all.  I'll dig deeper into the code and what's happening later.

> > The explanation for this is that
> > ...

> If locking for A isn't elided, then thread 1 should unlock A
> ...

I'll check that in detail.

> You cited the "Focus on PNT, allow E" option, but I'm not sure what kind
> of conclusions you draw from your test, and how it relates to this
> option.  Would you like to have a very conservative default tuning?  Or
> do you think that lock elision should only be enabled explicitly on z
> architecture?  Or what else?

For the moment my conclusion is:  HTM is tricky.  It often sounds
promising, but then in real code there are many little details
that may prevent you from harvesting the benefits.

> > P.S.:  Test run with default tuning values; I think it switches
> > to real locks after three failed transactions, and back to
> > transactions after three real locks.  I'm quite sure that given
> > _any_ set of tuning parameters, I can write you a test program
> > that has similarly bad performance using elision.
> 
> Certainly not for _any_.  For example, if we don't use elision anymore
> at all after 10 failed attempts globally, I guess the performance
> degradation that elision would cause would be pretty limited :)

We'll see about that.  ;-)  Don't forget that even if elision is
disabled, the mere fact that elision is compiled in and that there
possibly is an additional function call slows down
pthread_mutex_lock.

> Thanks for making the test, and it would be interesting if you can
> investigate this further, post more results, and perhaps experiment with
> different tuning options.  As Andi said, this data is necessary input to
> see which steps we need to take to make use of elision.

I have done a lot of testing on zEC12 with HTM, and I'm certainly
willing to write and run tests and provide data; but at the moment
I have to be careful with what I post because the legal clearance
process is slow.  :-/

Anyway, if you'd like to read a bit about HTM on zEC12, there is
some information available on the net:

* A _very_ interesting article about the hardware implementation
  details:

[1] http://dl.acm.org/citation.cfm?id=2457483

* Some chapters in the "principles of operation for zEC12"

[2] http://publibfi.boulder.ibm.com/epubs/pdf/dz9zr009.pdf

  The interesting instructions are tbegin, tbeginc, tend, tabort
  (p. 7-328 ff), ntstg (non-transactional store, p. 7-258 f), etnd
  (extract transaction nesting depth, p. 7-215 f) and ppa (perform
  processor assist, p. z-293 f).  There's also a chapter about the
  transactional execution facility (p. 5-86 ff).

  Unfortunately no information on the cycle counts of the above
  instructions is available in public (although I have internal
  access to this information).

P.S.:  Please don't cc me, I'm subscribed to the mailing list.

Ciao

Dominik ^_^  ^_^

-- 

Dominik Vogt
IBM Germany