From: Andi Kleen <ak@suse.de>
To: David Howells <dhowells@redhat.com>
Subject: Re: Why Semaphore Hardware-Dependent?
Date: Tue, 29 Aug 2006 20:33:25 +0200
User-Agent: KMail/1.9.3
Cc: Christoph Lameter <clameter@sgi.com>,
       Nick Piggin <nickpiggin@yahoo.com.au>,
       Arjan van de Ven <arjan@infradead.org>,
       Dong Feng <middle.fengdong@gmail.com>,
       Paul Mackerras <paulus@samba.org>, linux-kernel@vger.kernel.org,
       linux-arch@vger.kernel.org
References: <200608292018.01602.ak@suse.de> <Pine.LNX.4.64.0608291033380.19174@schroedinger.engr.sgi.com> <809.1156876259@warthog.cambridge.redhat.com>
In-Reply-To: <809.1156876259@warthog.cambridge.redhat.com>
MIME-Version: 1.0
Content-Type: text/plain;
  charset="iso-8859-15"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Message-Id: <200608292033.25194.ak@suse.de>
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 905
Lines: 23

On Tuesday 29 August 2006 20:30, David Howells wrote:
> Andi Kleen <ak@suse.de> wrote:
> 
> > BTW maybe it would be a good idea to switch the wait list to a hlist,
> > then the last user in the queue wouldn't need to 
> > touch the cache line of the head. Or maybe even a single linked
> > list then some more cache bounces might be avoidable.
> 
> You need a list_head to get O(1) push at one end and O(1) pop at the other.

The poper should know its node address already because it's on its own stack.

> In addition a singly-linked list makes interruptible ops non-O(1) also.

When they are interrupted I guess? Hardly a problem to make that slower.

-Andi

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/