16 Memory Management

Version 4¹

Memory management allows us to create new objects and get rid of them; or more generally, to allocate chunks of memory — make them available to a program — and deallocate them — the program has no further use for it.

Early languages and memory management:

FORTRAN (1957): no memory management
COBOL (1959): no memory management
Pascal (1970): explicit memory management
C (1972): explicit memory management
C++ (1985): explicit memory management
Python (1990): automatic memory management
Java (first public release 1995): automatic memory management
LISP (1958!!!): automatic memory management!

16.1 Explicit Memory Management

Why learn about it?
1. We might need to work with this sort of language.
2. We can sometimes use explicit memory management to optimize Java programs.
Program's memory is divided into the heap and the stack. "Heap" here is not the binary tree kind; it's just a region of memory.
Memory is allocated—made available for use by the program—; and deallocated—returned by the program when it is finished.
Local variables are (normally) allocated on the stack.
- What if a local variable is an object? The compiler may not know how much space to allocate for it (some objects are bigger than others), so it allocates a pointer on the stack, which will store the address of the object. These are what we call "reference variables" in Java.
- The actual object will be allocated on the heap.
Pointers
- The null pointer: represented as an invalid address.
- It's said that "Java does not have pointers." Actually, it does: the reference types are pointers; but Java restricts what you can do with them — you cannot do address computations as in C, C++, or assembly language — "safety" feature.
- Since we cannot "access memory addresses" in an unrestricted way, Drake simulates memory with an array. Fig. 16-3, p. 445.
The tasks of a memory manager:
- Keep track of memory in use by the program.
- When the program needs more, give it some more.
- When the program doesn't need so much, take some of it back so it can be re-used.

The Free List

Simplifying assumption: each object takes 2 "cells" of memory, each of the int (32 bit) size. (I will call these pairs of cells pairs.)
Fig. 16-5 shows the free list, which is a "linked" list containing all the unused memory available in the heap. (Linked, here, using array indices as simulated memory addresses.)
Initialization of the free list, allocate, and free: see Figures 16-6, 7, 8.
Freeing a linked structure requires freeing each "node".
- freeList
- freeTree (which doesn't make sense, because how can you have a tree with just a pair?)
Exercise: using a free list, allocate and deallocate memory for two lists [a, b, c] and [d, e]:
```
x = cons(a, cons(b, cons(c, []))) 
y = cons(d, cons(e, [])) 
free y
free x
```

Evaluation

Advantages of Explicit Memory Management

Efficiency? [The claim is often made, but dubious, as we shall see later.]

Disadvantages

Memory leaks occur when the programmer neglects to free objects that the program is done using. As the program keeps allocating new objects but not freeing them, eventually it may run out of memory. (Crash.)
Dangling pointers are pointers to objects that have been prematurely freed. Or at least to where those objects were, but actually, there's something else there now — see the problem?
Both errors can be hard to debug, because the symptoms are delayed.
Drake (p. 450) suggests that writing data (i.e., assignment) to where a dangling pointer points, can corrupt the data and/or instructions of another program!
- No, unless the operating system is very bad. One of the jobs of the O.S. is to protect each program's memory area from other programs. And usually not even the instructions of your own program, because they'd be in a "read-only" segment of memory.
Comparison: explicit vs. automatic memory management is like manual vs. automatic transmission! (Ah, not really!)

Using a Node Pool

A node pool is a collection (usually an array) of nodes (as in list nodes, for example) that are managed as a kind of mini free list.
- The node pool is pre-allocated all at once
- The node pool then allows the program to allocate and free nodes.
- A node pool can be used to gain some of the [alleged] efficiency of explicit memory management in a system that normally uses automatic memory management (such as Java).
- It can even improve on the efficiency of the standard allocate/free routines in languages like C and C++.

Remarks

In real life, the explicit memory manager must be much more complex than the example given here, mainly because it must satisfy requests for various sizes of object (different numbers of bytes allocated). When we can request different sizes of object, there are challenges in allocating and deallocating memory efficiently.
- The heap becomes divided into available "chunks" of different size.
- Find a big enough chunk efficiently.
- Allocate a region that's just large enough, if possible.
- Try to merge chunks together when freed, so as to avoid fragmentation into smaller and smaller chunks.
One of the things that makes a node pool attractive, is, since all the nodes are the same size, the allocation and deallocation can be much simpler, and therefore faster, than the fully general allocation/deallocation routines that allow variable sized chunks.

16.2 Automatic Memory Management

A. Reference Counting

Each allocated object keeps track of how many references (pointers) there are to it.
That is, whenever an object is created, its reference count is set to 1, since the allocator returns a pointer to it; whenever a new pointer is created or a pointer value changed or a pointer variable destroyed, the reference counts of the objects pointed at (one or two) are updated.
When the reference count of an object falls to zero, it is automatically deallocated.
Exercise: using a free list and reference counts, allocate and deallocate memory for two lists [a, b, c] and [d, e, b, c]:
```
x = cons(a, cons(b, cons(c)))
y = cons(d, cons(e, tail(x)))
x = y
x = []
```
Good news:
- Fast
- Simple
Bad news:
- Does not work well for cyclic structures, e.g., circular lists, cyclic graphs. The objects in such a structure refer to each other; consequently, their reference counts never drop to zero, and they cannot be reclaimed.

B. Garbage Collection (GC)

The big idea: when the system is low on memory, it "pauses" to take out the trash (actually, "recycle" would be a better term: the memory for objects no longer in use is reclaimed, so it can be reallocated to new objects).
Early garbage collectors took 20 to 30% of CPU time and resulted in a noticeable pause — seconds or minutes in length.
Modern GC is much faster.
GC identifies the "live" objects, or objects in use. These are the ones that are reachable from a "root set" (typically, the local variables active in a program).

GC preserves the live objects while reclaiming the space of all unused objects.

B. 1. Mark and Sweep GC

Each object has a "mark" bit that shows if it's in use.
Procedure: two phases —
1. "Mark": the garbage collector traverses reachable objects (depth-first traversal [why depth-first? because breadth-first requires more memory] of pointers). Each object so reached is marked as being in use (i.e., its mark bit is set).
2. "Sweep": after all such objects have been marked, sweep through the heap (iterate through all heap addresses) and deallocate everything that's not marked.
Good news:
- Works even for circular structures.
Bad news: it's slow, because sweep time is proportional to the size of the heap.
- Most objects are short-lived, so the heap is mostly garbage.

B. 2. Copying GC (Copy and Compact)

Is much more efficient than mark and sweep, because its running time is proportional to the number of live objects, which is much less than the heap size.
When not doing GC, the program uses only half of the heap, called the from space.
During GC, all live objects are identified and copied from the "from space" to the other half, called the to space.
At the end of GC, the to-space becomes the from-space, and the old from-space becomes the new to-space.
There is a complication: whenever a live object is moved, all pointers to the object must be updated to its new address.
Procedure:
1. Set the allocation pointer to the lowest address in the to-space. This pointer indicates where new objects can be allocated.
2. Start with all root objects, i.e., those referenced by local variables on the stack. Copy each root object into to-space, store its new address in the old object (this is called a forwarding address or forwarding pointer, and update the local variables to the new address. (Copying each root object increments the allocation pointer.)
3. Set sweep pointer to the lowest address in the to-space.
4. While sweep pointer < allocation pointer:
  1. word = the word referenced by the sweep pointer
  2. if word is a pointer:
    1. if the object word points at has not been copied into to-space, copy it now (increments allocation pointer), and set its forwarding address.
    2. word = forwarding address of the object just copied
  3. advance sweep pointer to next word
5. Switch spaces: (from, to) = (to, from).
Exercise: using copy/compact GC, allocate and deallocate memory for two lists [a, b, c] and [d, e, b, c], and collect the garbage:
```
x = cons(a, cons(b, cons(c, [])))
y = cons(d, cons(e, tail(x)))
x = y
y = cons( ... oh i'm out of space ... 1, [])
```

Remarks on Copying GC

The address of every live object has changed, but the programmer doesn't need to know or care about it, because all the pointers were updated to the objects' new addresses.
All live objects are now concentrated in the lower part of the former to-space, which is now the from-space. The memory has been compacted. Further, objects that are connected by pointers are now close together in memory. This compaction is beneficial to virtual memory and cache, which work best when related data are at nearby addresses.
The memory allocator doesn't have to hunt for a right-sized chunk. It just advances the allocation pointer by the amount needed. When it can't do that, it's time for a new GC.
The time it takes for GC is remarkably short, since most of the former from-space was garbage (typically about 80%). The time is proportional to the space used by live objects, which is much less than the size of the heap.
So, which is really more efficient, explicit memory management or automatic memory management? Copy/compact GC runs in time proportional to the live object space. Explicit memory management runs in time proportional to the number of objects deleted. Since the heap is usually mostly garbage, the surprising result is that copy and compact GC is typically faster than explicit memory management!
Generational GC offers additional speedup. (What's this? …)
Nevertheless, even a short pause for GC may be unacceptable for some "real-time" applications.
- Real time means the program must respond within a specified time interval. The control systems for an airplane would probably be real-time systems. Another example is music synthesis, where the program must output a sound sample every 1/44,100 of a second at the standard CD audio rate.
- So explicit memory management has a role here.
- On the other hand, there are also incremental, real-time garbage collectors, but they're very complicated.
In Exercise 16.11, p. 462: Note that Sun's Java license says it is not to be used for such applications!

Footnotes

Revision history:
- Version 4, 2010 Nov 30. Converted to markdown.
- Version 3, 2009 Nov 30. Converted to RST.
- Version 2, 2007 Nov 26: HTMLized about half.
- Version 1: 2006, plain text.
↩