The Dalvik era

Dalvik is the runtime Android shipped with for six years, and it is the reason DEX exists, the reason the 64K limit exists, and the reason the first Android phones could run Java-like code at all on hardware with a fraction of the memory of a laptop.

TL;DR#

• Dalvik was Android's original virtual machine: a register-based interpreter for DEX bytecode.
• It was designed for 2008 phones — little RAM, slow flash, no assumption of a JIT.
• Android 2.2 added a trace-based JIT, which compiled hot traces rather than whole methods.
• It was replaced by ART in Android 5.0, after ART spent Android 4.4 as an experimental option.
• Many Dalvik-era decisions survived: DEX, the 64K limit, dexopt, and the zygote model.¹

Mental model#

Think of a translator at a conference who speaks the language fluently but has no script.

They can translate anything you say, sentence by sentence, and they are fast enough for normal conversation. They cannot prepare a written translation in advance, and they get slower when the sentences are long or the vocabulary is dense.

Dalvik is the interpreter. It executes DEX bytecode directly. The trace-based JIT added in Android 2.2 is the translator noticing that a phrase keeps coming up and memorising it — but only after hearing it, and only for the exact sequence they heard.

Where the analogy breaks#

A human interpreter improves with familiarity across the whole conversation. Dalvik's interpreter did not learn; the JIT learned traces, and a trace is a specific path through the code. Change one branch and the trace is useless. That is a real limitation, and it is one of the reasons ART's method-based compilation was a better fit.

The big picture#

The pipeline shape is the same one ART uses. What differs is what happens on the device: Dalvik prepared the DEX for the phone at install time (dexopt) but did not compile it to native code, because there was no AOT compiler.

Deep dive#

The design constraints#

Dalvik was built for the T-Mobile G1: a 528 MHz ARM11 with 192 MB of RAM. Two constraints followed from that and shaped everything else:

• Memory. Every process had a Dalvik heap with a hard limit. The limit grew with device generations, but it was always a number an app had to respect.
• Startup. Class loading and verification had to be fast, because every app start paid for them — which is why the zygote preloading model was there from the first release.

The VM was register-based from the start. That was a deliberate choice over the JVM's stack machine: fewer instructions per operation, at the cost of wider encodings and a fixed frame size.²

The heap limit deserves a second look, because it explains an entire era of app architecture. When Runtime.getRuntime().maxMemory() reports a small number, an app cannot load a large bitmap at full resolution, cannot keep a long list of objects alive, and cannot cache aggressively. Out-of-memory crashes were the defining failure mode of Android apps for years, and many of the patterns developers still use — bitmap subsampling, LruCache, reusing views — were invented as answers to a heap that was far smaller than the screen resolution suggested.

A device with a big screen and a small heap forces exactly the kind of memory discipline that a desktop programmer never has to learn. That is the Dalvik era in one sentence.

The interpreter#

Dalvik's interpreter reads a DEX instruction, decodes the register operands, performs the operation, and moves to the next instruction. The loop is small and hand-tuned, and for a lot of code it was good enough.

A method compiles to something like this. The exact register numbers depend on the compiler, but the shape is stable:

# int sum(int a, int b) { return a + b; }
add-int v0, p1, p2
return v0

And a loop over an array shows why register-based code is compact — the operands are named directly, so there is no load/store pair around every arithmetic operation:

# for (int i = 0; i < n; i++) total += values[i];
const/4     v0, 0          # i = 0
const/4     v1, 0          # total = 0
:loop
if-ge       v0, p1, :end   # if (i >= n) goto end
aget        v2, p2, v0     # v2 = values[i]
add-int     v1, v1, v2     # total += v2
add-int/lit8 v0, v0, 1     # i++
goto        :loop
:end
return      v1

Seven instructions for a loop body that the JVM would express with several more. The cost is that every instruction is wider, and that a method needing more than 16 registers needs extra moves because many opcodes can only address v0–v15.²

The problem is dispatch overhead. Every instruction costs a decode and a branch, and a method that runs a tight loop pays that cost on every iteration. On a device where the CPU is also doing rendering and radio work, that overhead is visible.

The trace-based JIT#

Android 2.2 (API 8) added a JIT. It was trace-based: the VM watched execution, identified a hot path through the code — a sequence of instructions that ran repeatedly — and compiled that trace to native code. Subsequent trips through the same path took the compiled version.

A trace is recorded by the interpreter itself. When a backward branch is taken often enough, the VM starts recording the instructions that follow, stops at the next branch, and hands the sequence to the compiler. The compiled trace is keyed by its starting address, so the next time execution arrives there, it jumps into native code.

The advantage over AOT is information: the JIT sees which branch is actually taken, which types actually arrive, and which virtual calls actually resolve to one target. The disadvantage is that a trace is a path, not a method. It is brittle in the face of polymorphism and it does not help code that has not run yet — including the code that runs during startup, which is exactly when users are watching.

dexopt and the odex file#

Dalvik did have an install-time step: dexopt. It ran when an app was installed and produced an odex file — optimised DEX. The optimisation was not compilation to native code; it was preparation: rewriting instructions into a form that is cheaper for the interpreter, and doing verification once instead of on every launch.

The odex file is an ancestor of ART's .oat and .vdex, and the idea — pay at install time so that launch is cheaper — is the same. The difference is what the prepayment buys.

Garbage collection#

Dalvik's collector was a mark-sweep collector with stop-the-world pauses. Marking walks the object graph from the roots; sweeping returns unmarked objects to the free lists. The whole collection stops the app.

Two consequences show up in old apps:

• Pause time scales with live objects. A large heap means a long pause.
• The heap fragments. Sweeping frees objects but does not move them, so large allocations can fail even when total free memory is sufficient.

Dalvik never solved either problem. ART's concurrent copying collector is the answer, and it is covered in Garbage collection and jank.

Verification and the class loader#

Every app process had its own class loader over the preloaded bootstrap classes. Verification — checking that bytecode does not violate type safety — happened at load time, per class, and was a meaningful part of app startup.

The zygote model helped here too: classes loaded before the fork are verified once for every app that inherits them.

Why it was replaced#

By 2013 the constraints had changed. Phones had multiple cores, more RAM, and 64-bit processors were arriving. Dalvik's design assumed a single slow core and a tiny heap.

There was also a maintenance problem. Dalvik's interpreter and JIT were hand-written assembly for each architecture, which made every new CPU a porting project. ART's compiler is written in C++ and generates code for each target from one optimising backend, so supporting a new architecture is a backend exercise rather than a rewrite.

ART's argument was not "interpreter bad, compiler good". It was:

• AOT compilation at install makes first launch fast, because the code is already native.
• A real optimizing compiler can do whole-program analysis: inlining across methods, class hierarchy analysis, devirtualisation.
• A modern GC can keep pauses short on a large heap.

ART shipped as an experimental runtime in Android 4.4 (API 19) and became the only runtime in Android 5.0 (API 21).³

The transition was deliberately invisible to apps. A Dalvik-targeted APK contains DEX, and ART executes DEX. The runtime changed; the contract did not. That is the strongest evidence that DEX was the right level of abstraction to standardise on.

How it evolved#

The row that matters most for this page is API 8: the trace JIT. Everything before it was pure interpretation; everything after it was a gradual acknowledgment that interpretation alone was not enough.

Under the hood#

• ‹›↗the original VM implementation — historical, removed from current AOSP
• ‹›↗the interpreter loop — historical
• ‹›↗the trace-based JIT — historical
• ‹›dex-format.html↗the DEX specification Dalvik implemented — historical

Curiosity corner#

• Dalvik was named after a village in Iceland. The maintainers' naming tradition continued with ART, which is a backronym rather than a place.
• The trace JIT was a stopgap that lasted eight years. It shipped in 2010 and was replaced by ART's method-based JIT in 2016.
• dexopt outlived Dalvik. The name is still used for install-time preparation in ART, even though what it does is completely different.

Try it#

$ adb shell getprop dalvik.vm.heapsize

$ adb shell getprop persist.sys.dalvik.vm.lib.2

Check yourself#

Sources#