b_freelist TAILQ/SLIST

[Alexander Motin]

On 28.06.2013 18:56, Adrian Chadd wrote:
> On 28 June 2013 08:37, Alexander Motin <mav at 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