In a lengthy post on the Facebook Engineering blog today, Facebook software engineer Sapan Bhatia talks about the unique challenge of managing application size. He explains that Facebook’s developers are constantly adding new bits of code to the company’s mobile apps, including the Facebook app, Messenger, WhatsApp and Instagram.
Facebook Inc.’s software team has spent the last two years working on a way to compress application code with a view to keeping app sizes more manageable, ultimately coming up with a new technique called Superpack.
Facebook’s app developers already employ a bunch of data compression techniques, but the company said these methods cannot keep up with the rate at which it adds new features and updates.
“Every day, developers check in large volumes of code, and each line of code translates into additional bits in the apps that people ultimately download onto their phones,” he said. “Left unchecked, this added code would make the app bigger and bigger until eventually the time it takes to download would become unacceptable.”
According to Bhatia, Superpack’s strength lies in its ability to compress specific types of code such as machine code and bytecode as well as some kinds of structured data. He explained that the basic underlying approach to 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. What that means is that it’s possible to compress data by representing it as a program that generates that data, as opposed to compressing the information itself.
So for the last two years, Facebook’s team has been working on the Superpack technique, which it claims has been able to achieve “significantly better” compression ratios than existing tools.
“When that data is code to begin with then it can be transformed into one with a smaller compressed representation,” he wrote. “A program that generates Fibonacci numbers coupled with a list of indices is a highly compressed representation of a file containing such numbers.”
He added that the idea of reducing Kolmogorov complexity is not a new one in the area of data compression. What’s new is that Superpack employs a combination of compiler methods with modern compression techniques to achieve that goal.
Bhatia said Facebook has employed Superpack to put a check on developer-induced app growth in the past couple of years and actually managed to reduce the size of its Android apps. They are now “substantially smaller in comparison to regular Android APK compression,” Bhatia wrote, with the average app size reduction amounting to about 20%. The main Facebook app on Android, for example, has actually been reduced by more than 40% using Superpack, while Messenger has achieved a reduction of over 30%. For reasons that were not discussed, the technique appears to have been less successful with WhatsApp.