trivial-adjust-simple-array
2024-10-12
A tiny utility to change array size ensuring it is simple.
1trivial-adjust-simple-array
trivial-adjust-simple-array is a tiny simple Common Lisp utility library providing ADJUST-SIMPLE-ARRAY macro to change given SIMPLE-ARRAY size in a manner regular ADJUST-ARRAY does, while ensuring that the resulting array is still simple array. In other words, the following assertions are always correct:
(let ((adjusted-array (trivial-adjust-simple-array:adjust-simple-array
some-array some-new-size
:element-type 'some-array-element-type)))
(assert (null (array-displacement adjusted-array)))
(assert (null (array-has-fill-pointer-p adjusted-array)))
(assert (null (adjustable-array-p adjusted-array))))
trivial-adjust-simple-array also provides ADJUST-SIMPLE-ARRAYF modify macro akin to INCF and similar which can save you some typing:
(trivial-adjust-simple-array:adjust-simple-arrayf
my-array new-size
:element-type 'some-element-type :initial-element 0)
;; replaces my-array with its enlarged or shrunk version, keeping contents in place
;; and setting uninitialized elements to 0
1.1Installation
For now, you'll have to install LuckyLambda Quicklisp distribution (assuming you have Quicklisp installed) by executing the following in your Lisp : (ql-dist:install-dist "http://dist.luckylambda.technology/releases/lucky-lambda.txt")
Alternatively, just clone this repository to your Quicklisp's local-projects directory.
After that, just execute (ql:quickload :trivial-adjust-simple-array) in your Lisp.
1.2Supported implementations
This library is extremely portable and currently has been tested to work in following Common Lisp distributions:1.3Why?
Since its conception, Common Lisp had pretty advanced array types, which allowed:- sharing data with other arrays (essentially providing shallow copies), called displaced arrays;
- changing number of elements without touching underlying storage, by using fill pointer feature;
- changing storage size on the fly without shuffling element data around with the help of expressed adjustability feature.
The problem is that on many Common Lisp implementations, even accessing elements of such fancy shmancy arrays is much slower compared to regular SIMPLE-ARRAY with no advanced features, which is demonstrated by the following benchmark program:
(ql:quickload :trivial-benchmark)
(defun sum-simple-array (array)
(declare (type (simple-array (unsigned-byte 32)) array)
(optimize (speed 3) (safety 0)))
(loop :with s :of-type (unsigned-byte 32) := 0
:for x :of-type (unsigned-byte 32) :across array
:do (incf s x)
:finally (return s)))
(defun sum-advanced-array (array)
(declare (type (array (unsigned-byte 32)) array)
(optimize (speed 3) (safety 0)))
(loop :with s :of-type (unsigned-byte 32) := 0
:for x :of-type (unsigned-byte 32) :across array
:do (incf s x)
:finally (return s)))
(let* ((size 5000)
(simple-array (make-array size :element-type '(unsigned-byte 32)
:initial-element 42))
(advanced-array (make-array size :element-type '(unsigned-byte 32)
:initial-element 42
:fill-pointer size
:adjustable t)))
(trivial-benchmark:with-timing (10000)
(sum-simple-array simple-array))
(trivial-benchmark:with-timing (10000)
(sum-advanced-array advanced-array)))
Here are some results of that benchmark (higher is worse):
| Lisp implementation | sum-simple-array total | sum-advanced-array total |
|---|---|---|
| SBCL 2.4.5 | 0.034 | 0.221 |
| Clozure CL 1.12.2 | 0.207 | 0.565 |
| ABCL 1.9.2 | 0.111 | 0.323 |
| Allegro CL 10.1 | 0.337 | 0.496 |
| LispWorks 8.0.1 | 0.214 | 0.362 |
As we can see, acessing simple arrays is in some cases almost order of magnitude faster. So it would've been nice to have the array with performance characteristics of SIMPLE-ARRAY, yet sometimes occasionally reallocate it (for instance, to accomodate for more elements). Unfortunately, not all implementations keep arrays simple after call to ADJUST-ARRAY, which can be demonstrated by the following bit of code:
(print (type-of (adjust-array
(make-array 1 :element-type '(unsigned-byte 32)) 2
:element-type '(unsigned-byte 32))))
Not pointing fingers, but those implementations are ECL, MKCL, Clasp and Allegro CL. This is where this tiny library shines: it provides ADJUST-SIMPLE-ARRAY macro (to be used instead of ADJUST-ARRAY) which is guaranteed to return simple array with old data. Besides, it provides super convenient ADJUST-SIMPLE-ARRAYF modify macro that can be used to reallocate simple array in-place.