RE: hash & balanced trees

> You might be saying to yourself: but why use avl's, why not 2-3 trees
or
> something else? As far as I know, there is no algorithm that limits
> comparisons as well as avl.  If there is, tell me.  Comparisons are
the
> most expensive part here.  2-3 trees are optimal in limiting disk
> access.  But all our stuff is in memory. 

Note that on modern machines, the difference in speed between memory and
cache (never mind the CPU itself) is not entirely unlike the difference
between disk and memory.  There are other common characteristics as
well, e.g., the way you get an entire cache-line fetched whenever you
read a single byte of it, much the way when you read a byte off of a
disk the next few Kbytes on the same track come easily/immediately
(whether you want them or not)

That is, even though we're entirely in memory, data-locality can still
be very important.  If I had to pick my own prejudice, I'd probably go
with B-Trees with fanout commensurate with the size of the cache-line
(eg., 32 bytes -> 8 pointers -> fanout of 4 or 8 depending on whether
you intersperse data with the pointers..., i.e., probably *not* 2-3
trees).

And, of course, all of this should be entirely invisible to the
MOO-code-level programmer.

---

• Prev by Subject: Re: hash & balanced trees
• Next by Subject: hash tables
• Prev by thread: hash tables
• Next by thread: MOO survey
• Index(es):
  • Subject
  • Thread

Home |
Subject Index |
Thread Index