Ben Pfaff's Paper Comparing AVL, Red-Black, And Other Trees.

Hi All,

I'm having trouble (re) finding his paper if anyone would be so kind
to provide a link.

Also, if anyone else has any comments about relative performance of
one versus others, I would like to hear them. I already have my own
implementations of each in C++ using templates. Just curious about
what others have found.

TIA,

-Le Chaud Lapin-

Le Chaud Lapin <jaibuduvin@gmail.com> writes:

> I'm having trouble (re) finding his paper if anyone would be so kind
> to provide a link.

http://benpfaff.org/papers/libavl.pdf
--
Ben Pfaff
http://benpfaff.org

On Aug 21, 1:38*pm, Ben Pfaff <b...@cs.stanford.edu> wrote:
> Le Chaud Lapin <jaibudu...@gmail.com> writes:
>
> > I'm having trouble (re) finding his paper if anyone would be so kind
> > to provide a link.
>
> http://benpfaff.org/papers/libavl.pdf
> --
> Ben Pfaffhttp://benpfaff.org

Thanks Ben!

-Le Chaud Lapin-

On Thu, 21 Aug 2008 11:38:51 -0700, Ben Pfaff
<blp@cs.stanford.edu> wrote:

>Le Chaud Lapin <jaibuduvin@gmail.com> writes:
>
>> I'm having trouble (re) finding his paper if anyone would be so kind
>> to provide a link.
>
>http://benpfaff.org/papers/libavl.pdf

As a matter of curiousity is there any work on arranging trees in
blocks, with a view to improving locality. That is, the space
for nodes is allocated in blocks large enought to hold, say, the
children, grandchildren, and great-granchildren of a node. When
we traverse the tree we make one fetch of 14 nodes in one place
rather three fetches of 1 node each from different places. There
are obvious variations on the theme. My question is whether
people do this sort of thing and whether it is worth doing.



Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

cri@tiac.net (Richard Harter) writes:

> As a matter of curiousity is there any work on arranging trees in
> blocks, with a view to improving locality. That is, the space
> for nodes is allocated in blocks large enought to hold, say, the
> children, grandchildren, and great-granchildren of a node. When
> we traverse the tree we make one fetch of 14 nodes in one place
> rather three fetches of 1 node each from different places. There
> are obvious variations on the theme. My question is whether
> people do this sort of thing and whether it is worth doing.

Is that different from a B-tree?
--
"Mon peu de succès près des femmes est toujours venu de les trop aimer."
--Jean-Jacques Rousseau

Multi-level Trie Hashing by D.E. Zegour.

"Ben Pfaff" <blp@cs.stanford.edu> a écrit dans le message de news:
87d4k29hep.fsf@blp.benpfaff.org...
> cri@tiac.net (Richard Harter) writes:
>
> > As a matter of curiousity is there any work on arranging trees in
> > blocks, with a view to improving locality. That is, the space
> > for nodes is allocated in blocks large enought to hold, say, the
> > children, grandchildren, and great-granchildren of a node. When
> > we traverse the tree we make one fetch of 14 nodes in one place
> > rather three fetches of 1 node each from different places. There
> > are obvious variations on the theme. My question is whether
> > people do this sort of thing and whether it is worth doing.
>
> Is that different from a B-tree?
> --
> "Mon peu de succès près des femmes est toujours venu de les trop aimer."
> --Jean-Jacques Rousseau

On Thu, 21 Aug 2008 14:39:42 -0700, Ben Pfaff
<blp@cs.stanford.edu> wrote:

>cri@tiac.net (Richard Harter) writes:
>
>> As a matter of curiousity is there any work on arranging trees in
>> blocks, with a view to improving locality. That is, the space
>> for nodes is allocated in blocks large enought to hold, say, the
>> children, grandchildren, and great-granchildren of a node. When
>> we traverse the tree we make one fetch of 14 nodes in one place
>> rather three fetches of 1 node each from different places. There
>> are obvious variations on the theme. My question is whether
>> people do this sort of thing and whether it is worth doing.
>
>Is that different from a B-tree?

It might be. :-)

B-trees are an obvious path to improved locality and I should
have thought of them when I posed the question. But I was
thinking more like this:

Suppose we are building some kind of tree structure. A tree
basically is a collection of nodes, where a node typically has
key and data information, children links, and perhaps some other
links. When we insert or delete items in a tree we call little
routines that have names like getnode and freenode that do the
obvious.

When I write a tree manager of some kind I usually have a little
node manager that has a getnode and free node as an interface.
The usage looks like:

node = getnode();
freenode(node);

The routines are written for efficiency and use the usual tricks.

It is only recently that it occurred to me that there is a
problem with this approach. (I'm rather slow sometimes.)

It's fine in an environment where all memory accesses have about
the same cost and not so fine in environments where you have
tiers of caching because you want children near their parents for
fast tree traversal. To do this we need to tell getnode where
the parent is, e.g.,

child = getnode(parent);

In addition we need a getnode that can deliver a node "near" the
parent most of the time. Of course it still has to be very fast.

So my question really is: Is there stuff out there on building
this kind of node service, and is it worth doing?





Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.