Re: Translator

[RWK@fuji.ila.com (Robert W. Kerns)]

    Date: Thu, 13 Sep 90 21:24:03 PDT
    From: shirley@parc.xerox.com
    Are the names symbols?  If so, you might also consider storing the rewrites on
    the property list of each symbol.  This should yield lookups in roughly linear
    time.  (If the symbol naming some of your types is used for multiple purposes
    -- i.e., if some of them have long property lists -- you might want to arrange
    that the REWRITE-FUNCTION property appears at the beginning of the list.)

I recommend against property lists, for paging reasons.  (See below).
Also, for semantic reasons; you can't easily and efficiently enumerate
all of the defined rewrites, without maintaining a separate list.

    Offhand, I would guess that using hash tables or property lists are better for
    1000 choices than CASE and definitely better that string-append / intern /
    apply.

Actually, with this number of cases, STRING-APPEND/INTERN/APPLY will overtake
CASE, by about a factor of two, although it does depend on the size of your
package.  However, one factor not included is that STRING-APPEND conses, which
will make the GC work harder, which will likely eat up any savings.

    I don't know how paging issues might influence the choice.  For instance, hash
    tables may be better at keeping the working set down, which may be a factor.

Indeed.  Hash tables have much better paging behaviour.  For symbols
with no other properties, you could be talking about 2 pages per symbol
being touched.  That's up to two disk reads (and up to two disk writes)
per lookup.  Add in another page per property list entry that has to
be scanned before finding the right one.

This is the worst case scenario, since some of these page references may
in fact refer to the same page, or to pages sharing data from a previous
lookup.  But it can never equal the performance of a hash table for
frequently referenced data, since the hash table data is always right
together, and smaller besides.

    If you try several alternatives and measure the speed, I'd be interested to
    hear the results.

     - Mark Shirley