Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Lossless compression with Brotli

blogs.dropbox.com

Post reply on HN
Print view View original

41–50 of 66 posts

Re: Lossless compression with Brotli

#41

Post by jacobolus »

AceJohnny2 wrote: post #33

On a purely compression algorithm front, the recently format-stabilized [1] zstd [2] beats the pants down Brotli, in terms of compression speed, decompression speed, and compression ratio. Zstd isn't some random effort either, but a more flexible (in terms of compression time-for-ratio) effort by the creator of the popular and insanely fast lz4 compressor[3]. [1] http://fastcompression.blogspot.com/2016/06/zstandard-…

Take a look at Oodle Kraken, by Charles Bloom.

http://www.cbloom.com/rants.html (this is his blog, you’ll have to skim back through the last year of posts). But e.g. check out this very recent one http://cbloomrants.blogspot.com/2016/05/ps4-battle-miniz-vs-...

http://www.radgametools.com/oodle.htm http://www.radgametools.com/oodlewhatsnew.htm

HN thread https://news.ycombinator.com/item?id=11583898

Re: Lossless compression with Brotli

#42

Post by lifthrasiir »

maxst wrote: post #5

Somebody, make "image format powered by brotli", please.

Brotli is not as good as an image compression algorithm because it is strongly tuned to the "typical" workload for Web (have you looked at the preset dictionary? :-), not images.

I would instead suggest FLIF [1], which roughly consists of an image-specific context model, adaptive entropy coding and general interlacing (that makes any sufficiently long prefix of the file a valid approximation to the original image). Still in development, but seems very promising.

[1] http://flif.info/

Re: Lossless compression with Brotli

#43

Post by Dzugaru »

lifthrasiir wrote: post #42
maxst wrote: post #5

Somebody, make "image format powered by brotli", please.

Brotli is not as good as an image compression algorithm because it is strongly tuned to the "typical" workload for Web (have you looked at the preset dictionary? :-), not images. I would instead suggest FLIF [1], which roughly consists of an image-specific context model, adaptive entropy coding and general interlacing (that makes any sufficiently long prefix of the file a valid approximation to the original image). S…

Interesting, would like to see comparison with FFV1. Arithmetic coding beats Huffman all day every day, and pixel-aware predictors are a thing.

Re: Lossless compression with Brotli

#44

Post by rayiner »

Jweb_Guru wrote: post #15
Manishearth wrote: post #12

Earlier quoted context omitted.

It might be possible that jemalloc already does this? Rust uses it by default, and while I don't recall the specifics jemalloc does a bunch of things in userspace wrapped around malloc that make it better than malloc. Rust makes it easy to swap out the allocator too, so I'd love to see an allocator lib specifically focused on size management :)

Yes, this is precisely how jemalloc works.

And OS X's magazine allocator, in addition to probably dozens of others. Segregated-fit allocators are probably the dominant method.

Re: Lossless compression with Brotli

#45

Post by eln1 »

Dzugaru wrote: post #43
lifthrasiir wrote: post #42

Earlier quoted context omitted.

Brotli is not as good as an image compression algorithm because it is strongly tuned to the "typical" workload for Web (have you looked at the preset dictionary? :-), not images. I would instead suggest FLIF [1], which roughly consists of an image-specific context model, adaptive entropy coding and general interlacing (that makes any sufficiently long prefix of the file a valid approximation to the original image). S…

Interesting, would like to see comparison with FFV1. Arithmetic coding beats Huffman all day every day, and pixel-aware predictors are a thing.

Arithmetic coding is very expensive - zstd uses new entropy coding with compression ratio like arithmetic coding, but with Huffman-like speed: https://github.com/Cyan4973/zstd https://github.com/Cyan4973/FiniteStateEntropy http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Sys...

Re: Lossless compression with Brotli

#46

Post by est »

niftich wrote: post #7
maxst wrote: post #5

Somebody, make "image format powered by brotli", please.

Since most of Brotli's improvements over its ancestor LZ77 are due to its large, hardcoded, text-corpus dictionary [1], most of the algorithm's strengths would be wasted on binary data like images. Zopfli, from the same people, is a DEFLATE encoder, so it can be used in PNG [2] and this has already been added to some optimizers, e.g. AdvanceCOMP [3] [1] https://gist.github.com/klauspost/2900d5ba6f9b65d69c8e [2] https…

First time saw the Brotli dictionary. It has duplicates.

Line 3131 and 8704 both are "操作"

Re: Lossless compression with Brotli

#47

Post by gribbly »

daniel_rh wrote: post #32
saynsedit wrote: post #21

Earlier quoted context omitted.

Preventing compromise and ensuring determinism using checksums and SECCOMP is more reliable and easier to implement than reimplementing in rust an already de-facto secure library used millions of times every day. I'm sorry but the Rust rationale just isn't there. Porting to Rust is a strictly less efficient way of accomplishing the same exact goal. Now, writing a new library in rust, that's a different story and actu…

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.

A bit off topic, but I was excited about that lossless jpeg (re)compressor you guys had developed, is there a chance it will be open sourced ?

Re: Lossless compression with Brotli

#48

Post by unwind »

AceJohnny2 wrote: post #34
AceJohnny2 wrote: post #33

On a purely compression algorithm front, the recently format-stabilized [1] zstd [2] beats the pants down Brotli, in terms of compression speed, decompression speed, and compression ratio. Zstd isn't some random effort either, but a more flexible (in terms of compression time-for-ratio) effort by the creator of the popular and insanely fast lz4 compressor[3]. [1] http://fastcompression.blogspot.com/2016/06/zstandard-…

While I'm around, I've been looking for a good compressor for an embedded scenario, where compression time and memory is near-irrelevant (it's done offline), but streaming decompression time and memory use (both in code and scratch memory) is primordial. By memory use, I'm talking a system with single-digit megabyte RAM, and decompressor scratch memory usage in the dozens of kilobytes. Right now, we're using LZSS bec…

I've had good results with LZJB[1] (designed by Jeff Bonwick for ZFS) in embedded scenarios, perhaps at least worth testing for you?

I even have some public code for it, there's Python module [2] that will adequately address your wish for mediocre offline-friendly performance (heh) and a streaming C decompression library [3].

The runtime memory usage for the decompressor are tiny (which is good, since from my perspective your system sounds huge!) so that should be fine at least.

Very interested in any feedback you might have, of course.

[1] https://en.wikipedia.org/wiki/LZJB [2] https://github.com/unwind/python-lzjb [3] https://github.com/unwind/lzjb-stream

Re: Lossless compression with Brotli

#49

Post by blank_state »

JyrkiAlakuijala wrote: post #37
AceJohnny2 wrote: post #33

On a purely compression algorithm front, the recently format-stabilized [1] zstd [2] beats the pants down Brotli, in terms of compression speed, decompression speed, and compression ratio. Zstd isn't some random effort either, but a more flexible (in terms of compression time-for-ratio) effort by the creator of the popular and insanely fast lz4 compressor[3]. [1] http://fastcompression.blogspot.com/2016/06/zstandard-…

Brotli's fastest compression is slightly faster than zstd's. Zstd decompresses faster, but neither is slow. Zstd can use sliding window size longer than 16 MB, in brotli this is limited to 16 MB to have guarantees of the maximum resource use at decoding time. Zstd's longer sliding window helps with the longest files (16 MB+), and often benchmarking is done with 100 MB or even 1 GB files. Brotli compresses usually mor…

> Brotli's fastest compression is slightly faster than zstd's.

Come on, this is not serious.

Brotli's fastest compression algorithm is still significantly slower than zstd. And more importantly, it compresses _much worse_.

For a 3rd party evaluation, one can try [TurboBench](https://github.com/powturbo/TurboBench) or even [lzbench](https://github.com/inikep/lzbench) which are open-sourced. Squash introduces a wrapper layer with distortions which makes it less reliable, and more complex to use and install, quite a pity given the graphical presentation is very good. I'm interested in speed, and in this area, all benchmarks point in the same direction : for a given speed budget, Zstandard offers better ratio (and decompresses much faster).

Re: Lossless compression with Brotli

#50

Post by staticassertion »

saynsedit wrote: post #10

I'm having a hard time understanding the motivations for porting to rust... If they were going to run the whole thing in a SECCOMP container anyway, there is little damage a compromised C library could do. If reasoning about uninitialized memory would take a review of the entire brotli code base, didn't the rust port require that anyway? (speaking as someone who has done a couple of cross-language rewrites)

> If they were going to run the whole thing in a SECCOMP container anyway, there is little damage a compromised C library could do.

True, especially since they appear to be using a traditional seccomp sandbox, which means the process really can't do much.

Based on the architecture there is no broker process involved, you simply feed in data via read() and it writes the data out via write(). It has access to two other system calls by virtue of seccomp, so your kernel attack surface is quite small - but it is there.

The "no hostile process could escape the sandbox" is not really true since it assumes a perfect implementation of each system call available.

That said, kernel attack surface is drastically lowered, as are the capabilities of the process. But it can still read and write arbitrary files - unless, of course, they filter on fd, which I suppose they likely are.

As for determinism and robustness, those are still valid. To quote your other comment:

> an already de-facto secure library used millions of times every day.

The fact that it is used often does not mean it is "de-facto" secure. How could it? You can not prove it is secure, and doing so would be a huge pain. Whereas, given safe rust, you have strong guarantees about what can and can't happen in the code.

Post reply on HN