joakim at joakimsandgren.com
Tue May 19 04:25:03 EDT 2009
I just wanted to say that I just made a new mailbox in mail to keep
these kind of answers from Gary. That is like having a master jedi
answering with a lecture to your own little stupid question
empiriquement found in the try and error world...
I will do some other "try's" and will come back on this to know more...
Le 19 mai 09 à 04:08, Gary Byers a écrit :
> On Sun, 17 May 2009, Alexander Repenning wrote:
>> Computational complexity. Random array access is done in constant
>> 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,
> adjustable, etc.)
> - it asserts that the array in question has an element type of T
> 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)
> validate the implicit assertion that its second argument is a valid
> 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
> 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
> loops.) There are probably limits to how much better you can make
> 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
> dependent.) I don't think that anyone who's programmed in CL thinks
> that #'CL:+ is directly analogous to C's addition operator (on
> typed operands), and CL programmers somehow learn that declaring the
> types of CL:+'s operands (and in some cases the type of the result)
> greatly improve performance (especially when the type in question is
> If people honestly don't realize that there are similar issues with
> that's certainly surprising.
>> So far, that did not bug me too much, but recently, but thanks to
>> 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
>> 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
>> performance 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
>> vCard: http://www.cs.colorado.edu/~ralex/AlexanderRepenning.vcf
>> Openmcl-devel mailing list
>> Openmcl-devel at clozure.com
joakim sandgren musik
42, rue de Maubeuge
+33 (0)1 45 26 43 90
info at joakimsandgren.com
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Openmcl-devel