Re: Examining the VM splay tree effectiveness

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