daniel_rh

We heavily investigated zstd and met with the brilliant inventor, Yann, who provided amazing insights into the design and rationale behind zstd and why it is so fast and such an amazing technology. I also recompiled zstd into rust using https://github.com/immunant/c2rust and tried using various webasm mechanisms to run it (I didn't get webasm quite fast enough, and teaching c2rust to make it safe would be quite a slog).

But the main reason we settled on Brotli was the second order context modeling, which makes a substantial difference in the final size of files stored on Dropbox (several percent on average as I recall, with some files getting much, much smaller). And for the storage of files, especially cold files, every percent improvement imparts a cost savings.

Also, widespread in-browser support of Brotli makes it possible for us to serve the dropbox files directly to browsers in the future (especially since they are concatenatable). Zstd browser support isn't at the same level today.

Great question! We developed and deployed Lepton to losslessly encode JPEG image files. Lepton continues to deliver substantial storage and cost savings every year. You can read more about it here https://dropbox.tech/infrastructure/lepton-image-compression...

if a user has uploaded a file in the past and their desktop client can prove they have access, then they can avoid uploading it again

Savory with a touch of sweetness, Broccoli Bread cooks up like cornbread but offers fiber and calcium. The original name was Brot-cat-li (since files could be concatenated and compressed in parallel), but when we said it fast it sounded like "Broccoli" and the name stuck.

Dropbox uses a similar toolbox as https://chromium.googlesource.com/chromiumos/docs/+/master/s...

And yes, much of the overhead stems from the RPC server that needs to be implemented. For lepton we used a raw TCP server (a simple fork/exec server) to answer compression requests. For Lepton we would establish a connection and send a raw file on the socket and await the compressed file on the same socket. A strict SECCOMP filter was used for lepton. It was nice to avoid this for broccoli since it was implemented in the safe subset of rust.

Hi folks, I'm Daniel from Dropbox, and I am happy to answer any questions about this tech.

2 words: bash reduce

(eg using cut, sort, split -l, nohup, ssh to orchestrate a massive job with only bare unix tools available)

I can't find any information on linux support with KSP2. Does anyone have a link with more linux information? One of the many reasons I loved KSP was robust linux support.

or written in a secure language without undefined behavior and without any "unsafe" code like Rust or Safe Haskell.

IoT probably should be shipping code that uses static compiler checks as the first line of security defense rather than run-time checks like valgrind and asan.

Optometrists and Ophthalmologists both have training to check for disease in the eyes. In fact a dilated eye exam is a non-invasive way to get an actual look into your circulatory system to check for things like diabetes. So even people without glasses should be getting regular checkups.

Ophthalmologists also have specialized training for cutting the eye that they learn in medical school (eg: lasik), but for eye exams, an optometrist has the skill-set necessary to perform these kinds of screenings.

A lot of people just get auto-refracted or a checkup by an optician and assume that's enough to get new glasses, but those people can be among the tens of millions of Americans who don't realize they have pre-diabetes.

Does this abstraction target WebGL as well? I could imagine it being a nice portability layer for web-aware apps since rust can easily target wasm with a few compiler flags.

I love that the relooper can be disabled! I think that option will be really useful while the heuristics are being tuned, since many codebases avoid goto as a matter of style and can probably be translated without it, or with minor tweaks.

I'm a big corrode fan and I used it (plus a really simple python script https://github.com/dropbox/rust-brotli/blob/master/uncorrode... ) to help translate the brotli encoder https://github.com/google/brotli/tree/master/c/enc to safe, almost-idiomatic rust.

My initial attempts used top of tree corrode, but I found that the relooper got in the way of writing idiomatic rust, so I restarted my translation efforts and actually pinned corrode to before the relooper and backported a lot of the improvements that happened since the relooping effort https://github.com/danielrh/corrode/tree/unprocessed_loops

On one hand I'm very glad corrode supported the relooper: it got me excited about the capabilities of corrode, but in the end I think any serious port of a project is going to need to think about idiomatic control flow and will require a minor rewrite of the C code. The improvements to the C brotli encoder happened here https://github.com/danielrh/brotli/commits/corrode to remove the gotos and some negative array access.

All in all, the process to get the brotli encoder into rust was very smooth. Much of it may be due to the google engineers being extremely careful about memory ownership and design.

Anyhow I'm excited about c2rust, but am nervous that corrode may be de-emphasized since I know it worked well for me.

If you want to know more about the experience of porting a large existing project to rust, I posted about the rust brotli decoder here https://blogs.dropbox.com/tech/2016/06/lossless-compression-... (subsection "The Port")

DivANS author here: the compression benchmarks all measure seekability to the nearest 4MB chunk, but the current lib itself doesn't support seekability out of the box, yet. However, it would be trivial to reset the encoder at each 4mb chunk and could even be done without additional library support by just reinitializing the compressor (or decompressor) each 4mb

It has some similarities to zpaq, especially with the -mixing=2 parameter. With -mixing=2, DivANS runs 2 models to estimate the upcoming nibble or byte and dynamically chooses the best model based on past performance. One of the two models is good for more diffuse patterns and the other is good for more pronounced patterns. I believe the paq technology runs dozens of models and uses similar but slightly more advanced models to mix between them. This results in excellent compression but means you have to evaluate those models to decompress the data when you need it later.

Without -mixing=2 (eg for the results present in the blog post), DivANS actually relies on a static determination about which models to use in which situations, serialized into the file in the mixing map. It only ever evaluates a single model per nibble.

The idea of mashing up the intermediate representation with a bunch of different compressors isn't present in zpaq as far as I know, but the spirit of the idea is similar, but on a per-bit level, rather than on the IR level.

To compress files for a system like Dropbox we would recommend a) check if the file can compress with https://github.com/dropbox/lepton . Lepton has some new flags that can help it compress a wider range of files, so it's not just limited to pure JPEG files any longer.

b) then compress it with zlib -6 to get an idea of how compressible the data is.

c) if the data compresses by at least a percent with zlib, it's likely to do significantly better with more advanced compression like DivANS. About 1/3 of files in Dropbox fall into that >1% category but aren't compatible with Lepton. For those compressible files, DivANS gets 12.08% savings over zlib with the settings we chose in the blog post. Brotli, in contrast, gets 9.64% savings over zlib on that same data.

The crate is built with cargo build --release --features=simd --target=wasm32-unknown-unknown which aliases DefaultCDF16 type to the SIMD types.

However since WASM doesn't support vectorized instructions yet, I believe LLVM translates these to scalar and the result is actually 20% slower on both Firefox and Chrome than without the SIMD enabled.

Compared to the speed of the native binaries in https://blogs.dropbox.com/tech/2018/06/building-better-compr... the Firefox WASM binary seem to decode DivANS roughly 3x slower than native without multithreading at around 100 Mbit/s. Chrome goes more than 12x slower, running at around 20 Mbit/s. I'm a bit surprised that there is such a big performance gap between the browser and the native binaries.

This may be a reason to look further at the generated wasm and see where the time is being spent.

Blog co-author here: With the settings in the blog post, the DivANS algorithm skews towards saving space over speed. Brotli skews heavily towards decompression speed without sacrificing much ratio. The reason we focus a lot on comparing to Brotli, is that Brotli does extremely well on data stored at Dropbox.

However, I don't think the performance is a fundamental law, and there are clearly some clever optimizations yet-to-be done.

I was very surprised that the lzma-brotli mashup outperformed either. This leads me to think that with enough community involvement we could discover some really clever heuristics and algorithms for compression all together.

I'm the author of https://github.com/dropbox/rust-brotli and I certainly ran into the issues mentioned in the article, and the initial version of my brotli decoder and encoder were each almost 10x slower. I also worked around each and every one of them, and the result is something that performs at 80-90% of the speed of the original on average, and some files compress faster with rust than with the original brotli codec.

allocator: I ran into the same situation and abstracted it with a generic allocator: https://github.com/dropbox/rust-alloc-no-stdlib it's an ugly solution, but it works and can allow for significant perf improvements down the line by bundling all same types together

benchmarks: I simply made a test that printed the time

primitive types: it's easy to write generic functions that do this

macro system: I found to be amazing, but I never used it to compact data types

borrow checker: split_at_mut was super helpful...also core::cmp::replace was useful to taking away pieces of a structure and manipulating them, then putting them back

Though it wasn't all roses: to try to get SSE vectorization I had to convert this 6 line short string matching function https://github.com/dropbox/rust-brotli/blob/238c9c539b446d7d...

into this multi hundred line monster with macros and so forth https://github.com/dropbox/rust-brotli/blob/238c9c539b446d7d...

but in the end it was as fast as hand-tuned intrinsics in C

I also found myself scared by dependencies, including onto the std library, so I tried to get everything to remain within the core library. This should allow something as low-level as a codec to be used in kernel space or in another place where a custom allocator is needed.

I also found that "rewriting in safe rust from C" was made easy by corrode https://github.com/jameysharp/corrode since C and rust can be interface compatible, it's easy to go one file at a time and turn it into working rust, then safe rust.

The researchers specifically tested phone face up vs phone face down and noticed no statistical difference, I believe.

I thought you could use memoryview over a string to get rid of that allocation even in 2.7

https://docs.python.org/3/library/stdtypes.html#memoryview

GPL3 means it's not very reusable in any projects that aren't GPL3. Have you considered a BSD or MIT license? or CC0 if you want to get code reuse? Or at the very least LGPL2

SIMD support in Rust is still very early and required unsafe mode for SSE, and lepton makes heavy use of SSE intrinsics.

Now I do see http://huonw.github.io/simd/simd/ was being developed in August 2015, but it seems to be gathering dust of late.

I really do wish that Rust would provide nice alignment guarantees (eg 32 byte) without depending on customizing the allocator, and builtin, safe, SIMD instructions

rANS is really cool, but I think we tried it too early in the lepton research phase while some of the other ideas were still brewing... We might revisit rANS now that v1.0 is out!

Hi GrantS: That's pretty close to how it works. We always use the new prediction, even where it's worse than JPEG though (very rarely), to stay consistent.

As for having the mega-model that predicts all images better: well it turns out with the lepton model out you only lose a few tenths of a percent by training the model from scratch on each images individually. We have a test case for training a global model in the archive (it's https://github.com/dropbox/lepton/blob/master/src/lepton/tes... ) That trains the "perfect" lepton model on the current image then uses that same model to compress the image (It's not meant to be a fair test, but it gives us a best-case scenario for potential gains from a model that has been trained from a lot of images) and in this case it doesn't gain much, even in a controlled situation like the test suite.

However the idea you mention here may still be a good idea for a hypothetical model--but we haven't identified that model yet.

It's very easy to make a JPEG file that will not compress at all. Luckily it might look like snow from a television set rather than a typical image produced by a camera.

We live in a world where it is common for blue sky to occupy a portion of the frame and green grass to occupy another portion of the frame. Since images captured of our world exhibit repetition and patterns, there are opportunities for lossless compression that focuses on serializing deviations from the patterns.

Thanks for testing this! For archival purposes, be sure to check the exit code of the lepton binary after compressing each JPEG: the default parameters only support a subset of JPEGs (you need to pass -allowprogressive and -memory=2048M -threadmemory=256M to support a wider variety of large or progressive JPEG files). Lepton will not write images that it is unable to compress using the settings provided. In those cases be sure to keep the original JPEG.

Do you have a link to the code? Is it open source? Sounds pretty cool :-)

That's the idea behind the algorithm, yes. And since it's lossless, every original bit is preserved. The same idea could be applied on the Desktop client instead of on the server, which would save 22% of the bandwidth as well and make syncing faster.

Your argument is certainly reasonable. One case where it might matter is if SECCOMP weren't available on all platforms that needed to decompress data. Also: a vulnerability could decide to only strike after a certain clock date. In that way it could sneak past certain checksum checks and still cause issues later.