Re: [PATCH 3/3] Diff overhaul, adding the other half...

quoted

quoted

quoted

quoted

"LT" == Linus Torvalds [off-list ref] writes:

LT> Hmm.. It's not working well. Not only does it take a lot of CPU time (do 
LT> an fsck first to make sure you're not seekign the disk all over the 
LT> place), but it "finds" lots of things like this:

The "finds logs of funny things" problem should have been fixed
by now, and I am fixing a big screwup now as I reported. I have
two ideas on speeding up diff-tree -C I want to run by you.

I have not measured things yet, but I think the big CPU waste is
coming from either expanding all the blobs and/or running the
diff-delta on many file pairs.  If that is indeed the cause,
then helping the upfront check in the similarity estimator that
refuses to consider a file pair whose file size change is too
big may be a good way to resolve this problem.

One approach, which I think is an unacceptable change at this
stage (but I would seriously consider if this _were_ a week and
half old project), is to record the blob size as part of the
object ID.  We say object size is "unsigned long" everywhere, so
I am talking about making the object ID from 20-byte SHA1 to
24-byte SHA1 plus 4-byte integer in the network byte order.

Since I think the above is inpractical, the second best approach
would be to piggy-back on the optimization used in uncached
diff-cache, which avoids blob expansion if cache says what we
have in the work tree already matches the object we are
interested in.

When -C is in effect, we would make diff-tree read the current
cache first, so that diff_populate_filespec() can borrow from
the current work tree when a path in the tree we are looking at
has not changed.  This would obviously be effective only when we
are talking about recent history.

Thoughts?

On Mon, 23 May 2005, Junio C Hamano wrote:

I have not measured things yet, but I think the big CPU waste is
coming from either expanding all the blobs and/or running the
diff-delta on many file pairs.  If that is indeed the cause,
then helping the upfront check in the similarity estimator that
refuses to consider a file pair whose file size change is too
big may be a good way to resolve this problem.

Since pretty much all the blobs will be expanded in the working directory
anyway, it sounds like that would be the way to go. 

One approach, which I think is an unacceptable change at this
stage (but I would seriously consider if this _were_ a week and
half old project), is to record the blob size as part of the
object ID.  We say object size is "unsigned long" everywhere, so
I am talking about making the object ID from 20-byte SHA1 to
24-byte SHA1 plus 4-byte integer in the network byte order.

You can actually get the blob size fairly easily for non-delta objects, by 
just unpacking the beginning of it. But since we have the files..

That said, I don't think -C is that important. I personally don't see it
as a thing I'd run normally - it's more of a thing I might do between
releases rather than for something like git-whatchanged that looks at
every commit. It's an interesting thing to have _available_, but I don't
think it's a huge problem if it is a lot more expensive than the more
normal "-M".

		Linus