Date: Fri, 1 Oct 2010 13:53:53 +0800 From: Adrian Chadd <adrian@freebsd.org> To: Matthew Dillon <dillon@apollo.backplane.com> Cc: freebsd-current@freebsd.org Subject: Re: Examining the VM splay tree effectiveness Message-ID: <AANLkTi=U0ogtaiGFzasTok-y5dmw-sxo85h%2B%2BUrT-wu9@mail.gmail.com> In-Reply-To: <201010010449.o914nmVt024965@apollo.backplane.com> References: <4CA4BCD2.4070303@freebsd.org> <20100930172439.GA34369@freebsd.org> <4CA4CCF8.1050300@freebsd.org> <20100930174900.GA37733@freebsd.org> <20100930180417.GA39381@freebsd.org> <4CA504AD.8000102@freebsd.org> <4CA509FE.30303@freebsd.org> <AANLkTimz6ATKYPKyD3ZsYtfrEWc=km55DOd3iu=pM-6m@mail.gmail.com> <201010010449.o914nmVt024965@apollo.backplane.com>
index | next in thread | previous in thread | raw e-mail
On 1 October 2010 12:49, Matthew Dillon <dillon@apollo.backplane.com> wrote: > What turned out to be the best indexing mechanism was a chained > hash table whos hoppers were small linear arrays instead of single > elements. So instead of pointer-chaining each element you have a small > for() loop for 4-8 elements before you chain. The structure being > indexed would NOT be integrated into the index directly, the index > would point at the final structure from the hopper. > > For our purposes such linear arrays would contain a pointer and > an indexing value in as small an element as possible (8-16 bytes), > the idea being that you make the absolute best use of your cache line > and L1 cache / memory burst. One random access (initial hash index), > then linear accesses using a small indexing element, then one final > random access to get to the result structure and validate that > it's the one desired (at that point we'd be 99.9% sure that we have > the right structure because we have already compared the index value > stored in the hopper). As a plus the initial hash index also makes > MP locking the base of the chains easier. Sounds like B+tree style stuff. Minimise the "seek" operations, as random lookup times are orders of magnitude slower than sequential access times. (Memory is hierarchial, who would've thunk. :-) Adrianhelp
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?AANLkTi=U0ogtaiGFzasTok-y5dmw-sxo85h%2B%2BUrT-wu9>