Broadly, each such algorithm tries to substitute recurring sequences of data with pointers to their previous occurrences. Improved LZ parsingĬompressors typically identify repeating sequences of bytes using an algorithm selected from the LZ family. Semantic knowledge from the compiler half of Superpack leads to enhanced LZ parsing (the step in compression that eliminates redundancy), as well as improved entropy coding (the step that produces short codes for frequent pieces of information). One important ingredient of Superpack’s effectiveness is its ability to marry these compiler techniques with those used in mainstream data compression. 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. It gives the data compression engineer access to a treasure trove of mature compiler tools and techniques that can be repurposed to the end of data compression. There is considerable benefit in formalizing compression as a generative process that produces small programs. Superpack’s novel approach involves combining compiler methods with modern compression techniques to achieve this goal. The idea of reducing Kolmogorov complexity in itself is not new to the domain of compression. A program that generates Fibonacci numbers, coupled with a list of their indices, is a highly compressed representation of a file containing such numbers. When that data is code to begin with, then it can be transformed into one with a smaller compressed representation. In other words, data can be compressed by representing it as a program that generates the data. 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. Superpack’s strength lies in compressing code, such as machine code and bytecode, as well as other types of structured data. Compression is a mature field, and the techniques we’ve developed crosscut the entire compression spectrum, from data comprehension and Lempel-Ziv (LZ) parsing to statistical coding. While existing compression algorithms, such as Zip’s Deflate and Xz’s LZMA, work well with monolithic data, they weren’t enough to offset the pace of growth we were seeing in our apps, so we set out to develop our own solution. Superpack: Compilers meet data compression The reduction in the size of these apps thanks to Superpack is illustrated in the table below. Some apps that use Superpack include Facebook, Instagram, WhatsApp, and Messenger. Superpack’s compression 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 percent compared with Android’s default Zip compression. Over the past two years, Superpack has been able to check developer-induced app size growth and keep our Android apps small. Superpack pushes the limits of compression to achieve significantly better compression ratios than existing compression tools. So we developed a technique called Superpack, which combines compiler analysis with data compression to uncover size optimizations beyond the capability of traditional compression tools. But compression alone isn’t enough to keep pace with all the updates we make and features we add to our apps. Such savings are especially important in regions where mobile bandwidth is limited, making it costly to download large apps. These compressed files take up less space, which means smaller apps that download faster and use less bandwidth for billions of users around the world. Compression is one of the methods we use to keep app size minimal. ![]() Left unchecked, this added code would make the app bigger and bigger until eventually the time it takes to download would become unacceptable. Managing app size at Facebook is a unique challenge: 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.
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |