notes39

Objects take up space in memory. If your program creates lots of objects, throws them away, and creates more, you might eventually run out of memory. To reduce the chance that this will happen, Java has garbage collection.

While the Java Virtual Machine (JVM) runs your program, it also spends little bits of time searching for objects that you're no longer using, so it can reclaim their memory for use by other objects.

You don't have to know anything about garbage collection to be an effective Java programmer. But garbage collection is interesting because the JVM uses a lot of hidden data structures to manage memory. These data structures are hidden from your Java program–after all, the JVM, just like any other encapsulated module, should hide the details of how it is implemented. Here's a peak at what's going on under the hood.

Garbage collection's prime directive is to never sweep up an object your program might possibly use or inspect again. These objects are said to be live. The opposite of "live" is garbage–objects that your program cannot reference again. Java's design makes it possible for the JVM to determine whether an object can ever be used again by your program or not.

Garbage collection begins at the roots. A root is any object reference your program can access directly, without going through another object. There are two kinds (that we know about). First, every local variable (including parameters) in every stack frame on the program stack is a root if it is a reference. (Primitive types like ints are not roots; only references are.) Second, every class variable (aka "static" field) that is a reference is a root.

An object is live, and should not be garbage collected, if

• it is referenced by a root (obviously), or
• it is referenced by a field in another live object.

Note that this definition is recursive. Another way to say it is that an object is live if it is reachable from the roots. If you run depth-first search starting at all the roots, you will visit all the live objects and none of the garbage. And that's exactly what garbage collectors do: run depth-first search from the roots.

Each object has a small tag that allows the garbage collector to mark whether the object has been visited or not. The tag is invisible to your Java program, but it takes a few bits of the object's memory. (This is not the only "hidden" memory Java associates with an object–for example, every object has a hidden label that tells Java what class it's in.)

In any modern computer, memory is one huge array of bytes with addresses.

----------------------------
|   |   |   |   |   |   |   ...
----------------------------
  0   1   2   3   4   5   6

However, modern computers prefer to read or write four bytes at a time, and they do this much faster if the four bytes start at an address divisible by four, so that's how things like ints and floats are stored.

Every time you declare a local variable, you are naming a memory location. (You pick the name, Java picks the address.) An assignment statement writes something into a memory location.

              bob
   -----------------------------                         int bob;
...  |   |   | 3 |   |   |   |  ...
   -----------------------------                         bob = 3;
      208 212 216 220 224 228

Computers can store memory addresses in memory. To reduce the number of syllables, memory addresses are called pointers for short. Some languages like C allow you to declare variables that are pointers. A pointer field is a memory location that points to another memory location.

              bob     ptr
   -----------------------------
...  |   |   | 3 |   |216|   |  ...
   --------------------+--------
      208 212 216 220  |  228
               ^       |
               |       |
               \-------/

Java uses pointers too, but it considers them confidential information, and won't let you print them or look at the numbers directly. Java references are a little bit like pointers, but as we'll learn soon, they're actually more complicated than pointers.

The important point is that your computer's memory is just one giant array that has no structure except the structure you impose on it. Java saves you a huge amount of time and effort by structuring memory for you. Java does this by using hidden pointer-based data structures that you can't access from a Java program.

A mark-and-sweep garbage collector runs in two separate phases. The mark phase does a DFS from every root, and marks all the live objects. The sweep phase does a pass over all the objects in memory. Each object that was not marked as being live is garbage, and its memory is reclaimed.

How does the sweep phase do a pass over all the objects in memory? The JVM has an elaborate internal data structure for managing the heap. This hidden data structure keeps track of free memory and allocated memory so that new objects can be allocated without overwriting live ones. Time prevents my describing Java's heap data structure here, but it allows the garbage collector to do a pass over every object, even the ones that are not live. It's roughly like an invisible linked list that links everything.

Similarly, the stack frames on the stack are data structures that make it possible for the garbage collector to determine which data on the stack are references, and which are not.

When a mark-and-sweep collector runs, your program stops running for an instant while the garbage collector does a mark pass and a sweep pass. The garbage collector is typically started when the JVM tries to create a new object but doesn't have enough memory for it.

Typical programs allocate and forget a good many objects. One problem that arises is fragmentation, the tendency of the free memory to get broken up into lots of small pieces. Fragmentation can render Java unable to allocate a large object despite having lots of free memory available.

(Fragmentation also means that the memory caches and virtual memory don't perform as well. If you don't know why, wait until CS 61C or CS 152.)

To solve this problem, a compacting garbage collector actually picks up the objects and moves them to different locations in memory, thereby removing the space between the objects. This is easily done during the sweep phase.

-------------------------------------    -------------------------------------
|object  object    object   object  | => |objectobjectobjectobject           |
-------------------------------------    -------------------------------------

There's a problem here: if we pick up an object and move it, what about all the references to that object? Aren't those references wrong now?

Interestingly, in the Oracle JVM, a reference isn't a pointer. A reference is a handle. A handle is a pointer to a pointer.

When an object moves, Java corrects the second pointer so it points to the object's new address. That way, even if there are a million references to the object, they're all corrected in one fell swoop. The "second pointers" are kept in a special table, since they don't take as much memory as objects.

reference reference reference              reference reference reference
     |        |        |                        |        |        |     
     |        v        |                        |        v        |     
     \----->====<------/                        \----->====<------/     
        /---+- |                   ==>                 | -+----\        
        |   ====                                       ====    |
        v                                                      v
       object                                                object
    "Over here"                                       "No, wait, over here"

The special table of "second pointers" does not suffer from fragmentation because all pointers have exactly the same size. Objects suffer from fragmentation because when a small object is garbage collected, the space it leaves behind might not be large enough to accommodate a larger object. But a garbage-collected object's "second pointer" can simply be reused by any newly constructed object that comes along, because all "second pointers" have the same size.

Copying garbage collection is an alternative to mark and sweep. It does compaction, but it is faster than mark and sweep with compaction because there is only one phase, rather than a mark phase and a sweep phase.

Memory is divided into two distinct spaces, called the old space and the new space. A copying garbage collector finds the live objects by DFS as usual, but when it encounters an object in the old space, it immediately moves it to the new space. The object is moved to the first available memory location in the new space, so compaction is part of the deal. After all the objects are moved to the new space, the garbage objects that remain in the old space are simply forgotten. There is no need for a sweep phase.

Next time the garbage collector runs, the new space is relabeled the "old space" and the old space is relabeled the "new space". Long-lived objects may be copied back and forth between the two spaces many times.

While your program is running (between garbage collections), all your objects are in one space, while the other space sits empty.

The advantage of copying garbage collection is that it's fast. The disadvantage is that you effectively cut in half the amount of heap memory available to your program.