Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!ucsd!sdd.hp.com!wuarchive!mit-eddie!uw-beaver!cornell!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: <1811.UUL1.3#5129@willett.pgh.pa.us> Date: 5 Oct 90 03:27:24 GMT Organization: String, Scotch tape, and Paperclips. (in Pgh, PA) Lines: 37 Date: 09-24-90 (16:31) Number: 3858 (Echo) To: CHARLIE HITSELBERGER Refer#: NONE From: IAN WATTERS Read: 09-27-90 (12:24) Subj: HASHING THE DICTIONARY Status: PUBLIC MESSAGE CHpAnyway, I was thinking of doing something major league to the dictionary. CHpThe bigger the dictionary gets, the longer the average search takes. CHpThis slows down compiles. What if the FIND word were to Xor together CHpall of the bytes of the word being searched for, then Xor the two CHpnybbles of that, to get out a four-bit hash key. Then it starts in that CHp"thread" and searches backwards. The hashing algorithm is very simple CHpand could be easily implemented as a code word. Anybody out there have CHpany thoughts on this? Many Forths have hashed dictionaries. The one I wrote for a CP/M machine used 16 threads too, but a much simpler hashing function (length of string XOR first character from memory). I wanted to use words like $____, so that limited me to these two and I tried as many functions as I could until I found one that gave the most even distribution of results with the kernel and sample applications. You really notice the improvement in compile speed, especially if you don't use the fig-Forth directory structure. Ian --- ~ EZ 1.33 ~ I've a wonderful tagline, but this isn't it! PCRelay:IBBSNET -> #143 RelayNet (tm) 4.10a15 London UK +44 71 704 0760 NET/Mail : DC Information Exchange, MetroLink Int'l Hub. (202)433-6639 ----- This message came from GEnie via willett through a semi-automated process. Report problems to: dwp@willett.pgh.pa.us or uunet!willett!dwp