ralex at cs.colorado.edu
Sun May 17 22:15:39 EDT 2009
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
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
example here: http://code.google.com/p/xmlisp/
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
On May 17, 2009, at 3:42 PM, Joakim Sandgren wrote:
> 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?...
> Joakim Sandgren
> joakim sandgren musik
> 42, rue de Maubeuge
> 75009 Paris
> +33 (0)1 45 26 43 90
> info at joakimsandgren.com
> Openmcl-devel mailing list
> Openmcl-devel at clozure.com
Prof. Alexander Repenning
University of Colorado
Computer Science Department
Boulder, CO 80309-430
More information about the Openmcl-devel