From owner-freebsd-hackers@FreeBSD.ORG Fri Jun 28 16:22:20 2013 Return-Path: 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 8579FDFD; Fri, 28 Jun 2013 16:22:20 +0000 (UTC) (envelope-from mavbsd@gmail.com) Received: from mail-ea0-x22a.google.com (mail-ea0-x22a.google.com [IPv6:2a00:1450:4013:c01::22a]) by mx1.freebsd.org (Postfix) with ESMTP id E522E1742; Fri, 28 Jun 2013 16:22:19 +0000 (UTC) Received: by mail-ea0-f170.google.com with SMTP id h10so1135381eaj.15 for ; Fri, 28 Jun 2013 09:22:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=pmKcIQ0xPrIwS8xiXcW1Dd+q87TAPM3ub11x7eM1iY4=; b=F+hDcONw/Z06/vniRJi3pP6j2adTyQWMagTOlzpcJPKVlYa2ugg+61D5iaSPonK3p2 iixvvQpWEcSu1jGeHKY1mketxAuH0QI+qCFXZ8D2Ijfk/QiT+1jqXFYS69rq677t2w86 ZcRazb7ogYCgzXVJNQ/6OQ/U0nGYfsdb3OM4vxpKLoeiRaawB4Re/OFLrdula0cmyvVC 8qr8OKjOJz+CczW6WpWduB1wUU/8PKqody0lvZzMuGQZemItxtD7M2NH09r10ejlu1Nw eH97Q0/YtUYQS57d8TljynLSo5aLcY7kKJF8wdXFVuaCPv5winDS3aTZL+pQBMGrtkE4 7rkg== X-Received: by 10.15.110.10 with SMTP id cg10mr14610707eeb.57.1372436539109; Fri, 28 Jun 2013 09:22:19 -0700 (PDT) Received: from mavbook.mavhome.dp.ua (mavhome.mavhome.dp.ua. [213.227.240.37]) by mx.google.com with ESMTPSA id m1sm11470382eex.17.2013.06.28.09.22.17 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 28 Jun 2013 09:22:18 -0700 (PDT) Sender: Alexander Motin Message-ID: <51CDB837.7050908@FreeBSD.org> Date: Fri, 28 Jun 2013 19:22:15 +0300 From: Alexander Motin User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:17.0) Gecko/20130616 Thunderbird/17.0.6 MIME-Version: 1.0 To: Adrian Chadd Subject: Re: b_freelist TAILQ/SLIST References: <51CCAE14.6040504@FreeBSD.org> <20130628065732.GL91021@kib.kiev.ua> <51CD4FEA.7030605@FreeBSD.org> <51CDADA4.9090803@FreeBSD.org> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit 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 16:22:20 -0000 On 28.06.2013 18:56, Adrian Chadd wrote: > 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. That is true, but still TAILQ_INSERT/_REMOVE modify one more cache line then SLIST and also use branching. > 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. OK, I'll dig it more. -- Alexander Motin