[darcs-users] GSoC: network optimisation vs cache vs library?

Petr Rockai me at mornfall.net
Thu Apr 15 15:05:36 UTC 2010

Max Battcher <me at worldmaker.net> writes:
> It may be "revision 1782" to Trac, but 'show contents --match "hash
> 2008..."' is "commute this file to how it would appear if only the
> patches preceding or equal to this one with a timestamp from two years
> ago were applied" to darcs. (Which ends up being quite possibly not a
> "real" historic version at all [snip]
Just for the record, this is completely wrong. This operation does no
commutation at all. All it does is reconstruct the file as it was the
instant after patch "2008..." was applied. The reason it is expensive is
that obtaining the set of patches touching that file is O(n) in
*repository* history (from 2008... to HEAD) , not in the *file* history.

This will eventually be fixed of course and does not need any DAG data
(per Stephen), we just need a repository format that can get the set of
primitive patches for a file in O(file_history) instead of
O(repository_history). Benedikt's patchindex (formerly known as
filecache) is a step in this direction, although it does not solve the
problem completely. (What we get with that is O(file_history *
biggest_patch_touching_the_file) kinda-sorta.)

Of course, you could get down to O(logn) or even O(1) (in history size,
it's not going below O(n) in file size, you see) if you stored more
pristine copies of the file. But I guess we can look into that when we
find out that the above is not enough.


More information about the darcs-users mailing list