Improving CLOS memory-efficiency in Common Lisp?

CONTEXT:

I've started a long-term project in CL, and one of the subcomponents is a framework for lazy programming, which is meant to be as compatible as possible with external CL code.

One of the classes is lazy-cons.

(defclass lazy-cons (thunk sequences:sequence)
  ((head :initform nil :initarg :head :accessor :head)
   (tail :initform nil :initarg :tail :accessor :tail))) ;; slot 'gen is defined in the thunk superclass, as well

However, when trying to sort lazy lists of more than 1 million numbers, SBCL constantly runs out of heap space and crashes.

Attempted approaches:

I've implemented another class that reduces this issue via cache vectors.

But I'd still like to make lazy-cons itself more space-efficient, as this project is meant to be a background framework for other computing projects, some requiring high-performance computing. Even if the highest-performance code ends up passed to CFFI, the Lisp side should still be as efficient and scalable as possible.

For this project, I also need to be able to extend classes and use defmethod to specialize some functions (e.g. so I can use the trivial-extensible-sequences library). This precludes using structures for smaller representations, as the structure metaclass doesn't allow inheritance from normal classes.

PROBLEM:

Is it possible (e.g. via MOP, maybe?) to control objects' internal representation to be more efficient, while still allowing class inheritance and method specialization?

And if not, is there some way to at least keep the Lisp implementation from running out of heap space?

(I'm aware that you can increase the allocated heap, but that still doesn't guarantee that you won't unexpectedly fall into LDB; ideally, the code should fall into a condition (which can be automatically addressed) when the heap is about to fail, instead of just collapsing.)

Summary: there probably is not much you can usefully do, but it seems at least plausible that your problem is something else.

How much memory do things take up in SBCL?

On a 64-bit platform (well, specifically on ARM64 although I think x64 is the same), here are empirical allocations for various object types (these are worked by allocating a big array and seeing how much space that takes, then allocating a big array and filling it with many copies of various objects, seeing how much space that takes and then doing the appropriate arithmetic, and checking it all makes sense):

• instances of standard-class – 48 bytes + 16 bytes per pair of slots;
• instances of structure-class – 16 bytes + 16 bytes per pair of slots;
• arrays with element type t – 16 bytes + 16 bytes per 2 elements;
• strings – 16 bytes + 16 bytes per 4 characters;
• arrays with element-type single-float – 16 bytes + 16 bytes per 4 elements.
• cons – 16 bytes.

The 'n bytes per m elements' comes about because allocation happens on double-word (16-byte) boundaries.

Instances of classes which inherit slots from one or more superclasses don't require more space for them, and don't have bigger headers.

What this shows is that the standard CLOS representation of slots is really as good as it can be if you need to keep non-immediate objects (or large immediate objects, like fixnums say) in the slots.

You probably cannot easily save much memory

Assuming you do want to do that which I'm fairly sure you do, then the only way you can win is by saving the header overhead, which is really an extra four words (32 bytes) for a default CLOS object. My guess is that this is a hopeless endeavour: that header is there for a reason, and you're unlikely to be able to make it go away other than by major surgery.

But is this the real problem?

But the problem you're having is quite surprising: the overhead of a million fully-fledged standard-class instances over the best plausible case (array with two word header) is 32MB. The total size of a million-element list is 16MB, the total size of the equivalent thing implemented as structures with two slots is 32MB, or as CLOS objects with two slots 64MB. So the cost you're paying is 48MB compared with lists (not surprisingly: a million copies of a 48-byte header), and the best plausible cost is 16MB: 32MB better.

I don't do anything to set the heap size on my SBCL, and it starts with 1GB. This means that the overhead of a million 48-bit headers is 4.8% of the available heap space: if you are hitting this limit you were already almost out of memory.

So my intuition is that something else is the problem here. Chances are, if it's not the sorting algorithm, then if these things are representing lazy objects you're using functions to represent what are essentially promises in some way, and it's those that are killing you. I can't think of any way of implementing laziness in standard CL which doesn't do that: that overhead is unavoidable if so. But even so, functions are not that huge in general.

You can, as far as I can tell, at least get SBCL to handle storage exhaustion errors: the following works for me:

(defun foo (n)
  (handler-case
      (length (make-array n))
    (storage-condition (c)
      c)))

However I don't know how reliable this is: in particular I suspect there may be times where it doesn't even have enough space left to collect the garbage.