Courgette meets a dangerous (Red) Bend [LWN.net]

Courgette meets a dangerous (Red) Bend

Posted Nov 5, 2009 8:00 UTC (Thu) by dwmw2 (subscriber, #2063)
In reply to: Courgette meets a dangerous (Red) Bend by skvidal
Parent article: Courgette meets a dangerous (Red) Bend

"When I read what this patent is about it really seems to me the kind of thing that makes sense to patent. It is a good bit obscure, it isn't (to me) obvious and it seems to definitely be innovation."

I strongly disagree.

You start with a bunch of .o files. All but one of them is identical to the old version. The delta is small.

You link your .o files into an executable. The linker does its thing with all the relocations. The delta between old and new executable is now huge.

The thought process goes... "Oh, what changed? All those relocations? Well, they're not real information; they can be reproduced. Let's knock something up that lets us omit those from the delta we send over the wire..."

It seems entirely obvious to me; the build process is giving you a bloody great hint. It doesn't take a huge leap of intuition; you just need to be thinking about the problem coherently.

Personally, I would love to see a private criminal prosecution for fraud, against the "inventors" named on this patent and others like it. The patent system is broken, and the patent office is complicit in its brokenness. The best way forward is to use something outside that system, in my opinion.

(Log in to post comments)

Courgette meets a dangerous (Red) Bend

Posted Nov 5, 2009 19:27 UTC (Thu) by magnus (subscriber, #34778) [Link]

No it doesn't start with a bunch of .o files.

It starts with a practical problem (updates are too large), then thinking about the type of code changes that typically make up an update, then thinking about the relocations etc you mention, then coming up with this idea, then recognizing it's worth doing, then realizing the idea.

If it's so obvious, why aren't there any open source implementations? Why aren't automatic updates handled this way in Linux distros or commercial OS:es?

Courgette meets a dangerous (Red) Bend

Posted Nov 5, 2009 19:50 UTC (Thu) by dwmw2 (subscriber, #2063) [Link]

Remember, the patent doesn't cover the implementation. It's just the idea. However much work goes into the implementation, what's being protected by the patent is just the basic concept.

And you do start with .o files, every day. The relocation thing is staring you in the face every time you do a build. When you come up with the 'modified program' mentioned in this update process, you're just stepping backwards a step in the build process. You're not actually doing anything particularly new and exciting.

There's a very similar trick with compression. Packages (RPM/deb/etc.) are generally compressed, and when doing deltas on them it's useful to work on the uncompressed version rather than the compressed version. Otherwise you get a lot of unnecessary differences between the old and the new version. Small changes cascade into big changes in the compressed package.

And, in answer to your final question, I have no idea why people aren't doing either of the above. The deltarpm stuff which just went into Fedora is still operating on the compressed packages without bothering to optimise it, as far as I know.

It seems like people just don't care that much about how efficient the update process is, at least for Linux distributions. Why else would we still be using yum?

Courgette meets a dangerous (Red) Bend

Posted Nov 5, 2009 20:43 UTC (Thu) by skvidal (subscriber, #3094) [Link]

As compared to what? I keep waiting for the solution to shipping a lot of bits, often, to come trotting up but nothing has leapt into view. yum-presto has helped matters but it does eat up a good bit of cpu-time.

Courgette meets a dangerous (Red) Bend

Posted Nov 7, 2009 3:39 UTC (Sat) by magnus (subscriber, #34778) [Link]

When you come up with the 'modified program' mentioned in this update process, you're just stepping backwards a step in the build process. You're not actually doing anything particularly new and exciting.

I agree that stepping back in the build process by itself is not very interesting. If they had just diffed the .o files and linked at the other end, I would have agreed completely with you.

The interesting part is the concept of feeding linker relocation info as hints into a more generic binary delta/compression algorithm. This allows for relatively simple decompression/patching at the other side, and also for proprietary software it doesn't require you to expose too much of the code's internals.

Courgette meets a dangerous (Red) Bend

Posted Nov 24, 2009 22:57 UTC (Tue) by hozelda (guest, #19341) [Link]

>> If it's so obvious, why aren't there any open source implementations? Why aren't automatic updates handled this way in Linux distros or commercial OS:es?

Assuming you are correct... probably because there are more important things to worry about as a function of the resources available to tackle them.

The day this becomes a dominating issue, very good solutions will be developed independently. [ http://www.againstmonopoly.org/index.php?perm=59305600000... ]

The patent is likely unconstitutional (illegal) because it almost surely does not promote the progress of science and useful arts.