Dalvik VM Internals
Dan Bornstein
Google

•
•
•
•
•

Intro
Memory
CPU
Advice
Conclusion

Dalvík, Iceland

The Big Picture

The Big Picture

What is the Dalvik VM?
It is a virtual machine to…

•
•
•
•

run on a slow CPU
with relatively little RAM
on an OS without swap space
while powered by a battery

What is the Dalvik VM?
It is a virtual machine to…

•
•
•
•

run on a slow CPU
with relatively little RAM
on an OS without swap space
while powered by a battery

Memory Efficiency

•
•
•
•
•

Intro
Memory
CPU
Advice
Conclusion

Problem: Memory Efficiency

•

total system RAM: 64 MB

•
•

•

available RAM after high-level services have started: 20 MB

multiple independent mutually-suspicious processes

•

•

available RAM after low-level startup: 40 MB

separate address spaces, separate memory

large system library: 10 MB jar)

Problem: Memory Efficiency

•

total system RAM: 64 MB

•
•

•

available RAM after high-level services have started: 20 MB

multiple independent mutually-suspicious processes

•

•

available RAM after low-level startup: 40 MB

separate address spaces, separate memory

large system library: 10 MB

Dex File Anatomy
header
"Hello World"
"Lcom/google/Blort;"
"println"
…
void fn(int)
double fn(Object, int)
String fn()
…

string_ids
type_ids
proto_ids
field_ids

PrintStream.println(…)
Collection.size()
…

int
String[]
com.google.Blort
…

method_ids
class_defs

data

String.offset
Integer.MAX_VALUE
…

Dex File Anatomy
header
"Hello World"
"Lcom/google/Blort;"
"println"
…
void fn(int)
double fn(Object, int)
String fn()
…

string_ids
type_ids
proto_ids
field_ids

PrintStream.println(…)
Collection.size()
…

int
String[]
com.google.Blort
…

method_ids
class_defs

data

String.offset
Integer.MAX_VALUE
…

Dex File Anatomy
header
"Hello World"
"Lcom/google/Blort;"
"println"
…
void fn(int)
double fn(Object, int)
String fn()
…

string_ids
type_ids
proto_ids
field_ids

PrintStream.println(…)
Collection.size()
…

int
String[]
com.google.Blort
…

method_ids
class_defs

data

String.offset
Integer.MAX_VALUE
…

Dex File Anatomy
header
"Hello World"
"Lcom/google/Blort;"
"println"
…
void fn(int)
double fn(Object, int)
String fn()
…

string_ids
type_ids
proto_ids
field_ids

PrintStream.println(…)
Collection.size()
…

int
String[]
com.google.Blort
…

method_ids
class_defs

data

String.offset
Integer.MAX_VALUE
…

Dex File Anatomy
.jar file
.class file
heterogeneous
constant pool

.dex file

other data

string_ids
constant pool
type_ids
constant pool

.class file
heterogeneous
constant pool
other data

proto_ids
constant pool
field_ids
constant pool
method_ids
constant pool

.class file
heterogeneous
constant pool
other data

other data

Shared Constant Pool
public interface Zapper {
public String zap(String s, Object o);
}
public class Blort implements Zapper {
public String zap(String s, Object o) {
...;
}
}
public class ZapUser {
public void useZap(Zapper z) {
z.zap(...);
}
}

Shared Constant Pool
Original .class files
class Zapper
"Zapper"
"zap"

class Blort
"SourceFile"

"java/lang/Object"

"Blort"

"Zapper"

method ref

"zap"

"Zapper.java"

"Blort.java"

"(Ljava/lang/String;Ljava/lang/
Object;)Ljava/lang/String;"

"Code"

"()V"

"ZapUser"

"Zapper"

method ref

"zap"

"Code"
method ref
"()V"
"useZap"

"(Ljava/lang/String;Ljava/lang/
Object;)Ljava/lang/String;"

method ref

class ZapUser

"ZapUser.java"
"LineNumberTable"

"(Ljava/lang/String;Ljava/lang/
Object;)Ljava/lang/String;"
"java/lang/Object"
"<init>"
"(LZapper;)V"

"SourceFile"

"LineNumberTable"

"java/lang/Object"
"<init>"

"SourceFile"

Shared Constant Pool
Original .class files
class Zapper
"Zapper"
"zap"

class Blort
"SourceFile"

"java/lang/Object"

"Blort"

"Zapper"

method ref

"zap"

"Zapper.java"

"Blort.java"

"(Ljava/lang/String;Ljava/lang/
Object;)Ljava/lang/String;"

"Code"

"()V"

"ZapUser"

"Zapper"

method ref

"zap"

"Code"
method ref
"()V"
"useZap"

"(Ljava/lang/String;Ljava/lang/
Object;)Ljava/lang/String;"

method ref

class ZapUser

"ZapUser.java"
"LineNumberTable"

"(Ljava/lang/String;Ljava/lang/
Object;)Ljava/lang/String;"
"java/lang/Object"
"<init>"
"(LZapper;)V"

"SourceFile"

"LineNumberTable"

"java/lang/Object"
"<init>"

"SourceFile"

Shared Constant Pool
Original .class files
class Zapper
"Zapper"
"zap"

class Blort
"SourceFile"

"java/lang/Object"

"Blort"

"Zapper"

method ref

"zap"

"Zapper.java"

"Blort.java"

"(Ljava/lang/String;Ljava/lang/
Object;)Ljava/lang/String;"

"Code"

"()V"

"ZapUser"

"Zapper"

method ref

"zap"

"Code"
method ref
"()V"
"useZap"

"(Ljava/lang/String;Ljava/lang/
Object;)Ljava/lang/String;"

method ref

class ZapUser

"ZapUser.java"
"LineNumberTable"

"(Ljava/lang/String;Ljava/lang/
Object;)Ljava/lang/String;"
"java/lang/Object"
"<init>"
"(LZapper;)V"

"SourceFile"

"LineNumberTable"

"java/lang/Object"
"<init>"

"SourceFile"

Shared Constant Pool
.dex file
method id

"useZap"

"Zapper.java"

proto id

"LZapUser;"

"Blort.java"
"ZapUser.java"

method id

"LZapper;"

"<init>"
proto id

"V"

method id

method id

method id
"LBlort;"
method id
method id
proto id

"zap"
"Ljava/lang/String;"
"Ljava/lang/Object;"

Shared Constant Pool
Memory is saved via…

•
•
•

minimal repetition
per-type pools (implicit typing)
implicit labeling

Size Comparison
common system libraries
(U) 21445320 — 100%
(J) 10662048 — 50%
(D) 10311972 — 48%
web browser app
(U) 470312 — 100%
(J) 232065 — 49%
(D) 209248 — 44%
alarm clock app
(U) 119200 — 100%
(J) 61658 — 52%
(D) 53020 — 44%

(U) uncompressed jar file
(J) compressed jar file
(D) uncompressed dex file

4 Kinds Of Memory
•

clean vs. dirty

•
•

•

clean: mmap()ed and unwritten
dirty: malloc()ed

shared vs. private

•
•

shared: used by many processes
private: used by only one process

4 Kinds Of Memory
•

clean (shared or private)

•
•

•

application-specific dex files

shared dirty

•

•

common dex files (libraries)

???

private dirty

•
•

application “live” dex structures
application heap

Enter The Zygote
•
•
•
•

nascent VM process
starts at boot time
preloads and preinitializes classes
fork()s on command

Enter The Zygote
Zygote
Zygote heap
(shared dirty,
copy-on-write;
rarely written)

Maps
Maps dex file

Browser

(mmap()ed)

Browser dex file

Maps live code
and heap

(mmap()ed)

Home dex file

Browser live
code and heap

(mmap()ed)

core library dex
files

(private dirty)

(mmap()ed)

shared from
Zygote

"live" core
libraries
(shared dirty;
read-only)

Home

(private dirty)

Home live code
and heap

shared from
Zygote

(private dirty)
shared from
Zygote

4 Kinds Of Memory
•

clean (shared or private)

•
•

•

application-specific dex files

shared dirty

•
•

•

common dex files (libraries)

library “live” dex structures
shared copy-on-write heap (mostly not written)

private dirty

•
•

application “live” dex structures
application heap

GC And Sharing
embedded
mark bits

separated
mark bits

mark bits
object data
object data

mark bits

parallel
mark bits
object data

object data
object data
mark bits
object data

object data

.
.
.

.
.
.

GC And Sharing

•
•
•

separate process, separate heaps, separate GCs
GCs must be independent
GC should respect the sharing!

GC And Sharing
Mark bits kept separate from other heap memory.

object data

•
•
•

parallel
mark bits

avoids un-sharing pages
object data

better small cache behavior
doesn’t waste memory

object data

object data

.
.
.

CPU Efficiency

•
•
•
•
•

Intro
Memory
CPU
Advice
Conclusion

Problem: CPU Efficiency

•
•
•
•

CPU speed: 250-500MHz
bus speed: 100MHz
data cache: 16-32K
available RAM for apps: 20 MB

No JIT
•
•

usually doesn’t matter
lots of native code

•
•

•

system provides libs for graphics, media
JNI available

hardware support common (graphics, audio)

Install-Time Work
•

verification

•

dex structures aren’t “lying”

•
•

•

valid indices
valid offsets

code can’t misbehave

Install-Time Work
•

optimization

•
•
•
•
•

byte-swapping and padding (unnecessary on ARM)
static linking
“inlining” special native methods
pruning empty methods
adding auxiliary data

Register Machine
Why?

•
•
•

avoid instruction dispatch
avoid unnecessary memory access
consume instruction stream efficiently

•

higher semantic density per instruction

Register Machine
The stats

•
•
•

30% fewer instructions
35% fewer code units
35% more bytes in the instruction stream

•

but we get to consume two at a time

Example #1: Source

public static long sumArray(int[] arr) {
long sum = 0;
for (int i : arr) {
sum += i;
}
return sum;
}

Example #1: .class
0000:
0001:
0002:
0003:
0004:
0005:
0006:
0008:
0009:
000b:
000d:
000f:
0012:
0013:
0015:
0016:
0018:
0019:
001b:
001c:
001d:
001e:
0021:
0024:
0025:

lconst_0
lstore_1
aload_0
astore_3
aload_3
arraylength
istore 04
iconst_0
istore 05
iload 05
//
iload 04
//
if_icmpge 0024
//
aload_3
//
iload 05
//
iaload
//
istore 06
//
lload_1
//
iload 06
//
i2l
//
ladd
//
lstore_1
//
iinc 05, #+01
//
goto 000b
read local
lload_1
lreturn

rl
rl
rs
rl
rl
rs
rs
rl
rl
rs
rs
rs
rl

ws
ws
rs
ws
ws
rs
wl
rl
ws
ws
rs
rs
wl

• 25 bytes
• 14 dispatches
• 45 reads
• 16 writes
ws
ws ws
read stack
ws
rs rs ws ws
wl wl
write stack
write local

Example #1: .dex
0000:
0002:
0003:
0004:
0005:
0006:
0007:
0009:
000b:
000c:
000d:
000f:
0010:

const-wide/16 v0, #long 0
array-length v2, v8
const/4 v3, #int 0
move v7, v3
move-wide v3, v0
move v0, v7
if-ge v0, v2, 0010
aget v1, v8, v0
int-to-long v5, v1
add-long/2addr v3, v5
add-int/lit8 v0, v0, #int 1
goto 0007
return-wide v3

• 18 bytes
• 6 dispatches
• 19 reads
• 6 writes
//
//
//
//
//

r
r
r
r
r

r
r w
w w
r r r w w
w

Example #2: Source

private static final int[] S33KR1T_1NF0RM4T10N = {
0x4920616d, 0x20726174,
0x68657220, 0x666f6e64,
0x206f6620, 0x6d756666,
0x696e732e
};

Example #2: .class
0000:
0002:
0004:
0005:
0006:
0008:
0009:
000a:
000b:
000d:
000e:
000f:
0010:
0012:
0013:
0014:
0015:
0017:
0018:
0019:
001a:
001c:
001d:
001e:
001f:
0021:
0022:
0023:
0025:
0027:
0028:
002b:

bipush #+07
newarray int
dup
iconst_0
ldc #+4920616d
iastore
dup
iconst_1
ldc #+20726174
iastore
dup
iconst_2
ldc #+68657220
iastore
dup
iconst_3
ldc #+666f6e64
iastore
dup
iconst_4
ldc #+206f6620
iastore
dup
iconst_5
ldc #+6d756666
iastore
dup
bipush #+06
ldc #+696e732e
iastore
putstatic Example2.S33KR1T_1NF0RM4T10N:[I
return

...
dup
bipush #+NN
ldc #VVVVVVVV
iastore
...

Example #2: Hack!
private static final int[] S33KR1T_1NF0RM4T10N;
static {
String s =
"\u4920\u616d\u2072\u6174\u6865" +
"\u7270\u666f\u6e64\u206f\u6620" +
"\u6d75\u6666\u696e\u732e";
S33KR1T_1NF0RM4T10N = new int[7];

}

for (int i = 0, j = 0; i < 7; i++, j += 2) {
S33KR1T_1NF0RM4T10N[i] =
(s.charAt(j) << 16) | s.charAt(j+1);
}

Example #2: .dex
0000:
0001:
0003:
0006:

const/4 v0, #int 7 // #7
new-array v0, v0, int[]
fill-array-data v0, 000a
sput-object v0,
Example2.S33KR1T_1NF0RM4T10N:int[]
0008: return-void
0009: nop // spacer
000a: array-data // for fill-array-data @ 0003
0: 1226858861 // #4920616d
1: 544366964 // #20726174
2: 1751478816 // #68657220
3: 1718578788 // #666f6e64
4: 544171552 // #206f6620
5: 1836410470 // #6d756666
6: 1768846126 // #696e732e
0026:

Example #2: .dex
0000:
0001:
0003:
0006:

const/4 v0, #int 7 // #7
new-array v0, v0, int[]
fill-array-data v0, 000a
sput-object v0,
Example2.S33KR1T_1NF0RM4T10N:int[]
0008: return-void
0009: nop // spacer
000a: array-data // for fill-array-data @ 0003
0: 1315272293 // #4e657665
1: 1914726255 // #7220676f
2: 1852727584 // #6e6e6120
3: 1734964837 // #67697665
4: 544829301 // #20796f75
5: 544567355 // #2075703b
6: 544105846 // #206e6576
7: 1701978215 // #65722067
8: 1869508193 // #6f6e6e61
9: 543974772 // #206c6574
10: 544829301 // #20796f75
11: 543453047 // #20646f77
12: 1848520238 // #6e2e2e2e
003e:

Interpreters 101
The portable way
static void interp(const char* s) {
for (;;) {
switch (*(s++)) {
case 'a': printf("Hell");
case 'b': printf("o");
case 'c': printf(" w");
case 'd': printf("rld!\n");
case 'e': return;
}
}
}
int main(int argc, char** argv) {
interp("abcbde");
}

break;
break;
break;
break;

Interpreters 101
The gcc way
#define DISPATCH() \
{ goto *op_table[*((s)++) - 'a']; }
static void interp(const char* s) {
static void* op_table[] = {
&&op_a, &&op_b, &&op_c, &&op_d, &&op_e
};
DISPATCH();
op_a: printf("Hell"); DISPATCH();
op_b: printf("o"); DISPATCH();
op_c: printf(" w"); DISPATCH();
op_d: printf("rld!\n"); DISPATCH();
op_e: return;
}

Interpreters 101
ARM assembly
op_table:
.word op_a
.word op_b
...

Two memory reads

#define DISPATCH() ldrb r0, [rPC], #1 \
ldr pc, [rOP_TABLE, r0, lsl #2]
op_a: ...
DISPATCH()
op_b: ...
DISPATCH()
...

Interpreters 101
ARM assembly (cleverer)
One memory read
#define DISPATCH() ldrb r0, [rPC], #1 \
add pc, rFIRST_OP, r0, lsl #6
.align 64
op_a: // address gets stored in rFIRST_OP
... up to 16 instructions ...
op_b:
... up to 16 instructions ...
op_c:
... up to 16 instructions ...
...

Optimizing Your Code

•
•
•
•
•

Intro
Memory
CPU
Advice
Conclusion

Time Scale
•

human interaction scale

•

•

human perception scale

•
•

•

10-30 interactions / sec

25-30 image frames / sec
continuous audio, synched within 100 msec

computer scale

•

run as much and as fast as possible

Get Plenty Of Rest
A well-behaved app…

•
•

spends most of its time sleeping
reacts quickly and decisively to user and network input

Loop Wisely
(1) for (int i = initializer; i >= 0; i--)
(2) int limit = calculate limit;
for (int i = 0; i < limit; i++)
(3) Type[] array = get array;
for (Type obj : array)
(4) for (int i = 0; i < array.length; i++)
(5) for (int i = 0; i < this.var; i++)
(6) for (int i = 0; i < obj.size(); i++)
(7) Iterable<Type> list = get list;
for (Type obj : list)

Loop Wisely
(1) for (int i = initializer; i >= 0; i--)
(2) int limit = calculate limit;
for (int i = 0; i < limit; i++)
(3) Type[] array = get array;
for (Type obj : array)
(4) for (int i = 0; i < array.length; i++)
(5) for (int i = 0; i < this.var; i++)
(6) for (int i = 0; i < obj.size(); i++)
(7) Iterable<Type> list = get list;
for (Type obj : list)

Loop Wisely
(1) for (int i = initializer; i >= 0; i--)
(2) int limit = calculate limit;
for (int i = 0; i < limit; i++)
(3) Type[] array = get array;
for (Type obj : array)
(4) for (int i = 0; i < array.length; i++)
(5) for (int i = 0; i < this.var; i++)

Danger! Danger!

(6) for (int i = 0; i < obj.size(); i++)
(7) Iterable<Type> list = get list;
for (Type obj : list)

Danger! Danger!

Avoid Allocation

•
•

short-lived objects need to be GCed
long-lived objects take precious memory

That’s all!

•
•
•
•
•

Intro
Memory
CPU
Advice
Conclusion

Questions?

?