Quick analysis of improving xdelta3 extraction speed.
John Arbash Meinel
john at arbash-meinel.com
Fri Jun 22 01:02:59 BST 2007
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
I finally read all the way through the VCDIFF document. It is actually
pretty interesting what they let you do. Ultimately, though, I think
there will only be so much that we can do to improve extraction
performance and stay compatible with the VCDIFF spec. While we could
write an encoder that would generate valid VCDIFF output which would be
friendly to our decoder, the decoder wouldn't be 100% compatible with
the full VCDIFF spec.
Specifically, VCDIFF uses several indirections to get extra compression
of the output. It has a way to look up addresses, based on 4 different
algorithms (repeat a previous address based on a variable sized cache
defaulting to 768, use a small offset to a recently used address
[default of 4 recently used], offset based on current location, and
offset based on fixed location in the data). It then has a code table
which matches an 8-bit action against a table of definitions (which can
be changed by a header).
Not to mention that all integers in the file are "variable width" based
on setting their first bit to 1 or 0. (base 128, and the first bit
indicates whether you need to read another byte or not).
Anyway, we could do a few possible optimizations....
Disallow changing the "bytecode" interpreter, which would allow us to
hardcode certain actions. Which mostly allows us to tell our encoder to
only generate certain ones that we have special cased in the decoder.
Anyway, it is something we should think about.
John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFGexGzJdeBCYSNAAMRAushAJ9DX16hdsvGITnf4hBxiBfUh2wV7QCfXxe+
F9UFGb73UFtCm2+3OizY55I=
=zI9h
-----END PGP SIGNATURE-----
More information about the bazaar
mailing list