Re: [colorforth] DOES> How is colorForth different from other Forths?

["Samuel A. Falvo II" <kc5tja@xxxxxxxx>]

On Sunday 14 December 2003 12:36 pm, Jeff wrote:
> 0 constant struct
>
> : field ( n -- n ) dup create , 1+ does @ cells + ;
> : end-struct ( n -- ) create , does create @ cells allot ;

As far as I have learned from prior demonstrations and documentation, 
Chuck doesn't condone the use of structures, which is a pity in the 
sense that x86 architecture is optimized for them and an x86 machine 
Forth ought to also exploit that.  Nonetheless, vectors are too often 
overlooked, and have a number of advantages over structures.

Structures are best applied in the following situations:

1) You do not know the number of records in a database at design-time, 
much less compile-time.  These situations often occur when developing 
software to run in highly dynamic environments (e.g., operating systems, 
web browsers, word processors, etc).

2) When the performance of searching for an item is not a concern, but 
working directly with a relatively small number of related data is more 
important.  This is why caches were created, in fact: to keep related 
data local to the microprocessor.

Vectors really shine in the following cases:

1) You have a fixed number of items, known (at the latest) at 
compile-time.

2) Scanning/searching for items are more important than directly 
manipulating the fields. (e.g., scanning the Forth/Macro dictionary in 
ColorForth)

3) You work with a *lot* of items of the same type, often in a batch-like 
manner (e.g., netlists in OKAD-II for example).

Since structure access in Forth involves explicitly adding offsets 
(especially if you're walking down several layers of structures (A -> B 
-> C -> Field)), this adds execution time to the program unless you have 
a sufficiently smart-enough compiler.  Since ColorForth and MachineForth 
are intended to be very simple (generally speaking), it's preferred not 
to do this.  Working with vectors in Forth generally results in code 
that is equal in performance, if not faster, than structure-based code, 
and yet, is more readable and understandable to the coder.

For example, if your database has three fields (name, address, phone 
number, for example), then it makes sense to use three vectors (an array 
of names, an array of addresses, and an array of phone numbers).  
Scanning for a record is actually quite a bit faster this way, as more 
of what you're looking through is packed into a single cache line.

This is why FS/Forth has its most bizarre dictionary format.  It consists 
of two vectors: the first vector is a vector of <count, A, B, C> 
records, where A..C match the first three letters of a word's name 
(Chuck should remember this!).  Scanning this vector is incredibly fast, 
as a single 32-bit compare is used to rule out most word names when 
scanning the dictionary.  As FS/Forth permits up to 1024 words to be 
defined in the Forth dictionary, and 512 words in the Compiler 
dictionary (sorry, I don't think `macro' is an apt name for such words), 
we're looking at 6KB of memory used to store these two vectors in their 
entirety.

Assuming a match is made, the second vector is used to verify the match.  
The second vector is a vector of <D..O, address> *structures*, where 
D..O correspond to the fourth through 15th letters of a word's name.  
Note that the overhead of accessing a structure is avoided until it's 
actually necessary.  Even when necessary, the access patterns are quite 
deterministic: a pointer to a word structure starts at the beginning, 
and after comparing the word's name, it's automagically points to the 
word's CFA.  Note that each structure is 16 bytes long; again, this is 
due to cache considerations.

(Thus, while FS/Forth can handle 256-letter long names, only the first 15 
characters are considered relavent for searching purposes.  I don't 
expect this to be an issue for quite some time.)

--
Samuel A. Falvo II


---------------------------------------------------------------------
To unsubscribe, e-mail: colorforth-unsubscribe@xxxxxxxxxxxxxxxxxx
For additional commands, e-mail: colorforth-help@xxxxxxxxxxxxxxxxxx
Main web page - http://www.colorforth.com