From owner-freebsd-arch@FreeBSD.ORG Wed Sep 26 06:59:40 2007 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 6779816A420 for ; Wed, 26 Sep 2007 06:59:40 +0000 (UTC) (envelope-from asmrookie@gmail.com) Received: from nf-out-0910.google.com (nf-out-0910.google.com [64.233.182.189]) by mx1.freebsd.org (Postfix) with ESMTP id F0C0613C467 for ; Wed, 26 Sep 2007 06:59:39 +0000 (UTC) (envelope-from asmrookie@gmail.com) Received: by nf-out-0910.google.com with SMTP id b2so1632871nfb for ; Tue, 25 Sep 2007 23:59:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:message-id:date:from:sender:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references:x-google-sender-auth; bh=Yyd0Kt0q2A1GRkUwT62/Rn5k/Erc5kwRjhXvfl2yw4c=; b=MiM9PpjFpF5kG7MEi3NRo3G26GIsXyekFqjPGVXDxrb3agBk5Yyl0SpIZ2JO66Dh2QlU9dHk1t5LozGpue4vgVZf4zadJWWiBPeiz7g9DcKNg6gbYMF7PE6IuAzVZd6ybhG/eOHTWYTnGMmNFyY/rIP1oRiPmShtdjoZhYs2UxA= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:sender:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references:x-google-sender-auth; b=Oj+kNUOsyEwDXAQHLqSKUqT6aM5UjPrZV5Z0oHPI4N/NwwJGe2XbIqh3J8FB2D5bgB9N8nwTfstrjzK8V98x7yTuUWL3GzmgO6GUKHyMxXpgbjruIDbQ08XJvbSKqRS3ODpIJoQNWndQmrYmPc4lOJTkcO1WQFY5XY35AmGgPAw= Received: by 10.78.131.8 with SMTP id e8mr151374hud.1190789977617; Tue, 25 Sep 2007 23:59:37 -0700 (PDT) Received: by 10.78.97.18 with HTTP; Tue, 25 Sep 2007 23:59:37 -0700 (PDT) Message-ID: <3bbf2fe10709252359h7812ff7bsce9d393f80b65c06@mail.gmail.com> Date: Wed, 26 Sep 2007 08:59:37 +0200 From: "Attilio Rao" Sender: asmrookie@gmail.com To: "Jeff Roberson" In-Reply-To: <20070925155504.W556@10.0.0.1> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Content-Disposition: inline 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> X-Google-Sender-Auth: 12c5eeab311d1215 Cc: freebsd-smp@freebsd.org, freebsd-arch@freebsd.org Subject: Re: rwlocks: poor performance with adaptive spinning X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 26 Sep 2007 06:59:40 -0000 2007/9/26, Jeff Roberson : > 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