lkml.org 
[lkml]   [1999]   [Jan]   [22]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: arca-vm-26
Alan Mimms wrote:
> I do not wish to start a religious war about data structures.
Too late, you just did! :-)

I still think splay trees (aka. self-adjusting trees) are good, because
they have automatic cacheing properties which plain skip lists or the
other tree structures don't.

The downside is some pointer writing takes place when searching, except
when you get the same node as last time. Perhaps the memory write times
are significant. But then, any cache does this, including the one entry
VMA cache.

> Have you considered the relatively new data structure called a 'skip
> list'? I have replaced several subsystems in our system at work that
> would have been ready candidates for AVL or RB trees (or any of a cast
> of thousands of others) with skiplists to very good effect in
> insertion, deletion and search speed.

Have you ever tried splay trees? I would be interested to know of
applications in which skip lists outperform splay trees, and vice versa.
I would expect it to depend on whether the automatic cacheing is useful
or not.

-- Jamie

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:49    [W:0.068 / U:0.112 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site