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

[Alexander Repenning]

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.

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