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>
next in thread | previous in thread | raw e-mail | index | archive | help
On 1 October 2010 12:49, Matthew Dillon <dillon@apollo.backplane.com> wrote= : > =A0 =A0What turned out to be the best indexing mechanism was a chained > =A0 =A0hash table whos hoppers were small linear arrays instead of single > =A0 =A0elements. =A0So instead of pointer-chaining each element you have = a small > =A0 =A0for() loop for 4-8 elements before you chain. =A0The structure bei= ng > =A0 =A0indexed would NOT be integrated into the index directly, the index > =A0 =A0would point at the final structure from the hopper. > > =A0 =A0For our purposes such linear arrays would contain a pointer and > =A0 =A0an indexing value in as small an element as possible (8-16 bytes), > =A0 =A0the idea being that you make the absolute best use of your cache l= ine > =A0 =A0and L1 cache / memory burst. =A0One random access (initial hash in= dex), > =A0 =A0then linear accesses using a small indexing element, then one fina= l > =A0 =A0random access to get to the result structure and validate that > =A0 =A0it's the one desired (at that point we'd be 99.9% sure that we hav= e > =A0 =A0the right structure because we have already compared the index val= ue > =A0 =A0stored in the hopper). =A0As a plus the initial hash index also ma= kes > =A0 =A0MP 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. :-) Adrian
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?AANLkTi=U0ogtaiGFzasTok-y5dmw-sxo85h%2B%2BUrT-wu9>