{"thread":{"id":"3707","subject":"[PATCH] cogito: Avoid slowness when timewarping large trees.","startedAt":"2006-03-24T08:44:23Z","lastAt":"2006-03-26T18:05:49Z","messageCount":10,"participants":["Jeff King","Junio C Hamano","Shawn Pearce","Petr Baudis"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"17855","messageId":"20060324084423.GA30213@coredump.intra.peff.net","threadId":"3707","inReplyTo":null,"subject":"[PATCH] cogito: Avoid slowness when timewarping large trees.","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-03-24T08:44:23Z","receivedAt":"2006-03-24T08:44:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"\ntree_timewarp was calling read, egrep, and rm in an O(N) loop where N is\nthe number of changed files between two trees. This caused a bottleneck\nwhen seeking/switching/merging between trees with many changed files.\n\nOn the historical linux tree, the time to cg-seek from the head to the\ninitial commit (a change of 19099 files) dropped from 2m35s to 21s.\n\n---\n\n cg-Xlib |    9 +++------\n 1 files changed, 3 insertions(+), 6 deletions(-)\n\na9a160c0bd63973c53ba3aa74650728135d23ac7\ndiff --git a/cg-Xlib b/cg-Xlib\nindex a2f28cf..ceddeeb 100644\n--- a/cg-Xlib\n+++ b/cg-Xlib\n@@ -345,12 +345,9 @@ tree_timewarp()\n \n \t# Kill gone files\n \tgit-diff-tree -r \"$base\" \"$branch\" |\n-\t\twhile IFS=$'\\t' read header file; do\n-\t\t\t# match \":100755 000000 14d43b1abf... 000000000... D\"\n-\t\t\tif echo \"$header\" | egrep \"^:([^ ][^ ]* ){4}D\" >/dev/null; then\n-\t\t\t\trm -- \"$file\"\n-\t\t\tfi\n-\t\tdone\n+\t\t# match \":100755 000000 14d43b1abf... 000000000... D\"\n+\t\tsed -ne 's/^:\\([^ ][^ ]* \\)\\{4\\}D\\t//p' |\n+\t\txargs rm --\n \tgit-checkout-index -u -f -a\n \n \t# FIXME: Can produce bogus \"contains only garbage\" messages.\n-- \n1.2.4\n"},{"id":"17857","messageId":"7vd5gc16u2.fsf@assigned-by-dhcp.cox.net","threadId":"3707","inReplyTo":"20060324084423.GA30213@coredump.intra.peff.net","subject":"Re: [PATCH] cogito: Avoid slowness when timewarping large trees.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-24T10:21:25Z","receivedAt":"2006-03-24T10:21:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> tree_timewarp was calling read, egrep, and rm in an O(N) loop where N is\n> the number of changed files between two trees. This caused a bottleneck\n> when seeking/switching/merging between trees with many changed files.\n>...\n> ---\n>\n>  cg-Xlib |    9 +++------\n>  1 files changed, 3 insertions(+), 6 deletions(-)\n>\n> a9a160c0bd63973c53ba3aa74650728135d23ac7\n> diff --git a/cg-Xlib b/cg-Xlib\n> index a2f28cf..ceddeeb 100644\n> --- a/cg-Xlib\n> +++ b/cg-Xlib\n> @@ -345,12 +345,9 @@ tree_timewarp()\n>  \n>  \t# Kill gone files\n>  \tgit-diff-tree -r \"$base\" \"$branch\" |\n> ...\n> +\t\t# match \":100755 000000 14d43b1abf... 000000000... D\"\n> +\t\tsed -ne 's/^:\\([^ ][^ ]* \\)\\{4\\}D\\t//p' |\n> +\t\txargs rm --\n>  \tgit-checkout-index -u -f -a\n\nMetainformation fields are internally separated with SP and a\nTAB comes before pathname; you can just say:\n\n\tsed -ne 's/^:[^\t]* D\t//p'\n\nthere (whitespace inside [] and after D are TAB; one before D is\na SP).  You might also want to consider \"xargs rm -f --\", BTW.\n\nHowever, I wonder why it does not do this instead:\n\n\t... stash away the local changes\n\tgit-read-tree -m \"$base\" ;# reset the index to $base\n\n\t# switch to $branch -- removing gone files as well\n\tgit-read-tree -m -u \"$base\" \"$branch\"\n\nThen you can also lose diff-tree and checkout-index there.\n"},{"id":"17860","messageId":"20060324105543.GA2543@coredump.intra.peff.net","threadId":"3707","inReplyTo":"7vd5gc16u2.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] cogito: Avoid slowness when timewarping large trees.","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-03-24T10:55:44Z","receivedAt":"2006-03-24T10:55:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 24, 2006 at 02:21:25AM -0800, Junio C Hamano wrote:\n\n> Metainformation fields are internally separated with SP and a\n> TAB comes before pathname; you can just say:\n> \n> \tsed -ne 's/^:[^\t]* D\t//p'\n\nThat is much cleaner (I stupidly just converted the original regex\nverbatim).\n\n> a SP).  You might also want to consider \"xargs rm -f --\", BTW.\n\nOops, you're right. In particular, rm complains when there are no\ndeletions. \n\n> However, I wonder why it does not do this instead:\n> \n> \t... stash away the local changes\n> \tgit-read-tree -m \"$base\" ;# reset the index to $base\n> \n> \t# switch to $branch -- removing gone files as well\n> \tgit-read-tree -m -u \"$base\" \"$branch\"\n> \n> Then you can also lose diff-tree and checkout-index there.\n\nThis doesn't deal very well with local changes. The second read-tree\ncomplains about a not uptodate entry during the merge. Since we've\nalready stashed the local changes as a diff, we should be able to simply\nignore them during the read-tree. Should the first read-tree actually\nbe:\n  git-read-tree --reset \"$base\"\n?\n\n-Peff\n"},{"id":"17861","messageId":"7v3bh814z4.fsf@assigned-by-dhcp.cox.net","threadId":"3707","inReplyTo":"20060324105543.GA2543@coredump.intra.peff.net","subject":"Re: [PATCH] cogito: Avoid slowness when timewarping large trees.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-24T11:01:35Z","receivedAt":"2006-03-24T11:01:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> ... Should the first read-tree actually\n> be:\n>   git-read-tree --reset \"$base\"\n\nExactly.  That's what I meant.  Thanks.\n\nOriginally I wrote \"git reset\" there, but this being Cogito I\nthought Pasky preferred to use the true Plumbing and I botched\nit X-<.\n"},{"id":"17864","messageId":"20060324112246.GA5220@coredump.intra.peff.net","threadId":"3707","inReplyTo":"7v3bh814z4.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] cogito: Avoid slowness when timewarping large trees.","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-03-24T11:22:46Z","receivedAt":"2006-03-24T11:22:46Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 24, 2006 at 03:01:35AM -0800, Junio C Hamano wrote:\n\n> >   git-read-tree --reset \"$base\"\n> Exactly.  That's what I meant.  Thanks.\n\nHmm. That doesn't actually work, though. If I have a history like this:\n\n$ cg-init -m \"initial\"\n$ cg-tag initial\n$ echo contents >file\n$ cg-add file\n$ cg-commit -m \"added file\"\n\nand I try this:\n$ echo changes >file\n$ git-read-tree --reset master\n$ git-read-tree -m -u master initial\n\nI get this:\nfatal: Entry 'file' not uptodate. Cannot merge.\n\nIf I do an update-index before the second read-tree, then I simply get:\nfatal: Entry 'file' would be overwritten by merge. Cannot merge.\n\nIs there something I'm missing, or is a 'git reset --hard' really what\nwe want here (in that case, the fact that git reset changes the HEAD\nmight be a problem)?\n\n-Peff\n"},{"id":"17878","messageId":"20060324164352.GA20684@spearce.org","threadId":"3707","inReplyTo":"20060324112246.GA5220@coredump.intra.peff.net","subject":"Re: [PATCH] cogito: Avoid slowness when timewarping large trees.","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-03-24T16:43:52Z","receivedAt":"2006-03-24T16:43:52Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jeff King <peff@peff.net> wrote:\n> On Fri, Mar 24, 2006 at 03:01:35AM -0800, Junio C Hamano wrote:\n> \n> > >   git-read-tree --reset \"$base\"\n> > Exactly.  That's what I meant.  Thanks.\n> \n> Hmm. That doesn't actually work, though. If I have a history like this:\n> \n> $ cg-init -m \"initial\"\n> $ cg-tag initial\n> $ echo contents >file\n> $ cg-add file\n> $ cg-commit -m \"added file\"\n> \n> and I try this:\n> $ echo changes >file\n> $ git-read-tree --reset master\n> $ git-read-tree -m -u master initial\n> \n> I get this:\n> fatal: Entry 'file' not uptodate. Cannot merge.\n> \n> If I do an update-index before the second read-tree, then I simply get:\n> fatal: Entry 'file' would be overwritten by merge. Cannot merge.\n> \n> Is there something I'm missing, or is a 'git reset --hard' really what\n> we want here (in that case, the fact that git reset changes the HEAD\n> might be a problem)?\n\n\nThis is sort of what I'm doing in pg-reset-tree, which is kind\nof like 'git-reset --hard' but I think it is faster when $force\nis unset:\n\n  # Remove files left over from merge conflicts and files which are\n  # somehow modified.  If this makes a directory empty it may have\n  # been a new directory so delete that too.\n  #\n  (git-ls-files -z \\\n    --others \\\n    --ignored \\\n    --exclude='*#1' \\\n    --exclude='*#2' \\\n    --exclude='*#3' \\\n    --exclude='*.rej'\n   git-diff-index --name-only -z HEAD\n  ) | perl -n0e 'chomp; unlink; 1 while (s,/[^/]*$,, && rmdir)'\n  \n  # Rebuild the index and working directory.  We'll only checkout the\n  # files which don't exist.  This resets the modified files we deleted\n  # just above; remaining files will have their stat information updated\n  # in the index.\n  #\n  git-read-tree --reset HEAD &&\n  git-checkout-index --index --all $force \\\n    || die \"Can't reset index and working directory.\"\n\n  # Now that the working directory is clean we can safely merge it to\n  # to our target tree, $new_base.\n  #\n  git-read-tree -m -u HEAD $new_base\n\nThe $force in git-checkout-index may or may not be set to\n'--force'; its usually not set as its not usually necessary.\nUnfortunately I've got a case where I'm mounting a directory\nexported by SAMBA onto a Windows 2000 system and if I don't include\n--force during git-checkout-index it doesn't work right about 1/3\nof the time.  (It appears to be bad stat information coming from\nCygwin/Windows/SAMBA/Solaris.)\n\nYou can't skip the git-checkout-index step (I've tried) as the\nls-files/diff-index above causes the modified files (in your test\nabove 'changes') to disappear from the working directory and the\nread-tree may not bring it back.\n\nNow that I think about it isn't this sort of where you were before\nin cg-seek?\n\n-- \nShawn.\n"},{"id":"17919","messageId":"20060325093641.GA26284@coredump.intra.peff.net","threadId":"3707","inReplyTo":"20060324164352.GA20684@spearce.org","subject":"Re: [PATCH] cogito: Avoid slowness when timewarping large trees.","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-03-25T09:36:41Z","receivedAt":"2006-03-25T09:36:41Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 24, 2006 at 11:43:52AM -0500, Shawn Pearce wrote:\n\n> Now that I think about it isn't this sort of where you were before\n> in cg-seek?\n\nYes, that's basically it. Short of Junio explaining how the manual file\nremoval can be avoided, I think my original patch should be applied, as\nit causes an order of magnitude speed up. I will repost the cleaned-up\nversion.\n\n-Peff\n"},{"id":"17921","messageId":"20060325093957.GA27832@coredump.intra.peff.net","threadId":"3707","inReplyTo":"20060325093641.GA26284@coredump.intra.peff.net","subject":"[PATCH] Avoid slowness when timewarping large trees.","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2006-03-25T09:39:57Z","receivedAt":"2006-03-25T09:39:57Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"\ntree_timewarp was calling read, egrep, and rm in an O(N) loop where N is\nthe number of changed files between two trees. This caused a bottleneck\nwhen seeking/switching/merging between trees with many changed files.\n\nSigned-off-by: Jeff King <peff@peff.net>\n\n\n---\n\nThis is a repost of the initial patch featuring a few cleanups suggested\nby Junio. \n\n cg-Xlib |    9 +++------\n 1 files changed, 3 insertions(+), 6 deletions(-)\n\n5f79b37a0eb85ff4f643e70a7f2823e68e9d9ca4\ndiff --git a/cg-Xlib b/cg-Xlib\nindex 5896df7..1a9bd4f 100644\n--- a/cg-Xlib\n+++ b/cg-Xlib\n@@ -363,12 +363,9 @@ tree_timewarp()\n \n \t# Kill gone files\n \tgit-diff-tree -r \"$base\" \"$branch\" |\n-\t\twhile IFS=$'\\t' read header file; do\n-\t\t\t# match \":100755 000000 14d43b1abf... 000000000... D\"\n-\t\t\tif echo \"$header\" | egrep \"^:([^ ][^ ]* ){4}D\" >/dev/null; then\n-\t\t\t\trm -- \"$file\"\n-\t\t\tfi\n-\t\tdone\n+\t\t# match \":100755 000000 14d43b1abf... 000000000... D\"\n+\t\tsed -ne 's/^:[^\\t]* D\\t//p' |\n+\t\txargs rm -f --\n \tgit-checkout-index -u -f -a\n \n \t# FIXME: Can produce bogus \"contains only garbage\" messages.\n-- \n1.2.4\n"},{"id":"17946","messageId":"7v3bh6wb7p.fsf@assigned-by-dhcp.cox.net","threadId":"3707","inReplyTo":"20060325093641.GA26284@coredump.intra.peff.net","subject":"Re: [PATCH] cogito: Avoid slowness when timewarping large trees.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-25T19:55:38Z","receivedAt":"2006-03-25T19:55:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Fri, Mar 24, 2006 at 11:43:52AM -0500, Shawn Pearce wrote:\n>\n>> Now that I think about it isn't this sort of where you were before\n>> in cg-seek?\n>\n> Yes, that's basically it. Short of Junio explaining how the manual file\n> removal can be avoided,...\n\nPlease don't let me slow you down -- that \"git-read-tree --reset\"\none was just confused.  I was not thinking clearly about the\nmodification you already had in the working tree which you\nwanted to temporarily reset while switching.\n"},{"id":"18001","messageId":"20060326180549.GO18185@pasky.or.cz","threadId":"3707","inReplyTo":"20060325093957.GA27832@coredump.intra.peff.net","subject":"Re: [PATCH] Avoid slowness when timewarping large trees.","fromName":"Petr Baudis","fromEmail":"pasky@suse.cz","sentAt":"2006-03-26T18:05:49Z","receivedAt":"2006-03-26T18:05:49Z","isPatch":true,"sender":{"key":"pasky@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/18439?v=4"},"body":"Dear diary, on Sat, Mar 25, 2006 at 10:39:57AM CET, I got a letter\nwhere Jeff King <peff@peff.net> said that...\n> tree_timewarp was calling read, egrep, and rm in an O(N) loop where N is\n> the number of changed files between two trees. This caused a bottleneck\n> when seeking/switching/merging between trees with many changed files.\n> \n> Signed-off-by: Jeff King <peff@peff.net>\n\nThanks, applied.\n\n-- \n\t\t\t\tPetr \"Pasky\" Baudis\nStuff: http://pasky.or.cz/\nRight now I am having amnesia and deja-vu at the same time.  I think\nI have forgotten this before.\n"}]}