360andev jake wharton share fb

Exploring Java's Hidden Costs

As Java 8 features come to Android, it’s important to remember that every standard library API and language feature comes with an associated cost. Even as devices get faster and have more memory, concerns of code size and performance overhead are still very relevant. This 360AnDev talk will be an exploration of hidden costs associated with some of Java’s features. We’ll focus on optimizations relevant for both library and application developers and on the tools that can be used to measure their impact.


Dex files (1:14)

We’ll start with a multiple choice question. How many methods are in this piece of code? Zero, one or two?


class Example {
}

You probably immediately have a gut reaction. Maybe it’s zero, maybe it’s one, and maybe it’s two. Let’s take a look and see if we can answer this question. First of all, there are zero methods inside this class. I’ve written no methods in the source file, so that’s perfectly valid to say. Of course, that would be a really uninteresting answer to this problem. Let’s start taking our class through the build pipeline of Android and see what comes up:


$ echo "class Example {
}" > Example.java

$ javac Example.java

$ javap Example.class
class Example {
Example();
}

We take our contents here and write it to a file, then use the Java compiler to take the source code and turn it into a class file. And then we can use this other tool from the Java development kit called javap. That is going to allow us to see inside the class file about what was compiled. If we run this on our compiled class, we see that there’s a constructor inside our example class. We didn’t write one in the source file, but Java C has taken the liberty of adding that constructor automatically. That means that there’s zero methods in source file but one method in the class. But that is not where Android builds stop:


$ dx --dex --output=example.dex Example.class

$ dexdump -f example.dex

In the Android SDK, there’s a tool called dx, which does dexing, which takes the Java class files, and turns it into Android’s Dalvik bytecode. We can run our example class through dex, and there’s another tool in the Android SDK called dexdump, which will give us a little information about what’s inside these dex files. You run it, and it’s going to print out a bunch of stuff. It’s like offsets into the file and counts and its various tables. If we look closely, one of these things stands out, and that’s the method table inside the dex file:


method_ids_size : 2

It says that there are two methods in our class. That makes no sense. Unfortunately, dexdump doesn’t give us an easy way to look at what the methods are. In response to that, I wrote a little tool which I’ll use to dump methods inside of a dex file:


$ dex-method-list example.dex
Example <init>()
java.lang.Object <init>()

If we do this, we see that it does return two methods. It returns our constructor, which we know the Java compiler created, even though we didn’t write one. But it also says that there is an object constructor. Certainly, our code is not calling new object everywhere, so where does this method come from that winds up being referenced in the dex file? If we go back to the javap tool that prints class file information, you can give it some additional flags to look more deeply inside the classes. I’m going to pass the -c flag, which is going to decompile the bytecode into something that’s a little more human readable.


$ javap -c Example.class
class Example {
    Example();
        Code:
            0: aload_0
            1: invokespecial #1 //java/lang/Object."<init>":()V
            4: return
}

At index one, it’s our generated constructor that is calling the super class constructor. That is because, even though it didn’t declare it, Example extends from Object. Every constructor has to call the super class constructor. It gets inserted automatically. That means there are two methods from our class flow.

All of these answers to my initial question were correct. The difference between these though is terminology. It’s where they live. We didn’t declare any methods. But only humans care about this. As humans, we read and write these files. We’re the only ones that really care what goes in and out of them. The other two are the ones that are more important, the number of methods that are actually compiled in the class files. These are the methods that declared or not, are inside that class.

The two methods are the number of methods that are referenced. That is inclusive in the sense that our own methods that we wrote are counted, and also all of the others that are referenced from within those methods from calling out to Android’s logger. That Log.d method that I’m referring to counts against this reference method panel, which is what’s in the dex file. That is what people traditionally refer to when you talk about method count on Android, because dex has the infamous limit for the number of methods that can be referenced.

We saw a constructor being created without us having declared one, so let’s look for some other hidden things that are generated that we might not have known were there. Nested classes are a useful construct, but they’re not in Java 1.0. They came in a later version. You see stuff like this for when you’re defining an adapter inside of a view or presenter:


// ItemsView.java
public class ItemsView {
    private class ItemsAdapter {
    }
}

$ javac ItemsView.java

$ ls
ItemsView.class
ItemsView.java
ItemsView$ItemsAdapter.class

If we can compile this class, this is one file with two classes. One nested inside the other. If we compile this, we see that two separate class files end up in the file system. If Java had truly nested classes, we would only get one class file. We would get ItemsView.class. But there’s no true nesting in Java, so what are in these classes? In the ItemsView, the outer class, all we have is the constructor. There’s no reference, no hint that there was an inner class:


$ javap 'ItemsView$ItemsAdapter'
class ItemsView$ItemsAdapter {
    ItemsView$ItemsAdapter();
}

If we look at the contents of the nested class, you see that it has its implicit constructor, and you know that it was inside an outer class because its name got mangled. Another important thing to note if I go back, we see that this ItemsView class is public, which is what we declared in the source file. But the inner class, the nested class, even though it’s declared as private, it’s not private in the class file. It’s package scoped. That makes sense because we had two class files that were generated, in the same package. Again, that just further proves that there’s no true nesting in Java.

Even though you’re nesting those two class definitions, you’re effectively just creating two classes that are next to each other in the same package. You could do this if you wanted to.

I know that I can do stuff to find a private static method in the outer class, and I can refer to that private method in the inner class.

Now that we know that there’s no such thing as true nesting, though, how does this work in our hypothetical separated system where our ItemsAdapter class needs to refer to the private method in ItemsView? That will not compile, however this will:

Get more development news like this


// ItemsView.java

public class ItemsView {
    private static String displayText(String item) {
        return ""; // TODO
    }

    private class ItemsAdapter {
        void bindItem(TextView tv, String item) {
            tv.setText(ItemsView.displayText(item));
        }
    }
}

What’s going on here? When you go back to our tools, we can use javac again.


$ javac -bootclasspath android-sdk/platforms/android-24/android.jar \
    ItemsView.java

$ javap -c 'ItemsView$ItemsAdapter'
class ItemsView$ItemAdapter {
    void bindItem(android.widget.TextView, java.lang.String);
    Code:
        0: aload_1
        1: aload_2
        2: invokestatic #3 // Method ItemsView.access$000:…
        5: invokevirtual #4 // Method TextView.setText:…
        8: return
}

I’m referencing TextView, so I had to add the Android APIs to Java. Now I’m going to print out the contents of the nested class to see what method it has called. If you look at index two, it’s not calling the displayText method. It’s calling access$000, which we didn’t define. Is that in the ItemsView class?


$ javap -p ItemsView123

class ItemsView {
    ItemsView();
    private static java.lang.String displayText();
    static java.lang.String access$000();
}

If we look, it is. We see our private static method is still there, but we now have this additional method that we didn’t write automatically being added.


$ javap -p -c ItemsView123

class ItemsView {
    ItemsView();
        Code: <removed>

private static java.lang.String displayText();
    Code: <removed>
    
static java.lang.String access$000();
    Code:
        0: aload_0
        1: invokestatic #1 // Method displayText:…
        4: areturn
}

If we look at the contents of that method, all it does is forward the call to our original displayText method. That makes sense because we need some way to call this private method from a package scoped to a class. Java’s going to synthesize a package scoped method to facilitate that method call.


// ItemsView.java
public class ItemsView {
    private static String displayText(String item) {
        return ""; // TODO
    }

    static String access$000(String item) {
        return displayText(item);
    }
}

// ItemsView$ItemsAdapter.java
class ItemsView$ItemsAdapter {
    void bindItem(TextView tv, String item) {
        tv.setText(ItemsView.access$000(item));
    }
}

If we go back to our separated example, our manual example, we can make this compile in the exact same way. We can add that method, and we can update the other class to refer to it. The dex file has this limit of methods, and so when you have these methods that are going to be added based on the ways that you’re writing your source file, those can add up. It’s important to understand this is happening because we’re trying to access a private member somewhere that it can’t work.

More Dex (10:52)

So you might say, “Well, you only did Java C. Maybe the dex tool can see that and automatically eliminate that method for us.”

If we compile our two classes that are generated and list them out, you can see that that’s not the case. The dex tool compiles it like it was any other method. It does end up in your dex file.

You might say, “Well, I heard about this new Jack compiler. And the Jack compiler takes the source file directly and directly produces dex files, so maybe it can do something where it doesn’t need to generate this extra method.” There’s certainly no access method. However, there’s this -wrap0 method, which is effectively the same thing.

There’s also a tool called ProGuard, which probably a lot of people are using. You might say, “Well ProGuard should be able to take care of this, right?” I can write a quick ProGuard key. I can run ProGuard on our class files and print out the methods.

You’ll see that the access method is still there. But if you look closely, we retain the access method, but displayText disappeared. What the hell’s going on here? You can unzip the jar that ProGuard produced, and then we can go back to our javap tool and look inside the ProGuarded class file:


$ unzip example-proguard.jar

$ javap -c ItemsView

public final class ItemsView {
    static java.lang.String access$000(java.lang.String);
        Code:
            0: ldc #1 // String ""
            2: areturn
}

If we look at the access method, it no longer is calling displayText. ProGuard has essentially taken the contents of displayText and moved them into the access method and deleted the displayText method. This access method was the only one referring to that private method, so it just inlined it because no one else was using it. Yes, ProGuard can kind of help. But it’s also not guaranteed to be able to do this. We got lucky because this is such a trivial example, but it is certainly not guaranteed. You might think, “Well, I don’t really nest classes that much, maybe it’s a handful. So if I’m only getting a handful of these extra methods, it’s not a big deal, right?”

Anonymous class (13:06)

Let me introduce you to our friend the anonymous class:


class MyActivity extends Activity {
    @Override protected void onCreate(Bundle state) {
        super.onCreate(state);

        setContentView(R.layout.whatever);
        findViewById(R.id.button).setOnClickListener(
            new OnClickListener() {
                @Override public void onClick(View view) {
                    // Hello!
                }
            });
    }
}

Anonymous classes behave the exact same way. They are effectively the same thing. It’s a nested class, but it has no name. If in these listeners, which we use all too frequently, you reference a private method in the imposing class, that’s going to generate a synthetic access method.


class MyActivity extends Activity {
    @Override protected void onCreate(Bundle state) {
        super.onCreate(state);

        setContentView(R.layout.whatever);
        findViewById(R.id.button).setOnClickListener(
            new OnClickListener() {
                @Override public void onClick(View view) {
                    doSomething();
                }
            });
    }
    
    private void doSomething() {
        // ...
    }
}

That is also true for fields:


class MyActivity extends Activity {
    private int count;

    @Override protected void onCreate(Bundle state) {
        super.onCreate(state);

        setContentView(R.layout.whatever);
        findViewById(R.id.button).setOnClickListener(
            new OnClickListener() {
                @Override public void onClick(View view) {
                    count = 0;
                    ++count;
                    --count;
                    count++;
                    count--;
                    Log.d("Count", "= " + count);
                }
            });
    }
}

I think this is the one that’s probably a lot more common. We have fields in these outer classes, these activities that we’re modifying the state of, inside of these listeners. I’ve done a completely awful implementation here, but what I’m doing is setting a value. I’m using a pre-increment, pre-decrement, post-increment, and a post-decrement, and then the log message has to read the value from the field. How many methods are we going to get from this? Maybe only two. Maybe one for reading, one for writing, and then the increment and decrement get turned into reads increments and writes. If that was only the case:


$ javac -bootclasspath android-sdk/platforms/android-24/android.jar \
MyActivity.java

$ javap MyActivity
class MyActivity extends android.app.Activity {
    MyActivity();
    protected void onCreate(android.os.Bundle);
    static int access$002(MyActivity, int); // count = 0    write
    static int access$004(MyActivity);        // ++count         preinc
    static int access$006(MyActivity);        // --count         predec
    static int access$008(MyActivity);        // count++         postinc
    static int access$010(MyActivity);        // count--         postdec
    static int access$000(MyActivity);        // count         read
}

We compile this, and one method is being generated for each of those types. So if you think that in an activity or fragment or whatever, you have four or five listeners, you have maybe ten fields that are private in the outer class. You’re getting a nice combination of explosion of access methods. You still might be unconvinced that this is a problem. Say, “Well, maybe it’s 50, maybe it’s 100. Is that really a big deal?” It turns out we can find out.

In the wild (15:03)

You can find out how prevalent these are in the wild. These commands will pull every APK from your phone.

You can see the table on slide 77, it sorts it by the most accessor methods by package name. And for my phone, we’re in the multiple thousands. Amazon makes up five of the top six here. The top ones are in 5,000 synthetic accessor methods. 5,000 methods, that’s an entire library. That’s like an apken pad. You have an entire apken pad of useless methods that only exist to be jumping points to some other method.

Also because we looked at ProGuard, obfuscation and inlining is going to screw with these numbers.

We can fix this. That is easy to do. We just have to not make something private. We have to make it package scoped when we’re referencing it across those boundaries. IntelliGate has an inspection for this. It’s not enabled by default, but you can go in and search for a private member. Which is fun to search for, and it will take our example, and it will highlight it yellow. You can option enter on it, and it will give you an intention action to just take that private member that you’re accessing and make it package scoped.

When you think about these nested classes, try to think of them as siblings instead of with having a parent-child relationship. You can’t really access a private member from an outer class. You have to make it package scoped. That is not going to cause problems because even if you’re a library, hopefully, these people aren’t putting classes in the same packages as you so that they can access these things that you’re making more visible. I also put in a feature request for a link check for this. Hopefully, in the future, you could potentially fail your build if you’re doing this.

Synthetic methods (18:45)

These synthetic methods are called synthetic because you didn’t write them.


// Callbacks.java

interface Callback<T> {
    void call(T value);
}

class StringCallback implements Callback<String> {
    @Override public void call(String value) {
        System.out.println(value);
    }
}

They were generated automatically for you. These accessor ones are not the only ones. Generics is another thing that came post-Java 1.0, and so it had to be retrofitted into how Java works. We see this a lot in libraries and even in our own applications. We’re using these generic interfaces because they’re extremely convenient, and they allow us to retain type safety.


$ javac Callbacks.java

$ javap StringCallback
class StringCallback implements Callback<java.lang.String> {
    StringCallback();
    public void call(java.lang.String);
    public void call(java.lang.Object);
}

If we just have a method that accepts a generic value, when you compile this, you’re going to find that every method that accepts that generic is going to get turned into two methods. One that accepts a string, whatever the generic type that you’re using is, and one that’s just object. That is like what erasure is. We have to generate code that only uses object because that’s what is going to end up being called when you access this generic method.


$ javap -c StringCallback
class StringCallback implements Callback<java.lang.String> {
    StringCallback();
        Code: <removed>

    public void call(java.lang.String);
        Code: <removed>

    public void call(java.lang.Object);
        Code:
        0: aload_0
        1: aload_1
        2: checkcast #4 // class java/lang/String
        5: invokevirtual #5 // Method call:(Ljava/lang/String;)V
        8: return
}

If we look at what goes in that extra method, it’s just a cast. It casts to that year type and then it calls the real implementation that accepts the generic. Anyone that’s calling this call method is going to dispatch to this object method. Their calling code is going to pass in whatever their object is and then this code has to cast it and call into the real implementation. Every method that uses a generic, winds up turning into two methods.

That is also true of return values. If you have a method that’s returning a generic, you basically see the exact same thing. Two methods get generated. One that returns. In this case, our view. Then at the bottom, one that returns objects. This one’s a lot more simple because it doesn’t have to really do anything, it just accepts the view and then re-returns it as an object type.

Another interesting thing to note here, which a lot of people don’t realize, is that this is a feature of the Java language.

If you have a method that you’re overriding, you can change its return value to be a more specific version of that type. That is called a covariant return type. It doesn’t even have to be, like in this case, we’re implementing an interface. The base class doesn’t even have to be an interface or anything. You can just be overriding a method from a base class. You can change its return type to be something more specific.

The reason that you would do something like this is if you had other methods in our second class, which had to call into this get method, and they want the implementation type. Not the more broad, in this case, View type. It will allow them to do customizations that were only specific to TextView because they’re in that class already.

Covariant return type (21:58)

Covariant return type. I’m sure you can guess what happens here.


$ javap TextViewProvider

class TextViewProvider extends ViewProvider {
    TextViewProvider();
    public android.widget.TextView get(android.content.Context);
    public android.view.View get(android.content.Context);
    public java.lang.Object get(android.content.Context);
}

We get another method. In this case, it’s both a generic and a covariant return type. We’ve taken our one method and turned it into three by basically not doing anything. I wanted to know how prevalent this was in applications so I checked every app that I had installed and it’s in the low thousands. There’s not a whole lot you can do here. I showed that ProGuard can kind of help. The advantage of this case is that if ProGuard can detect that no one is referring to the generic version of the method, the method that takes an object or returns object. It can eliminate that, so you will see hundreds or thousands of these can be removed by ProGuard. But some of them can’t because you are using them in the generic sense where you’re calling the method on the interface.

The last example that I want to look at for methods deals with something that’s new and upcoming in Android which is the the Java 8 language features.


class Greeter {
    void sayHi() {
        System.out.println("Hi!");
    }
}

class Example {
    public static void main(String... args) {
        Executor executor = Executors.newSingleThreadExecutor();
        final Greeter greeter = new Greeter();
        executor.execute(new Runnable() {
            @Override public void run() {
                greeter.sayHi();
            }
        });
    }
}

We’ve had retro-lamina for awhile. But now the Jack compiler is also implementing these in the same spirit, which is allowing them to be used in a way that’s back portable. But is there an associated cost to these new language features?

I have a simple class which says, Hi when we call its method. What I want to do is take my Greeter and make it say hello on this Executor. Executor has a single method called run, and it accepts a Runnable. In the current world, we would make that creator type final. Then we would create a new runnable and call the method directly.


class Greeter {
    void sayHi() {
        System.out.println("Hi!");
    }
}

class Example {
    public static void main(String... args) {
        Executor executor = Executors.newSingleThreadExecutor();
        Greeter greeter = new Greeter();
        executor.execute(() -> greeter.sayHi());
    }
}

In Lambda World it’s just reducing the verbosity of doing that. That will still create a Runnable, but it does so implicitly. You don’t have to specify the type. You don’t have to know the actual method name or the argument types.

The last one is method references. These are a little more interesting because it infers that this is a method that returns nothing and accepts no arguments. I can turn that into a Runnable automatically because I know all I have to do is call that method.


class Greeter {
    void sayHi() {
        System.out.println("Hi!");
    }
}

class Example {
    public static void main(String... args) {
        Executor executor = Executors.newSingleThreadExecutor();
        Greeter greeter = new Greeter();
        executor.execute(greeter::sayHi);
    }
}

How much do these cost? (24:45)

That’s fun, but how much do these cost? What are the costs of applying these language features? I set up a Retrolambda toolchain here and a toolchain using Jack.


Retrolambda toolchain

$ javac *.java

$ java -Dretrolambda.inputDir=. -Dretrolambda.classpath=. \
    -jar retrolambda.jar

$ dx --dex --output=example.dex *.class

$ dex-method-list example.dex


Jack toolchain 

$ java -jar android-sdk/build-tools/24.0.1/jack.jar \
        -cp android-sdk/platforms/android-24/android.jar \
        --output-dex . *.java

$ dex-method-list classes.dex

Neither of these is using ProGuard, or minification in Jack’s case, because it doesn’t affect the results. In the anonymous class case, the case that we’ve been using for so long, it’s always two methods.


Example$1 <init>(Greeter)
Example$1 run()

$ javap -c 'Example$1'
final class Example$1 implements java.lang.Runnable {
    Example$1(Greeter);
        Code: <removed>

    public void run();
        Code:
        0: aload_0
        1: getfield #1 // Field val$greeter:LGreeter;
        4: invokevirtual #3 // Method Greeter.sayHi:()V
        7: return
}

If we compile our example, we see that this is our anonymous class, given assigned a monotonically increasing number here. We see the constructor. The constructor’s going to take in the Greeter class for us and then it has a run method, which if we decompile it, all it does is call the method. That is exactly what we expect, very straightforward.

If you’re using an old version of retrolambda, this is really expensive. That one little tiny line of code can be six or seven methods to produce that functionality, but the current version’s down to four. And Jack even bests it with three. But what’s the difference? Why is there that extra method?

We know how to figure that out. This is retrolambda, which has two additional methods:


Example lambda$main$0(Greeter)
Example$$Lambda$1 <init>(Greeter)
Example$$Lambda$1 lambdaFactory$(Greeter)  Runnable
Example$$Lambda$1 run()

$ javap -c 'Example$$Lambda$1'

final class Example$$Lambda$1 implements java.lang.Runnable {
    public void run();
        Code:
            0: aload_0
            1: getfield #15 // Field arg$1:LGreeter;
            4: invokestatic #21 // Method Example.lambda$main$0:
            7: return
}

The one that’s new is the top one. What’s happening here is, you’re defining a block of code inside the lambda, and that code has to go somewhere. It’s not encoded in the method that defines the lambda because that would be weird. It doesn’t belong to that method. It has to be stored somewhere so that it can be passed into whatever you’re calling.

That’s what this top method is. It just copies and pastes whatever you write into the lambda into method in that same class. You can see the implementation here. All it does is delegate to the sayHi method. Very similar to what our runnable implementation did. We still have our constructor. We still have our run method. Except the repair of the run method is different. Instead of calling Greeter directly, it’s going to call back into the original class and call that lambda method. That is the extra method. Here’s where retrolambda screws it up.


Example lambda$main$0(Greeter)
Example$$Lambda$1 <init>(Greeter)
Example$$Lambda$1 lambdaFactory$(Greeter)  Runnable
Example$$Lambda$1 run()

Instead of calling the constructor directly to create this generated class, it generates another method, which is a static factory method that calls the constructor. Jack’s basically the same thing except it doesn’t have that additional static method.


Example -Example_lambda$1(Greeter)
Example <init>()
Example main(String[])
Example run(Runnable)
Example$-void_main_java_lang_String__args_LambdaImpl0 <init>(Greeter)
Example$-void_main_java_lang_String__args_LambdaImpl0 run()
Greeter <init>()
Greeter sayHi()
java.io.PrintStream println(String)
java.lang.Object <init>()
java.lang.Runnable run()

We still get the lambda one, although it’s named kind of crazy, and then the generated class is named very creatively with the entire type signature in the name. So that’s it. Three methods. Lambdas cause that additional method at the top to be created. That’s why they cost one additional method.

Method references are also really interesting. Retrolambda and Jack are essentially tied. Retrolambda sometimes has to generate an extra method, and that’s because you might be referring to a private method, and so it’s not retrolambda generating it. Java generates one of those synthetic accessor methods because if you’re passing a reference to a private method to another class, it’s going to have no way of calling that. That’s what the fourth one is.

Jack, interestingly enough, generates three for every single method reference. It should be generating two for every single one except for that private case. In that case, it should only be generating three. Currently, it generates an accessor method for every single method reference. There’s a bug filed for that too, so hopefully we’ll see Jack get down to two methods. That’s really important because that puts the method reference on the same par as the anonymous class. It makes it a zero cost abstraction from switching from the anonymous class to the method reference, which will be nice.

Lambda’s, unfortunately, will likely never get down to the same amount. The reason that that will never happen is that you also could be referring to private members or private methods inside of the lambda. It can’t copy that into the generated runnable. Because again, it doesn’t have any way of accessing those things. We can count these as well.

Lambdas in the wild (30:05)

Let’s look and see how many lambdas are being used in the wild. Same deal. By the way, this takes a long time.


#!/bin/bash             lambdas.sh
set -e

ALL=$(dex-method-list $1)

RL=$(echo "$ALL" | \grep ' lambda\$' | wc -l | xargs)
JACK=$(echo "$ALL" | \grep '_lambda\$' | wc -l | xargs)

NAME=$(basename $1)

echo -e "$NAME\t$RL\t$JACK"


$ column -t -s $'\t' \
    <(echo -e "NAME\tRETROLAMBDA\tJACK" \
        && find apks -type f | \
            xargs -L1 ./lambdas.sh | \
            sort -k2,2nr)

NAME                         RETROLAMBDA     JACK
com.squareup.cash             826             0
com.robinhood.android         680             0
com.imdb.mobile             306             0
com.stackexchange.marvin     174             0
com.eventbrite.attendee     53                 0
com.untappdllc.app             53                 0

It takes around 10 minutes. It also depends on how many apps that you end up pulling. If you wind up doing this for whatever reason, don’t get impatient. It will take a long time, but you will get a result.

Unfortunately, apparently not a lot of people are using lambdas, and I was excited to see that we pay the most. We have 826 lambdas. That’s the number of lambdas and not the number of methods. The number of methods that we have from our lambdas is 826 times three or maybe four.

No one’s using Jack yet, or at least, of the applications I installed, no one’s using Jack with lambdas. They might be using Jack and not using lambdas, which would be weird. Or additionally, they could be ProGuarding.

So again, this ProGuard completely hides these lambda classes and names of the methods. If you’re a popular application using lambdas, and you ProGuard, that’s probably why you’re not on this list. Or I just don’t like your app. That was all on methods.

The reason I was looking into this was one, to stave off hitting the 65K limit. But those methods have a run time cost as well. There are costs for loading additional bytecode. There’s also costs for the extra trampoline that you have to go through when you’re executing them. The private field one is my favorite because a lot of times you see that happen inside these anonymous listeners. Those are usually running as the result of the UI interaction on the main thread.

What you don’t want is a computationally expensive piece of code that you have to run on the main thread, whether it’s for animation, size calculation, whatever. You don’t want those, every single time you’re referencing those fields; you don’t want to be jumping through that extra method. Looking up a field is fairly fast. Invoking a method and then looking up a field is still going to be fast, but it’s 100% of the time going to be slower than just looking up the field. You’re introducing these indirections which you’re not going to be dropping frames all of a sudden because these accessor methods exist. But they’re useless methods that the only thing they serve to do is bloat your APK and very, very subtly slow down your application.

Collections (33:21)

I want to change gears a tiny bit and talk about something a little more run-time focused. That has to deal with collections.


HashMap<K, V>                ArrayMap<K, V>
HashSet<K, V>                ArraySet<V>
HashMap<Integer, V>            SparseArray<V>
HashMap<Integer, Boolean>    SparseBooleanArray
HashMap<Integer, Integer>    SparseIntArray
HashMap<Integer, Long>        SparseLongArray
HashMap<Long, V>            LongSparseArray<V>

If you have anything that resembles the following in your application, you’re probably wasting more resources than you should.

Android has these specialized collections which I think most people nowadays know about. The implementation varies, but they’re specialized to these cases which are very common. For example, when you have an integer index into a map referring to some value. There’s a specialized collection for that.

A lot of times people talk about this on the context of autoboxing. What autoboxing is, if you’re not aware, is if we have this HashMap, which accepts an integer key, so you have an integer of some value, and you want to put a value in this map. Or conversely, you’re iterating over the entries, and you want to get the value from a key, this conversion isn’t straightforward. It has to go through an additional step called autoboxing, which is where it takes the primitive value and turns it into the class version of that, which in this case is an integer.

The bottom one’s not that expensive. It’s unwrapping a type. The top one is the one that’s bad. For small numbers, there’s a cache, so it’s not bad, but if you had a random slew of integers, it’s going to be allocating objects every single time you call a method. Which is generic and accepts the big I integer. That is what most people talk about as the big advantage. It’s very true that this is a significant advantage, but it turns out there are two other big advantages which aren’t talked about a lot.

The first one is data indirection. If you look at how HashMap is implemented, it has an array of these nodes, and that keeps its own size. When you’re either putting a value or looking up a value, it has to jump into this array. That is the hashing step. This is the cost and time operation where it finds the hash and then does the offset into the array. However, this is an array of nodes. The node type has both the key and the value. It also has the hash, and it has a pointer to an additional node. We got to the array; we found the reference to the node, and we have to jump to the node now. Then we have to look inside the node if we want the value. We get the reference to the value, and we have to jump to it. We have to go through these indirections. They’re in all different spaces in memory. You have to make these jumps in memory to get a value for a single key. Or to put a value at a single key. And then it can get worse.

This is the hash collision problem, where if two items hash to the same bucket, HashMap will degrade into what is a linked list inside that bucket. If we happen to hit this case, we now have to walk the link list and find the matching exact hash. I’m going to look at sparse array. Sparse array’s the replacement for this one here. We’re going to look at that in a second, but before we get there, the other advantage just comes around to overhead. The overhead in memory of these collections. We have two classes here.


$ java -jar jol-cli-0.5-full.jar internals java.util.HashMap
# Running 64-bit HotSpot VM.
# Objects are 8 bytes aligned.
java.util.HashMap object internals:
OFFSET     SIZE     TYPE DESCRIPTION                 VALUE
0         4         (object header)                 01 00 00 00
4         4         (object header)                 00 00 00 00
8         4         (object header)                 9f 37 00 f8
12         4         Set AbstractMap.keySet             null
16         4         Collection AbstractMap.values     null
20         4         int HashMap.size                 0
24         4         int HashMap.modCount             0
28         4         int HashMap.threshold             0
32         4         float HashMap.loadFactor         0.75
36         4         Node[] HashMap.table             null
40         4         Set HashMap.entrySet             null
44         4         (loss due to the next object alignment)

Instance size: 48 bytes
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total

We can use a tool called Java object layout, and it’s going to tell us what the overhead of creating one of these objects is in memory. Running on HashMap, it’s going to print out a bunch of stuff. It is showing you the cost per field. The important number is here at the bottom, where every instance of a HashMap, just the HashMap, not the nodes, not the keys or values or anything. Just the HashMap object itself is 48 bytes. It’s not bad. That’s small.


$ java -jar jol-cli-0.5-full.jar internals 'java.util.HashMap$Node'
# Running 64-bit HotSpot VM.
# Objects are 8 bytes aligned.

java.util.HashMap$Node object internals:
OFFSET     SIZE     TYPE DESCRIPTION     VALUE
0         12         (object header)     N/A
12         4         int Node.hash         N/A
16         4         Object Node.key     N/A
20         4         Object Node.value     N/A
24         4         Node Node.next         N/A
28         4         (loss due to the next object alignment)

Instance size: 32 bytes
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total

We’re running on the node object. Same stuff. We see our four fields. This one’s 32 bytes. It’s 32 bytes for every single node in that map. Every item in that map, every key and value pair is going to be inside one of these nodes. It’s 32 times the number of entries.

We can use a formula like this to figure out what the actual size of an object is at runtime when I start putting values into it. That is not fully correct. You also have to account for things like the array. There’s an array that has to hold the nodes, so we need to account for the space that that array has to occupy. That is complicated. It’s four, which is a single integer, which is the reference to each array, multiplied by the size of the array.

The problem is, HashMap has this thing called a load factor. The eight at the end is a constant overhead for every array. But the load factor never tries to be full. It tries to maintain a certain percentage of fullness, so when it reaches that percentage, it’s going to grow as an array list would. The HashMap is also going to grow so that it can maintain some empty spaces.

The reason for that is because, if that doesn’t happen, you start getting a lot of collisions and a lot of degradation performance. That would be approximately the value that a HashMap with however many entries and whatever the load factor is. We could figure out how many bytes in memory this is going to occupy. By the way, the default load factor is 75%. HashMap tries to stay 3/4 full at all times.

Sparse array is what you should be using if you want to replace HashMaps like this. Let’s look at the two cases we looked at in HashMap, which is the indirection, the levels of indirection, and the size of memory. Sparse array stores two arrays that are siblings. One is just the keys; the other is just the values. If we’re looking up a value in this map, or putting a value on this map, the first thing we do is we go into this integer array, and unlike HashMap, it’s not constant time. It has to do a binary search inside this array. We can then jump to the values array, and in this case, the binary search gave us the exact cell in the values array to look up the value. Because that array is the values, we can then return, jump directly to that reference and return that back to you.

There’s a lot less indirection here regarding memory. The integer array is continuous; there’s no linked list. We can jump directly inside the values array. There’s no node object that we have to unwrap and then get to the value. There’s a lot less indirection. However, it does come with that slow down of not being perfectly constant time. This is why you want to keep them for relatively small maps. And by small, it’s in the order of hundreds of entries. If you get into the thousands, the performance of the binary search is going to cause it to be so slow that the overhead of HashMap probably starts looking pretty appealing regarding performance.


$ javac SparseArray.java

$ java -cp .:jol-cli-0.5-full.jar org.openjdk.jol.Main \
internals android.util.SparseArray

# Running 64-bit HotSpot VM.
# Objects are 8 bytes aligned.

android.util.SparseArray object internals:
OFFSET     SIZE     TYPE DESCRIPTION                 VALUE
0         4         (object header)                 01 00 00 00
4         4         (object header)                 00 00 00 00
8         4         (object header)                 1a 69 01 f8
12         4         int SparseArray.mSize             0
16         1         boolean SparseArray.mGarbage     false
17         3         (alignment/padding gap)         N/A
20         4         int[] SparseArray.mKeys         [0, 0, 0, 0, 0, 0, ]
24         4         Object[] SparseArray.mValues     [null, null, null, ]
28         4         (loss due to the next object alignment)

Instance size: 32 bytes
Space losses: 3 bytes internal + 4 bytes external = 7 bytes total

In this case, because the classes are exactly the same and the JVM 64 bit, and Android’s now 64 bit, the number should be translatable. If that bothers you, treat them as an approximation and allow for some 20% variance. It’s certainly a lot easier than figuring out how to get the object sizes on Android itself. Which is not impossible, it’s just a lot easier this way.

The object itself for sparse array is a little bit smaller, 32 bytes. That size doesn’t matter. What does matter, however, is that you know these aren’t just 32 plates. We have the entry problem again. We have to account for the array, that is, the integers for the keys, and that’s four times the number of entries, plus eight. Then there’s also the array for the values, which is the same thing, four times the number of entries, plus eight.

What’s different here is that sparse array doesn’t have a load factor, but it does implicitly because these arrays are trees. They’re binary trees. They’re not filled. They’re not contiguous. There are spaces inside of them that are unoccupied. We have to account for that with a little fudge factor, which is similar to the load factor. In this case, and it totally depends on what data you’re putting into the map, I’m using the same value. I’m assuming that these arrays are going to be about 75% full, which is a pretty safe assumption.


SparseArray<V>
32 + (4 * entries + 4 * entries) / 0.75

HashMap<Integer, V>
48 + 32 * entries + 4 * (entries / loadFactor) + 8

Now we can make a direct comparison against these things. We know that we can count the indirection jumps. That’s easy. Now we can use these equations to compare the actual values of memory that these instances would occupy.


SparseArray<V>
32 + (4 * 50 + 4 * 50) / 0.75 = 656

HashMap<Integer, V>
48 + 32 * 50 + 4 * (50 / 0.75) + 8 = 1922

I’m going to use .75 again for HashMap, which is the default. We can pick a value for number of entries. In this case, I picked 50. Maybe it’s a map of states in the United States. Then we can run these computations. What you see is that the sparse array is 1/3 of the size. You have to remember; there’s a slight performance overhead to this because every operation is no longer constant time. It’s 50 elements, and so the number of searches in the binary tree is going to be very fast.

Conclusion (44:18)

There are some extremely trivial to-dos to avoid this overhead, both at compile time with methods, and run-time for the overhead of various objects, and the indirection that they may afford.

Turn on that private member inspection and listen to it. Don’t ignore it. You don’t have to do it for every single type, or all at once. For libraries it’s a little more important.

As a library, you should want to minimize your impact both in APK size and run-time performance. If you have a library, you might want to go through and find all these. There is no reason for the synthetic accessor methods to exist in libraries. It’s a waste of space in the dex file. It’s a waste of time in the run-time. Report them as bugs.

If you are using retrolambda, make sure you’re upgraded to the latest version. If you’re writing an open-source library, maybe just suck it up and deal with the anonymous classes. It goes back to the fact that you want to have the minimal impact for your application developers, so that you’re never the problem as the library.

Try out Jack. It’s a big deal. It’s still undergoing rapid development. It’s missing a lot of things that are going to make it applicable to everyone here, but certainly, there’s going to be applications which are more trivial, or not doing anything exotic in build time.

Don’t ignore bugs. Don’t switch, find it crashes and be like, “Oh, whatever, I’ll try in two years.” You can do that, just report the bug before you switch back to Java C index. This is the future, and you can cover your ears and close your eyes, but it’s happening. It’s better to find these things sooner rather than later. Then just turn on ProGuard. ProGuard helps out here. Whether you’re using ProGuard or there’s the new shrinker which is incremental and still works with instant run and presumably will be what Jack uses as well.

Don’t use overly matchy rules. If you ever see * * in a ProGuard rules file, that is wrong 100% of the time. That is never what you should be using because you’ve effectively just nuked any advantages that you were getting from ProGuard. You’re saying that “Yeah, I’m pulling in OkHttp, but I don’t want all of these methods from HTTP/2, which I’m not even using. I don’t want them to be stripped. I want to retain them just in case.” It’s not smart. If you see these on open-source libraries, that is a bug. Report that as a bug. If you have those in your own app, try and figure out why they were initially there. Take them out, and think and look at the failure of ProGuard and see if there’s something more specific that you can change your rule too. If this stuff is really tickling you and interesting you, there are a few other presentations that you can take a look at.

Resources

Next Up: Realm Java enables you to efficiently write your Android app’s model layer in a safe, persisted, and fast way.

General link arrow white

About the content

This talk was delivered live in July 2016 at 360 AnDev. The video was recorded, produced, and transcribed by Realm, and is published here with the permission of the conference organizers.

Jake Wharton

Jake Wharton is an Android developer at Square working on Square Cash. For the past 5 years he’s been living with a severe allergy to boilerplate code and bad APIs. He speaks at conferences all around the world to educate more about this terrible plague that afflicts many developers.

4 design patterns for a RESTless mobile integration »

close