Date: Wed, 26 Sep 2007 08:59:37 +0200 From: "Attilio Rao" <attilio@freebsd.org> To: "Jeff Roberson" <jroberson@chesapeake.net> Cc: freebsd-smp@freebsd.org, freebsd-arch@freebsd.org Subject: Re: rwlocks: poor performance with adaptive spinning Message-ID: <3bbf2fe10709252359h7812ff7bsce9d393f80b65c06@mail.gmail.com> In-Reply-To: <20070925155504.W556@10.0.0.1> References: <3bbf2fe10709221932i386f65b9h6f47ab4bee08c528@mail.gmail.com> <200709241152.41660.jhb@freebsd.org> <20070924135554.F547@10.0.0.1> <200709251314.42707.jhb@freebsd.org> <20070925155504.W556@10.0.0.1>
next in thread | previous in thread | raw e-mail | index | archive | help
2007/9/26, Jeff Roberson <jroberson@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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?3bbf2fe10709252359h7812ff7bsce9d393f80b65c06>