[Openmcl-devel] Cost of AREF?

[Stas Boukarev]

Some of the slow down appears because of dotimes,
try (dotimes (index (the fixnum (length coefficients))) ...)

On Sat, Oct 26, 2019 at 7:43 AM Steven Nunez <steve_nunez at yahoo.com> wrote:
>
> Does anyone know if AREF is an 'expensive' operation? I've got two versions of a function that differ, mostly, in what they loop over:
>
> (defun ep1 (coefficients x)
> "SIMPLE-ARRAY version of coefficients."
>   (declare (double-float x)((simple-array double-float) coefficients)
>        (optimize(speed 3)(safety 0)))
>   (let ((sum 0d0))
>     (declare (double-float sum))
>     (dotimes (index (length coefficients))
>       (setf sum (+ (aref coefficients index)
>                 (* x sum))))
>     (the double-float sum)))
>
> (defun ep2 (coefficients x)
> "LIST version of coefficients."
>   (declare (optimize(speed 3)(safety 0)))
>   (assert (typep coefficients 'list) () "COEFFICIENTS must be a LIST")
>      (let((sum (car coefficients)))
>        (declare (double-float sum x))
>        (loop for i double-float in (cdr coefficients)
>       do (setf sum (+ i (* x sum))))
>        sum))
>
> The list version executes faster than the simple-array version, which I find surprising. Not by a great deal, but consistently faster. As I understand the layout of the LIST version, the double-float is in the CAR of the CONS, saving a pointer dereference to get the value, but the loop still needs to dereference the CDR pointer. In the SIMPLE-ARRAY version, the DOUBLE-FLOATS are laid out in contiguous memory, which in theory should be faster to access. I think I've seen similar behaviour before, with loops over short lists out-performing arrays up to a certain length.
>
> The only thing I can think of is that AREF might be a more expensive operation than reading the car, so for short lists the pointer dereferencing doesn't make a significant difference. Does that sound like a reasonable theory?
> _______________________________________________
> Openmcl-devel mailing list
> Openmcl-devel at clozure.com
> https://lists.clozure.com/mailman/listinfo/openmcl-devel