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

# Re: hash & balanced trees

- Date: Tue, 01 Jul 97 12:28:51 -0400
- From:
- cc: Richard Godard <janus@cam.org>, moo-cows@the-b.org
- In-reply-to: Your message of "Tue, 01 Jul 97 08:13:42 EDT." <Pine.SOL.3.91.970701080716.13091A-100000@atl1>

    Charles Bancroft writes:

    > Richard Godard writes:

    >> That's fine for mutable data type... but unless I'm mistaken MOO
    >> lists are not.

    As seen by MOO programmers, lists are immutable.  How they're
    implemented internally doesn't matter.  For example, when executing

       l = {"foo", "bar", "baz"};
       l[2] = "quux";

    we currently implement the second line close to

       l = listset(l, "quux", 2);

    making a new copy of l, mutating the copy, placing the copy in l, and
    then throwing away the original value of l.

    However, in this instance we can (theoretically) avoid the
    malloc/copy/free by noting that there are no other references to l as
    we enter the l[2]="quux" statement--and nobody will notice if we just
    mutate the list l points to directly.  Anybody have a cite for "The
    implementation may cheat, but it must not get caught"?

    It's possible that we could reimplement MOO lists as some fancier data
    structure internally, but I don't think it's going to happen.

    > Not sure that one would want to replace the moo list data type with
    > a hash or tree.  Rather, by adding new builtin support for
    > alternative types, it gives programmers a choice.

    FWIW, I am firmly opposed to giving programmers mutable data types as
    a choice.

    > Why not add both a $hash and a $tree =8?

    Cos they both would likely implement $dictionary, and their
    performance characteristics aren't all that different.

    While I'm at it, I should point out that naive hash tables are not
    necessarily a good implementation of dictionaries.  Given a relatively
    full dictionary, d, say we want to insert a new element:

       // Force an additional reference, since this situation comes
       // up in code a lot, especially for hacking on properties:
       old_d = d;
       d["jay"] = #3920;

    The worst thing we can do is copy the entire dictionary and add "jay"
    to the new copy of d.  You may have to do this for hash tables.
    (Come to think of it, you can pull the same kind of trick below with
    hash chains, but I need to think about this more before I can get rid
    of my distaste for hashing.)

    Consider instead a binary search tree, with each node reference
    counted.  As we descend the tree, we copy each node along our path,
    but while we're copying we only have to bump the refcount on the paths
    not taken.  We insert "jay" at the appropriate spot, do whatever
    rebalancing needs to be done, and return the head of our new tree,
    which shares all but O(log n) nodes with the old tree.

    At least at first glance, trees have better memory utilization than
    hash tables, so this certainly argues for trees.  It may come down to
    which one we can pull better tricks for, though.  For example, we can
    rebalance trees or compact hash tables during idle CPU time---or
    inside of a hash chain, it should be possible to do MRU sorting as
    long as it's clear that we're not sharing substructure.  Interaction
    with the allocator is critical for anything as cons-y as these
    structs, too.

    I'm staring at all those baroque search techniques at the back of the
    data structures book and my head hurts.  Thinking is hard.  Anybody
    have any ideas?
    --
    Jay Carlson    nop@nop.com    nop@kagoona.mitre.org

    Flat text is just *never* what you want.   ---stephen p spackman

Follow-Ups:

- Re: hash & balanced trees

- From: Charles Victor Bancroft <bancroft@america.net>

References:

- re:hash & balanced trees

- From: Charles Victor Bancroft <bancroft@america.net>

- Prev by Subject: Re: hash & balanced trees
- Next by Subject: Re: hash & balanced trees
- Prev by thread: Re: hash & balanced trees
- Next by thread: Re: hash & balanced trees
- Index(es):
  - Subject
  - Thread

Home | Subject Index | Thread Index