Date: Fri, 28 Jun 2013 19:22:15 +0300 From: Alexander Motin <mav@FreeBSD.org> To: Adrian Chadd <adrian@freebsd.org> Cc: Konstantin Belousov <kostikbel@gmail.com>, hackers@freebsd.org Subject: Re: b_freelist TAILQ/SLIST Message-ID: <51CDB837.7050908@FreeBSD.org> 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%2BmusP7d0vOVHy%2BiU_aXtc0Zowuw@mail.gmail.com> <51CDADA4.9090803@FreeBSD.org> <CAJ-Vmo=T4084a31ASjNGt-eztfzwfeMdttEYU98h-=QjuSLUBA@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On 28.06.2013 18:56, Adrian Chadd 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. 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?51CDB837.7050908>