_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

You should look at my Qforth. I use hashed chained linked list to hold the words. It's superfast.

Toshi

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Not sure where you downloaded it but there's a chance it's a NUFX archive (a.k.a a Shrinkit archive), which is a funky Apple II archive format (Shrinkit is the name of the application that creates and extracts these files). NuFX files usually have a .shk extension. NuFX files can be identified by the first 6 bytes: $4E $F5 $46 $E9 $6C $E5, which is the ASCII string "NuFile" with bit 7 alternating. The header for the first (archived) file starts at the 48th byte, so those 4 bytes will be $4E $F5 $46 $D8, which is the string "NuFX", again with bit 7 alternating. (The header for each archived file contains the "NuFX" ID string.) Anyway, there's a C program out there specifically designed for creating/extracting these files on non-Apple systems. However, you might be able to save yourself a lot of trouble. I have already "unshrunk" Qforth source code sitting around that I downloaded from somewhere, the Ground archive I think. If you need an exact URL, I can look it up.

Anyway, if you don't want to go wading through all the Qforth source code, here's a brief description of hashing (at least as it applies to Forth dictonary searching), and how Qforth does it. The grouping by name length that you have proposed above is a form of hashing. The item you are searching for is called the key. In a Forth dictionary lookup, the key is the name of the word. The idea is to divide the dictonary up into smaller pieces. Each piece is referenced by a number. You compute this number using the hash function, which is a function of the key, in other words, f(key) is your hash function. In your group-by-name-length method, f(name) -- remember, in this instance, the name of the word is the key -- is:



Ideally, you want to choose a hash function that distributes the words as evenly as possible between the various pieces. If you have N total words and K pieces, then each piece could contain as few as N/K words. In other words, f(key) returns only K distinct values. In your example, K=10. You also want a hash function that can be quickly computed, since it doesn't do much good for the search to be faster if the preparation time (i.e. computing the hash function) eats up the savings. There is something of an art to choosing a hash function. Length, while easy to compute, isn't really ideal, since there are (well, I haven't counted them, but there probably are) more standard 3 character words than standard 9 character words, for instance. In Qforth, K=128, and the hash function is:

f(name) = (char1 XOR char2 XOR ... XOR charL) AND $7F

where L is the number of characters in the word. Then Qforth uses that to look up the address of the appropriate piece in an array. However, if you use a word like MARKER you will have to save the current lengths (or ends) of all K pieces so that you can dispose of the heads. (You could generate a new array when you get to MARKER, but that's also space consuming.) An alternative is to rebuild all the pieces when its time to dispose of the heads, which is time consuming. QForth, for example, builds each of the pieces at cold start, which does add to the amount of initialization time.

One other reason why you may see less speed up than you hoped (with any method) particularly in Forth is that many definitions use the last few words just defined, which will be found almost immediately even if those words are merely stored in a single linked list like in FIG-Forth.

Another option with separated heads is to group by name length, then arrange the heads of the words in alphabetical order. Then each name comparison rules out about half of the dictionary. (You do have to think it through to make sure that your search implementation works correctly.) So, it will take at most about log2(N) comparisions to find a word. Very fast, and there isn't much of a space penalty. Creating new heads (as well as deleting a head) can be slow, since a lot bytes may need to be moved to insert the new head in alphabetical order. So this method isn't so good for user defined words, but it works well for words in the kernel.

A third option is to use an AVL tree. There's an article in Forth Dimensions V2#4 starting on p.96 (it starts on p. 112 of the V2 .pdf file available at www.forth.org) about AVL trees that includes some 6800 assembly and Forth code for searching, inserting, and deleting. AVL trees are also descibed (among other places) in Knuth's "The Art Of Computer Programming", Volume 3, Section 6.2.3.

Briefly, the idea is similar to pre-alphabetizing the dictionary, but instead of arranging the names in a particular order, you simply add 2 pointers to EACH head. One points to words that are "lower" (i.e. alphabetically) and the other points to words that are "higher" (alphabetically). Adding to the tree is easy, but the trick is to keep the tree balanced. In other words, if you have N heads, the maximum height of an optimal tree is only about log2(N). For example, the optimal arrangement of the words A through G is:



It turns out that maintaining an optimal tree when adding heads is difficult. An AVL tree won't always be optimal (it depends on what order you add the heads), but its worst case height is less than 1.5*log2(N) which is still very efficient. (There's a more precise formula for the worst case height but it involves log base sqrt(1.25)+0.5. Really.) Insertion (including re-balancing the tree) is very fast and easy, no more than a single re-balancing operation is needed. Deleting heads is a bit more involved, but at most log2(N) re-balancing operations are needed, and even that isn't bad.

It only takes a single pointer to define a new tree, so MARKER can be easily implemented also. In that case, you would search the new tree first, and the old tree second, which would take 1.5*log2(N2)+1.5*log2(N1) comparisons, rather than the 1.5*log2(N2+N1) comparisons that a single tree would take, but it's still very fast. It's even possible to handle redefined words without overwriting the old head.

As I alluded to above, the biggest issue is that it requires 2 pointers plus 1 byte (a balance factor) PER HEAD. So for 2 byte pointers, that's 5*N additional bytes of head space required. The balance factor isn't used when searching for words, it's only used to re-balance the tree when adding or deleting heads. (There are only three possible values for the balance factor, so it could conceivably be stored in two bits fairly easily, but masking off those two bits -- wherever they may packed -- will take additional time.)

I think it's worth keeping in mind (although I don't suppose anybody really needs it pointed
out to them) that what may be ideal in some sense, may yet be suboptimal in light
of other considerations.
eg. you might be better off with an"ideal hash" (using ideal here in the slightly different
sense of no collisions) on some subset of more probable words than with a hash that has
a better distribution on the possible words.
ie if 90% of your searches are on 20 predefined words, it may be worth putting
some effort into optimizing for those 20 words even if it results in a hash that's a little less
than "ideal" in some way.
Or even after you've taken in to account other (more obvious or structural) biases
(like 3 characters v 9 characters).

You are right that when it comes to hashing, the word "ideal" generally means "no collisions". There are some things to keep in mind when specifically applying hashing to a Forth dictionary search, though. (I wasn't intentionally trying to gloss over hashing in general, but I was trying to stick to hashing in Forth.)

First, in Forth, it can be especially difficult to anticipate what names will be used for user-defined (application) words, especially since words can, and often will, contain ANY character, except (ordinarily) space.

Second, if a word is redefined, the most recent definition is the one that must be returned by subsequent searches. So if a new word collides with one of the "20 most used" words, but the two have a different name, that "most used" word will have to be found last, and therefore be found less quickly.

There are some options that allow you put the "most used" word first, so that it can be found immediately, though. One way is to handle a redefined word by simply overwriting the old head, and forget about using a word like MARKER. If you wanted to reset the dictionary (to what it was at cold start) you would have to reload the kernel from scratch. Another way is to handle a redefined word by creating a new head (which would be found last), but make the new head point to the old definition, and the old head (i.e. the one that would be found soonest) point to the new defintion. In other words, swap the heads when the name is identical. Note that this means that you have to check if a word is being redefined every time you create a new head. Since redefined words aren't common, this makes creating a new head slower on average.

For the reasons above, I am personally somewhat skeptical of hash functions that are specifically intended to have no collisions for the most frequently used words. I have the sneaky suspicion that it would be all too possible to hit a worst case scenario where the new words collide ONLY (or at least chiefly) with the most frequently words. Of course it's not so easy to find a hash function that distributes words evenly, either!

Your suggestion to consider tailoring to the situation is good advice. Just be aware that Forth can pose unique challenges in that regard.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

"Ideal hash" isn't the phrase used to describe a hash with no collisions.

It's called a "perfect hash".

There's at least one perfect hash generator floating around on the web in source form, but I don't remember the name offhand. I think it's a GNU package.

Toshi

Technically correct of course

And for my part , perhaps I should have just left out the "no collisions" bit
or elaborated somewhat.

There are a number of techniques for achieving perfect hashes along with the attendant example code and there used to be several web pages that
would generate them for you.

They usually (to my knowledge) involve elaborate parameterized algorithms
that use a brute force search for paramteres to map arbitrary keys
to the smallest possible
space (few or no empty spots).

The term "perfect hash" is associated in my mind with these techniques
that involve so much concomitant overhead they're essentially useless for
less than millions or billions of keys.

I deliberately chose not to use the term "perfect hash"
For one thing, it might have sounded I was quibbling over semantics
then too, you might derive a hash with no collisions relatively easily if you don't mind
a sparsely populated hash space, but it's not what I think of as a perfect hash.
In this case it's not a problem because other keys could fill the empty spots.

But no collisions for some subset of words was just an appropriate example

I was really trying to offer a reminder not to let one's thinking become too limited. The term "perfect hash" would just introduce another set of
mental constraints and that would be the opposite of what I was trying to do.

I don't know, maybe other people don't have the same problem I have with
not letting their unconscious assumptions narrow their view

In retrospect, I probably skipped to some of the Forth-specific issues a little too quickly, and didn't cover the basics of hashing adequately. So let's start again.

The idea behind hashing is to speed up a search by calculating a number from the key (i.e. the data you searching for). The key could be any kind of data, but in all of the examples below, the key will be a string. In other words, we'll be searching for a string. That's all hashing really consists of, calculating a number that is a function of the key (i.e. the string). This function is called the hash function.

Suppose you're writing a traditional two-pass assembler. An NMOS 6502 has 56 different mnemonics. To keep this example simple, we'll only have four assembler directives: DB, DW, EQU, and ORG, bringing us to a total of 60 different opcodes. If we arranged the opcodes alphabetically, we could ensure that only 6 string comparisions are needed rather than 60. But suppose we had a function whose input was a string (the opcode), and returned a different number (between 0 and 59) for each of the 60 valid opcodes. Now we use this number to index into an array that consists of pointers to routines that handle each of the 60 opcodes. You'd likely want to catch an invalid opcode error, so you'd still be left with 1 string comparison. But if the hash function could be quickly computed, that one and only string comparison would make the search very fast.

Even though the opcodes could be in any order (i.e. it isn't necessary for ASL to be 0 and TYA to be 59, as long as each valid opcode results in a different number), finding such a function that can be calculated easily and quickly could be quite a challenge. Suppose we could find a function that returns a different number between 0 and 255 for each of the 60 valid opcodes. This is slightly less memory efficient (yet still not too bad), but on a 6502 it could be just as fast if your array was implemented as two tables (one for the low byte of the pointer, the other for the high byte) and was accessed by Absolute,X or Absolute,Y addressing. This new function should be easier to find than the old function, and might even be easier and faster to compute as well (since it's less restrictive).

Incidentally, if the assembler was part of a C compiler system (where the compiler generates a human-readble source file, which is then fed to the assembler to produce the object file) instead of a stand-alone assembler, you can go from one string comparison to zero string comparisons. The compiler will only feed the assembler valid opcodes, either a valid 6502 mnemonic or a valid assembler directive, so you don't need to check for the invalid opcode error. So an opcode can be determined by simply computing the hash function.

Getting back to the stand-alone assembler example, another place where hashing could be used is the symbol table. When the object code is intended for a specific system, it's common to have a file that contains a set of EQUates of standard names for ROM entry points, I/O addresses, etc. These labels are known beforehand and their names won't be changed. But you also have the labels that the user chooses. Some of these names can be anticipated. Labels like COUNT, LOOP, PTR, and variations thereof are common no matter what type of program the user writes. But the names of most of the user's labels will be difficult to predict, which raises a couple of issues:

1. The hash function might return the same number for two different labels

2. The number of labels the user will define won't be known beforehand, and the number of possible values that the hash function should return is a question. Note that if the hash function returns 256 different values and the user defines 257 labels, the hash function must return the same number for at least 2 of the labels.

When a hash function returns the same value for two different label names in the symbol table, this is called a collision. Normally, the goal with hashing is to have no collisions. But collisions are not the end of the world. For example, if the hash function returns the same value for the labels AB, CD, EF, and GH, after computing the hash function, all you have to do is perform a few string comparisions to tell these labels apart. These label names could be stored in a linked list, or in an AVL tree, etc. But keep in mind that if you had, say 100 labels, and those four were the only ones where there was a collision, 4 string comparisons MAXIMUM (if those four were stored in a linked list) vs. 50 string comparsions AVERAGE (if hashing wasn't used and the entire symbol table -- all 100 labels -- was stored as a linked list) is still a substantial speed improvement, even though no collisions would be faster yet.

Now let's consider how hashing can be applied to a Forth dictionary search. The examples above have laid much of the foundation. You have words like IF and SWAP whose names are known beforehand and won't be changing, and then you have the word names that the user will choose. There are several things to consider with Forth specifically, which have been mentioned above, so I'll just list them here without much elaboration.

1. It is much more difficult to predict the names of the words that a user will define since not just 0-9 and A-Z but pretty much any character is fair game.

2. If you are using multiple vocabularies (ASSEMBLER, EDITOR, etc.), each vocabulary will ordinarily need its own pointer array (remember that from several paragraphs ago?), which can get space-expensive.

3. Likewise, if you are using MARKER, the entire pointer array must be saved (or at least any information needed to reconstruct it), so that its current state can be restored later.

4. Most colon definitions make use of the last few words that were just defined, which can ordinarily be found immediately with any search method.

5. If words are fairly evenly distributed among the possible return values of the hash function, this can help improve the worst case.

6. If you can set things up so the most commonly used words have no collisions, the overall search time is likely to improve.

7. When a word is redefined, the new definition must be found before (or instead of) the old. This means that a frequently used word in the kernel like DUP is usually found last, so collisions with user defined words can make searching slower.

For these reasons, you may want to combine hashing with other techniques to improve performance. In Forth, it shouldn't be too hard to write some debugging code that collects statistics on how words are distributed and how frequently they are used. You could use that information as you experiment.

By the way, I only started learning Forth...oh it must have been 1999 or so -- it was definitely not before 1998. Admittedly, there is a lot of source code in those FD .pdf files that is barely legible. Using 200% or 400% size is practically a necessity in some cases. Fortunately, I have some other (non-Forth) material on AVL trees, so I haven't had to rely solely on that FD article.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

That's good, because until now, I'm rather shocked that nobody offered another option, one which is wholesale independent of the data structure used to locate words with: caches.

One method to solve the problem of taking longer to find the earliest defined words (such as @ and !, and most of the other Forth primitives) is to cache your search results. FIND, in this case, would be the sole maintainer for the cache -- no other subsystem need be aware of it.

The way FIND works in this case is simple:



Note that it has worse worst-case performance, since FIND is scanning two data structures -- a list (O(m) time) and, say, a hash (O(n/k) time), for a total of O(m)+O(n/k) time. But, you really have to write some horrifyingly pathological code to encounter this -- more often than not, the cost of a cache miss will be simply O(n/k)/2, and the cost of a cache hit will, on average, be O(m)/2.

As long as your cache is small (for example, 16 to 64 elements tops), this should markedly improve performance for Forth compilation. Since the cache does not need to be in strict chronological order, you will find that words like !, @, BEGIN, WIHLE, IF, etc. will tend to be at the head of the list, in contrast to the end of the list. But so will words that you last defined too. Which makes sense -- given some software you're coding, you rarely will ever tend to use middle-level words when you're coding high-level words, because that substrate has already been coded. Instead, you tend to use language primitives and the words of the software layer you're working with just below the one you're defining. E.g.,



Which, in my opinion, should be the way things are done anyway. Note that it's not strict of course -- caches are used precisely because they're dynamic -- if it turns out that you end up using intermediate layers more often that another, then of course, access to that intermediate layer will be faster too.

Anyway, I hope I have explained this well. I need to head off to work now.

You're making things much more complicated than it needs to be IMHO.

You can accomplish the same effect with a hashed chained linked list by moving the found item to the head of the list for that hash value, and this way you don't need a separate cache.

Toshi

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

This is true for processors that lack data caches. But modern CPUs tend to have caches. To maximize locality, you want as much data fetched per cache-line-fetch as possible. Hence, even with your hash+linked-list solution, you still end up jumping all over hell and creation in RAM, thus invalidating the very purpose and utility of the microprocessor's cache. Don't believe me? Benchmark it.

And then, as Garth indicates above, you can't even use the hash list rechaining technique for ROM-resident words.