Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!zaphod.mps.ohio-state.edu!wuarchive!udel!rochester!pt.cs.cmu.edu!dsl.pitt.edu!pitt!willett!ForthNet
From: ForthNet@willett.pgh.pa.us (ForthNet articles from GEnie)
Newsgroups: comp.lang.forth
Subject: Conventions and "tricks" used in Forth
Message-ID: <1962.UUL1.3#5129@willett.pgh.pa.us>
Date: 7 Nov 90 01:34:27 GMT
Organization: String, Scotch tape, and Paperclips.  (in Pgh, PA)
Lines: 32


 Date: 11-05-90 (14:13)              Number: 109 of 110 (Echo)
   To: JONAH THOMAS                  Refer#: 4
 From: RAY DUNCAN                      Read: NO
 Subj: HASHING THE DICTIONARY        Status: PUBLIC MESSAGE
 Conf: FORTH (58)                 Read Type: GENERAL (+)

 With a hash table the payoff is immediate; the code to hash the name
 being looked up, probe the hash table, and compare to the actual header
 is all in assembly language and very fast.  This turns out to ALWAYS be
 more efficient than the traditional linear search of a linked
 dictionary, when the dictionary is of any USEFUL size.  When the
 dictionary gets large, the difference in lookup speed is enormous, and
 you have the additional advantage that interpretation of numbers is also
 speeded up drastically --- FIND typically knows immediately (with a
 couple of probes of the hash table) that the token is not a Forth word,
 instead of being required to exhaustively compare the token against
 every name in the current search order before attempting conversion to a
 number.

 On the other hand, this kind of dictionary management doesn't lend
 itself to quick ports of the language or to  ROMing; for these
 situations (where compilation speed is unimportant compared to the
 benefits of having a small, interactive system) we still use (or at
 least start with) the more traditional linked dictionary (sometimes
 adding a lookup cache later if we don't feel like going the whole
 distance to the hashed dictionary).
 <<<>>>

-----
This message came from GEnie via willett through a semi-automated process.
Report problems to: dwp@willett.pgh.pa.us or uunet!willett!dwp