[Sbcl-help] Displacing multidimensional arrays seems slow; is there a way to speed it up?

[Shubhamkar Ayare via Sbcl-help]

Consider the following function to construct a displaced array:

(defun displace (array dimensions offset)
(declare (optimize speed))
(make-array dimensions
:displaced-to array
:displaced-index-offset offset
:element-type (array-element-type array)))

Then, displacing a 2 or 3 dimensional array seems 10 times slower than a 1-dimensional array.

CL-USER> (let ((a (make-array 10000 :element-type 'single-float)))
(time (loop repeat 100
do (loop for i below 100 do (displace a 100 i)))))
Evaluation took:
0.028 seconds of real time
0.027223 seconds of total run time (0.011161 user, 0.016062 system)
96.43% CPU
60,118,594 processor cycles
655,312 bytes consed
NIL

CL-USER> (let ((a (make-array '(100 100) :element-type 'single-float)))
(time (loop repeat 100
do (loop for i below 100 do (displace a 100 i)))))
Evaluation took:
0.248 seconds of real time
0.247534 seconds of total run time (0.243644 user, 0.003890 system)
[ Run times consist of 0.006 seconds GC time, and 0.242 seconds non-GC time. ]
100.00% CPU
544,595,372 processor cycles
383,365,264 bytes consed
NIL

CL-USER> (let ((a (make-array '(10 10 100) :element-type 'single-float)))
(time (loop repeat 100
do (loop for i below 100 do (displace a 100 i)))))
Evaluation took:
0.244 seconds of real time
0.243558 seconds of total run time (0.227575 user, 0.015983 system)
[ Run times consist of 0.007 seconds GC time, and 0.237 seconds non-GC time. ]
100.00% CPU
536,291,788 processor cycles
354,713,920 bytes consed
NIL

Is there a way to speed the multidimensional cases more? This becomes important
because the array-operations library relies quite a bit on constructing
displaced arrays[1].

Regards,
Shubhamkar

1. displace function in array-operations library:
https://github.com/Lisp-Stat/array-operations/blob/master/src/displacing.lisp
2. Formerly, https://github.com/tpapp/array-operations/blob/master/src/displacement.lisp


_______________________________________________
Sbcl-help mailing list
Sbcl...@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/sbcl-help

[Stas Boukarev]

There's a way. I'll implement it after the freeze. But if you really want arrays to be fast you shouldn't use displaced arrays.

[Shubhamkar Ayare via Sbcl-help]

That'd be great, thank you!

And, about the speed, I think there are two aspects here: in terms of access
performance through a naive CL:AREF, simple arrays would definitely be faster
than displaced. However, in terms of creation, I'd expect displaced arrays to be
faster to create especially as their size gets larger because creation of simple
arrays would also involve a component of copying over the contents.

Even for the access, vectorized access - first obtain the underlying
array/vector and the offset through multiple calls to CL:ARRAY-DISPLACEMENT and
perhaps SB-EXT:ARRAY-STORAGE-VECTOR and access the storage vector directly - of
displaced arrays can be almost as fast as simple arrays.