Lambda the Ultimate

Erlang's separate-heaps are pretty good like this as you say. There's also that fun Erlang performance hack for avoiding GC when you have a lot of short-lived processes (e.g. HTTP request handlers). First you measure how much heap allocation they typically do and then - if it's reasonably small - you preinitialize their heaps to that size. That way most processes will run and terminate without GC'ing and you can scrap their whole heap without ever traversing it.

Generation-scavenging collectors seem particularly fun too. When GC cost is proportional only to live data and not garbage then there's clearly an opportunity for lots of guilt-free allocation :-). Seems you could do a trick like the Erlang one, for example. Suppose you have a function that typically allocates 2MB of temporary data. If you call it with an empty 2MB "nursery" generation and don't GC until it returns then the GC should cost close to zero -- there's no live data in the nursery, it's all become garbage.

The catch with generational collectors seems to be what you mentioned: At some point, the GC is going to go through that 128MB of data. Continuing the GC-as-tool idea, we would want to understand when and why the older generations get collected and see if we can control it.

Some ideas come to mind. What about if we initially heap-allocate our 128MB, force it all the way into the last generation, and then be careful not to allocate enough long-lived data to ever need to collect that generation? Alternatively, what about "tenuring" the last generation so that the GC will leave it alone until further notice and stop at the second-last generation instead?

This is the kind of thing that interests me. In my heart I feel that generation-scavenging collectors are really good and that they support a very nice programming style. Lots of (Lisp) code I see is instead written to fight the GC and I'm not sure that it does so effectively. Do they know something I don't or do they they just want to be portable to other garbage collectors? (I wonder if language specs should state required GC characteristics the same as RnRS does for tail-call optimization.)

Anyway, it's at this point that I always make some measurements that turn out to be totally invalid in some unforseen way. I will continue this tradition with a follow-up :-)

• Fresh Lisp image (as fresh as mine usually are, anyway).
• With 64MB of live conses allocated in the oldest generation.
• The same as the previous case but with the last generation tenured.

(in-package :cl-user)

(defconstant megabytes 64
  "We will heap-allocate this many long-lived megabytes of conses.")

;; Save the results (standard output) to a file.
(dribble "/tmp/results")
(setq *trace-output* *standard-output*)

(setq *gc-verbose* t)
(setq *compile-print* nil)
(setq *compile-verbose* nil)


(defun work ()
  "Do some work that will require garbage collections."
  ;; Recompile regexp system
  (dotimes (i 3)
    (asdf:oos 'asdf:compile-op :cl-ppcre :force t)))

(defun say (format &rest args)
  "Print a message on a single line in a grep'able way."
  (format t "~&/// ~?~%" format args))

(say "Warming up")
(work)
(gc :full t)

(say "RUN: small heap")
(time (work))
(gc :full t)

(say "Generating lots of data on the heap")
(defvar *waste*
  (loop for i from 1 to (* megabytes 1024 1024 1/8) collect i))

(say "Forcing it all into the last generation")
(gc :full t)

(say "RUN: big heap")
(time (work))
(gc :full t)

(say "Tenuring last generation")

;; We have to poke a C variable for this.
(alien:def-alien-variable ("gencgc_oldest_gen_to_gc" gencgc-oldest-gen-to-gc)
    c-call::int)

(decf gencgc-oldest-gen-to-gc)

(say "RUN: big (tenured) heap")
(time (work))
(gc :full t)

$ grep -e '^///' -e 'seconds' -e 'bytes consed' -e 'page faults'  /
tmp/results 
/// Warming up
/// RUN: small heap
;   45.95 seconds of real time
;   22.014652 seconds of user run time
;   0.993849 seconds of system run time
;   [Run times include 4.63 seconds GC run time]
;   0 page faults and
;   718,752,904 bytes consed.
/// Generating lots of data on the heap
/// Forcing it all into the last generation
/// RUN: big heap
;   46.24 seconds of real time
;   22.3676 seconds of user run time
;   1.047841 seconds of system run time
;   [Run times include 4.98 seconds GC run time]
;   0 page faults and
;   718,632,984 bytes consed.
/// Tenuring last generation
/// RUN: big (tenured) heap
;   46.34 seconds of real time
;   22.383596 seconds of user run time
;   1.026844 seconds of system run time
;   [Run times include 5.06 seconds GC run time]
;   0 page faults and
;   718,784,504 bytes consed.

If so, it's a strong, strong case for using reference counting when at all possible.

Please elaborate on this statement ;-). I think I can guesstimate on your assumptions and conclusions but is there any proof that reference counting (or some hybrid gc algorithm using reference counting) outperforms other, say generational, gc algorithms?

How would the compiler make use of such information?

If it's a generational GC the compiler can include information about the initial size of the nursery, so the data allocated for the function is never moved to older generations. Allocate, return and clean the whole area.

It seems that every different type of GC and different configurations would need its own set of flags and different annotations to get similar effects. And even then, most GC systems are simply not flexible enough to really provide much (though Beltway is a partial exception; there are also a lot of good looking papers at that link, e.g. Ulterior Reference Counting). More desirable would be dynamically adaptable behavior as the memory profile of a program changes throughout its life, as well as the needs.

I don't really see annotations being too useful for anything beyond tweaking for most GC implementations.

As an example, let's say you are using an implementation that uses Appel's simple generational GC (a 2-age copying collector). The scenario is "the world data for a level of a 3D game" (a large amount of staged long-lived data plus a reasonable amount of normal garbage) we're optimizing for latency but it isn't hard real-time (i.e. a half second hiccup once in a blue moon is acceptable, a 3-second pause regularly is not). Loading the data can generate pauses as long as necessary. What kind of annotations would provide good behavior and how would they be realized? What about other GC configurations?

To contrast, simply using a simple manual pool allocator for the world data and leaving the rest to the GC would work assuming the remaining live data is typically quickly collectible.

First off, I don't think annotations should be tied to specific implementation patterns(for instance, saying a function needs about 2MB of RAM is just a fact of existence, and if its a fact that can be _used_ by the GC algorithm, great, if not, it is nice that its an annotation that does not change anything about the code itself or its meaning.

Second, I think it would be nice to have this sort of stuff available for more than just memory optimizations. I think a generalized scheme for encoding information(that is perhaps checkable) that doesn't change the semantics of the code would be a desirable thing, in that it might help both compiler writers(having more information available), and programmers("optimizing" their code without making it uglier). I guess "typing" annotations are sort of like this(but they change the semantics of your code). Of course, yeah, you _can_ manage it yourself(pools and such), but that involves modifying the code(and usually writing more code) to get better performance without really changing the semantics(or algorithm really).

I have ho idea how it could work.

I do have a generational GC with two generations. What can it do with the information that a given function usually allocates mo more than 2MB of heap (or any other amount)?

If the programmer thinks that it's useful to GC before the real work of the function, he can call the function MaybeGarbageCollect which performs a GC if a significant amount of allocation occurred since last GC. This increases the chance that the function will run without GC. No need for an annotation. Of course a GC will still happen if the function allocates too much.

My implementation tends to GC when all threads are idle or waiting for I/O, so there should rarely be a need to call such function manually.

How would a compiler use annotations about space usage?

.... a garbage collector would be something that is provided by the operating system, not by a programming language.

Unless you were implying that the GC is ideal as well, this would seem like the worst-case scenario, not the ideal one. Such an approach is unlikely to be optimal for all applications, and in fact is more likely to be suboptimal for all applications. Especially, as there usually is some cooperation required between the language and the GC.

I'm thoroughly in the exokernel camp in thinking that the ideal solution is in the opposite direction. The operating system should be providing as much access to the hardware as is securely possible and otherwise get out of the way.

I thought this had been settled years ago. Kernels are, if anything, strict (and rather small) subsets of operating systems. Linux the OS is far more than Linux the kernel (which is why RMS thinks he is justified in calling it Gnu/Linux); much of Windows (any version) runs in user space, etc.

The definition of OS I am using here, is that bunch of software which abstracts away the underlying machine. Which is far greater than the kernel. While an argument can be made that kernels are too big and monolithic, I'm all for putting as much functionality as possible (assuming the requirements are general-purpose in nature and well-defined) in a common location (in user-space, preferably) which is then available to all application programmers. Under this expansive definition, a language runtime or VM is part of an "OS", and you might have more than one "OS" (or operating environments) running on your machine. (In the mainframe world, one finds numerous different kernels running on the same machine).

And perhaps GC policies ought to be customizeable on a per-application basis. OTOH, the current practice, especially for many research languages, is to ship the GC with the language itself--often times resulting in a GC policy which is poorly-tuned to the hardware which it is running on.

Of course, it ought to be pointed out that efficient GC requires many services which can only be performed at kernel level (at least on current systems)--determining the presence/absense of a page in main memory, implementing read/write barriers, etc. One reason that many language developers like targetting the JVM or CLR is that they no longer have to worry about this junk.

Of course, in an ideal world typing systems will get clever enough that compilers can manage the program store on behalf of the user without requiring external garbage collectors; but in the real world that sorta thing is probably undecideable.

Region inference is decidable, but can result in space explosions that you don't want in the contexts in which region inference is most useful, such as embedded systems with rather dramatic, fixed space constraints. The ML-Kit papers are still the best resource for learning about the issues, and on this particular topic, "Combining Region Inference and Garbage Collection" is particularly relevent.

The definition of OS I am using here, is that bunch of software which abstracts away the underlying machine.

The definition of OS I'm using is the exokernel one, anything that can't be avoided or changed.* I.e. if I must (directly or indirectly) use the "OS" GC then it's a problem whether or not it is in the "kernel" proper. Of course, I have no compunction against optional "standard" libraries that provide abstractions for common things. However, I think we are more or less in agreement here.

Anyways, it was a good excuse to throw out the exokernel link as there are some really cool approaches to combining security and modularity.

* With this definition user-space/kernel-space is irrelevant, microkernel servers are in user-space but you can't avoid them, so by the above definition they are still part of the OS.

And perhaps GC policies ought to be customizeable on a per-application basis. OTOH, the current practice, especially for many research languages, is to ship the GC with the language itself--often times resulting in a GC policy which is poorly-tuned to the hardware which it is running on.

They really should, but... But current implementations and techniques fairly closely bind the language implementation with the run-time and specifically the GC. For most implementations, about the only reasonable way to swap out GCs is to have different branches of the compiler and runtime, and even that is a chunk of work. Or, alternatively, the application can manage (some of the) memory itself.

Of course, it ought to be pointed out that efficient GC requires many services which can only be performed at kernel level (at least on current systems)--determining the presence/absense of a page in main memory, implementing read/write barriers, etc.

Hence me being in favor of exokernels.

Hence me being in favor of exokernels.

Is the philosophy of exokernels just a return to an ancient principle of separation of mechanism and policy? Whether and why was this principle forgotten in middle ages (around 80ies I guess)? Is its return made possible by better historical context (hardware/software/market)?

The principle of separation of mechanism and policy seems to have suffered for several reasons:

1) The belief among many that integrated systems can be made more capable than separated systems, and that the boundary between systems, when well-demarcated, can be a source of tension and difficulty. In many cases, this is true. Fortunately, more advanced means of composing programs, and more advanced "substrates" to build programs on has alleviated this concern a bit.

2) Many vendors have found that building integrated systems increases vendor lock-in, and reduces the chance that competing products can replace their own. (This principle, unfortunately, has guided much of the design of the most popular consumer operating system). The rise of open-source software, which encourages mixing and matching of components, is posing a major threat to the integrated model.

3) The X Windowing System. I'm not going to engage in a general round of X-bashing here (this post was composed on a computer running Gnome on X11, after all), but a guiding principle of X development was separation of mechanism and policy. X, for the first fifteen years or so of its existence, was a usability disaster--which many blamed on "mechanism not policy". A major reason for X's usability flaws, of course, was that policy was delegated to application programmers (many of whom new little about good UI design), resulting in an inconsistent hodgepodge. Most modern X deployments now do the right thing, and assign the policy role to the desktop environment (Gnome or KDE mainly) rather than application code. X still maintains the seperation (X itself has little policy), but the policy is now handled at the right level of the SW stack.

It depends on the language probably more than on factors which are only known to the OS. For example on object representation.

I'm not convinced that targeting CLR or JVM from a language which is not similar to C# and Java gives better efficiency than targeting C and implementing a GC by hand. Maybe their GCs have shorter pauses or they better integrate with native threads, but they require to use a constraining VM, and an object system and representation of values which is suitable only for statically typed languages. What is more important?

any pause more than a couple hundred milliseconds in length is going to disturb the user

People routinely tolerate much longer waits from applications, eg. web apps. If this pausing is only occasional, they may not really notice. I think it really depends what kind of app and what kind of usage we are taking about.

having to "rethink the arrangement of your data" seems to me to be a bigger inconvenience to the programmer than having to insert compiler hints here and there... the programmer should be able to specify algorithms and data structures in the most natural form possible.

Hmmm. I have to completely disagree with this assumption.

Sure, when starting an app, use the most natural form that you can think of at the time.

But if it fails to have desirable memory or performance characteristics, it is the responsibility of a good programmer to do what is possible with basic algorithmic/data structure improvements to fix the problem.

Expecting the compiler to make good performance out of bad (or simply not good enough) programming is expecting way too much from a dumb machine, IMHO.

I mean, tail-call optimization turns excessive recursion(bad memory performance) into good(almost no memory)?

The sort of optimizations that I'm talking about are not the sort that involve wrong algorithms/data structures. If your game(or whatever) needs a 128MB of RAM, to store the textures, its a 128MB of RAM. Writing extra(maybe buggy code) to manage that memory to stop the GC from doing something stupid is a waste of effort, and does not involve a "sufficiently smart compiler". In fact, annotating performance information about code is assuming a quite dumb compiler in my opinion.

My personal feeling that annotations are good idea comes from this: when you start optimizing code, it frequently becomes bigger, buggier, and harder to maintain. If the same information could be expressed in some kind of annotation attached to the clean, readable, pure expression of the algorithm, it would be easier to read and maintain. If it didn't change the semantics of the code, it would have the added bonus that, if it goes out-of-date, it would only affect performance, not correctness of the code. Its disentangling things.

Expecting a programmer optimize correct code without altering correctness is expecting too much from a dumb programmer(at least, when the dumb programmer is me). I dunno, yeah, computers are dumb, but I hear some of them play a mean game of chess on occasion anyway :)

If you create good abstractions (i.e, encapsulate your data as well designed ADTs), changing representation shouldn't be too hard and make the code buggier. And by making data structures more efficient, I don't mean implementing GC manually. When you have a specific problematic data abstraction, you can almost always fix it directly, without having to use the general purpose technique that is GC.

I mean, tail-call optimization turns excessive recursion(bad memory performance) into good(almost no memory)?

From my point of view, this is backwards. TCO preserves the definition of the algorithm from the clutches of a particular unfortunate implementation.

Very small specialized procedure stacks are a design choice of a platform, not of the language itself (in most cases).

The sort of optimizations that I'm talking about are not the sort that involve wrong algorithms/data structures.

If the system (compiler, OS, etc.) is bad, that is of course the system designer's fault. Complain or switch systems. ;-)

The part of the equation the programmer controls is algorithmic, so algorithmic solutions should be tried first. (A good profiler can help here.)

Obviously, if these solutions become complex beyond the programmer's understanding, they should stop. ;-)