Last fall we announced ReDex, a tool for reducing the size of Android apps to improve performance. At the time, we were working on optimizations such as minification, inlining, and dead code elimination to make the bytecode smaller, but we hadn't yet put them to the test in production. Now we have! In November, we shipped the first ReDex-optimized version of Facebook for Android, which was 25 percent smaller and had up to 30 percent faster start times. Today we’re excited to announce that we are open-sourcing ReDex, with the hope that developers can use these tools to make every Android app smaller and faster — not just Facebook.
In our previous post, we talked about several of the optimizations we had built into ReDex. Since then, we’ve implemented several new optimizations that helped us achieve the speedups we saw in production.
Feedback-directed class layout
One way we achieved speedup was to optimize our app’s bytecode layout on disk. By default, classes in the dex files are not organized with respect to their runtime behavior but are placed in whatever order the build toolchain happens to use. When the app starts, the disk has to seek out class data scattered randomly around a very large file, which leads to delays, especially on older devices with slower internal flash storage. We realized that optimizing class locality would improve bytecode-loading performance.
We used an approach that is common to native code optimizers: feedback-directed optimization (FDO). To perform FDO, we first gather runtime data in the lab. Since cold start performance is important to people using Facebook, we trace the classes loaded during cold start on a set of test devices. We then feed this class trace into ReDex, which places the classes used during cold start first in the dex. This placement minimizes the number of fetches from flash needed to load bytecode on startup.
Coding against interfaces rather than implementations is a good software engineering practice. However, sometimes the release version of an app has interfaces with only a single implementation. This extra interface takes up additional space in memory and consumes extra method refs, which may force us to have additional dex. In addition, calling interface methods is usually less efficient at runtime than calling virtual methods.
ReDex can remove unnecessary interfaces because it sees the whole program at once. To remove such interfaces, we perform an analysis pass that walks the class hierarchy and finds any interfaces with only a single implementor. Once single-implementor interfaces are identified, we traverse the code and rewrite method calls to directly invoke the implementation method, and then delete the now unused interface.
Dex files include some metadata that is unnecessary at runtime. For example, every class contains the name of the Java source file that defines it. We wrote a simple pass to strip out these source file references and replace them with other strings that already appear in the dex. Since filenames are often quite long and descriptive, this optimization saves a considerable amount of storage.
Another bit of metadata to consider are annotations. While some annotations are required at runtime, many are used only by analysis tools or the build system. We added a whitelist-based pass to remove unnecessary annotations from release builds.
We measured performance on a set of test devices in the lab as well as by gathering telemetry data from real-world devices. Our laboratory measurements were promising: On a clean Nexus 4 running Android 4.4, we found that start-up time was reduced from about 2 seconds to only 1.6 seconds — a 20 percent speedup.
After stabilizing all of the optimizations we were working on, we launched our first version of ReDex in November. With this version, we reduced Facebook's dex size by about 25 percent. This reduction saves a good chunk of disk space for people using Facebook on Android, and it also speeds up cold start since the system has to fetch less bytecode to get running.
Our real-world data produced very similar results. Overall, we saw about a 20 percent reduction in cold start time across all people using Facebook. While fast, high-end phones saw speedups, we were happy to discover that ReDex provided the greatest benefit — up to 25 to 30 percent speedups — for typical Android devices, which make up the majority of phones that people use to access Facebook around the world. This effect is mostly because of memory pressure: Devices with smaller memory and slower flash benefit the most from optimizations that reduce the number of bytecode fetches and the disk space used.
Designing for developers
It was important to our team to build a tool that would not only improve the experience of everyone using Facebook for Android, but would also be easy for developers to use. We designed ReDex to be ergonomic from a developer's point of view: We wanted to be able to iterate quickly on ReDex so that we could test and tune our optimizations efficiently. This need led us to three design principles:
- It needs to be fast. Having a fast build process is extremely important for developers. Not only is it downright frustrating to wait a long time for a build, but it also slows down the development of new optimizations and makes it hard to tune settings for the best performance. We worked hard to optimize ReDex itself: Even on an app as big as Facebook, it runs in only 30 seconds.
- It has to have a simple interface. The dex bytecode is only one part of Android’s APK format. We’ve built ReDex to handle all the details of unpacking the bytecode from an APK, analyzing it, and repacking it all in the same format. This design makes it very easy to add ReDex to an existing build toolchain without adding supporting scripts.
- It needs to be configurable. To make an app smaller, ReDex will remove code that it thinks can be optimized away. But there are a few situations in which ReDex can’t determine that code is still in use. One is JNI: An app that uses native code can instantiate objects and call methods in native code that the bytecode optimizer can’t see. Another is reflection: A program can invoke methods using arbitrary strings, so ReDex can’t prove that methods are unused. In practice, many things aren’t accessed via JNI or reflection, so we assume that they aren’t. But for the cases that are, we’ve made it easy to specify what methods not to optimize. Simply feed a JSON configuration file into ReDex letting it know what to leave alone. Our online docs describe how to write a good config file.
Open source: Write a ReDex optimization
We’re really excited to make this technology available to the whole Android community. We’re looking forward to helping make other apps faster. We have carefully written ReDex to separate the library that parses and produces dex from the optimizations themselves. We've done this to create a platform to reduce the amount of work necessary to write new optimizations and tools for dex. Starting today, you can find ReDex on GitHub and try it out on your apps. We'd love to get feedback in any form: We’re happy to hear issues and suggestions, and doubly happy to receive pull requests with great new features. We can't wait to hear from you!