3

Consider this simple example:

(deftype image nil '(simple-array single-float (100)))

Here we are defining a shorthand for a type that is an array that is holding single floats. Let us try creating one like that:

(defparameter tmp
  (make-array 100
              :element-type 'single-float
              :initial-element 0.0))

Let's check the type just in case:

CL-USER> (type-of tmp)
(SIMPLE-ARRAY SINGLE-FLOAT (100))

All good. Let us see if we could have those little arrays in another array, to make the retrieval easier, instead of putting everything into a single dimensional array and ending up having a headache calculating the access indexes.

(defparameter image-array
  (make-array 10
              :element-type 'image
              :initial-element tmp))

There is no way it is going to fail but checking just in case:

CL-USER> (type-of image-array)
(SIMPLE-VECTOR 10)

Oops, that is not what we want at all. Seems like this new array defaulted to the default element type:

CL-USER> (array-element-type image-array)
T

That likely means that the application will now have to type check not just the container array elements, but also the elements of child arrays with all the consequences for the performance. The questions that arises is this:

Is storing typed arrays as array elements in another array possible in SBCL?

EDIT: That might be a bit too early to panic though as this returns the right type:

CL-USER> (type-of (aref image-array 0))
(SIMPLE-ARRAY SINGLE-FLOAT (100))

In that case, why do we get T as the element type from (array-element-type image-array)?

Improve this question
2
  • As per the discussion below, in short, SBCL reports the elements of the outer array as T because inner arrays are reference type. It seems like it reports only primitive types as array elements, while reference types are upgraded to T. The type of the inner arrays will be reported correctly. Commented Aug 7, 2017 at 16:27
  • 1
    You should look at upgraded-array-element-type. Commented Aug 7, 2017 at 20:16

2 Answers 2

Reset to default
7

A bit background what ELEMENT TYPE actually means

If you give an element type to MAKE-ARRAY you ask the Common Lisp implementation to create an array with optimized space layout (!) which might be restricted to certain element types. You don't need to get an array for exactly this element type, but an array which is most space efficient in this implementation for this element type.

  • for numbers the implementation may have special versions for bits, 8 bit bytes, 16 bit words, 32 bit words and a few more.

  • it might have special versions for arrays of characters, like strings

  • it might have special versions for one or more float number types

Whether there are more depends on the implementation your are using.

For any element type which has not a special implementation, the element type gets upgraded to T. This means that the array can have all kinds of objects as elements and larger elements like arrays, strings, structures, CLOS objects, ... will always be stored as a pointer to the object on the heap.

A few examples for a certain implementation:

Integers

CL-USER> (upgraded-array-element-type '(integer 0 1))
(UNSIGNED-BYTE 1)                                                                                                                                                 
CL-USER> (upgraded-array-element-type '(integer 0 2))
(UNSIGNED-BYTE 2)                                                                                                                                                 
CL-USER> (upgraded-array-element-type '(integer 0 3))
(UNSIGNED-BYTE 2)                                                                                                                                                 
CL-USER> (upgraded-array-element-type '(integer 0 4))
(UNSIGNED-BYTE 4)                                                                                                                                                 
CL-USER> (upgraded-array-element-type '(integer 0 5))
(UNSIGNED-BYTE 4)                                                                                                                                                 
CL-USER> (upgraded-array-element-type '(integer 0 7))
(UNSIGNED-BYTE 4)                                                                                                                                                 
CL-USER> (upgraded-array-element-type '(integer 0 8))
(UNSIGNED-BYTE 4)                                                                                                                                                 
CL-USER> (upgraded-array-element-type '(integer 0 15))
(UNSIGNED-BYTE 4)                                                                                                                                                 
CL-USER> (upgraded-array-element-type '(integer 0 16))
(UNSIGNED-BYTE 8)                                                                                                                                                 
CL-USER> (upgraded-array-element-type '(integer 0 256))
(UNSIGNED-BYTE 16)                                                                                                                                                
CL-USER> (upgraded-array-element-type '(integer 0 4423423))
(UNSIGNED-BYTE 32)                                                                                                                                                
CL-USER> (upgraded-array-element-type '(integer 0 4423423423423))
(UNSIGNED-BYTE 64)                                                                                                                                                
CL-USER> (upgraded-array-element-type '(integer 0 4423423423423423423423423423423))
T

Characters 

CL-USER> (upgraded-array-element-type 'character)
CHARACTER

Floats

CL-USER> (upgraded-array-element-type 'single-float)
SINGLE-FLOAT                                                                                                                                                      
CL-USER> (upgraded-array-element-type 'long-float)
DOUBLE-FLOAT

Array

CL-USER> (upgraded-array-element-type 'array)
T

Even if you ask for more specific versions of arrays as elements, you very likely get T as an answer.

When to ask for a special array

The most important reason is to save space. If you have only bits, the general array can store bits, but a bit vector will save lots of space.

But: operations for arrays with special element types can be slower. At runtime in safe code there might be an additonal type check and the operations to change / read elements might need slower processor instructions.

Limitations of Common Lisp arrays

Thus Common Lisp does not have optimized storage layout for arrays of structures, vectors, CLOS objects, etc. Since there is a pointer for each element stored, access always needs an indirection and there is nothing that will guarantee that these objects are stored in linear order in memory. Stored in linear order are the pointers to them in the array.

Check your implementation whether it has optimized space layout for float (single, double, long, ...) arrays.

Multi-dimensional arrays

Common Lisp supports true multi-dimensional arrays with up to ARRAY-RANK-LIMIT (ABCL has max 8 dimensions on my ARM, some other implementations support more dimensions). These multi-dimensional arrays can also have specialised element types.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

4

Seems like an XY-problem: you'd better use a multidimensional array of floats:

(make-array (list width height) ...)

... then you do (aref matrix row column) and you don't have to compute indices. When you store an array inside an array, you still need to keep the metadata associated with each arrays, like the type of its elements, because you could be referencing each array from elsewhere. That's why the main array only store references and not raw floats.

Note also that the type that can be stored in an array can be a supertype of the declared type, due to array upgrading: System Class ARRAY.

Improve this answer

8 Comments

I suppose in this case two dimensional array will work better in regards of performance as one would be able to access the values in it directly compared to array-in-array approach that can only hold pointers to child arrays.
@Werdok Yes (but beware of premature optimization).
@Werdok You can also use "array-total-size" and "row-major-aref" to access the array as a flat one; I think it should be possible to use SBCL's generic sequences to manipulate a multidimensional array as a sequence using those functions; this looks like something fun to do.
You could also make a single-dimensional displaced array to map/read into.
@Werdok Yes, for perfomance displaced arrays will lose against manipulating the array directly. For real world usage you should try and profile both approaches to see if the convenience is worth the cost. In most application programming the extra allocation will be negligible, but for performance-sensitive applications it might not be a good idea.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.