Google compression algorithm Zopfli may lead to faster Internet

http://news.cnet.com/8301-1023_3-57571982-93/google-compression-algorithm-zopfli-may-lead-to-faster-internet/

by paulschlacter • 13 years ago

64 55 13 years ago

news.cnet.com

pilif• 13 years ago

Nitpicking: the thing should be called Zöpfli (note the umlaut). The diminutive in Swiss German often also affects vocals in addition to adding the li suffix.

A Zöpfli is a small Zopf which is the bread the algorithm is named after. To make matters worse: in the process of being diminished, the word even changes gender from masculine to neutral at least in the dialect I use. Pro tip: never waste your time learning Swiss German unless you know it by growing up with it :p

I can't really add a lot from the technical perspective aside if the fact that its really cool to be able to invest more time into compressing such that decompression still uses the unaltered old decodes, requires no more time (to uncompress) and still produces significantly smaller compressed data.

cleverjake• 13 years ago

Nitpicking your nitpick - the chose to spell it a different way than the thing it was named after. That doesn't make it wrong.

csense5• 13 years ago

> the thing should be called Zöpfli (note the umlaut)

No, it shouldn't.

A few years ago I downloaded a tarball of Java code. Every file had one of those "ö" characters, because the author spelled his name that way, and his name was in a comment at the top of every file as part of his license notice.

The project would not compile.

I tried compiling with Eclipse. I tried the included Ant script. I tried compiling directly by typing a javac invocation into the command line. I tried every permutation of the locale environment variables that Google knew about. My environment was very conservative, an official Sun Java toolchain from apt on a recent Ubuntu.

Finally, I wrote a script to delete that line from every file. It compiled just fine after that!

Putting anything but ASCII in source code will give everyone who ever tries to build the code endless nightmares of toolchain breakage.

Dylan16807• 13 years ago

Hey, just because java has a stupid flaw is no reason to infect the rest of the world.

X-Istence3• 13 years ago

So what you are saying is that Java was broken. Not that using characters containing an umlaut is a terrible idea.

The world is no longer ASCII, unicode is here to stay. I don't see that disappearing anytime soon, get used to it.

Speaking of which, code I write in Python that deals with ØMQ has the Ø in it ... i've found some editors that don't deal with it correctly, but that is the fault of the editor, not the file.

pyre• 13 years ago

Many languages explicitly allow you to use Unicode even in variable names. Your issue was a limitation of the language, though I can see the issue with using the name in a compression algorithm that has the potential to be used in many languages that might not deal with the non-ASCII characters all that well.

martinp• 13 years ago

This is incorrect. Java supports Unicode in source files just fine, as long as the file encoding is correct.

The problem is that certain IDEs (such as Eclipse) default to ISO-encoding on Windows. This works fine as long as you're only using Windows, but it will fail on Linux.

At my previous job certain developers preferred Windows and ended up commiting ISO-encoded source files which our build server (Ubuntu Server) failed to compile for this exact reason. A quick recode(1) usually resolves it.

masklinn• 13 years ago

> Putting anything but ASCII in source code will give everyone who ever tries to build the code endless nightmares of toolchain breakage.

Only if you use garbage tools.

X-Istence3• 13 years ago

Schweitzerdeutsch is really very different from Hochdeutsch, the two have the same written language (mostly) but spoken they are worlds apart.

Having lived in Switzerland in Basel, which is right on the German border I got to hear all kinds of German!

drucken• 13 years ago

Schweitzerdeutsch

Schweizerdeutsch

czr80• 13 years ago

There is a certain irony in calling out a Google product for mangling their source name - consider it a company tradition!

dalke• 13 years ago

+googol

rtkwe• 13 years ago

> Due to the amount of CPU time required — 2 to 3 orders of magnitude more than zlib at maximum quality — Zopfli is best suited for applications where data is compressed once and sent over a network many times, for example, static content for the web.

So it's not a magic bullet, and only results in 3-8 percent shrink compared the zlib at maximum compression. It is interesting that it is able to be decompressed by existing algorithms, which means it can be rolled out immediately instead of waiting for it to be adopted by enough browsers to make the compression time investment useful.

Google's blog post is here: http://googledevelopers.blogspot.com.es/2013/02/compress-dat...

gillianseed• 13 years ago

Well it uses the same deflate algorithm which is used by zlib, gzip etc.

There are many much more capable compression algorithms which will get much better results with alot less cpu time (lzma comes to mind), however the big deal is that deflate is supported by all browsers and thus it is a standarized means of compressing content.

With that, being able to squeeze out 3-8% more compression for compressed web content can likely be attractive if it is a decent part of your bandwidth usage.

mmastrac• 13 years ago

I've been wondering how this compares to straight-up AdvanceComp. I've used that for pre-compressing gzipped files for a while now.

Negitivefrags3• 13 years ago

So we distribute our game client over HTTP and it's something like 4GB compressed using gzip.

When I saw zopfli, my immediate reaction was that it should save a non-trivial amount of money for us while leading to a slightly faster download for our users. Hearing a 100 times increase in compression time doesn't sound like much compared to the number of times the files are downloaded right?

The last incremental patch we did to the game took 79 seconds in our build system to compress with the usual gzip. This is only compressing the files that were changed since the last patch, not the entire game client, so larger patches would take longer. If we changed to zopfli, it would take 2.2 hours.

That would put a serious dent in our agility. When we are trying to deploy a new patch, adding 2.2 hours (or more) somewhere in the middle of it really isn't viable. (It's already maddening when the rest of the process takes ~40 minutes with all the automated tests that we run).

So then lets look at the savings that this would buy us. We distributed about 30TB yesterday. Bandwidth costs 2c per gig. This would save us about 30 dollars a day.

So much for that!

newman314• 13 years ago

Did you get noticeable compression from zopfli though?

shard• 13 years ago

What about the possibility of simply sending the gzip version until the zopfli version is ready, then switching over? Seems like you'd get the best of both worlds.

moonboots• 13 years ago

Have you considered a newer compression program like xz [1]? The backwards compatibility of Zopfli is only necessary for clients that are relatively hard to update, e.g. browsers. If you are already distributing a custom game client, you could bundle an arbitrary compression library that has a better compression ratio, faster compression time, etc. than gzip.

[1] http://en.wikipedia.org/wiki/Xz

jmspring2• 13 years ago

I suspect compatibility with deflate is the main factor.

There are a number of LZ related compression algorithms with different properties - speed, compression, suitable to embed, etc.

It wholly depends on what the main goal is, in this case it seems better at rest storage for data that doesn't change regularly is key.

cheald2• 13 years ago

I'd just like to say that your team's patch delivery mechanism/speed is ridiculously impressive. I've been playing since early closed beta and the way you guys runs things makes me just plain happy. Kudos!

csense5• 13 years ago

4GB is really pushing the boundaries of what you should be using HTTP for. It's a nontrivial download for users with slower connection speeds, so you should really have better failure recovery than a simple HTTP download provides.

You should distribute it in pieces, or use bittorrent or rsync or some other protocol which allows correcting a bad block in transit. Users should download a small downloader program which speaks whatever protocol, then the downloader downloads the actual game. (Think about the way Blizzard does WoW updates.)

Checking blocks should theoretically possible using HTTP transfers with byte ranges, if you have a separate index file with checksums for each block. That way you get failure recovery but serve your content from Really Efficient Webservers like nginx or Amazon S3. Anyone know of any projects that do this?

You should also consider using a more modern compression algorithm like bz2 or lzma, if you have control over the application running on both ends of the connection. I'm guessing you'll see these results with Zopfli:

   gzip -c9 > zopfli -i1000 > bzip2 > bzip2 -c9 > xz   # compressed size
   gzip -c9 < bzip2 < bzip2 -c9 < xz, zopfli -i1000    # compression time

Not really sure about xz vs. zopfli for compression speed, but I'm sure that xz's LZMA algorithm gets way better compression than gzip for most data, due to fundamental limitations in the design of gzip's format.

The only real reason to use Zopfli is when the client only knows gzip compression and you can't change it (for example, many, many people have static webpages, CSS, JS, etc., which need to support several different web browsers as clients).

zobzu• 13 years ago

Sounds like we'd be better off using lzma altogether.

loeg• 13 years ago

> Checking blocks should theoretically possible using HTTP transfers with byte ranges, if you have a separate index file with checksums for each block. That way you get failure recovery but serve your content from Really Efficient Webservers like nginx or Amazon S3. Anyone know of any projects that do this?

Sure, one example is bittorrent (WebSeeding), among others[0]. Turns out bittorrent is a pretty good format for describing chunks of a file (full SHA1 per chunk, variable sized, if you care), and any httpd with byte-range support can fetch arbitrary bittorrent chunks of files.

[0] https://en.wikipedia.org/wiki/BitTorrent#Web_seeding

Negitivefrags3• 13 years ago

I absolutely agree that improvements could be made to our patching system, so here are a few more details as to why we do things how we do them.

1) It is actually working right now. This is the biggest deal at a startup. It's good enough. We have lots of other features to work on that will give us higher bang for our buck.

2) We wanted to be able to use an "off the shelf" CDN for distribution. It's nice to be able to farm out parts of your infrastructure you don't want to deal with.

3) We don't want to have to deal with versions in the patching system. Our patching systems first use is right in our office. The same deployment infrastructure that deploys the game to production runs in our office with every commit from a programmer or artist. When someone runs the game client (or one of the in house tools) the patching system syncs up the files to the latest version.

For real production clients, there can be several versions between the last time someone ran the game client and the next time. It's easier conceptually to deal with.

4) The client is over 100,000 files. Each file is generally quite small which limits the damage of not using an actual diffing solution. The larger files like textures and audio don't diff very well anyway when artists make changes due to the nature of the data formats.

5) It was really fast to develop. It's just libcurl. Once again, we are a small startup so we have lots of things we need to be focusing on that are not our patching system.

All the files are checked against hashes after download so we can correct errors. This is especially important due to the surprisingly large number of buggy caching proxies that some users seem to have in front of them.

One day I would love to make the best possible patching system. Unfortunately it's just not as high on the list as so many of the other things we need to be doing!

csense5• 13 years ago

Nitpicking my own comment: Actually bzip2 and bzip2 -c9 are the same thing, since -9 is the default for bzip2.

endtime• 13 years ago

You could do a gzip patch, and then replace it with the Zopfli patch 2 hours later...no?

ck22• 13 years ago

Try 7zip's gzip output in "ultra" profile (mx9) - it's within 1% of zopfli and a fraction of the time to compress.

cperciva• 13 years ago

Why are you not using bsdiff? This seems like a bug.

pja• 13 years ago

Game assets don't change in the ways that compiled binaries do, so bsdiff doesn't sound like it would be appropriate.

rorrr• 13 years ago

You should send compressed DIFFs only, and not whole changed files.

thret• 13 years ago

How much time would it save your users, collectively?

kokey• 13 years ago

It will be nice for your customers to have a smaller download. To speed this sort of thing up you can probably spin up an elastic cluster to do the compression work, and shut down when it's done.

Tichy• 13 years ago

Apart from what others said, perhaps faster downloads also would lead to better user retention.

cheald2• 13 years ago

Speaking as a customer of theirs, it's already impressively fast. :)

qznc• 13 years ago

Why not used BitTorrent?

For example, Facebook uses it to deploy their server code.

http://torrentfreak.com/facebook-uses-bittorrent-and-they-lo...

jmspring2• 13 years ago

Compression is always a trade off between time, memory, and size. If zopfli keeps compatibility with deflate, there will be those that will find a use for it.

The poster that suggested zlib until zopfli would be ready has the right idea where dynamic is coming in and awaiting compression.

WestCoastJustin• 13 years ago

You can browse the code here [1]. You can also find the pdf paper here [2].

[1] https://code.google.com/p/zopfli/source/browse/

[2] https://zopfli.googlecode.com/files/Data_compression_using_Z...

ck22• 13 years ago

Deja vu - this was just on HN 48 hours ago.

http://news.ycombinator.com/item?id=5301688

7zip does it in a fraction of the time within 100 bytes

   92629 bytes  jquery-1.9.1.min.js 
   31783 bytes  7z.exe -mx9 -tgzip a "jquery-1.9.1.min.js.gz" "jquery-1.9.1.min.js"
   31688 bytes  zopfli.exe -v --i1000 "jquery-1.9.1.min.js"

BTW if you need a windows binary, mingw compiles it without any trouble.

allerratio3• 13 years ago

What would be nice is a library that you can load with LD_Preload and replaces zlib compression. That way I could easily use e.g. Optipng with this new algorithm.

lucian19003• 13 years ago

I don't think that would be of much use, since only it only deals with compression.

allerratio3• 13 years ago

It only needs to overwrite the compression methods

kunil• 13 years ago

Do we really need a new compression algorithm to use compression with http?

lucian19003• 13 years ago

It is the same format as gzip (deflate).

mrinterweb• 13 years ago

Compression advantage over zlib =~ 3-8% CPU time over zlib's maximum compression =~ 20x-30x

Definitely would not want to use Zopfli compression on demand unless it is going into a long-term cache.

pjscott• 13 years ago

... Which is exactly Zopfli's intended purpose. Many things are read a lot more often than they're written.

goggles99• 13 years ago

up to 8 percent smaller than zlib.

Always with the spin, cause if you say on average 3% people yawn even more than they are yawning at 8%.

Wake me up when there is a stable/reproducible quantum parallelism (I don't mean Schumacher compression either) means of compression, not a tweak in an existing compression algorithm - Sorry to sound grumpy, but I just don't see this as news worthy or anything to get exited about. Many of us did this with similar results in grad school or in our spare time as a hobby. You can even find some of them on SF or GH if you don't believe me.

This is one of those stories where something is dressed up to sound really good and a couple of years later you wonder to yourself, "What ever happened to that?" You go look it up and find a dead end, usually because the original concept was over-hyped or unachievable.

After enough false optimism, the sane human will start to sour on "breakthrough" news and become cynical - because "doing the same thing over and over again and expecting different results" (Einstein) is the very definition of insanity right?

Google compression algorithm Zopfli may lead to faster Internet

Related Stories