[Subject Prev][Subject Next][Thread Prev][Thread Next][Subject Index][Thread Index]

# RE: hash & balanced trees

- Date: Mon, 7 Jul 1997 15:39:25 -0700
- From:
- Content-Type: text/plain

    > 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