From owner-freebsd-hackers@FreeBSD.ORG Fri Jun 28 15:56:54 2013 Return-Path: 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 AD5A41FF; Fri, 28 Jun 2013 15:56:54 +0000 (UTC) (envelope-from adrian.chadd@gmail.com) Received: from mail-qc0-x230.google.com (mail-qc0-x230.google.com [IPv6:2607:f8b0:400d:c01::230]) by mx1.freebsd.org (Postfix) with ESMTP id 61DD315DC; Fri, 28 Jun 2013 15:56:54 +0000 (UTC) Received: by mail-qc0-f176.google.com with SMTP id z10so1462599qcx.35 for ; Fri, 28 Jun 2013 08:56:54 -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=Hc+Etr5FEvgF5ej2ZHPPvnYAtq5piHO2rRzLoEGSF8s=; b=IDmxnr+bhWPm+T2V+7ZNzGsZiiPQHxq5+DpeEvBRKsKbC7NdUWKVrwcxvx1GNB6fEw c+iycJMDN0JMoXK+X6jX1uP5bAn+20dFp5vQ8rMdD5Uzz/Y8c6sGeoYZLjGHPSVlrE3G dKOvqK8vn4BUu4vccWOIaHDFheelysUwMhGqncm44LPHTalAX7+VM6GJSP9P5Uzp+I1O PTBEzNQuCTOaFxk+OSr1hfek0yEbZ2ggoVwH7nd5mrN4kU4R9Ss1jxs7QRXkOM73SnNx o3BWwrxRu+3Mk9JHKD+ZU4agNbHvvlvgtXwOXpMLUrIeAm/XOS2ytUi8dESCK9DgQtwl 13aQ== MIME-Version: 1.0 X-Received: by 10.224.190.137 with SMTP id di9mr18263598qab.95.1372435013976; Fri, 28 Jun 2013 08:56:53 -0700 (PDT) Sender: adrian.chadd@gmail.com Received: by 10.224.214.7 with HTTP; Fri, 28 Jun 2013 08:56:53 -0700 (PDT) In-Reply-To: <51CDADA4.9090803@FreeBSD.org> References: <51CCAE14.6040504@FreeBSD.org> <20130628065732.GL91021@kib.kiev.ua> <51CD4FEA.7030605@FreeBSD.org> <51CDADA4.9090803@FreeBSD.org> Date: Fri, 28 Jun 2013 08:56:53 -0700 X-Google-Sender-Auth: 4KL2v_vKoRFJuSc_lJGl-jC-SYE Message-ID: Subject: Re: b_freelist TAILQ/SLIST From: Adrian Chadd To: Alexander Motin Content-Type: text/plain; charset=ISO-8859-1 Cc: Konstantin Belousov , hackers@freebsd.org X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 28 Jun 2013 15:56:54 -0000 On 28 June 2013 08:37, Alexander Motin 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. You've already bitten the overhead of loading the struct from RAM into L1/L2 cache; once that's done, the second pointer operation should just hit the cache. Same with the store - if they're in the same cache line, the overhead will be very small. The memory controller is likely operating on multiples of L1 cache lines anyway. The only time I can see that being a benefit (on current hardware) is if you're trying to pack more into cache lines; but then if you're doing that, you're likely better off with an array rather than lists. That way you don't waste 4/8 (or 2x that for the double-linked list) bytes for each pointer for each list element, as well as another 4/8 byte pointer to 'self'. But that doesn't -always- give a boost; it also depends upon memory layout and whether you're using all the cache lines or not. So yes - I think you're on to something and I think it's worth digging deeper into what's going on before you commit something. No, don't commit the SLIST change until you absolutely, positively know why it's actually being helpful. It's way way too "voodoo" right now. Thanks, Adrian