rwlocks: poor performance with adaptive spinning

[Attilio Rao]

2007/9/26, Jeff Roberson <jroberson at chesapeake.net>:
> On Tue, 25 Sep 2007, John Baldwin wrote:
>
> >
> > So I looked at this some more and now I don't understand why the trywait() and
> > cancel() changes were done.  Some background:
>
> I wanted the turnstile chain lock to protect only the association between
> the turnstile and lock.  This way it further reduces the contention domain
> for the hard lock/unlock cases.  We sometimes see a lot of contention on
> the turnstile chain that may be due to hash collisions.  If this reduced
> contention doesn't help I think it would be possible to revert this
> change.

Well, the change jhb is suggesting won't reduce tc_lock contention for
sure, but it will prevent the turnstile lookup/locking if not
necessary.
Mainly, we need a spinlock held in order to protect mtx_lock bitfield
(as well as rw_lock) by setting waiters flags.
While in the past code this lock was only tc_lock, currently mtx_lock
is both protected by tc_lock and ts_lock, which it doesn't seem
strictly necessary.
if, for example, you lock tc_lock than you scan the chain and lock
ts_lock (basically what turnstile_trywait() does) and later you find
lock is released or that the state of lock changed and you cannot set
a waiters flag, you did the ts_locking and hash table scanning even if
it wasn't needed.

> I'm not sure why you're calling this O(n).  It's O(n) with the number of
> hash collisions, but it's a hash lookup.  We should consider using a real
> hash algorithm here if the distribution is bad.

Well, the hash lookup (worst case) has O(n) complexity.
This linear complexity cames from the O(1) * O(n) which is the access
to the list and the scanning of this one. So this is reduced to the
same complexity of a linked list.
However, some time ago I saw empirically that starting from a 'struct
thread' allocated address the highest level of entropy in the word
came after a right shift of 10 bits (for ia32) and 12 bits for amd64.
Currently, turnstile and sleepqueues only uses 8 bits of right
shifting.

Thanks,
Attilio


-- 
Peace can only be achieved by understanding - A. Einstein