John Fremlin's blog: How to optimise Common Lisp under SBCL: the garbage collector (draft)

With Common Lisp and other systems which don't trust the programmer to manage memory, garbage collection can become a major and unpredictable resource hog. And it only becomes visible with larger workloads. For example, you can reverse a small list of 10k elements very quickly (less than 10 cycles/node), but with 1M elements you are down to 28 cycles/node.

CL-USER> (time (reverse (make-list 10000)))
Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  922,320 processor cycles
  319,488 bytes consed
CL-USER> (time (reverse (make-list 1000000)))
Evaluation took:
  0.155 seconds of real time
  0.150000 seconds of total run time (0.140000 user, 0.010000 system)
  [ Run times consist of 0.110 seconds GC time, and 0.040 seconds non-GC time. ]
  96.77% CPU
  277,827,183 processor cycles
  31,998,416 bytes consed

This means you have ensure that your design does not require much memory allocation (consing). The worst kind of consing is that where some of the data sticks around for a while and gets tenured, then dereferenced later on. Garbage collectors are most efficient with either immediately throwing data away, or with keeping it forever.

You need to think about the rate of garbage generation and the amount of memory you will run through, and to run your mock-up experiments at your estimated processing rates for a few minutes. Compared to the typical one, SBCL's garbage collector is tuned to be fast but generally not particularly memory efficient (tune by fiddling with things in sb-ext, like sb-ext:bytes-consed-between-gcs). If you are planning to use most of RAM for actual data, then the garbage collector will have to work hard (additionally, SBCL and most other Lisp environments react very badly to running out of memory).

There are many ways to reduce the amount of garbage generated: pre-allocating buffers, declaring local functions and variables dynamic-extent, etc. But these often affect the way the API is structured, so you should consider whether it is going to be important before writing lots of code. The heavy Lisp users like ITA Software use manual memory allocation via mmap (let me plug manardb which lets you escape from the Lisp GC in a portable way, and gives you persistence almost for free).

Continued.