autodispatching method trees

[Eugen Leitl <ui22204@xxxxxxxxxxxxxxxxxxxxxxx>]

Autodispatching trees.


Recently I realized one can do autodispatching method trees,
which is especially efficient on threaded code machines as
Chuck's chips.

Code would thread through branches, alternatives selected by
data on TOS.

E.g. if we are to implement a variable-resolution mutation map
for a GA, we can automagically dispatch the mutation code (e.g.
take a rand, mutate position if rand is smaller then entered
value) using one integer index on TOS letting the work be done
directly by code.

This is the elementary structure for a binary tree:


		    /\
		   /  \
		  /\  /\
		      etc.

+---------------+-----------+------------+
| CALL dispatch | CALL left | CALL right |  ( branching node )
+---------------+-----------+------------+

Selection is terminated ("grounding") by direct calling the
appropriate method. For termination with noop method, dummy
method air is used.

: air  drop pop drop ; ( drop TOS, drop last return adress, return )
 ( a -- )

Hence terminating tree branches are compiled as CALL air. There
is only one dispatch method for the whole structure. It can
dispatch via relative addressing and knowledge what branches
stand at two subsequent addresses.

: dispatch ( a -- b )

  shift left			      ( shift out MSB bit )
  return; if shifted out bit is zero  ( CALL left if zero )
  pop return address to TOS	      ( CALL right if one )
  increment TOS 		      ( tweaking return address )
  push TOS to return stack
  ;

The pluses of above scheme are vastly reduced tree traverse
times: we use a hardware traverser (processor) using only one
test statement for each bifurcation selection. The minus is
additional space due to one CALL statement per pair and
necessity to write code by program. Cheap, imo.

A much better application would trying to detect which object is
clicked/selected/etc. on screen. We have to find the object at
that x,y position, find the appropriate method (method select as
offset) and call it. We use event,x,y on TOS and a quadtree to
dispatch event to the right object. Each screen object may have
automagical tree surgery invocation when its properties (size,
position) are changed as a result of previous event. Node
entries can be reclaimed either explicitly or by a gc.

: air drop drop drop pop drop ; ( dummy thread terminating method )

: dispatch
   extract MSB bits from x and y
   pop return address, increment it by following table:

			  +----+----+
   00 0 		  | 00 | 01 |  select codes for
   01 1 		  +----+----+  each branch of four
   10 2 		  | 10 | 11 |
   11 3 		  +----+----+

   ;

The structure is now:

CALL dispatch  CALL 00	CALL 01  CALL 10  CALL 11

Notice that the store fraction between dispatching code and
pointers is much better now.

A coarse grained method map (array, quadratical pixel blocks of
length 2,4 or 8 for each method, method pointers autopainting)
might be better for 2d. For 3d this won't do: array size would
be too big by far.

An octree dispatch is much better:

MSB Bit combintations: 000, 001, 010, 011, 100, 101, 110, 111
according offsets:	 0    1    2	3    4	  5    6    7

event, x, y, z on TOS

If in VR we want to let an object know it has been clicked (e.g.
I want to apply some operation upon a particular amino acid in a
protein structure, positioning cursur with a 6DOF mouse and
triggering according action), octree dispatch is fastest. The
same structure can be used for a fast renderer, deciding whether
light ray hits upon an object or not and causing the appropriate
action.

		   ________
		  /   /   /
		 /---+---/|   space slab recursively cut in
		/___/___/|/   eight compound subslabs
		|   |	|+|
		|---+---||/
		|   |	|/
		+---+---+

Any comments?

-- eugene