[Openmcl-devel] Lisp versus JavaScript (was: list - vector)

Mon May 18 19:08:46 PDT 2009

On Sun, 17 May 2009, Alexander Repenning wrote:

> Computational complexity. Random array access is done in constant time
> whereas random list access is done in linear time. If you need random
> access then lists are generally a bad idea. Of course, that constant
> time can vary a lot. svref can be pretty fast but aref is a
> notoriously slow access function for multidimensional arrays compared
> to, say, C.

Among the reasons that SVREF tends to be faster than AREF are:

   - it asserts that the array in question is SIMPLE (not displaced, not
     adjustable, etc.)

   - it asserts that the array in question has an element type of T (not
     BIT, not CHARACTER, not some subtype of FLOAT or INTEGER ...)

A fully safe SVREF can basically validate these assertions (which in this
case amount to checking that its first argument is a SIMPLE-VECTOR) and
validate the implicit assertion that its second argument is a valid vector
index for the first arg, then execute a simple LOAD instruction.  In most
CL implementations,

(defun foo (a i)
   (svref a i))

(defun bar (a i)
   (declare (type simple-vector a))
   (aref a i))

will compile to exactly the same code (and that code will test the
implicit and explict assertions about A and I and then do a simple
LOAD instruction.)

A third case:

(defun baz (a i)
   (aref a i))

will have to discover (at runtime) whether or not A is some sort of
vector or not (since that's all that's being asserted), whether or not
it's "simple" or not (and what this means is somewhat implementation
dependent), what it's element-type is, and what sort of LOAD
instruction ("load word", "load byte", "load bit", "load signed byte",
"load single-float", ...) needs to be executed.  If BAZ's A argument
is in fact a SIMPLE-VECTOR, we'll wind up executing the same simple
LOAD instruction as in the other cases (where that's asserted), but
it'll take us a while to realize that.  ("a while" is probably "a few
times the cost of the LOAD" in this case.)

If CL had only a single array type (say, something like a
SIMPLE-VECTOR, but possibly with a single level of displacement to
support "growing", and with vectors of vectors used to simulate
multidimensional arrays), then AREF would always be a simple,
easily-inlined operation whose naive use would offer C-like
performance.  (Unfortunately, we'd all be stuck with nothing
but Javascript-like arrays in that case.)

The traditional way of trying to optimize things like AREF (when
nothing much is known about the array)  is to cache information
about the array (outside of a loop, for instance) and transform
the AREF into someting simpler that uses that cached information.
(I believe that the Lisp Machines did this and called the cache
an "array register"; Fortran implementations (Fortran arrays tend
to be much higher-level things than C arrays) often call the cache
a "dope vector."  Hiding some of the details, the idea would be to
transform something like:

(let* ((sum 0))
   (dotimes (i (length a)) (incf sum (aref a i))))

into something like

(let* ((sum 0)
        (f (%get-1d-aref-function-for a)))
   (dotimes (i (length a)) (incf sum (funcall f a i))))

If A turns out at runtime to be a SIMPLE-VECTOR, then
%GET-1D-AREF-FUNCTION-FOR might return something like SVREF; if it's a
SIMPLE-STRING, then a simple version of SCHAR may be returned (and the
"function" might be something that's not quite a full-blown lisp
function, called by something not quite as general as FUNCALL.)

Whether and how much this wins depends (on things like what type of
array A actually turns out to be, on how many times the loop actually
executes, and other things.)  If it does win (compared to just a naive
AREF), it's still not likely to produce code that's nearly as good as
that in which the compiler's involved a bit more (e.g., where there
are declarations about the array's simplicity and element-type.)

This (the cache/dope-vector/array-register idea) is certainly worth
exploring (as are similar things which remove redundant operations from
loops.)  There are probably limits to how much better you can make things
when the compiler's not aware of the array's element-type (at least.)

The general way in which one makes calls to AREF faster in CL is to
let the compiler transform those calls into something simpler (SVREF
or SCHAR or SBIT or %SIMPLE-UNSIGNED-BYTE-16-REF or
%SIMPLE-DOUBLE-FLOAT-REF or ...), and doing that transformation at
compile-time (on the basis of declarations and/or inferred type
information) is preferable to doing it at runtime (and obviously
better than doing it repeatedly at runtime, in the middle of a loop.)
CCL does a fairly good job of getting to and sometimes beyond that
starting point if AREF's first argument is declared to be a
SIMPLE-ARRAY of specified element-type (and I'd like to be able to do
some things involving arrays not explicitly declared to be SIMPLE
arrays in the next version.)

If you're starting from the assumption that #'CL:AREF (without any
compile-time assertions) is somehow analogous (performance-wise or
otherwise) to an array-reference operator in a language with one array
type, you probably won't get very far very fast; that's simply not
a reasonable assumption.  In my mind, this is the sort of thing that
every serious CL programmer should know (though I admit to not being
entirely clear on how this knowledge is to be acquired; I imagine that
most of what's written about it tends to be excruciatingly implementation-
dependent.)   I don't think that anyone who's programmed in CL thinks
that #'CL:+ is directly analogous to C's addition operator (on explicitly
typed operands), and CL programmers somehow learn that declaring the
types of CL:+'s operands (and in some cases the type of the result) can
greatly improve performance (especially when the type in question is
FIXNUM.)

If people honestly don't realize that there are similar issues with AREF,
that's certainly surprising.

>
> So far, that did not bug me too much, but recently, but thanks to some
> Apple involvement, even the "slow" scripting languages such as
> JavaScript are getting amazingly fast. For instance, I was really
> quite shocked to see the performance of JavaScript in game of life here:
>
> http://o3d-life.googlecode.com/svn/trunk/life.html
>
> You need to have the newest JavaScript engines, e.g. the one in Safari
> 4 to get the full speed.
>
> I wondered if Lisp (CCL) can still match this. I intentionally did not
> use any declarations and optimizations to roughly approximate the
> JavaScript. You can find the result as "game of life.lisp" XMLisp
> example here: http://code.google.com/p/xmlisp/
>
> At any rate, Lisp had a very hard hard time to match the JavaScript
> performance. The COUNT-LIFE function including many Aref array
> accesses is the main bottleneck. If you replace the call to (count-
> life Self i j) with (random 9) the frame rate shoots up 4x. This is
> not surprising but the fact that JavaScript can about match the Lisp
> performance is.
>
> Alex
>
>
>
> On May 17, 2009, at 3:42 PM, Joakim Sandgren wrote:
>
>> Hi,
>> It seems to me that the speed relations list/simple-vector has
>> changed in ccl in comparison with mcl.
>>
>> in mcl, the list was always faster until you wanted a element quite
>> deep into a long list.
>>
>> now, in ccl I did a dotimes test where I took the 100s element of a
>> list using nth
>> and the 100 element of a simple-vector using svref.
>> The vector was much faster.
>> This was the normal relation in mcl too.
>>
>> Then I took the 4th element in the same list (still with nth)
>> and the 4th element of the same vector with svref
>> and the vector is still clearly faster!!
>> This is new to me.
>>
>> Should I abandon lists? And start to do everything in vectors?
>> Sometime in my project code I have some "heavy" searching fetching
>> elements with search criteria in many quite long lists.
>> And this do take some time sometimes.
>> Again, should I start to use vectors, in ccl?...
>>
>> Sincerely
>> Joakim
>>
>>
>>
>>
>> Joakim Sandgren
>> joakim sandgren musik
>> 42, rue de Maubeuge
>> 75009 Paris
>> France
>> +33 (0)1 45 26 43 90
>> info at joakimsandgren.com
>> http://www.joakimsandgren.com
>>
>> _______________________________________________
>> Openmcl-devel mailing list
>> Openmcl-devel at clozure.com
>> http://clozure.com/mailman/listinfo/openmcl-devel
>
> Prof. Alexander Repenning
>
> University of Colorado
> Computer Science Department
> Boulder, CO 80309-430
>
> vCard: http://www.cs.colorado.edu/~ralex/AlexanderRepenning.vcf
>
>
> _______________________________________________
> Openmcl-devel mailing list
> Openmcl-devel at clozure.com
> http://clozure.com/mailman/listinfo/openmcl-devel
>
>