Wordlists and compilation speed

[jkotlinski]

It was always the case that durexforth does not have Wordlists.
Biggest reason not to, is brevity and ease of implementation. The feature is optional and not needed.

It now crossed my mind that there could be a concrete benefit to having optional wordlists: compilation speed. Practically, it might help FIND-NAME speed considerably if assembler words can be skipped in the search.
(exactly how much it would help, would need to be measured)

On a tangent, I realize now that the traditional Ragsdale assembler, where e.g. # ,X ,Y are separate words, is helpful for reducing word count and thus compilation speed.

[jkotlinski]

Two potential changes:

• implement wordlists
• switch to Ragsdale assembler

[burnsauce]

Two potential changes:

* implement wordlists

I was thinking this might be difficult, but we have a free bit in SIZE_FLAGS if it's just the assembler words.

CODE would set a flag that causes FIND-NAME to include assembler words. So, a single optional wordlist just for assembly.

Search speed over this region could be relatively quick if this was bit was $80 because then in non-assembly mode, a preemptive bmi will skip the word, with a balance of:

• +3 cycles per word in dictionary (~350)
• -7 cycles for the 109 assembler words
  A balance of +287 cycles or so to lookup pushya, even before considering the O(1) cost.

So on reflection, this approach is not worth it.

Implementing 1 additional built-in wordlist to FIND-NAME could probably be done without too much fuss, considering that the size of the wordlist is fixed and it's a special case, so it could reside anywhere. Turn-key operation will require it to be its own little space though, not anywhere below HERE.

It would complicate SAVE-* a bit to handle that memory chunk.

Aside from those thoughts, I think the dictionary structure would need to change to accommodate wordlists.

* switch to Ragsdale assembler

Neat!

[burnsauce]

Turning the existing dictionary structure into a linked list would cost about 700 bytes in data.

Unclear what the code size cost would be. Navigating the dictionary would save some cycles, and this would permit separate wordlists. Some words would need to be added, obviously, to manage the wordlists.

edit: Actually, navigating a linked list would take 50% more cycles than navigating by addition, 27 vs 18.

I'm starting to think there are no savings to be had without a radical change to the dictionary.

[Whammo]

A fixed size array is still pretty flexible and cool. In the unlikely event the array is full, swap in another array.

[burnsauce]

Also, using nibbles for the attributes mean complications when sorting, as MOVE is insufficient.

[Whammo]

Perhaps LATEST will always be the first entry and put at the end when latest changes, and entries move up ( swap with the one above ) one index in memory each time they're accessed up to LATEST + 1 😄

[Whammo]

Of course it would be all backwards to end search on 0

[Whammo]

An ongoing bubble sort may be a bit of overhead- but I'm spitballing here!
Thanks, I'm enjoying thinking about it.

[Whammo]

I think the arrays might be thoroughly optimized by the time from start-up to user prompt, so the bubble sort might could be forgotten at that point.

[Whammo]

I dare to say if there is a faster way to traverse a dictionary, then Chuck Moore hasn't found it yet! 😄

[burnsauce]

Sure, there's an optimization, but it doesn't alleviate the cost very much or the complexity at all.
The current design is literally 1 indirect load and 1 and,# to get the string length. The array version costs many more cycles.

It begs the question: where are the speed improvements in compilation with the array version? If NAME is slower, what is faster?

[Whammo]

With a table of four offsets, compiling with IRQs off, zero page indirect addressing, bubble sort during start-up, the savings could be considerable. I'm no engineer, but it seems right.

[burnsauce]

There are 2 things the dictionary provides: names and associated tokens.

We have demonstrated, I think you'll agree, that looking up names is significantly slower. Arrays as described are flat out slower. Unquestionably.

Which leaves fetching execution tokens. The current idiom is to add an 8-bit number to the 16-bit name pointer already available FIND-NAME, fetch that and put it on the stack.

The array design would need to update base addresses at the top of FIND-NAME even if the string didn't match so that you wouldn't need a bunch of compare/branches here to reuse your convenient index. You would save a half-dozen cycles fetching the XT here over the current version, at the cost of a dozen cycles for every single lookup to cache the base address, a net loss in the search algorithm as we would only have to look up the XT for the matching entry.

It's not faster than the current design, demonstrably, on paper, not in concept. Whatever savings "could" be there are overshadowed by the costs for the current design goal: compilation speed.

You could prove me wrong by writing and profiling the code though. :)

[Whammo]

You mean I can't just hang enough buzz-words to sell you on it, and get you to do all the work? 😄
I do appreciate your effort. Thank you.

[burnsauce]

Having a couple of days to think about this, I have some ideas.

The string length issue of a design using arrays can be partially alleviated by using counted strings in the string string section. This is still +1 layer of indirection from the current design.

But imagine we left the dictionary as-is, and added a cache of pointers into the current dictionary. Let's say the cache is 256 entries, split by MSB/LSB for a total of 512 bytes.

The structure of the cache would be a binary heap, 8 layers deep. That means that 256 of the words could be searched in 8 operations. Consider:

: find-cache ( caddr u -- xt | 0 )
  0 >r begin
    2dup r@ get-cache compare
    ?dup 0= if r@ get-cache + @ exit then
    r> 2* 1+ swap <0 if 1+ then
    dup 256 <
  while >r repeat
  drop 2drop 0 ;

Obviously this would be written in assembly, but we can see the operations:

• COMPARE produces a 0,-1, or 1, in as few operations as comparing the length, and as many as comparing the entire string
• Navigating to the next entry is 1 2* (ASL) and 1-2 increments, which should be pretty fast.

Notes:

• The cache will contain the most recent 256 words and a pointer to the 257th to continue linear search
• Obviously, this adds code and data to the existing core, but the cache could be built at run-time.

[jkotlinski]

A silly idea to speed up FIND. Theres one bit free in the ”name length” byte. That could be used to store if the sum of characters in the name is even or odd. By comparing that together with string length, in 50% of cases we can dismiss ”wrong” strings with same string length without comparing actual characters. Does it matter? Probably not much. But it could be done.

…

On Sun, 9 Jan 2022 at 05:30, Poindexter Frink ***@***.***> wrote: There are 2 things the dictionary provides: names and associated tokens. We have demonstrated, I think you'll agree, that looking up names is significantly slower. Arrays as described are flat out slower. Unquestionably. Which leaves fetching execution tokens. The current idiom is to add an 8-bit number to the 16-bit name pointer already available FIND-NAME, fetch that and put it on the stack. The array design would need to update base addresses at the top of FIND-NAME even if the string didn't match so that you wouldn't need a bunch of compare/branches here to reuse your convenient index. You would save a half-dozen cycles fetching the XT here over the current version, at the cost of a dozen cycles for every single lookup to cache the base address, a net loss in the search algorithm as we would only have to look up the XT for the matching entry. It's not faster than the current design, demonstrably, on paper, not in concept. Whatever savings "could" be there are overshadowed by the costs for the current design goal: compilation speed. You could prove me wrong by writing and profiling the code though. :) — Reply to this email directly, view it on GitHub <#422 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAY34O7SSHTXAIUZPO237S3UVEFODANCNFSM5LQOQNNQ> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. You are receiving this because you authored the thread.Message ID: ***@***.***>

[burnsauce]

The name length already has a field that indicates even or odd: bit 0

[Whammo]

Why not parity? 😄

[iclembot]

PowerMops has an interesting (FIND)..

.. not sure if it's relevant to this discussion, but I vaguely remember 68k Mops doing something like what you described above.

: (FIND)  { string-addr lfa
			\ 1st_wd dic-addr str-addr n mismatch? mask flag_byte
			  -- xt flag | -- string-addr false }

\ lfa points to the dictionary entry where the search is to start.

\ first we do a fast check on the length byte and first 3 bytes, then, if
\ this succeeds, we check the full length, 4 bytes at a time.  Note names
\ are always aligned and padded out to a 4-byte boundary with zeros.

	$ 1fffffff -> mask
	string-addr @  mask and  -> 1st_wd

	BEGIN
		lfa 4+ -> dic-addr
		dic-addr @  1st_wd xor  mask and
		NIF				\ 1st wds match - do full-length check, using
						\  the string length (as the dic entry may have
						\  the $20 bit set to make us not match the word
						\  while target compiling from 68k Mops).
			string-addr c@  $ 3F and
			2 >> -> n
			false -> mismatch?
			string-addr -> str-addr
			dic-addr c@  -> flag_byte
			BEGIN
			n WHILE
				4 ++> str-addr  4 ++> dic-addr
				str-addr @  dic-addr @ =
				NIF			\ mismatch - bail out of inner loop and
							\  return to main loop
					true -> mismatch?  1 -> n
				THEN
				1 --> n
			REPEAT
			mismatch?
			NIF			\ found!
				dic-addr 6 +  			\ return xt
				clearHi32				\ can get nonzero somehow
				flag_byte  $ 40 and
				IF  1  ELSE  -1  THEN	\ and flag (1 immed, -1 non-immed)
				EXIT
			THEN
		THEN

		lfa @ dup
		NIF			\ failed
			drop  string-addr false  EXIT
		ELSE
			++> lfa
		THEN
	AGAIN
;

forward  initFind

:f initFind  false  ;f

: FIND  ( str-addr -- xt flag  |  str-addr -- false )

	initFind  ?dup  ?EXIT
	<'> extraFind 2+ @abs @
	IF			\ extraFind has a non-default action set - let's execute it:
		extraFind	?dup  ?EXIT
	THEN
	dup thread displace
	(find)
;

[Whammo]

I imagine there are many optimizations for a fixed length string.

[burnsauce]

I hate to admit it, but FIND-NAME is almost useless and slows down FIND. Given that it's only used in wordlist.fs, a forth implementation could exist there, leaving it out of the core.

[burnsauce]

#426 addresses this for a ~32-cycle O(1) improvement of FIND

[burnsauce]

For measuring compilation speed, I am going to measure the time taken to include the following files:

• gfx - for its heavy use of the assembly words
• v - for the sheer size of its forth source

[Whammo]

What if we kept track of the first unique feature of each word?
A list of unique:
lengths,
last letters,
second to last letters,
etc.