Date: Fri, 28 Jun 2013 11:21:19 -0700 From: Adrian Chadd <adrian@freebsd.org> To: mdf@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: <CAJ-VmonEDnnTKVROBLoKDUJ2udk0mu1m4=7dnrkpPZFq-xMBRA@mail.gmail.com> In-Reply-To: <CAMBSHm9CBhf5didHvJ6JmTCqPWJYy3VB=zetTd3emyO_vNiSKQ@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> <CAMBSHm9CBhf5didHvJ6JmTCqPWJYy3VB=zetTd3emyO_vNiSKQ@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On 28 June 2013 09:18, <mdf@freebsd.org> wrote: >> 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. Good point. -adrian
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CAJ-VmonEDnnTKVROBLoKDUJ2udk0mu1m4=7dnrkpPZFq-xMBRA>