Re: [Sbcl-devel] adjustable array speed

[Christophe R. <cs...@ca...>]

"Robert E. Brown" <bb...@sp...> writes:

> Inlining AREF and (SETF AREF) for simple arrays seems to result in a speedup
> of about a factor of 10.  That is, when I compare the execution speed of
> functions that use VECTOR-PUSH or AREF on adjustable arrays to similar
> operations on simple arrays (which get inlined), the former run about 10
> times slower than the latter.
>
> I noticed this recently while experimenting with a Lisp implementation of
> priority queues, which uses an adjustable array to implement a heap.  The
> code runs about 10 times slower than the C++ equivalent, in part because all
> the adjustable array access operations are roughly that much slower.  One
> could rewrite the code to use simple arrays, but then one would end up
> duplicating all the array size adjustment logic already inside Lisp
> adjustable arrays.
>
> Are adjustable array accessors just seldom used, and hence not often a speed
> bottleneck?  Because AREF, VECTOR-PUSH, and VECTOR-PUSH-EXTEND are not
> inlined when operating on adjustable arrays, they appear to always do
> argument type checking, which seems to account for their slower execution
> speed.

I seem to recall a compiler bug that was exercised when we had both
transforms for (simple-array * (*)) and for (vector t).  I think that
Alexey fixed it, but I don't think that the compiler transforms were
reinstated.

If the bug is indeed fixed, it would by no means be a problem to
introduce an inlining or other efficiency tweak, maybe conditional on
(> speed space) or somesuch.

Cheers,

Christophe
-- 
http://www-jcsu.jesus.cam.ac.uk/~csr21/       +44 1223 510 299/+44 7729 383 757
(set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b)))
(defvar b "~&Just another Lisp hacker~%")    (pprint #36rJesusCollegeCambridge)