patchcogito: Avoid slowness when timewarping large trees.

tree_timewarp was calling read, egrep, and rm in an O(N) loop where N is the number of changed files between two trees. This caused a bottleneck when seeking/switching/merging between trees with many changed files.

On the historical linux tree, the time to cg-seek from the head to the initial commit (a change of 19099 files) dropped from 2m35s to 21s.

---

 cg-Xlib |    9 +++------
 1 files changed, 3 insertions(+), 6 deletions(-)

a9a160c0bd63973c53ba3aa74650728135d23ac7

Jeff King <peff@peff.net> writes:

Metainformation fields are internally separated with SP and a TAB comes before pathname; you can just say:

	sed -ne 's/^:[^	]* D	//p'

there (whitespace inside [] and after D are TAB; one before D is a SP). You might also want to consider "xargs rm -f --", BTW.

However, I wonder why it does not do this instead:

	... stash away the local changes
	git-read-tree -m "$base" ;# reset the index to $base

	# switch to $branch -- removing gone files as well
	git-read-tree -m -u "$base" "$branch"

Then you can also lose diff-tree and checkout-index there.

On Fri, Mar 24, 2006 at 02:21:25AM -0800, Junio C Hamano wrote:

That is much cleaner (I stupidly just converted the original regex verbatim).

Oops, you're right. In particular, rm complains when there are no deletions.

This doesn't deal very well with local changes. The second read-tree
complains about a not uptodate entry during the merge. Since we've
already stashed the local changes as a diff, we should be able to simply
ignore them during the read-tree. Should the first read-tree actually
be:
  git-read-tree --reset "$base"
?

-Peff

Jeff King <peff@peff.net> writes:

Exactly.  That's what I meant.  Thanks.

Originally I wrote "git reset" there, but this being Cogito I thought Pasky preferred to use the true Plumbing and I botched it X-<.

On Fri, Mar 24, 2006 at 03:01:35AM -0800, Junio C Hamano wrote:

Hmm. That doesn't actually work, though. If I have a history like this:

$ cg-init -m "initial" $ cg-tag initial $ echo contents >file $ cg-add file $ cg-commit -m "added file"

and I try this: $ echo changes >file $ git-read-tree --reset master $ git-read-tree -m -u master initial

I get this: fatal: Entry 'file' not uptodate. Cannot merge.

If I do an update-index before the second read-tree, then I simply get: fatal: Entry 'file' would be overwritten by merge. Cannot merge.

Is there something I'm missing, or is a 'git reset --hard' really what we want here (in that case, the fact that git reset changes the HEAD might be a problem)?

-Peff

Jeff King <peff@peff.net> wrote:

This is sort of what I'm doing in pg-reset-tree, which is kind of like 'git-reset --hard' but I think it is faster when $force is unset:

  # Remove files left over from merge conflicts and files which are
  # somehow modified.  If this makes a directory empty it may have
  # been a new directory so delete that too.
  #
  (git-ls-files -z \
    --others \
    --ignored \
    --exclude='*#1' \
    --exclude='*#2' \
    --exclude='*#3' \
    --exclude='*.rej'
   git-diff-index --name-only -z HEAD
  ) | perl -n0e 'chomp; unlink; 1 while (s,/[^/]*$,, && rmdir)'
  
  # Rebuild the index and working directory.  We'll only checkout the
  # files which don't exist.  This resets the modified files we deleted
  # just above; remaining files will have their stat information updated
  # in the index.
  #
  git-read-tree --reset HEAD &&
  git-checkout-index --index --all $force \
    || die "Can't reset index and working directory."

  # Now that the working directory is clean we can safely merge it to
  # to our target tree, $new_base.
  #
  git-read-tree -m -u HEAD $new_base

The $force in git-checkout-index may or may not be set to '--force'; its usually not set as its not usually necessary. Unfortunately I've got a case where I'm mounting a directory exported by SAMBA onto a Windows 2000 system and if I don't include --force during git-checkout-index it doesn't work right about 1/3 of the time. (It appears to be bad stat information coming from Cygwin/Windows/SAMBA/Solaris.)

You can't skip the git-checkout-index step (I've tried) as the ls-files/diff-index above causes the modified files (in your test above 'changes') to disappear from the working directory and the read-tree may not bring it back.

Now that I think about it isn't this sort of where you were before in cg-seek?

On Fri, Mar 24, 2006 at 11:43:52AM -0500, Shawn Pearce wrote:

Yes, that's basically it. Short of Junio explaining how the manual file removal can be avoided, I think my original patch should be applied, as it causes an order of magnitude speed up. I will repost the cleaned-up version.

-Peff

tree_timewarp was calling read, egrep, and rm in an O(N) loop where N is the number of changed files between two trees. This caused a bottleneck when seeking/switching/merging between trees with many changed files.

Signed-off-by: Jeff King <peff@peff.net>

---

This is a repost of the initial patch featuring a few cleanups suggested by Junio.

 cg-Xlib |    9 +++------
 1 files changed, 3 insertions(+), 6 deletions(-)

5f79b37a0eb85ff4f643e70a7f2823e68e9d9ca4

Dear diary, on Sat, Mar 25, 2006 at 10:39:57AM CET, I got a letter where Jeff King <peff@peff.net> said that...

Thanks, applied.

Jeff King <peff@peff.net> writes:

Please don't let me slow you down -- that "git-read-tree --reset" one was just confused. I was not thinking clearly about the modification you already had in the working tree which you wanted to temporarily reset while switching.