Hacker News Reader

> It's hard for me to imagine any sane architecture where using more memory and having if fragmented rather than contiguous is going to perform as well as using a contiguous block of memory.

Yet many of the language runtimes are actually following the Lisp model. Just that it's there not the cons cell with two slots, but arrays and objects with slots. A Java program is a multitude of dynamically allocated objects with one or more slots, where many of the slots contain pointers to other objects. The memory management is done by the runtime (and, usually, its garbage collector).

> Sometimes they aren't. That doesn't fit the narrative that Lisp is god's gift to McCarthy who then gifted it to humanity, but it is reality.

Other than what you might think (and set up as a strawman), that's well known and the evolution of Lisp is also showing how the implementations had to deal with this problem.

The LISP 1 implementation introduced mark&sweep garbage collection (-> McCarthy). As a reaction to it Collins proposed "reference counting" as another way to manage&reclaim allocated memory.

Over time early Lisp programs (Macsyma is an example often mentioned) were problematic on multi-user time-shared machines. One reaction to that was to develop single user workstations for Lisp, where all the memory was available to a single user. There one then used large virtual memory, which still made memory access (for example during garbage collection) time consuming. A GC run of a large heap in VM could run for 30 minutes making the computer mostly unusable during that time. Vectors/Arrays and OOP objects then also used the model of dynamic allocation with many referenced objects (unless they were of some primitive types). Generational GCs, compacting GCs, hardware-supported GCs, etc. were invented and implemented. Full GCs through virtual memory heaps were rare then. The availability of cheaper RAM made it possible that more of the large heaps fit into RAM.

Lisp implementations early on added vectors and other data structures. But they still often need pointers. A vector of records (called structures in Common Lisp) is usually a vector with pointers to records. For example Common Lisp implementations usually will not provide vectors of inline records. A vector of fixnums OTOH will be a vector without pointers -> the fixnums will be stored directly in the vector.

In the end a Lisp heap is a huge graph of objects referencing other objects. This does not only effect CONS cells, but also vectors, arrays, records, ... -> they also reference other, non-primitive, objects via pointers.

That's not very different from any other language runtime which uses dynamic memory allocation and a heap of linked objects (-> Java, JavaScript, ...). The problem of dealing/avoiding non-locality and pointer-chasing is there, too.

View on HN

(defun test1 (n p) (let ((v (make-array n))) (map-into v (lambda () (make-array 10 :initial-element 1000))) (loop repeat p do (setf v (reverse v))) v)) (defun test2 (n p) (let ((l (make-list n))) (map-into l (lambda () (make-array 10 :initial-element 1000))) (loop repeat p do (setf l (reverse l))) l)) CL-USER 15 > (time (test1 10000 100)) Timing the evaluation of (TEST1 10000 100) User time = 0.005 System time = 0.000 Elapsed time = 0.003 Allocation = 9088696 bytes 1 Page faults GC time = 0.000 #(# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ...) CL-USER 16 > (time (test2 10000 100)) Timing the evaluation of (TEST2 10000 100) User time = 0.008 System time = 0.001 Elapsed time = 0.006 Allocation = 17113288 bytes 842 Page faults GC time = 0.003 (# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ...)

CL-USER 22 > (time (test1 10000 100)) Timing the evaluation of (TEST1 10000 100) User time = 0.016 System time = 0.000 Elapsed time = 0.012 Allocation = 9148776 bytes 0 Page faults GC time = 0.000 #(A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A ...) CL-USER 26 > (time (test2 10000 100)) Timing the evaluation of (TEST2 10000 100) User time = 0.000 System time = 0.000 Elapsed time = 0.000 Allocation = 1042248 bytes 0 Page faults GC time = 0.000 (A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A ...)