From: Karl Fogel [mailto:kfogel@galois.collab.net]
> Bill Tutt <billtut@microsoft.com> writes:
> > I was looking through the design doc, and a few questions entered my
mind.
> The design doc is pretty old; better off reading header files right
> now. :-)
Heh. I have trouble keeping track of my email, let alone time to grok header
files. :)
> > VDelta: How would you compare and contrast vdelta vs. xdelta of PRCS
fame?
> > It might be useful to spend a paragraph comparing it, or if one of the
> > vdelta docs makes the comparison, then mentiong that would also be cool.
> vdelta docs do this comparison
Err, I must be blind. I dug up "Delta Algorithms: An Emprical Analysis" ACM
Transactions on Software Engineering and Methodology, Vol 7, No. 2, April
'98, and it compares vdelta against diff, diff + gzip, and bdiff, but not
against xdelta.
The thesis the xdelta author wrote
(http://www.xcf.berkeley.edu/~jmacd/xdfs.ps) briefly discusses the
differences, but doesn't actually analytically analyze those differences.
Briefly it states: (2nd to last paragraph in Section 3)
"Vo's Vdelta is a constant-space, linear-time algorithm that combines
traditional text compression techniques with delta compression. Spearating
text compression from delta compression benefits in reduced complexity since
it is possible to use off-the-shelf text compression tools, and the XDFS
source buffer technique also relies on the use of a plaintext patch file.
For these reasons the Xdelta system does not directly incorporate text
compression into its algorithms."
Additionally:
Xdelta is linear-space, linear time vs. Vdelta which is constant-space,
linear time.
This gives XDelta some bad worst case scenarios if you're not paying
attention. (Most source code control users aren't paying attention.) This
seems like a definite downside to Xdelta, given the precept that source code
control systems (and server processes in general) should try and avoid
unbounded resource worst cases. (Xdelta's memory requirement is upper
bounded at N/2 where N is the target version length)
It's also not altogether clear (based on the thesis) to me how much XDFS-r's
"source buffer" buys you. It might be worth investigating &/or bugging Josh
about the data he gets for with and without the source buffer.
Hoping he isn't rehashing something that for some reason didn't show up in
the mailing list archives,
Bill
Received on Sat Oct 21 14:36:06 2006