What is New in Android Lollipop

It is exciting times with the new Android Lollipop (Android 5.0) release hitting a late model Android handset near you. It is apparently already available on Motorola Droid X and G and slated for Nexus phones on November 12th. There is a lot of interesting features in this release, from the switching on of the Android Runtime (ART) which enables ahead-of-time compilation of Android apps (instead of the more traditional Dalvik just-in-time compilation) to a new garbage collector.

ART was introduced in KitKat (Android 4.4) but it is now the default in Lollipop.

High-Level Programming Languages for Embedded Systems: Garbage Collection and FPGAs

Just when it looked like the big guys (well, basically Apple, that big chunk of the NASDAQ) were moving away from tracing garbage collectors, researchers from IBM Research has taken the leap to bring garbage collection to FPGAs [PDF]. Though hardware-assisted garbage collection isn't new, this degree of implementation of a complete concurrent garbage collector on an FPGA is. The authors consider this a first step in bringing high-level languages to the FPGA and embedded computing realm. It should be interesting to see where this goes.

Comparative Memory Management, Part 1

When Apple first announced Automatic Reference Counting (ARC) at WWDC in 2011, the fanfare was considerable. Developers took it be the best thing since sliced bread. Some called it "innovative". The whole idea that iOS and now MacOS X developers (since Mountain Lion) could be freed from error-prone manual memory management without the runtime pauses of conventional garbage collection was certainly played up by the Apple machine. However, when I saw the words "reference counting" and "no overhead" in the same sentence, I cringed. Reference counting isn't a new concept at all. Automatic reference counting is used in a number of languages including Python and Delphi, though neither of those languages can claim to be the sole pioneer. More importantly, reference counting implies the presence of a reference count for each object (a considerable runtime memory overhead especially if lots of small objects are allocated) and the constant maintenance of the reference count (i.e., reference counters for each object must be updated when new owners lay claim (retain) or old owners release).

Garbage Collection in JavaScript, Part 2

Of the Chrome V8 JavaScript engine's 198kloc source (excluding comments), about 19kloc comprise the garbage collector. It is a generational Cheney copying collector with mark sweep. In October 2011 the V8 team added an incremental garbage collector to the mix. Incremental garbage collection contrasts with traditional stop-the-world garbage collection in that it is more amenable to low-latency applications requiring minimizing garbage collection pauses at the cost of reduced total throughput. The V8 garbage collector actually has a whole assortment of configurable flags (see shell --help). If these options can be tweaked, one can provide a customized JavaScript experience (especially garbage collector experience) tailored to the particular performance needs of the app.

Notes from the MacQueenFest

I had the excellent opportunity to attend the MacQueenFest a couple of weekends ago in honor of David MacQueen. The venue provided interesting insight into what the alumni of the ML community was up to these days. Many of the slides are now up on the website. The talks were scheduled roughly chronologically based on Dave's contributions. Most were looking forward as much as they were considering the historical significance of the contributions.

Garbage Collection in JavaScript, Part 1

A recent post on Scirra claimed that reusing long-lived objects was an ingredient to good JavaScript garbage collection behavior. That made me curious. This claim is generally true when the garbage collector in question is a generational one. Generational garbage collectors split the heap (memory from where all non-stack allocated things are allocated from) into several "generations". The "generational assumption" is that short-lived objects tend to be collected more frequently than long-lived objects in the heap. Upon each garbage collection, any objects which aren't collected can be promoted to the long-lived generation. The idea is that by running garbage collection less frequently on longer-lived generations, garbage collection can feel more responsive.

The problem is that generational garbage collection isn't universal. It isn't the most responsive form of garbage collection or memory management either (concurrent and incremental garbage collectors are more advanced and optimized for realtime/low-latency applications). Furthermore, although generational garbage collectors for the major browsers are in the works [Firefox, WebKit/Safari], it appears that currently only Chrome deploys one in the release browser. In fact, Chrome V8 cites generational collection as one of the main features of V8 enabling high-performance JavaScript. Around 7/20/2012, Mozilla added an Incremental Garbage Collector to Firefox 16, which reduces GC pause times by incrementalizing collection rounds, but this says nothing of and does not rely on the generation assumption. In Lisp (the first implementations of "generation" garbage collectors by Lieberman and Hewitt [PDF] and Moon [PDF]), Smalltalk (one of the first languages with generational collectors [David Ungar's paper Generation Scavenging: A Non-disruptlve High Perfornmance Storage Reclamation Algorithm, PDF]) and the higher-order typed language work (Haskell, OCaml, Standard ML, etc.), we have been using generational collectors for quite a while.

The Scirra post suggests attempting to avoid garbage collection, but that is a very tricky matter. I think the realtime performance of such an approach would be very sensitive to the design of the garbage collector and any related heuristics. Moreover, if JavaScript interpreters move beyond generational collectors at some point, programming styles exploiting the generational assumption won't have the same payoff as before.

Continue to Part 2 in this series where I introduce profiling and benchmarking features in the Chrome V8 garbage collector.