Pandora PND diffs

[PokeParadox]

or adjusted so it uses the filesystem for hints as opposed to searching for abstracts binary data?

 

[M-HT]

I took a look at the beat source code and changed it to use less memory (for larger files) and be much faster.

This time, creating the Wesnoth patch took 15 minutes and the resulting patch file was 229 MB (compressed with xz it's 225 MB).

Using linear extrapolation, creating the patch file using the original version would take 47.5 hours.

 

[WizardStan]

What did you change? We can run original vs new against a bunch of different PNDs and see if how effective it still is.

 

[M-HT]

The resulting patch file is the same, only generated faster.

 

[M-HT]

Here is the changed file delta.hpp (rename the attachment), located in the beat/nall/bps subdirectory of the original source.

Note that I'm not a C++ programmer (much less C++11) so the changes are probably not idiomatic C++ code.

Also note, that to decrease the memory usage even further I'm using 32-bit offsets, so the maximum file size is 4GB.

delta.hpp.txt

 

[WizardStan]

So I did a search for "squashfs diff" on a whim to see if someone else had already solved the problem. They have.

I just used bsdiff on wormux vs warmux. It required half the RAM (peak at 1.6GB), created a file 1MB smaller than beat (32MB vs 33MB), and did it in 2 minutes.

Did the same for Wesnoth 1.8.6 vs 1.11.3: consumed 5GB of RAM to start (but after a few minutes fell to 3.2GB for some reason) and took 15 minutes to create a 203MB patch file. Versions closer together would definitely have much smaller numbers.

Unfortunately, applying the patch seems to require (n+m) RAM: it loads the entire file in memory and patches there before dumping to the hard drive. This definitely won't work on the Pandora as is, but I suspect it can be optimized to write as it goes and just keep a small buffer. Patching was almost instantaneous on my desktop, so might take a few seconds on the Pandora, assuming we can get RAM requirements down.

Assuming the server has enough RAM, this is not entirely unacceptable. According to the repo statistics, the average file size is almost 20MB now. Linear extrapolation would lead me to suspect it would take about 60 seconds and require 300MB of RAM per update. A server with enough RAM and multiple CPUs could handle several updates at once.

 

[milkshake]

Another note to point out is that the repo may not always have the old version of an app on the sever since the app owner can delete old versions plus the old version may have come from an old app store etc which would mean no patch file could be created.

 

[Binky]

the app owner can delete old versions

Do they do that often?

 

[M-HT]

@WizardStan
That's worse than xdelta3. Also, xdelta3 doesn't work on the whole file at once, but on file parts. Default is 64MB, I used 128MB to achieve better result (279 vs 201). This is also roughly the memory requirement when patching.

 

[milkshake]

Do they do that often?

Not sure I don't record that activity.

 

[mcobit]

I did it sometimes, but only if older versions would do bad things, that they should not or didn't work at all because of something I forgot to put in the package or something.

 

[WizardStan]

That's worse than xdelta3

Oh neat. Xdelta3 also supports merging patches. It took seconds to diff wormux to warmux and did indeed create a patch file slightly smaller than bsdiff, so fast I didn't even have time to figure out how much RAM it was using . This just keeps getting better and better.Wesnoth was also done in under a minute and used almost no RAM, but the patch is significantly larger: 290MB vs 210MB. That's not really a fair test, since most people will just be upgrading one or two versions back, not, 2 years.

Another note to point out is that the repo may not always have the old version of an app on the sever

When a new version is uploaded, make a diff directly between the previous and latest version. Keep, say, last 10 updates worth of patches? Or 6 months? Details to be worked out. If someone comes along and needs a patch from a version you've recorded, use xdelta to merge the patches they need and just send that one file. If they've been away too long just send the most recent version.

 

[M-HT]

Wesnoth was also done in under a minute and used almost no RAM, but the patch is significantly larger: 290MB vs 210MB. That's not really a fair test, since most people will just be upgrading one or two versions back, not, 2 years.

I used parameter -B134217728 to achieve better file size (width xdelta3). You can also disable compression, because the difference between compressed and uncompressed patch file is quite small - squashfs is already compressed, so the difference can't be compressed much.

 

[WizardStan]

Ok, awesome

Wider blocks makes smaller file, didn't see any time difference. Well done