Re: rwlocks: poor performance with adaptive spinning

2007/9/26, Jeff Roberson <jroberson@xxxxxxxxxxxxxx>:
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
_______________________________________________
freebsd-arch@xxxxxxxxxxx mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "freebsd-arch-unsubscribe@xxxxxxxxxxx"

Relevant Pages

  • Re: rwlocks: poor performance with adaptive spinning
    ... I wanted the turnstile chain lock to protect only the association between ... the turnstile chain that may be due to hash collisions. ...
    (freebsd-arch)
  • Re: rwlocks: poor performance with adaptive spinning
    ... This way it further reduces the contention domain ... the turnstile chain that may be due to hash collisions. ... While in the past code this lock was only tc_lock, ...
    (freebsd-arch)
  • Re: rwlocks: poor performance with adaptive spinning
    ... something strange about adaptive spinning popped ... the lock held in read mode too), but we first should be sure to start ... I wanted the turnstile chain lock to protect only the association between the turnstile and lock. ... It's Owith the number of hash collisions, but it's a hash lookup. ...
    (freebsd-arch)
  • Re: rwlocks: poor performance with adaptive spinning
    ... starvation of waiters. ... something strange about adaptive spinning popped ... the lock held in read mode too), but we first should be sure to start ... When the initial turnstile code was split out of the the mutex code, ...
    (freebsd-arch)