[darcs-users] optimising darcs annotate

Petr Rockai me at mornfall.net
Wed Oct 8 05:43:06 UTC 2008


Eric Kow <kowey at darcs.net> writes:
> On Tue, Oct 07, 2008 at 10:59:03 -0400, David Roundy wrote:
>> Yes, any sort of mapping between files and patches that modify them
>> would do.  It's a simple problem (albeit extremely tedious), so it
>> hasn't seemed worth documenting.  Various people have volunteered to
>> do it (or one person twice), and I'm pretty certain it's in the bug
>> tracker as well.
> Also adding to this, I remember on IRC some people worrying that this
> might be tricky with file/directory renames, and Taylor R Campbell
> pointing out that a conservative estimate would be good enough.
Another worry is, that the cache would be O(m*n) if we are talking about named
patches, where m = number of files and n = number of named patches. If we could
address primitive patches reasonably (which we however probably can't right
now), it could be done in O(n) for n = number of primitive patches.

I'd argue that the O(m*n) case is reasonably unlikely to be a problem. So until
we choose to expose primitive patches a little more, I'd vote for adopting this
solution. This shouldn't cause too much upward compatibility trouble.

> I think that this means is putting into the map any patch which *might*
> touch a file, but doesn't necessarily do so.  Anyway, in case anybody
> was worried about this being tricky, please keep in mind other simple
> options, such as the one I think Taylor suggested.
I am quite sure you can tell pretty exactly which hunks touch which
files. Afterall, you have to be able to apply the right hunks to right
files. It might be a little tricky to extract that information from a
pre-existing, non-cached repo -- you basically have to replay the patches,
noting down the file relationships as you go. (You don't need to keep around
the file contents though, only which files they have touched, so it shouldn't
be too time-consuming either).

Sorry that I am not sending patches, but if no-one picks up on this, I might
try to mint the semi-dirty solution (named patch <-> file map) into code. As
always, time is a constraint.


Peter Rockai | me()mornfall!net | prockai()redhat!com
 http://blog.mornfall.net | http://web.mornfall.net

"In My Egotistical Opinion, most people's C programs should be
 indented six feet downward and covered with dirt."
     -- Blair P. Houghton on the subject of C program indentation

More information about the darcs-users mailing list