4 ms·
Question for jgrahamc: how much more efficient is your binary delta algorithm than cperciva's bsdiff [1]? I assume since you've got the preimages of compressio
by sigil 14y ago
Question for jgrahamc: how much more efficient is your binary delta algorithm than cperciva's bsdiff [1]?
I assume since you've got the preimages of compression, as well as control over the compression format, that the diff and patch operations are much more efficient in space and time than they would be with arbitrary binary data. But...by how much?
[1] http://www.daemonology.net/bsdiff/ http://www.daemonology.net/bsdiff/
- j_s 14y agoI am particularly interested in this aspect of the discussion (explaining the process leading to deciding to develop a new tech in-house instead of re-using any existing approach). In an ideal world there would be plenty of experimentation with real-world data to justify things, but I don't read about that happening too often.
- sigil 14y agoAgree with you there on "profile first." But knowing jgrahamc, he did -- and I'd love to know the results.
- jgrahamc 14y ago:-) Yes, that's very true. Initially, I wasn't actually planning to do deltas for the compression technique and it was in testing with a whole bunch of common sites that I stumbled upon the fact that they don't change very much. That lead me to wonder about the algorithms that might be used. I did test quite a lot of stuff (and at one point thought I'd come up with a truly cool new algorithm only to realize that I was mistaken :-) to decide what to do. Railgun has to trade off three things: compression efficiency, space and time. Because we are trying to do this for performance time is the most important thing to optimize for, followed by efficiency, followed by space. bsdiff is very, very good at delta compressing binary things; Railgun isn't as good, but it's very, very fast.
- thristian 14y agoOut of curiosity, can you say anything about the algorithm you are using? A year or two ago I got quite interested in delta compression, read all the papers I could find on the topic, and eventually came up with an algorithm that seems pretty competitive, although I've mostly focussed on efficient compression rather than speed. Someday I'll get around to porting the code from Python to C and find out what the performance is really like. For what it's worth, my code is here: https://gitorious.org/python-blip https://gitorious.org/python-blip
- jakubw 14y agobsdiff is not a general purpose binary delta algorithm, it's targeted at executables. When you change a single line in the source code of a program and recompile it, bsdiff produces a small diff, even though a normal binary diff between the old and new executable would be huge due to how even a single extra instruction can cause many more addresses to shift. bsdiff wouldn't be particularly useful here.