Facebook building 'on-demand executable file format' that self-inflates using homebrew compression

Already shrinks The Social Network’s™ Android apps by 20 per cent compared to rivals, has uses beyond that

Facebook has developed promising asymmetric compression technology and aspires to share it with the world.

Dubbed "Superpack" and detailed in a post by Facebook Engineering software engineer Sapan Bhatia, the tech "combines compiler analysis with data compression to uncover size optimizations beyond the capability of traditional compression tools".

Bhatia explains that Facebook needs compression because its apps keep bloating, but users don't want bigger apps. Algorithmic options such as Deflate and LZMA can certainly do a job, but Bhatia said they "work well with monolithic data" but "weren't enough to offset the pace of growth we were seeing in our apps".

So Facebook did its own thing.

"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," Bhatia wrote. "In other words, data can be compressed by representing it as a program that generates the data."

Bhatia admits that the idea of reducing Kolmogorov complexity in itself "is not new to the domain of compression". But Superpack puts it to work in novel ways "by combining compiler methods with modern compression techniques".

The project works rather well. Bhatia reports that Superpack "has helped reduce the size of our fleet of Android apps, which are substantially smaller in comparison to regular Android APK compression, with average savings of over 20 per cent compared with Android's default Zip compression".

Which may be a mixed blessing given Facebook's apps have proven problematic in so many ways.

But Facebook is already contemplating other uses for Superpack, because it is good at compressing code and data.

"We are working on a new on-demand executable file format that saves disk space by keeping shared libraries compressed and decompressing them at load time," Bhatia wrote. Delta compression of code to reduce the size of software updates is another option.

Longer-term data storage is also on the agenda.

"We are also investigating using Superpack as a cold-storage compressor, to compress log data and files that are rarely used," Bhatia wrote.

The project is also applicable to iOS, and Bhatia said a port is on the cards – as is sharing it outside Facebook.

"We aspire to bring the benefits of Superpack to everyone. To this end, we are exploring ways to improve the compatibility of our compression work with the Android ecosystem," Bhatia wrote, adding "We may someday consider open-sourcing Superpack."

For now, Bhatia and Facebook are content to have blogged about Superpack. The post describing the tech includes more mathematical detail and compression wonkery than it's sensible to include in a news story but will probably go some way towards satisfying the curious. ®