🚀 go-pugleaf

Fernando Pereira actually said something extremely encouraging to me:
he said that there were algorithms where something "one or two orders
of magnitude faster" than N+K trees was needed (hence arrays).

Now, my claim that N+K trees are a practical alternative to arrays is
to be understood as a claim that a particular *data structure* (which
can be inspected and manipulated as a plain Prolog data structure if
need be) is a practical alternative.  That's all.  The claim is that
a data structure is ok, not that it shouldn't be built in.

Here's what I have in mind.  3+4 trees represented as perfectly ordinary
Prolog terms can nevertheless be manipulated by built-in predicates that
are implemented in hand-optimised machine code.  The observable behaviour
of such built-in predicates would be exactly the same as the observable
behaviour of appropriate Prolog code, but it could be a lot faster.  In
fact, the attainable speedup is in exactly the "one or two orders of
magnitude faster" ballpark that Fernando says we need.

I haven't got all the figures I want yet.  But on an Encore Multimax
(NS32532), plain ordinary C code (not hand-optimised assembler) gave
me the following average times to access any element of an N-element
array represented as an 3+4 tree:
	N =        10   t =  8 usec
	          100	    12 usec
	        1,000	    16 usec
	       10,000	    20 usec
	      100,000	    24 usec
	    1,000,000	    29 usec
That's about a 4usec increase for every 10-fold expansion of the array.
The C code behaved exactly like get_label/3 on p143 of the book, and this
time does include loops to dereference, type checks, checks that the
nodes of the tree have the right functor, and preparation to build missing
parts of the tree and so on.

I repeat, this is plain ordinary C code.  Hand-optimised assembly code
should be able to do somewhat better (at a rough guess, 3 usec steps
rather than 4 usec, so that 1,000-element "arrays" might cost 13-usec
per element access).

There are more measurements to be made, but it looks as though 3+4
trees _are_ a practical alternative to arrays _if_ they are implemented
well.

-- 
Fixed in the next release.