From owner-freebsd-hackers@FreeBSD.ORG  Fri Jun 28 18:21:20 2013
Return-Path: <owner-freebsd-hackers@FreeBSD.ORG>
Delivered-To: hackers@freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115])
 by hub.freebsd.org (Postfix) with ESMTP id 4E153A67;
 Fri, 28 Jun 2013 18:21:20 +0000 (UTC)
 (envelope-from adrian.chadd@gmail.com)
Received: from mail-qa0-x22d.google.com (mail-qa0-x22d.google.com
 [IPv6:2607:f8b0:400d:c00::22d])
 by mx1.freebsd.org (Postfix) with ESMTP id E497D1D49;
 Fri, 28 Jun 2013 18:21:19 +0000 (UTC)
Received: by mail-qa0-f45.google.com with SMTP id ci6so786158qab.18
 for <multiple recipients>; Fri, 28 Jun 2013 11:21:19 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
 h=mime-version:sender:in-reply-to:references:date
 :x-google-sender-auth:message-id:subject:from:to:cc:content-type;
 bh=X31Nut++pRjKfKr3U3vdop/p/U6c5dzTb0WwH/ehhfA=;
 b=lKnx57+WgZaDp4GanL6ROqI5taTRIuDdlWtXaIrmcOUZcjHgTzS56dJYktyMFy4fmH
 mhvZVYzneHyzGChVLtCnBdWUsvL6XGY18CfQc9x33FK8Yxhkozq++PDDctPVnMVeCmQl
 FajUy+5ehoiITfiXi1q8yU+Pch9a1ZhcFr5HjE8Ozjm35QQY6UF7eTM61KH55ckAGyzS
 kjYm+2f3zcQ3HxJcNgWywZUAryr7bLusqJp+77ozxHtpNPpMW1x8lHYOfc7Fw3ZD2hm5
 DgQdYmDf2UASG1/3ESxKYWXF1R20MhwvcPMH0HM4ooIJ9huoJVc62oz+vPhRMreXaoI+
 F3PA==
MIME-Version: 1.0
X-Received: by 10.224.21.130 with SMTP id j2mr19606519qab.112.1372443679474;
 Fri, 28 Jun 2013 11:21:19 -0700 (PDT)
Sender: adrian.chadd@gmail.com
Received: by 10.224.214.7 with HTTP; Fri, 28 Jun 2013 11:21:19 -0700 (PDT)
In-Reply-To: <CAMBSHm9CBhf5didHvJ6JmTCqPWJYy3VB=zetTd3emyO_vNiSKQ@mail.gmail.com>
References: <51CCAE14.6040504@FreeBSD.org> <20130628065732.GL91021@kib.kiev.ua>
 <51CD4FEA.7030605@FreeBSD.org>
 <CAJ-VmonKubEaU1RQ=D49SEj+musP7d0vOVHy+iU_aXtc0Zowuw@mail.gmail.com>
 <51CDADA4.9090803@FreeBSD.org>
 <CAJ-Vmo=T4084a31ASjNGt-eztfzwfeMdttEYU98h-=QjuSLUBA@mail.gmail.com>
 <CAMBSHm9CBhf5didHvJ6JmTCqPWJYy3VB=zetTd3emyO_vNiSKQ@mail.gmail.com>
Date: Fri, 28 Jun 2013 11:21:19 -0700
X-Google-Sender-Auth: 0ZqxfMs7T42W4PSA8owViIWZx-0
Message-ID: <CAJ-VmonEDnnTKVROBLoKDUJ2udk0mu1m4=7dnrkpPZFq-xMBRA@mail.gmail.com>
Subject: Re: b_freelist TAILQ/SLIST
From: Adrian Chadd <adrian@freebsd.org>
To: mdf@freebsd.org
Content-Type: text/plain; charset=ISO-8859-1
Cc: Konstantin Belousov <kostikbel@gmail.com>,
 Alexander Motin <mav@freebsd.org>, FreeBSD Hackers <hackers@freebsd.org>
X-BeenThere: freebsd-hackers@freebsd.org
X-Mailman-Version: 2.1.14
Precedence: list
List-Id: Technical Discussions relating to FreeBSD
 <freebsd-hackers.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/options/freebsd-hackers>, 
 <mailto:freebsd-hackers-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-hackers>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Help: <mailto:freebsd-hackers-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>,
 <mailto:freebsd-hackers-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Fri, 28 Jun 2013 18:21:20 -0000

On 28 June 2013 09:18,  <mdf@freebsd.org> wrote:

>> You can't make that assumption. I bet that if both pointers are in the
>> _same_ cache line, the overhead of maintaining a double linked list is
>> trivial.
>
>
> No, it's not.  A singly-linked SLIST only needs to modify the head of the
> list and the current element.  A doubly-linked LIST needs to modify both the
> head as well as the old first element, which may not be in cache (and may
> not be in the same TLB, either).  I don't recall exactly what [S]TAILQ
> touches, but the doubly-linked version still has to modify more entries that
> are not contiguous.

Good point.



-adrian