[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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?
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
No, no, it's really equivalent to
(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
(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
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
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
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.
- fast arefs
- From: Barry Margolin <email@example.com>