{"thread":{"id":"3201","subject":"Bottlenecks in git merge","startedAt":"2006-01-31T21:33:14Z","lastAt":"2006-02-04T12:56:01Z","messageCount":11,"participants":["Peter Eriksen","Junio C Hamano","Petr Baudis","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"15335","messageId":"20060131213314.GA32131@ebar091.ebar.dtu.dk","threadId":"3201","inReplyTo":null,"subject":"Bottlenecks in git merge","fromName":"Peter Eriksen","fromEmail":"s022018@student.dtu.dk","sentAt":"2006-01-31T21:33:14Z","receivedAt":"2006-01-31T21:33:14Z","isPatch":false,"sender":{"key":"s022018@student.dtu.dk","avatar":null},"body":"Hello, \n\nIn connection with Ian Molton's question about merge have I played a\nlittle with 'git merge' on the kernel sources. What I find is that a\nmerge can take quite some time, but I'm not sure where that time exactly\ngoes to. Here are the times I got:\n\nRecursive (default): 4m22.282s\nResolve (-s resolve): 3m23.548s\n\n\nWhat is taking so long?\n\nRegards,\n\nPeter\n\n\n==============================>8==================\n#!/bin/sh\n# Run from linux-2.6\n\nchange_readme() {\n\tsed -i \"s/are much better/are better/\" README\n}\n\ngit checkout -f master\ngit branch -d test\ngit checkout -b test v2.6.12\nchange_readme\ngit commit -a -m \"Work, work, work\"\ntime git merge $STRATEGY \"Merging happily.\" HEAD v2.6.15\n"},{"id":"15342","messageId":"7vk6cgq9ny.fsf@assigned-by-dhcp.cox.net","threadId":"3201","inReplyTo":"20060131213314.GA32131@ebar091.ebar.dtu.dk","subject":"Re: Bottlenecks in git merge","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-01-31T23:06:57Z","receivedAt":"2006-01-31T23:06:57Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Peter Eriksen\" writes:\n\n> Recursive (default): 4m22.282s\n> Resolve (-s resolve): 3m23.548s\n>\n> What is taking so long?\n\nI am actually surprised that recursive is not much slower than\nresolve. I expected to see bigger difference for a merge like\nthis.\n\n> git checkout -b test v2.6.12\n> change_readme\n> git commit -a -m \"Work, work, work\"\n> time git merge $STRATEGY \"Merging happily.\" HEAD v2.6.15\n\nYou are merging a variant of v2.6.12 and v2.6.15. Each of these\ntwo official revisions has roughly 18,000 files, and they differ\nat 10,723 files among them.\n\nWith an up-to-date index that has small changes from v2.6.12,\nmerging these two revisions using read-tree -m to do the trivial\nmerge (the part that comes before recursive/resolve) leaves\nabout 850 files to be resolved in the working tree. For these\nfiles, you need to do an equivalent of merge-one-file to merge\nthe differences (in this particular case, most of them are\n\"removed in one but unchanged in the other\" kind). In addition,\nyou have to checkout the result of the merge, which means you\nneed to update at least 10,723 files.\n\nI suspect that it might make things quite faster if we resolved\ncase 8 and 10 (see either Documentation/technical/trivial-merge\nor t/t1000) in index for this particular case, but it has\ncorrectness issues. A merge strategy may want to say \"This file\nwas removed by the other branch while it stayed on our branch;\nbut this is not a remove but actually a rename\", and do\nsomething different from what merge-one-file does, and resolving\nthese cases in index closes the door for that possibility.\n"},{"id":"15344","messageId":"20060131232731.GA31278@pasky.or.cz","threadId":"3201","inReplyTo":"20060131213314.GA32131@ebar091.ebar.dtu.dk","subject":"Re: Bottlenecks in git merge","fromName":"Petr Baudis","fromEmail":"pasky@suse.cz","sentAt":"2006-01-31T23:27:32Z","receivedAt":"2006-01-31T23:27:32Z","isPatch":false,"sender":{"key":"pasky@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/18439?v=4"},"body":"Hello,\n\nDear diary, on Tue, Jan 31, 2006 at 10:33:14PM CET, I got a letter\nwhere Peter Eriksen said that...\n> In connection with Ian Molton's question about merge have I played a\n> little with 'git merge' on the kernel sources. What I find is that a\n> merge can take quite some time, but I'm not sure where that time exactly\n> goes to. Here are the times I got:\n> \n> Recursive (default): 4m22.282s\n> Resolve (-s resolve): 3m23.548s\n> \n> \n> What is taking so long?\n\nit is difficult to benchmark for me since everything required for the\nmerge (that is, both all the objects and the whole working tree) just\nwon't fit into my caches (or Linux at least won't let it stay there for\nlong enough). I ended up repeatedly calling the subcommands, but that\nobviously is not a real world usage pattern. Proportionally, the\nsignificant eaters of time for cg-merge (similar to -s resolve) are:\n\ngit-merge-base --- 1s cached, 10s to 20s uncached\ngit-read-tree -m --- 1s cached, 10s or more uncached\ngit-read-tree -m -u --- 1m50s w/ heavy disk activity, but big part of it\n is writing blocks\ngit-merge-index -a \\\n\t-o /bin/true --- 1s cached\ngit-merge-index -a \\\n\t-o ~/cogito/cg-Xmergefile\n --- 1m27s with some disk activity (44s user, 20s sys)\n cg-Xmergefile is very similar to\n\t\t\t git-merge-one-file\n\nNote that the time spent by git-read-tree here is just checking out the\nnew file versions, which is inevitable. ;-)\n\nThe real killer here is therefore git-merge-one-file. Most frequent hits\nhere are probably of the added-in-one case, resulting in two more\nfork()s, reloading the index like mad all the time.\n\nComparing cg-merge to git-merge, one difference is that git-merge tries\nto do kind of \"trivial\" merge first (apparently even if -s was passed to\nit), the point of which kind of escapes me if you are using the resolve\nstrategy, but which causes two git-update-index calls - even one can\ntake good half a minute or more if your cache is cold.\n\n-- \n\t\t\t\tPetr \"Pasky\" Baudis\nStuff: http://pasky.or.cz/\nOf the 3 great composers Mozart tells us what it's like to be human,\nBeethoven tells us what it's like to be Beethoven and Bach tells us\nwhat it's like to be the universe. -- Douglas Adams\n"},{"id":"15345","messageId":"20060131233504.GB31278@pasky.or.cz","threadId":"3201","inReplyTo":"7vk6cgq9ny.fsf@assigned-by-dhcp.cox.net","subject":"Re: Bottlenecks in git merge","fromName":"Petr Baudis","fromEmail":"pasky@suse.cz","sentAt":"2006-01-31T23:35:04Z","receivedAt":"2006-01-31T23:35:04Z","isPatch":false,"sender":{"key":"pasky@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/18439?v=4"},"body":"Dear diary, on Wed, Feb 01, 2006 at 12:06:57AM CET, I got a letter\nwhere Junio C Hamano said that...\n> \"Peter Eriksen\" writes:\n> \n> > Recursive (default): 4m22.282s\n> > Resolve (-s resolve): 3m23.548s\n> >\n> > What is taking so long?\n> \n> I am actually surprised that recursive is not much slower than\n> resolve. I expected to see bigger difference for a merge like\n> this.\n> \n> > git checkout -b test v2.6.12\n> > change_readme\n> > git commit -a -m \"Work, work, work\"\n> > time git merge $STRATEGY \"Merging happily.\" HEAD v2.6.15\n> \n> You are merging a variant of v2.6.12 and v2.6.15. Each of these\n> two official revisions has roughly 18,000 files, and they differ\n> at 10,723 files among them.\n> \n> With an up-to-date index that has small changes from v2.6.12,\n> merging these two revisions using read-tree -m to do the trivial\n> merge (the part that comes before recursive/resolve) leaves\n> about 850 files to be resolved in the working tree. For these\n> files, you need to do an equivalent of merge-one-file to merge\n> the differences (in this particular case, most of them are\n> \"removed in one but unchanged in the other\" kind). In addition,\n> you have to checkout the result of the merge, which means you\n> need to update at least 10,723 files.\n> \n> I suspect that it might make things quite faster if we resolved\n> case 8 and 10 (see either Documentation/technical/trivial-merge\n> or t/t1000) in index for this particular case, but it has\n> correctness issues. A merge strategy may want to say \"This file\n> was removed by the other branch while it stayed on our branch;\n> but this is not a remove but actually a rename\", and do\n> something different from what merge-one-file does, and resolving\n> these cases in index closes the door for that possibility.\n\nWhat about letting the file-handler actually tell merge-index what to\ndo? merge-index could make a fifo at fd 3 for it (we might fork a\nspecial buffering process for it to avoid PIPE_BUF issues) and let it\nwrite there a sequence of lines like:\n\n\tpath\\0{add|remove|update} {workingcopy| }\n\nThat would avoid many in-file-handler forks and especially perpetual\nreloading and rewriting of the index file, which _seems_ to be the main\ntime waster according to my somewhat fuzzy benchmarks.\n\n-- \n\t\t\t\tPetr \"Pasky\" Baudis\nStuff: http://pasky.or.cz/\nOf the 3 great composers Mozart tells us what it's like to be human,\nBeethoven tells us what it's like to be Beethoven and Bach tells us\nwhat it's like to be the universe. -- Douglas Adams\n"},{"id":"15348","messageId":"Pine.LNX.4.64.0601311533040.7301@g5.osdl.org","threadId":"3201","inReplyTo":"7vk6cgq9ny.fsf@assigned-by-dhcp.cox.net","subject":"Re: Bottlenecks in git merge","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-01-31T23:45:27Z","receivedAt":"2006-01-31T23:45:27Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 31 Jan 2006, Junio C Hamano wrote:\n> \n> I am actually surprised that recursive is not much slower than\n> resolve. I expected to see bigger difference for a merge like\n> this.\n\nWell, if most of the cost is just the trivial single-file merges and the \nfact that we have to update a ton of files from an old version (and it \nprobably is), the difference between the trivial and the recursive merge \nis not going to be huge.\n\n> With an up-to-date index that has small changes from v2.6.12,\n> merging these two revisions using read-tree -m to do the trivial\n> merge (the part that comes before recursive/resolve) leaves\n> about 850 files to be resolved in the working tree. For these\n> files, you need to do an equivalent of merge-one-file to merge\n> the differences (in this particular case, most of them are\n> \"removed in one but unchanged in the other\" kind). In addition,\n> you have to checkout the result of the merge, which means you\n> need to update at least 10,723 files.\n\nIt would be interesting to see how big the \"resolve 850 files\" part is vs \nthe \"check out 10k+ files\" is.\n\nIn particular, if the \"resolve 850 files\" is a noticeable portion of it, \nthen the right thing to do may be to just re-write git-merge-one-file.sh \nin C. Right now, almost _all_ of the expense of that thing is just the \nshell interpreter startup. The actual actions it does are usually fairly \ncheap.\n\n(yes, a real three-way merge is more expensive, but I suspect that even \nthat isn't much more expensive than starting up an invocation of \"bash\". \nThe other actions that merge-one-file does are _really_ trivial).\n\nIn fact, we could hardcode the \"git-merge-one-file\" behaviour inside \n\"git-merge-index\". \n\nNow, that won't help \"recursive\" (which doesn't use git-merge-one-file at \nall, and does it all by hand), but it would be an interesting test to \nmake, becuase if it makes the simpler \"-s resolve\" merge even faster, then \nwe know that this is likely a large portion of the time.\n\nThen, somebody would have to consider what to do about \ngit-merge-recursive. For example, if the _common_ case is \"modified in \nboth, but differently\", and they merge cleanly, maybe the recursive merge \ncould handle those separately and fast with a special \"git-merge-one-file\" \ninvocation (just to cut down the number of files that it needs to think \nmore about).\n\n\t\tLinus\n"},{"id":"15351","messageId":"7vvevzoqm0.fsf@assigned-by-dhcp.cox.net","threadId":"3201","inReplyTo":"20060131233504.GB31278@pasky.or.cz","subject":"Re: Bottlenecks in git merge","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-01T00:43:51Z","receivedAt":"2006-02-01T00:43:51Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Petr Baudis writes:\n\n> What about letting the file-handler actually tell merge-index what to\n> do? merge-index could make a fifo at fd 3 for it (we might fork a\n> special buffering process for it to avoid PIPE_BUF issues) and let it\n> write there a sequence of lines like...\n\nYes. That is sensible.\n\nA merge handler that is willing to look at the current index\nstages (and merge-recursive certainly is capable of doing that)\ncan open an outgoing pipe to 'git-update-index --index-info' and\ndrive it. The command syntax is a bit different from what you\nwrote in your message and I think if we go this route we should\nmake --index-info a bit easier to use by allowing it to accept\nstage 0 entries.\n\n-- >8 --\nupdate-index --index-info: allow stage 0 entries.\n\nSomehow we did not allow stuffing the index with stage 0 entries\nthrough --index-info interface. I do not think of a reason to\nforbid it offhand.\n\nSigned-off-by: Junio C Hamano \n---\ndiff --git a/update-index.c b/update-index.c\nindex 2361e41..94436dd 100644\n--- a/update-index.c\n+++ b/update-index.c\n@@ -303,7 +303,7 @@ static void read_index_info(int line_ter\n \t\tif (!tab || tab - ptr < 41)\n \t\t\tgoto bad_line;\n \n-\t\tif (tab[-2] == ' ' && '1' <= tab[-1] && tab[-1] <= '3') {\n+\t\tif (tab[-2] == ' ' && '0' <= tab[-1] && tab[-1] <= '3') {\n \t\t\tstage = tab[-1] - '0';\n \t\t\tptr = tab + 1; /* point at the head of path */\n \t\t\ttab = tab - 2; /* point at tail of sha1 */\n"},{"id":"15352","messageId":"20060201005035.GD31278@pasky.or.cz","threadId":"3201","inReplyTo":"Pine.LNX.4.64.0601311533040.7301@g5.osdl.org","subject":"Re: Bottlenecks in git merge","fromName":"Petr Baudis","fromEmail":"pasky@suse.cz","sentAt":"2006-02-01T00:50:35Z","receivedAt":"2006-02-01T00:50:35Z","isPatch":false,"sender":{"key":"pasky@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/18439?v=4"},"body":"Dear diary, on Wed, Feb 01, 2006 at 12:45:27AM CET, I got a letter\nwhere Linus Torvalds said that...\n> It would be interesting to see how big the \"resolve 850 files\" part is vs \n> the \"check out 10k+ files\" is.\n\nSee my other mail.\n\n> In particular, if the \"resolve 850 files\" is a noticeable portion of it, \n> then the right thing to do may be to just re-write git-merge-one-file.sh \n> in C. Right now, almost _all_ of the expense of that thing is just the \n> shell interpreter startup. The actual actions it does are usually fairly \n> cheap.\n\nNope.\n\nxpasky@machine[0:0]~/linux-2.6.git$ echo -e '#!/bin/sh\\n/bin/true' >r && chmod a+x r\nxpasky@machine[0:0]~/linux-2.6.git$ time git-merge-index -o ./r -a\n\nreal 0m3.827s\nuser 0m1.788s\nsys 0m2.004s\nxpasky@machine[0:0]~/linux-2.6.git$ time git-merge-index -o ~/git-pb/git-merge-one-file -a\n[lots of \"Removing\"]\n\nreal 1m21.773s\nuser 0m30.806s\nsys 0m13.248s\n\nThe costs are apparently in git-update-index, not in the shell.\n\n-- \n\t\t\t\tPetr \"Pasky\" Baudis\nStuff: http://pasky.or.cz/\nOf the 3 great composers Mozart tells us what it's like to be human,\nBeethoven tells us what it's like to be Beethoven and Bach tells us\nwhat it's like to be the universe. -- Douglas Adams\n"},{"id":"15354","messageId":"Pine.LNX.4.64.0601311701000.7301@g5.osdl.org","threadId":"3201","inReplyTo":"20060201005035.GD31278@pasky.or.cz","subject":"Re: Bottlenecks in git merge","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-02-01T01:04:00Z","receivedAt":"2006-02-01T01:04:00Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 1 Feb 2006, Petr Baudis wrote:\n> \n> xpasky@machine[0:0]~/linux-2.6.git$ echo -e '#!/bin/sh\\n/bin/true' >r && chmod a+x r\n> xpasky@machine[0:0]~/linux-2.6.git$ time git-merge-index -o ./r -a\n> \n> real 0m3.827s\n> user 0m1.788s\n> sys 0m2.004s\n> xpasky@machine[0:0]~/linux-2.6.git$ time git-merge-index -o ~/git-pb/git-merge-one-file -a\n> [lots of \"Removing\"]\n> \n> real 1m21.773s\n> user 0m30.806s\n> sys 0m13.248s\n> \n> The costs are apparently in git-update-index, not in the shell.\n\nBtw, this is where \"oprofile\" really shines. You can get exact listings of \nwhich symbols in which programs are taking up CPU-time, even when the time \nis spent in hundreds of different executions of a program.\n\nMe, I'm too lazy to use it often, but not too lazy to point others towards \nit.\n\nYou do need to have kernel support for it compiled in, and it works better \non certain CPU's (that have supported counters) than on others.\n\n\t\tLinus\n"},{"id":"15558","messageId":"7v8xsr60n2.fsf@assigned-by-dhcp.cox.net","threadId":"3201","inReplyTo":"20060131213314.GA32131@ebar091.ebar.dtu.dk","subject":"[PATCH] read-tree --aggressive","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-04T07:31:13Z","receivedAt":"2006-02-04T07:31:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Peter Eriksen\" writes:\n\n> In connection with Ian Molton's question about merge have I played a\n> little with 'git merge' on the kernel sources. What I find is that a\n> merge can take quite some time, but I'm not sure where that time exactly\n> goes to. Here are the times I got:\n>\n> Recursive (default): 4m22.282s\n> Resolve (-s resolve): 3m23.548s\n\nIn your sample script, you do not disable the post-merge diff,\nwhich is typically one of the most expensive part in the whole\nmerge, and I am wondering how fast a machine you are using to\nget 4 minutes. The post-merge diff is generated by piping the\noutput of 'diff-tree -M' to 'apply --stat --summary', and that\nstep alone takes about 12 minutes wallclock time on my box X-<.\n\nSince my box is not as fast as yours, I've eliminated the\npost-merge diff step and tried your final merge step like this:\n\n\t$ time git merge --no-summary -s resolve \\\n 'Merging happily' HEAD v2.6.15 >/dev/null\n\nand got this:\n\n real\t2m15.737s\n user\t1m43.320s\n sys\t0m26.690s\n\nWith the attached patch, the most expensive part, which is the\nrepeated invocation of git-merge-one-file to remove many deleted\npaths, is eliminated. The result is this.\n\n real\t0m20.311s\n user\t0m15.780s\n sys\t0m4.150s\n\nThis patch would not help recursive strategy, though. Calling\nread-tree with --aggressive flag essentially disables the\nbenefit we would expect to get from it -- rename detection.\n\n-- >8 --\nA new flag --aggressive resolves what we traditionally resolved\nwith external git-merge-one-file inside index while read-tree\n3-way merge works.\n\ngit-merge-octopus and git-merge-resolve use this flag before\nrunning git-merge-index with git-merge-one-file.\n\nSigned-off-by: Junio C Hamano \n\n---\n\n git-merge-octopus.sh | 2 +-\n git-merge-resolve.sh | 2 +-\n read-tree.c | 32 ++++++++++++++++++++++++++++++++\n 3 files changed, 34 insertions(+), 2 deletions(-)\n\n2a4bb6bc618bdad6529d9ffe361bc8b7dd28a56c\ndiff --git a/git-merge-octopus.sh b/git-merge-octopus.sh\nindex eb74f96..eb3f473 100755\n--- a/git-merge-octopus.sh\n+++ b/git-merge-octopus.sh\n@@ -90,7 +90,7 @@ do\n \tNON_FF_MERGE=1\n \n \techo \"Trying simple merge with $SHA1\"\n-\tgit-read-tree -u -m $common $MRT $SHA1 || exit 2\n+\tgit-read-tree -u -m --aggressive $common $MRT $SHA1 || exit 2\n \tnext=$(git-write-tree 2>/dev/null)\n \tif test $? -ne 0\n \tthen\ndiff --git a/git-merge-resolve.sh b/git-merge-resolve.sh\nindex 966e81f..0a8ef21 100755\n--- a/git-merge-resolve.sh\n+++ b/git-merge-resolve.sh\n@@ -38,7 +38,7 @@ then\n fi\n \n git-update-index --refresh 2>/dev/null\n-git-read-tree -u -m $bases $head $remotes || exit 2\n+git-read-tree -u -m --aggressive $bases $head $remotes || exit 2\n echo \"Trying simple merge.\"\n if result_tree=$(git-write-tree 2>/dev/null)\n then\ndiff --git a/read-tree.c b/read-tree.c\nindex a46c6fe..5580f15 100644\n--- a/read-tree.c\n+++ b/read-tree.c\n@@ -15,6 +15,7 @@ static int update = 0;\n static int index_only = 0;\n static int nontrivial_merge = 0;\n static int trivial_merges_only = 0;\n+static int aggressive = 0;\n \n static int head_idx = -1;\n static int merge_size = 0;\n@@ -424,11 +425,14 @@ static int threeway_merge(struct cache_e\n \tint df_conflict_remote = 0;\n \n \tint any_anc_missing = 0;\n+\tint no_anc_exists = 1;\n \tint i;\n \n \tfor (i = 1; i < head_idx; i++) {\n \t\tif (!stages[i])\n \t\t\tany_anc_missing = 1;\n+\t\telse\n+\t\t\tno_anc_exists = 0;\n \t}\n \n \tindex = stages[0];\n@@ -489,6 +493,29 @@ static int threeway_merge(struct cache_e\n \tif (!head && !remote && any_anc_missing)\n \t\treturn 0;\n \n+\t/* Under the new \"aggressive\" rule, we resolve mostly trivial\n+\t * cases that we historically had git-merge-one-file resolve.\n+\t */\n+\tif (aggressive) {\n+\t\tint head_deleted = !head && !df_conflict_head;\n+\t\tint remote_deleted = !remote && !df_conflict_remote;\n+\t\t/*\n+\t\t * Deleted in both.\n+\t\t * Deleted in one and unchanged in the other.\n+\t\t */\n+\t\tif ((head_deleted && remote_deleted) ||\n+\t\t (head_deleted && remote && remote_match) ||\n+\t\t (remote_deleted && head && head_match))\n+\t\t\treturn 0;\n+\n+\t\t/*\n+\t\t * Added in both, identically.\n+\t\t */\n+\t\tif (no_anc_exists && head && remote && same(head, remote))\n+\t\t\treturn merged_entry(head, index);\n+\n+\t}\n+\n \t/* Below are \"no merge\" cases, which require that the index be\n \t * up-to-date to avoid the files getting overwritten with\n \t * conflict resolution files. \n@@ -677,6 +704,11 @@ int main(int argc, char **argv)\n \t\t\tcontinue;\n \t\t}\n \n+\t\tif (!strcmp(arg, \"--aggressive\")) {\n+\t\t\taggressive = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\n \t\t/* \"-m\" stands for \"merge\", meaning we start in stage 1 */\n \t\tif (!strcmp(arg, \"-m\")) {\n \t\t\tif (stage || merge)\n-- \n1.1.6.ge2129\n"},{"id":"15571","messageId":"20060204115201.GA22333@ebar091.ebar.dtu.dk","threadId":"3201","inReplyTo":"7v8xsr60n2.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] read-tree --aggressive","fromName":"Peter Eriksen","fromEmail":"s022018@student.dtu.dk","sentAt":"2006-02-04T11:52:01Z","receivedAt":"2006-02-04T11:52:01Z","isPatch":true,"sender":{"key":"s022018@student.dtu.dk","avatar":null},"body":"On Fri, Feb 03, 2006 at 11:31:13PM -0800, Junio C Hamano wrote:\n> \"Peter Eriksen\" writes:\n> \n> > In connection with Ian Molton's question about merge have I played a\n> > little with 'git merge' on the kernel sources. What I find is that a\n> > merge can take quite some time, but I'm not sure where that time exactly\n> > goes to. Here are the times I got:\n> >\n> > Recursive (default): 4m22.282s\n> > Resolve (-s resolve): 3m23.548s\n> \n> In your sample script, you do not disable the post-merge diff,\n> which is typically one of the most expensive part in the whole\n> merge, and I am wondering how fast a machine you are using to\n> get 4 minutes. The post-merge diff is generated by piping the\n> output of 'diff-tree -M' to 'apply --stat --summary', and that\n> step alone takes about 12 minutes wallclock time on my box X-<.\n> \n> Since my box is not as fast as yours, I've eliminated the\n> post-merge diff step and tried your final merge step like this:\n> \n> \t$ time git merge --no-summary -s resolve \\\n> 'Merging happily' HEAD v2.6.15 >/dev/null\n> \n> and got this:\n> \n> real\t2m15.737s\n> user\t1m43.320s\n> sys\t0m26.690s\n\nI got this:\n\nreal 0m51.661s\nuser 0m28.302s\nsys 0m8.949s\n\n> With the attached patch, the most expensive part, which is the\n> repeated invocation of git-merge-one-file to remove many deleted\n> paths, is eliminated. The result is this.\n> \n> real\t0m20.311s\n> user\t0m15.780s\n> sys\t0m4.150s\n\nI got this:\n\nreal 0m20.221s\nuser 0m6.456s\nsys 0m1.828s\n\n> This patch would not help recursive strategy, though. Calling\n> read-tree with --aggressive flag essentially disables the\n> benefit we would expect to get from it -- rename detection.\n\nAha, so now I better understand where all the time goes. Most of the\ntime is spend calculating the merge summary. After that the bottleneck\nwas the large amount of git-merge-one-file invocations.\n\nWith the aggressive patch applied it feels like the merge is mostly IO\nbound, which might explain why we get similar running times. I did get\none run of 12s, but that was a lucky shot I guess. Repeated runs gave\nbetween 15s and 21s but most where close to 20s.\n\nThanks,\n\nPeter\n"},{"id":"15575","messageId":"7v4q3fxoym.fsf@assigned-by-dhcp.cox.net","threadId":"3201","inReplyTo":"7v8xsr60n2.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] read-tree --aggressive","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-02-04T12:56:01Z","receivedAt":"2006-02-04T12:56:01Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> This patch would not help recursive strategy, though. Calling\n> read-tree with --aggressive flag essentially disables the\n> benefit we would expect to get from it -- rename detection.\n\nI think we could fairly easily tweak this by trying at least\nhalf of the rename detection inside read-tree. That would make\nit usable by merge-recursive as well.\n\nInstead of doing \"aggressive\" in the threeway_merge function\nfirst, we can process the stages without it in the first pass,\nand run an equivalent of diff-stages -M internally between stage\n#2 and stage #3, and keep the matched paths unmerged (we need to\nmark these paths somehow). After that, we can do \"aggressive\"\ncollapsing to reduce the amount of trivial merges that recursive\ndoes not have to look at for renaming merges.\n\nIf we are ambitious, we could go further. We could actually\nmove the stages around after running the rename detection diff\nbetween stages #2 and #3, along with working tree files as\nneeded. Then merge-resolve would be able to do the renaming\nmerge similar to merge-recursive.\n"}]}