From owner-freebsd-hackers@FreeBSD.ORG  Fri Jun 28 16:18:57 2013
Return-Path: <owner-freebsd-hackers@FreeBSD.ORG>
Delivered-To: hackers@freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org
 [IPv6:2001:1900:2254:206a::19:1])
 by hub.freebsd.org (Postfix) with ESMTP id CA028CF2;
 Fri, 28 Jun 2013 16:18:57 +0000 (UTC)
 (envelope-from mdf356@gmail.com)
Received: from mail-ob0-x22f.google.com (mail-ob0-x22f.google.com
 [IPv6:2607:f8b0:4003:c01::22f])
 by mx1.freebsd.org (Postfix) with ESMTP id 7DA7B1728;
 Fri, 28 Jun 2013 16:18:57 +0000 (UTC)
Received: by mail-ob0-f175.google.com with SMTP id xn12so2168127obc.34
 for <multiple recipients>; Fri, 28 Jun 2013 09:18:57 -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=cPyPkZdDV2vG2U/bW5gQgBrrXmc+rqSfio5xOgJttBY=;
 b=hTbNz/ycOki8A47ttFe8uiTOcwozed7zXMPgmoJ//1kVz+BktyZ2sSZIIdfv9Sny0V
 uHQqsG90+sxePAVlQRK5ldWuiHocqa8xvfTWFsb0x0sbKLktUqzy/Q1V+rck8tQ111oV
 QTktnIIwm3EXEmCIeryAtreSlaknZ6FjSnEuEN0X2PMEw0TO72T6vytL0fySQNu1CYQH
 q2RSqM6zsCJ3sT+Fp2ARxbXwAm9Vd3G9jxIll4vKla3/4oTKW7leVpnG326ORL11+prH
 gslo9HkXKZE8EfMRewwWIzc54jtJEvCbxS5WxxRxDmxxxjsyIzYaJCI5FmF036fK7sFY
 8bkw==
MIME-Version: 1.0
X-Received: by 10.60.164.33 with SMTP id yn1mr5424742oeb.5.1372436337120; Fri,
 28 Jun 2013 09:18:57 -0700 (PDT)
Sender: mdf356@gmail.com
Received: by 10.182.165.162 with HTTP; Fri, 28 Jun 2013 09:18:57 -0700 (PDT)
In-Reply-To: <CAJ-Vmo=T4084a31ASjNGt-eztfzwfeMdttEYU98h-=QjuSLUBA@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>
Date: Fri, 28 Jun 2013 09:18:57 -0700
X-Google-Sender-Auth: A593obBiIXHan0gXkMIY9zsv7Tg
Message-ID: <CAMBSHm9CBhf5didHvJ6JmTCqPWJYy3VB=zetTd3emyO_vNiSKQ@mail.gmail.com>
Subject: Re: b_freelist TAILQ/SLIST
From: mdf@FreeBSD.org
To: Adrian Chadd <adrian@freebsd.org>
Content-Type: text/plain; charset=ISO-8859-1
X-Content-Filtered-By: Mailman/MimeDel 2.1.14
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 16:18:57 -0000

On Fri, Jun 28, 2013 at 8:56 AM, Adrian Chadd <adrian@freebsd.org> wrote:

> On 28 June 2013 08:37, Alexander Motin <mav@freebsd.org> wrote:
> >> Otherwise it may just creep up again after someone does another change
> >> in an unrelated part of the kernel.
> >
> > Big win or small, TAILQ is still heavier then STAILQ, while it is not
> needed
> > there at all.
>
> 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.

Thanks,
matthew