The ART of Garbage Collection

The ART documentation in the Android SDK has been updated (hat tip to Juan David Sánchez for pointing it out).

And it hints at something that I had been really hoping for, once I saw the I|O presentation description for the talk on ART mention “garbage collection”. Quoting the documentation:

…a compacting garbage collector is under development in the Android Open-Source Project (AOSP) to improve memory management. Because of this, you should avoid using techniques that are incompatible with compacting GC (such as saving pointers to object instance data). This is particularly important for apps that make use of the Java Native Interface (JNI).

This is big. Really big. Because our heap is really small.

However, the reason why we get so darned many OutOfMemoryErrors isn’t because we are out of memory. Instead, there is no single block of memory that is big enough for our request.

In Java, on the JVM, if there is no single block of memory big enough, that means that we are actually out of memory (with respect to this request, anyway). That is why the exception is OutOfMemoryError and not CouldYouAskForSomethingSmallerPlzKThxByeError.

However, the JVM has one thing that the Dalvik VM does not: a compacting garbage collector.

When we write programs in a language running on a runtime supporting garbage collection, we create a bunch of objects, and we later release some subset of those objects. The other ones we hold onto for a while, because we are still using them. In Android, for example, our Application, our ContentProviders, our Threads, our own static data members, and so on are going to live for quite some time, in many cases for the duration of the process. Anything they can reach also will not get garbage-collected. So, we allocate a bunch of memory and release some of that memory as our app runs.

With a compacting garbage collector, the long-lived objects get slid around in memory, to allow the freed-up blocks of memory to be coalesced. The net is that all free heap space should be available as one contiguous block, eligible for allocation.

(the details are more complicated than that, but this is a blog post, not a dissertation)

With a non-compacting garbage collector, nothing is slid around in memory. We wind up with heap fragmentation, as what was once a pristine 16MB (or 32MB, or 48MB, or whatever) heap now is a bunch of objects with interspersed free memory. Even though we might have 10MB of free heap space, if the largest single block of that free heap space is only 1MB, we cannot allocate an 8MB Bitmap, because there is no free block big enough.

The Dalvik VM has a non-compacting garbage collector.

The ART VM has a non-compacting garbage collector… today. If the work going on in the AOSP pans out, ART will get a compacting garbage collector in the future. And if they’re advising us to pay attention to this in our native C/C++ code with the NDK, they must feel reasonably good that their hard work on the compacting garbage collector will pan out.

When that happens, and ART is turned on by default for all users of some new version of Android, OutOfMemoryErrors will not completely go away, but they should become less frequent and more accurately represent the error message itself.

I, for one, welcome our new ARTist overlords.