Examining the VM splay tree effectiveness
Adrian Chadd
adrian at freebsd.org
Fri Oct 1 05:53:54 UTC 2010
On 1 October 2010 12:49, Matthew Dillon <dillon at 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. :-)
Adrian
More information about the freebsd-current
mailing list