rwlocks: poor performance with adaptive spinning
attilio at freebsd.org
Tue Sep 25 23:59:40 PDT 2007
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
Well, the change jhb is suggesting won't reduce tc_lock contention for
sure, but it will prevent the turnstile lookup/locking if not
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
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
Peace can only be achieved by understanding - A. Einstein
More information about the freebsd-smp