Date: Fri, 28 Jun 2013 09:18:57 -0700 From: mdf@FreeBSD.org To: Adrian Chadd <adrian@freebsd.org> Cc: Konstantin Belousov <kostikbel@gmail.com>, Alexander Motin <mav@freebsd.org>, FreeBSD Hackers <hackers@freebsd.org> Subject: Re: b_freelist TAILQ/SLIST Message-ID: <CAMBSHm9CBhf5didHvJ6JmTCqPWJYy3VB=zetTd3emyO_vNiSKQ@mail.gmail.com> 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 Fri, Jun 28, 2013 at 8:56 AM, Adrian Chadd <adrian@freebsd.org> 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. 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CAMBSHm9CBhf5didHvJ6JmTCqPWJYy3VB=zetTd3emyO_vNiSKQ>