New Binary Diffing Algorithm Announced By Google

bheer writes "Today Google's Open-Source Chromium project announced a new compression technique called Courgette geared towards distributing really small updates. Courgette achieves smaller diffs (about 9x in one example) than standard binary-diffing algorithms like bsdiff by disassembling the code and sending the assembler diffs over the wire. This, the Chromium devs say, will allow them to send smaller, more frequent updates, making users more secure. Since this will be released as open source, it should make distributing updates a lot easier for the open-source community."

Comments

uses a primitive automatic disassembler

[flowsnake]

An interesting approach - I wonder if this would also work as well on compiled bytecode like .NET or Java uses?

Re:uses a primitive automatic disassembler

[hattig]

Why not just ship the affected .class files for Java? Disassemble the Jar that is being updated, replace/add/remove the class(es) as per the update instructions and rebuild the Jar.

Chrome's problem is that a massive, bulky, chrome.dll file needs to be sent out with each update, and that it isn't easy to split it up into its constituent parts because it is lower level.

It's not a new idea, but quite impressive that they've actually gone and worked it all out so that it is reliable. And nicer than patching via jumps (noop the old code, add a jump to new code, append new code to end).

Re:uses a primitive automatic disassembler

[FunkyELF]

It's an interesting approach to a problem that should never have arisen. Why does everything have to be thrown into a 10MB dll? People are browsing on computers, not wristwatches, and there's no reason to abandon modular design to tangle things together for trivial performance gains.

Just because the end result is a 10MB dll doesn't mean that the code and design isn't modular. Thats like saying Linux isn't modular because the live CDs / DVDs come in a single gigantic 4.7Gb .iso file.

Also less overhead for Google

[Enderandrew]

Google has to pay the cost for maintaining servers and handling bandwidth for all the OS updates they push out. The more efficient they are in this process, the more money the save.

The good news is that the same benefits could be applied to Red Hat, Ubuntu, openSUSE, etc. Lower costs helps the profitability of companies trying to make a profit on Linux.

The end users also see benefits in that their packages download quicker. I'd be honestly pretty disappointed in any major distro that doesn't start implementing a binary diff solution around this.

Re:Also less overhead for Google

[maxume]

Yeah, but it is probably more like unplugging wall warts than insulating your house.

That is, it will be a hassle, be visible, and show a tiny benefit, all the while distracting from more worthwhile activity.

Re:Also less overhead for Google

[Enderandrew]

I don't run Ubuntu, but rather openSUSE. When I download updates (including weekly snapshot builds of KDE 4, Firefox and OpenOffice) I end up downloading around 3 gigs each time. That is practically the whole OS. Small binary diffs would make a huge difference here.

I doubt I pull 3 gigs of bandwidth from all Google sites combined in a week.

The other difference is that other Google sites generate revenue. The OS likely will not.

wait a minute

[six]

announced a new compression technique called Courgette geared towards distributing really small updates

I just RTFA, this has nothing to do with a compression technique.

What they developed is a technique to make small diffs from *executable binary files* and it doesn't look like it's portable to anything other than x86 because the patch engine has to embed an architecture specific assembler + disasembler.

Bad explanation

[DoofusOfDeath]

Courgette achieves smaller diffs (about 9x in one example)

That's potentially very misleading. I can compress any document, down to a single but, if my compression algorithm is sufficiently tailored to that document. For example:

if (compressed_data[0] == 0):
      return = get_Magna_Carta_text()
else:
      return unzip(compressed_data[1:])

What we need to know is the overall distribution of compression ratios, or at least the average compression ratio, over a large population of documents.

Can a layman get an explanation in English?

[AP31R0N]

Please?

Re:Can a layman get an explanation in English?

[PCM2]

But, if the compilers are similar enough to create the same pseudocode/bytecode/ASM, or smart enough to save the source code, and use it for future comparisons, then wouldn't one patch be just as portable as the original source code?

It's a good theory and you're a smart person, but:

1. The compilers probably wouldn't be similar enough. Even developers who use GCC to compile something for Linux usually use Visual Studio to compile the same code for Windows. (The source code for Chrome, for example, shipped as a Visual Studio project.) Mac OS X likes to have everything written in Objective C, so that output would probably be very different.
2. Different operating systems rely on different shared libraries to do the same things. So a function call that opens a file in Linux might not look like a function call to do the same thing on Windows -- it might take a different number of arguments, for example, which means it would look rather different in machine language.

Portability doesn't appear to be Google's primary concern, though. They seem to be keen on the idea of delivering binaries over the wire (real binaries, not bytecode) -- see Google Native Client.

Re:Solving the wrong problem

[Joe Random]

If the code is so awful that the bandwidth required for security updates is a problem, the product is defective by design.

No one is saying that the bandwidth is a problem. They're just saying that the bandwidth is unnecessary. FSM-forbid that anyone try to optimize something.

Plus, as the article points out, smaller updates mean more people can receive the update per unit-bandwidth, which means faster distribution of security updates when something critical is fixed.

Re:dictionary

[Big_Monkey_Bird]

zoo-kee-nee

Re:Like many brilliant ideas...

[merreborn]

Like many brilliant ideas... it makes you smack yourself on the head and go "why hasn't everybody been doing this for years?".

Probably because the old solution was:

A) Simple
B) Good enough for most purposes.

Sure, you can shave 80% off your patch filesize... but unless you're as big as google, patch bandwidth probably isn't a major priority -- you've likely got much more important things to dedicate engineering resources to.

You know how they say "Necessity is the mother of invention"? Well, when an invention isn't really necessary for most folks, it tends to show up a little later than it might otherwise have.

Re:Solving the wrong problem

[Anonymous Coward]

Out of curiosity, could you please point us to some of your code so we can do a comparison?

Thanks.

Re:Like many brilliant ideas...

[Just Some Guy]

Actually, it made me smack my head and say "I assumed we were already doing this".

Sure, you can shave 80% off your patch filesize... but unless you're as big as google, patch bandwidth probably isn't a major priority

So, you've never installed a service pack or another OS update? I'd be more than happy to run "sudo aptitude patch-upgrade" to download the 3KB difference between OpenOffice 3.1.foo and 3.1.foo+1.

Re:Rsync

[Anonymous Coward]

Well, not to mention 90%+ of Windows users lack a compiler and linker. And for the other 10% it can be either some version of VC or a windows port of GCC. This is doubly annoying because C++ code has no standardized ABI (in the vein of early 90's UNIX adding extensions that did nothing but make sysadmin work twice as hard) so you have to ensure all your .dlls have been compiled by the same compiler, etc.

Asking a Windows user to compile something is like asking a painter to engineer a building.

Anyone like zucchini?

[Anonymous Coward]

In case anyone has missed the reference of the name "Courgette", it's French for summer squash/zucchini type vegetables. So, Courgette as in squash, and squash as in make smaller.