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.
> 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.
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.
> The world is no longer ASCII, unicode is here to stay.
I wouldn't have a problem with it, if Everything Just Worked. If everything international was UTF-8 and Just Worked, I'd be cool with that. But:
1. > some editors that don't deal with it correctly
2. You need fonts installed, otherwise you get boxes everywhere.
3. You need to specify locale somewhere. This is currently sometimes manual: Applications can't automatically agree on locale, because not everybody uses UTF-8, and not every format that can be in multiple locales puts it somewhere.
4. Linux insists on "generating locales." Now that's a mess.
Now people who want to show how edgy they are by insisting on using the empty set symbol are wasting my time, because when I install $COOLAPP that depends on $AWESOMELIB which requires $YOURPYTHONZEROMQLIB, then I discover after hours of Googling cryptic error messages and browsing multiple forums for these different projects (plus the OS(es) and programming language(s) involved), that your Python was compiled with wide-character support, and I have to bootstrap a wide-character-compatible gcc in order to build wide-character-compatible Python that can run $COOLAPP, but I have to also create more locales and change the LC_ALL environment variable, which (when I finally do it) will of course cause another obscure error message, and it turns out that $OTHERCOMPONENT really doesn't want to use wide characters because it only knows UTF-8, and there's really no way to have multiple processes in the same address space because different character widths can only run in different chroots because they're like amd64 and i386 before Ubuntu grew multilib support...
I haven't had this exact breakage, but the point is that this is the sort of rabbit hole you can find yourself falling down, all because you wanted two dots over your 'o', or a slash through it, just to show how edgy and hip and modern you are.
Fortunately you have contact information in your profile, so when your code does this and I end up wasting 10 hours of my life with this garbage, I know where to send the invoice.
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.
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.
But figuring out exactly what part of the tool is buggy is hard. If I'd have figured out what the problem was (probably spending hours), and reported it, the javac people would've said, "javac is working just fine, you specified the wrong locale." The Eclipse people would've said, "Eclipse is working just fine, it uses the system locale as a default when you don't specify." The Ubuntu people would have said, "Our locale setup is fine, it's your fault for not selecting ISO-1234-5678 instead of or in addition to UTF back when you installed the system. Oh, and of course you also have to set your environment variables correctly..." The author would have said, "I'm using a normal system and it compiles fine for me. If I change encoding so it compiles for you, it breaks on my system!"
The upshot is, the tool support is garbage, because you have to jump through a bunch of hoops to get code to compile. I recall the error messages not being helpful. (Would it be so hard for the compiler to say "Warning: Unrecognized character o.., it looks like you're using ISY-2358 encoding even though you didn't specify. To make this warning go away, enable the ISQ-1337 locale, regenerate your locales, and set the LC_ALL environment variable.") Being able to compile a given piece of source code into object code should not break if you change obscure environment settings between machines.
Spending hours figuring out what's breaking, only to find out that things aren't breaking and I have to change a bunch of settings on every development machine I use (with different values for every program I compile, of course), is a lot more effort than just limiting your source files to character codes less than 128 (or 126 or whatever the top ASCII character is).
> 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.
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.
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.
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.
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.
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!
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:
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).
> 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.
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!
From a user perspective I wish you guys would switch to something better like bit torrent (at least offer an alternative torrent download).
I almost gave up before playing the game when an interrupted download meant that I had to start again, and it is pretty frustrating not even maxing out my slow internet connection at peak times for patches.
The fact that you don't have any kind of diffing solution seems like absoulte madness to me.
You don't have to start again. It's just that the progress bar starts from zero again. If you download 2GB of 4GB initially then start again, when you restart it will show 0% of 2GB to download.
It's effectively a diffing system where the block size is on average the size of a file (about 42kb).
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.
Why are you not using bsdiff? This seems like a bug.
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.
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.
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.
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?
58 comments
[ 6.3 ms ] story [ 93.6 ms ] threadA 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.
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.
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.
I wouldn't have a problem with it, if Everything Just Worked. If everything international was UTF-8 and Just Worked, I'd be cool with that. But:
1. > some editors that don't deal with it correctly
2. You need fonts installed, otherwise you get boxes everywhere.
3. You need to specify locale somewhere. This is currently sometimes manual: Applications can't automatically agree on locale, because not everybody uses UTF-8, and not every format that can be in multiple locales puts it somewhere.
4. Linux insists on "generating locales." Now that's a mess.
Now people who want to show how edgy they are by insisting on using the empty set symbol are wasting my time, because when I install $COOLAPP that depends on $AWESOMELIB which requires $YOURPYTHONZEROMQLIB, then I discover after hours of Googling cryptic error messages and browsing multiple forums for these different projects (plus the OS(es) and programming language(s) involved), that your Python was compiled with wide-character support, and I have to bootstrap a wide-character-compatible gcc in order to build wide-character-compatible Python that can run $COOLAPP, but I have to also create more locales and change the LC_ALL environment variable, which (when I finally do it) will of course cause another obscure error message, and it turns out that $OTHERCOMPONENT really doesn't want to use wide characters because it only knows UTF-8, and there's really no way to have multiple processes in the same address space because different character widths can only run in different chroots because they're like amd64 and i386 before Ubuntu grew multilib support...
I haven't had this exact breakage, but the point is that this is the sort of rabbit hole you can find yourself falling down, all because you wanted two dots over your 'o', or a slash through it, just to show how edgy and hip and modern you are.
Fortunately you have contact information in your profile, so when your code does this and I end up wasting 10 hours of my life with this garbage, I know where to send the invoice.
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.
Only if you use garbage tools.
But figuring out exactly what part of the tool is buggy is hard. If I'd have figured out what the problem was (probably spending hours), and reported it, the javac people would've said, "javac is working just fine, you specified the wrong locale." The Eclipse people would've said, "Eclipse is working just fine, it uses the system locale as a default when you don't specify." The Ubuntu people would have said, "Our locale setup is fine, it's your fault for not selecting ISO-1234-5678 instead of or in addition to UTF back when you installed the system. Oh, and of course you also have to set your environment variables correctly..." The author would have said, "I'm using a normal system and it compiles fine for me. If I change encoding so it compiles for you, it breaks on my system!"
The upshot is, the tool support is garbage, because you have to jump through a bunch of hoops to get code to compile. I recall the error messages not being helpful. (Would it be so hard for the compiler to say "Warning: Unrecognized character o.., it looks like you're using ISY-2358 encoding even though you didn't specify. To make this warning go away, enable the ISQ-1337 locale, regenerate your locales, and set the LC_ALL environment variable.") Being able to compile a given piece of source code into object code should not break if you change obscure environment settings between machines.
Spending hours figuring out what's breaking, only to find out that things aren't breaking and I have to change a bunch of settings on every development machine I use (with different values for every program I compile, of course), is a lot more effort than just limiting your source files to character codes less than 128 (or 126 or whatever the top ASCII character is).
Having lived in Switzerland in Basel, which is right on the German border I got to hear all kinds of German!
Schweizerdeutsch
It's been almost 12 years since I lived in Switzerland :-)
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...
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.
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!
[1] http://en.wikipedia.org/wiki/Xz
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.
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.
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:
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).
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
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!
I almost gave up before playing the game when an interrupted download meant that I had to start again, and it is pretty frustrating not even maxing out my slow internet connection at peak times for patches.
The fact that you don't have any kind of diffing solution seems like absoulte madness to me.
It's effectively a diffing system where the block size is on average the size of a file (about 42kb).
Why are you not using bsdiff? This seems like a bug.
For example, Facebook uses it to deploy their server code.
http://torrentfreak.com/facebook-uses-bittorrent-and-they-lo...
The poster that suggested zlib until zopfli would be ready has the right idea where dynamic is coming in and awaiting compression.
[1] https://code.google.com/p/zopfli/source/browse/
[2] https://zopfli.googlecode.com/files/Data_compression_using_Z...
http://news.ycombinator.com/item?id=5301688
7zip does it in a fraction of the time within 100 bytes
BTW if you need a windows binary, mingw compiles it without any trouble.Definitely would not want to use Zopfli compression on demand unless it is going into a long-term cache.
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?