In a recent article, Facebook described its novel technique for Android app compression, Superpack, which combines compiler analysis with data compression. While not yet available for everyone, Facebook is hoping to open source it.
According to Facebook engineers, Superpack has been able to reduce the size of their Android apps by over 20 percent over the default Android APK Zip compression for the last two years.
The approach underlying Superpack is based on an insight in Kolmogorov’s algorithmic measure of complexity, which defines the information content of a piece of data as the length of the shortest program that can generate that data.
For example, a program that generates a Fibonacci sequence can be seen as a compressed representation of a list of Fibonacci numbers. Reducing Kolmogorov complexity is not a new approach to data compression, says Facebook, but what sets Superpack apart is it combining compiler methods with modern compression techniques.
Superpack compression leverages common compiler techniques such as parsing and code generation, as well as more recent innovations such as Satisfiability modulo theories (SMT) solvers to find the smallest programs.
The compiler brings semantic knowledge about the program that is used to effectively enhance the compression step by both helping eliminate redundancy as well as optimizing the representation of frequent pieces of information, i.e. reduce entropy coding.
This approach is used to compress executable code. For non-code data, Superpack will try to transform them into programs that can be executed at decompression time to generate the original data.
An example of this technique is the compression of Dex references, which are labels for well-known values in Dex code. Dex references have a high degree of locality. To exploit this locality, we transform references into a language that stores recent values in a logical register, and issues forthcoming values as deltas from the values that were pinned down.
One limitation of Superpack, says Facebook, comes from the lack of integration with the tools used to create and distribute Android updates. In fact, updates of Superpack-compressed apps end up being larger than updates of Zip-compressed apps, basically due to the fact that app updates are distributed as compressed archives, which requires the ability to decompress an app's content, calculate its delta, and then compress it again.
We believe that issues of this type could be addressed through finer-grained interfaces between Superpack and Android tools, increased customizability in Android’s distribution mechanisms, and a public documentation of Superpack’s file format and compression methods.
As mentioned, Superpack is not available outside of Facebook. But its approach is replicable to other platforms as well, including iOS and others. Facebook itself is working on those ports, with the aim of making it available more broadly.
Facebook's engineers cover much more ground about Superpack than what can be summarized here, so do not miss the original article for the full details.