fast arefs

[Barry Margolin <barmar@think.com>]

    Date: Thu, 7 Jan 88 18:40 EST
    From: Dan Aronson <Dan@Think.COM>

    Does anyone know how to do really fast arefs on the lispm (even faster than
    sys:array-register).  I have complete control over my arrays, I can wire
    them down if necessary.  

The answer probably depends on the context.  What is the element type of
the array (pointers probably will only help if they are integral words)?
Are you looping over the elements of the array or referencing an
individual element frequently (as when arrays are used to hold
structures).  How many times do you reference the same array element?

    I have found sys:%make-pointer-offset and
    sys:%p-contents-increment-pointer, which probably play a role, but I don't
    know how to use them.  Has anyone had any experience trying to do this?

Well, if you're trying to speed up iteration over an array, and the
thing that bothers you is the repeated pusing of the index,
sys:%p-contents-increment-pointer seems to be what you want.
(sys:%p-contents-increment-pointer local-var) appears to be equivalent to

      (progn
	(setq local-var
	      (sys:%make-pointer-offset sys:dtp-locative
					local-var 1))
	nil)

but it compiles into a single instruction; it's the moral equivalent of
C's pointer++ (except that it doesn't also return a useful value).  A
really fast loop over an array could be written

(loop with cur-ptr = array
      with end-ptr = (sys:%make-pointer-offset sys:dtp-locative array
					       (1- (sys:%structure-total-size array)))
      until (eq cur-ptr end-ptr) do
  (sys:%p-contents-increment-pointer cur-ptr)
  (do-something (location-contents cur-ptr)))

Note that the compiled code for the above loop is only two instructions
shorter than the loop generated by

	(loop for x being the array-elements of array do
	  (do-something x))

It's 8 instructions vs. 10, so I guess a 20% speedup of an inner loop is
nothing to sneeze at, although this assumes that (do-something x) is
trivial (like stuffing the element down the channel to the Connection
Machine?).

I suspect that wiring the array down won't be necessary.  If your inner
loop is short it is extremely unlikely that the current page would be
discarded while you are using it.  Wiring the array would prevent a
pause in the middle of the loop, but the total time taken by the
operation will be the same (you either wait for each page as you need
it, or wait for them all at the beginning of the loop); you might be
able to speed this up a bit by using SYS:PAGE-IN-ARRAY with HANG-P =
NIL, so that the paging system would effectively anticipate the page
faults.

                                                barmar