Functional interfaces to compression (or: Down With Streams!)

Keith Winstein
Assistant Professor, Stanford
Date: Jan. 11, 2019 / Time: 1:15pm / Room: Packard 202

Abstract

From a computer-science perspective, the world of compression can seem like an amazing country glimpsed through a narrow straw. The problem isn't the compression itself, but the typical interface: a stream of symbols (or audio samples, pixels, video frames, nucleotides, or Lidar points...) goes in, an opaque bitstream comes out, and on the other side, the bitstream is translated back into some approximation of the input. The coding and decoding modules maintain an internal state that evolves over time. In practice, these "streaming" interfaces with inaccessible mutable state have limited the kinds of applications that can be built.

In this talk, I'll discuss my group's experience with what can happen when we build applications around compression systems that expose a "functional" interface, one that makes state explicit and visible. We've found it's possible to achieve tighter couplings between coding and the rest of an application, improving performance and allowing compression algorithms to be used in settings where they were previously infeasible. In Lepton (NSDI 2017), we implemented a Huffman and a JPEG encoder in purely functional style, allowing the system to compress images in parallel across a distributed network filesystem with arbitrary block boundaries (e.g., in the middle of a Huffman symbol or JPEG block). This free-software system is is in production at Dropbox and has compressed, by 23%, hundreds of petabytes of user files. ExCamera (NSDI 2017) uses a purely functional video codec to parallelize video encoding into thousands of tiny tasks, each handling a fraction of a second of video, much shorter than the interval between key frames, and executing with 4,000-way parallelism on AWS Lambda. Salsify (NSDI 2018) uses a purely functional video codec to explore execution paths of the encoder without committing to them, letting it match the capacity estimates from a transport protocol. This architecture outperforms "streaming"-oriented video applications -- Skype, Facetime, Hangouts, WebRTC -- in delay and visual quality. I'll briefly discuss some of our ongoing work in trying to compress the communication between a pair of neural networks jointly trained to accomplish some goal, e.g. to support efficient evaluation when data and compute live in different places. In general, our findings suggest that while, in some contexts, improvements in codecs may have reached a point of diminishing returns, compression *systems* still have plenty of low-hanging fruit.

Bio

Keith Winstein is an assistant professor of computer science and, by courtesy, of electrical engineering at Stanford University. His research group designs networked systems that cross traditional abstraction boundaries, using statistical and functional techniques. Winstein did his undergraduate and graduate work at MIT and joined the Stanford faculty in 2014. From 2007-2010, he was a staff reporter at The Wall Street Journal.