Standard structures in common lisp are always pointers. This is not the best practice in terms of performance, as it commonly results in cache miss when you loop across several objects.
Immediate structures can be represented by a contiguous memory block. For example, with immediate structures:
(defstruct a x y z)
(make-array 5 :initial-element (make-a))
will results in a memory structure that looks like below:
x1 y1 z1 x2 y2 z3 z3 y3 ....
It is also known that this is sometimes not the best solution in terms of speed.
Imagine a program which needs to handle only the slot x in the loop. Since the cache memory is limited, It is better to allocate each slot in a separate contiguous memory array as follows:
The drawback of this method is obviously the same problem which appears in C: No trivial garbage collection is available. To remove an element (during GC), you should resize the memory array or even copy the entire array; One way to address this is to have several chunks of short arrays, but this would require #4. To manage GC, you need a boxed value managed by a finalizer which frees the memory cell in the array.
You can sometimes avoid this drawback.
When the number of structures is fixed, garbage collection is unnecessary.
also, when the number is small, you can have an "ignore" bit that you can skip the element.
Related: manardb http://quickdocs.org/manardb/ seems to have accomplished the first goal (immediate structures). I do not know about the column-based alignment.
Standard structures in common lisp are always pointers. This is not the best practice in terms of performance, as it commonly results in cache miss when you loop across several objects.
Immediate structures can be represented by a contiguous memory block. For example, with immediate structures:
will results in a memory structure that looks like below:
It is also known that this is sometimes not the best solution in terms of speed. Imagine a program which needs to handle only the slot
xin the loop. Since the cache memory is limited, It is better to allocate each slot in a separate contiguous memory array as follows:The drawback of this method is obviously the same problem which appears in C: No trivial garbage collection is available. To remove an element (during GC), you should resize the memory array or even copy the entire array; One way to address this is to have several chunks of short arrays, but this would require #4. To manage GC, you need a boxed value managed by a finalizer which frees the memory cell in the array.
You can sometimes avoid this drawback.
Related: manardb http://quickdocs.org/manardb/ seems to have accomplished the first goal (immediate structures). I do not know about the column-based alignment.