b_freelist TAILQ/SLIST

[mdf at FreeBSD.org]

On Fri, Jun 28, 2013 at 8:56 AM, Adrian Chadd <adrian at freebsd.org> 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.


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