Test feasibility of recent word cache to improve compile performance

[patricksurry]

The flex-header work shows that most of the cycles for compilation are spent finding NTs by name and by XT. That work also makes things a bit worse since walking that linked list gets a bit slower.

It seems that a very simple random-replacement cache of recently used words could make a huge improvement. It would need to invalidate on a few wordlist changes, marker etc.

I'm curious to test the idea and see what the cost (code size, added complexity) vs benefit (speed) looks like, and how it varies with code size.

[SamCoVT]

I'd be curious to see what this look like. It will be complicated by the fact that the search order can be modified at any time. The data structures are not exposed for forth, so you'll just need to deal with the words that modify them. From the Search-Order set, that would be:
FORTH ONLY PREVIOUS SET-ORDER
If you were to invalidate your cache when these words are called, I think you will be good. Technically ALSO changes the search order, but it does so by duplicating the first wordlist, so it doesn't really change which version of a word would be used if there are multiple with the same name.

Is this going to be an array of pointers to NTs? I'm not sure what size would be reasonable, but if you give this a go, we can run some tests and see what kind of performance boost there is.

I'm not too worried about compile time performance, but if you want to give this a go then we can see if the complexity is worth the speedup.

[SamCoVT]

I just remembered that COLD should also be on that list, as it sets the initial search order. You'll probably want it to set up your data structures anyway.

[patricksurry]

Yes, I think in both cases you'd have a list of 2^k NTs (probably k <= 7 so the array is max 256 bytes or 128 entries),
indexed by a k-bit key. To invalidate the cache you just fill it with 0s (null NTs).

For xt_to_nt you could use k bits of the xt's LSB as the index; for find_name you'd use k bits of some simple hash of the name. So it would be cheap to look up the corresponding cache entry and check whether the NT there is actually a match.

Either way, when you eventually find the right NT you'd update the corresponding cache entry. Maybe there's an argument for only replacing an existing element with some probability p, so that words used more often are more likely to remain cached even if you occasionally get a key collision? Also curious how performance changes with cache size.

Maybe I could capture a log of calls to the two routines and do some experimentation in python or something. Though I guess would vary with what forth source you were compiling?

[patricksurry]

I started working on this and realized that many of the "wasted" cycles are actually due to the necessary full scan of all NTs when adding a new word, or even just parsing a number. So just caching recent words probably isn't enough. I started playing with a v simple bloom filter to avoid the scan with reasonable probability which does seem to have a positive impact despite the overhead of generating hash values for word names. But I need to pick that up again and couple with a little cache.

[SamCoVT]

Another possibility would be to use recognizers, but the default action with recognizers is the current behavior (look for a name, then try for a number if a name isn't found). Adding recognizers would just give the programmer control over the order that the input is attempted to be turned into something else (such as a number on the stack, or an XT to be run or compiled). If the programmer knows that lots of numbers will be entered, they could attempt number conversion first and only do name lookup if number conversion fails. That does, of course, preclude you from naming words using only numbers.

I do agree that for a new name, you really need to check to see if it's already in there if you want to issue the "redefined" message. We could make that message (and the check) optional. I'm not sure it's worth the trouble, though - that's the kind of message where you are either like "yes, I did" or "oh no, what have I done!" and I can't imagine a situation where I wouldn't want to know about it either way.

You're still going to run through the entire dictionary for numbers, though. You technically have to, as base-36 is a valid number base (uses all digits and all alphabet characters, eg. "drop" would be a valid number, but would be found in the dictionary first). If a program is going to accept a lot of numbers, then the programmer can read them in as strings and do the conversion directly using >number without the lookup.