# [PATCH] cogito: Avoid slowness when timewarping large trees. 10 messages from 2006-03-24 to 2006-03-26. Participants: Jeff King, Junio C Hamano, Shawn Pearce, Petr Baudis. Thread: https://gitlist.dev/t/3707 ## Jeff King, 2006-03-24 08:44 Subject: [PATCH] cogito: Avoid slowness when timewarping large trees. Message-ID: <20060324084423.GA30213@coredump.intra.peff.net> URL: https://gitlist.dev/e/20060324084423.GA30213%40coredump.intra.peff.net ``` 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 diff --git a/cg-Xlib b/cg-Xlib index a2f28cf..ceddeeb 100644 --- a/cg-Xlib +++ b/cg-Xlib @@ -345,12 +345,9 @@ tree_timewarp() # Kill gone files git-diff-tree -r "$base" "$branch" | - while IFS=$'\t' read header file; do - # match ":100755 000000 14d43b1abf... 000000000... D" - if echo "$header" | egrep "^:([^ ][^ ]* ){4}D" >/dev/null; then - rm -- "$file" - fi - done + # match ":100755 000000 14d43b1abf... 000000000... D" + sed -ne 's/^:\([^ ][^ ]* \)\{4\}D\t//p' | + xargs rm -- git-checkout-index -u -f -a # FIXME: Can produce bogus "contains only garbage" messages. -- 1.2.4 ``` ## Junio C Hamano, 2006-03-24 10:21 Subject: Re: [PATCH] cogito: Avoid slowness when timewarping large trees. Message-ID: <7vd5gc16u2.fsf@assigned-by-dhcp.cox.net> URL: https://gitlist.dev/e/7vd5gc16u2.fsf%40assigned-by-dhcp.cox.net In-Reply-To: <20060324084423.GA30213@coredump.intra.peff.net> ``` Jeff King writes: > 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. >... > --- > > cg-Xlib | 9 +++------ > 1 files changed, 3 insertions(+), 6 deletions(-) > > a9a160c0bd63973c53ba3aa74650728135d23ac7 > diff --git a/cg-Xlib b/cg-Xlib > index a2f28cf..ceddeeb 100644 > --- a/cg-Xlib > +++ b/cg-Xlib > @@ -345,12 +345,9 @@ tree_timewarp() > > # Kill gone files > git-diff-tree -r "$base" "$branch" | > ... > + # match ":100755 000000 14d43b1abf... 000000000... D" > + sed -ne 's/^:\([^ ][^ ]* \)\{4\}D\t//p' | > + xargs rm -- > git-checkout-index -u -f -a 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. ``` ## Jeff King, 2006-03-24 10:55 Subject: Re: [PATCH] cogito: Avoid slowness when timewarping large trees. Message-ID: <20060324105543.GA2543@coredump.intra.peff.net> URL: https://gitlist.dev/e/20060324105543.GA2543%40coredump.intra.peff.net In-Reply-To: <7vd5gc16u2.fsf@assigned-by-dhcp.cox.net> ``` On Fri, Mar 24, 2006 at 02:21:25AM -0800, Junio C Hamano wrote: > Metainformation fields are internally separated with SP and a > TAB comes before pathname; you can just say: > > sed -ne 's/^:[^ ]* D //p' That is much cleaner (I stupidly just converted the original regex verbatim). > a SP). You might also want to consider "xargs rm -f --", BTW. Oops, you're right. In particular, rm complains when there are no deletions. > 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. 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 ``` ## Junio C Hamano, 2006-03-24 11:01 Subject: Re: [PATCH] cogito: Avoid slowness when timewarping large trees. Message-ID: <7v3bh814z4.fsf@assigned-by-dhcp.cox.net> URL: https://gitlist.dev/e/7v3bh814z4.fsf%40assigned-by-dhcp.cox.net In-Reply-To: <20060324105543.GA2543@coredump.intra.peff.net> ``` Jeff King writes: > ... Should the first read-tree actually > be: > git-read-tree --reset "$base" 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-<. ``` ## Jeff King, 2006-03-24 11:22 Subject: Re: [PATCH] cogito: Avoid slowness when timewarping large trees. Message-ID: <20060324112246.GA5220@coredump.intra.peff.net> URL: https://gitlist.dev/e/20060324112246.GA5220%40coredump.intra.peff.net In-Reply-To: <7v3bh814z4.fsf@assigned-by-dhcp.cox.net> ``` On Fri, Mar 24, 2006 at 03:01:35AM -0800, Junio C Hamano wrote: > > git-read-tree --reset "$base" > Exactly. That's what I meant. Thanks. 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 ``` ## Shawn Pearce, 2006-03-24 16:43 Subject: Re: [PATCH] cogito: Avoid slowness when timewarping large trees. Message-ID: <20060324164352.GA20684@spearce.org> URL: https://gitlist.dev/e/20060324164352.GA20684%40spearce.org In-Reply-To: <20060324112246.GA5220@coredump.intra.peff.net> ``` Jeff King wrote: > On Fri, Mar 24, 2006 at 03:01:35AM -0800, Junio C Hamano wrote: > > > > git-read-tree --reset "$base" > > Exactly. That's what I meant. Thanks. > > 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)? 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? -- Shawn. ``` ## Jeff King, 2006-03-25 09:36 Subject: Re: [PATCH] cogito: Avoid slowness when timewarping large trees. Message-ID: <20060325093641.GA26284@coredump.intra.peff.net> URL: https://gitlist.dev/e/20060325093641.GA26284%40coredump.intra.peff.net In-Reply-To: <20060324164352.GA20684@spearce.org> ``` On Fri, Mar 24, 2006 at 11:43:52AM -0500, Shawn Pearce wrote: > Now that I think about it isn't this sort of where you were before > in cg-seek? 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 ``` ## Jeff King, 2006-03-25 09:39 Subject: [PATCH] Avoid slowness when timewarping large trees. Message-ID: <20060325093957.GA27832@coredump.intra.peff.net> URL: https://gitlist.dev/e/20060325093957.GA27832%40coredump.intra.peff.net In-Reply-To: <20060325093641.GA26284@coredump.intra.peff.net> ``` 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 --- 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 diff --git a/cg-Xlib b/cg-Xlib index 5896df7..1a9bd4f 100644 --- a/cg-Xlib +++ b/cg-Xlib @@ -363,12 +363,9 @@ tree_timewarp() # Kill gone files git-diff-tree -r "$base" "$branch" | - while IFS=$'\t' read header file; do - # match ":100755 000000 14d43b1abf... 000000000... D" - if echo "$header" | egrep "^:([^ ][^ ]* ){4}D" >/dev/null; then - rm -- "$file" - fi - done + # match ":100755 000000 14d43b1abf... 000000000... D" + sed -ne 's/^:[^\t]* D\t//p' | + xargs rm -f -- git-checkout-index -u -f -a # FIXME: Can produce bogus "contains only garbage" messages. -- 1.2.4 ``` ## Junio C Hamano, 2006-03-25 19:55 Subject: Re: [PATCH] cogito: Avoid slowness when timewarping large trees. Message-ID: <7v3bh6wb7p.fsf@assigned-by-dhcp.cox.net> URL: https://gitlist.dev/e/7v3bh6wb7p.fsf%40assigned-by-dhcp.cox.net In-Reply-To: <20060325093641.GA26284@coredump.intra.peff.net> ``` Jeff King writes: > On Fri, Mar 24, 2006 at 11:43:52AM -0500, Shawn Pearce wrote: > >> Now that I think about it isn't this sort of where you were before >> in cg-seek? > > Yes, that's basically it. Short of Junio explaining how the manual file > removal can be avoided,... 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. ``` ## Petr Baudis, 2006-03-26 18:05 Subject: Re: [PATCH] Avoid slowness when timewarping large trees. Message-ID: <20060326180549.GO18185@pasky.or.cz> URL: https://gitlist.dev/e/20060326180549.GO18185%40pasky.or.cz In-Reply-To: <20060325093957.GA27832@coredump.intra.peff.net> ``` Dear diary, on Sat, Mar 25, 2006 at 10:39:57AM CET, I got a letter where Jeff King said that... > 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 Thanks, applied. -- Petr "Pasky" Baudis Stuff: http://pasky.or.cz/ Right now I am having amnesia and deja-vu at the same time. I think I have forgotten this before. ```