fast arefs

["Robert W. Kerns" <RWK@scrc-yukon.arpa>]

    Date: Fri, 8 Jan 88 00:09 EST
    From: 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?
Appropriate questions.
    
	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)

No, no, it's really equivalent to
    
(progn
  (setq local-var
	(sys:%make-pointer-offset sys:dtp-locative
				  local-var 1))
  (sys:%p-contents-offset local-var 0))

Note carefully that it's pre-increment, not post-increment.
So you want to start off with a pointer that's one 1before0 the
one you want to read.

    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)))

;;; assuming a vector; but the general case isn't much harder.
(loop with cur-ptr = (sys:%make-pointer-offset sys:dtp-locative (locf (aref array 0)) -1)
      with end-ptr = (locf (aref array (1- (length array))))
      until (eq cur-ptr end-ptr) do
  (do-something (sys:%p-contents-increment-pointer 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
Try 5 instructions vs 8.

    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.

But wiring (or explicitly paging in) the array will cost more time than
you'll save by writing the loop to be maximally fast, if the array is at
all small!  If the array is small, you're better off just letting the
paging system page it in.  Otherwise, your advice is right.  Wiring the
page is unlikely to buy you anything, unless you are looking for
real-time respose, and then only if you're going to be doing repeated
accesses separated in time, with other paging going on between.