Fwd: Examining the VM splay tree effectiveness

By mistake last mail went to hackers.... sending it to freebsd-current

--
Hi,
Sorry for pitching in late on the discussion....
Looks like I have missed many mails,  Will start from this point in the
discussion


<Andre>
I just took a look (not in-depth though) at the patch and can't follow
your conclusion. It is not ready to go into svn in its current state.

Even though it is called a radix trie it doesn't look like one.  On first
impression it looks much more like an AA tree.  A radix trie, which we
already have in our network routing table code, is a variable length
(mask) tree that does path compression.  See net/radix.[ch] and

<<Mayur>>

The data-structure is  just like a page table where the index is chopped in
to sub-indices. i th sub-index is offset into corresponding node node on
(i+1)th level. The difference between then wikipedia description of
radixtree and our implementation is that nodes with single child are not
merged with parent (level compression). Also, we started with variable size
slots (sub-indices) but Jeff thought its little too flexible. Current
implementation works with fixed sized sub-indices (size is multiple of
sizeof original index)

About the benchmark: It works on uniform random numbers. Objective was to
optimize random accesses on large objects (~4G-2T)

Take a look at radix_tree_shrink() this function reduces the depth of the
tree (if possible).  Special case of path compression.

<</Mayur>>

http://en.wikipedia.org/wiki/Radix_tree<http://www.google.com/url?sa=D&q=http://en.wikipedia.org/wiki/Radix_tree&usg=AFQjCNH0t4IHDs9BvHhtvMhgaLDZT6y91g>
Extrapolating in a complete guesstimating way from the lookup function
I'd say it may perform only slightly better in an ideal case than a RB
tree but with the added overall expense of requiring external memory to
store the index and branch nodes.  This is probably a nasty disadvantage.
<<Mayur>>
I don't get you, please elaborate. The way tree is structured we do not need
space to store index (nor does radix-trie), it is implicit from the position
of the "value" corresponding the index.
<</Mayur>>
</Andre>

Thanks,
Mayur