{"thread":{"id":"9476","subject":"[PATCH 1/2] Move old index entry removal from \"unpack_trees()\" into the individual functions","startedAt":"2007-08-10T19:15:54Z","lastAt":"2007-08-11T17:27:10Z","messageCount":7,"participants":["Linus Torvalds","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"50434","messageId":"alpine.LFD.0.999.0708101213560.30176@woody.linux-foundation.org","threadId":"9476","inReplyTo":null,"subject":"[PATCH 1/2] Move old index entry removal from \"unpack_trees()\" into the individual functions","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-10T19:15:54Z","receivedAt":"2007-08-10T19:15:54Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis makes no changes to current code, but it allows the individual merge \nfunctions to decide what to do about the old entry.  They might decide to \nupdate it in place, rather than force them to always delete and re-add it.\n    \nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nThis commit on purpose does *not* change any behaviour, it just lays the \ngroundwork for the next patch, which optimizes the hell out of the two \ncommon cases.\n\n unpack-trees.c |   29 +++++++++++++++++++++++------\n unpack-trees.h |   11 ++++++-----\n 2 files changed, 29 insertions(+), 11 deletions(-)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 5d1ffd1..7fed5d2 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -58,10 +58,17 @@ static int entcmp(const char *name1, int dir1, const char *name2, int dir2)\n \treturn ret;\n }\n \n+static inline void remove_entry(int remove)\n+{\n+\tif (remove >= 0)\n+\t\tremove_cache_entry_at(remove);\n+}\n+\n static int unpack_trees_rec(struct tree_entry_list **posns, int len,\n \t\t\t    const char *base, struct unpack_trees_options *o,\n \t\t\t    struct tree_entry_list *df_conflict_list)\n {\n+\tint remove;\n \tint baselen = strlen(base);\n \tint src_size = len + 1;\n \tint i_stk = i_stk;\n@@ -145,10 +152,11 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len,\n \n \t\tsubposns = xcalloc(len, sizeof(struct tree_list_entry *));\n \n+\t\tremove = -1;\n \t\tif (cache_name && !strcmp(cache_name, first)) {\n \t\t\tany_files = 1;\n \t\t\tsrc[0] = active_cache[o->pos];\n-\t\t\tremove_cache_entry_at(o->pos);\n+\t\t\tremove = o->pos;\n \t\t}\n \n \t\tfor (i = 0; i < len; i++) {\n@@ -214,13 +222,14 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len,\n \t\t\t\t\t\tprintf(\"\\n\");\n \t\t\t\t}\n #endif\n-\t\t\t\tret = o->fn(src, o);\n+\t\t\t\tret = o->fn(src, o, remove);\n \n #if DBRT_DEBUG > 1\n \t\t\t\tprintf(\"Added %d entries\\n\", ret);\n #endif\n \t\t\t\to->pos += ret;\n \t\t\t} else {\n+\t\t\t\tremove_entry(remove);\n \t\t\t\tfor (i = 0; i < src_size; i++) {\n \t\t\t\t\tif (src[i]) {\n \t\t\t\t\t\tadd_cache_entry(src[i], ADD_CACHE_OK_TO_ADD|ADD_CACHE_SKIP_DFCHECK);\n@@ -641,7 +650,8 @@ static void show_stage_entry(FILE *o,\n #endif\n \n int threeway_merge(struct cache_entry **stages,\n-\t\tstruct unpack_trees_options *o)\n+\t\tstruct unpack_trees_options *o,\n+\t\tint remove)\n {\n \tstruct cache_entry *index;\n \tstruct cache_entry *head;\n@@ -657,6 +667,7 @@ int threeway_merge(struct cache_entry **stages,\n \tint no_anc_exists = 1;\n \tint i;\n \n+\tremove_entry(remove);\t\t\n \tfor (i = 1; i < o->head_idx; i++) {\n \t\tif (!stages[i] || stages[i] == o->df_conflict_entry)\n \t\t\tany_anc_missing = 1;\n@@ -809,12 +820,14 @@ int threeway_merge(struct cache_entry **stages,\n  *\n  */\n int twoway_merge(struct cache_entry **src,\n-\t\tstruct unpack_trees_options *o)\n+\t\tstruct unpack_trees_options *o,\n+\t\tint remove)\n {\n \tstruct cache_entry *current = src[0];\n \tstruct cache_entry *oldtree = src[1];\n \tstruct cache_entry *newtree = src[2];\n \n+\tremove_entry(remove);\n \tif (o->merge_size != 2)\n \t\treturn error(\"Cannot do a twoway merge of %d trees\",\n \t\t\t     o->merge_size);\n@@ -868,11 +881,13 @@ int twoway_merge(struct cache_entry **src,\n  * stage0 does not have anything there.\n  */\n int bind_merge(struct cache_entry **src,\n-\t\tstruct unpack_trees_options *o)\n+\t\tstruct unpack_trees_options *o,\n+\t\tint remove)\n {\n \tstruct cache_entry *old = src[0];\n \tstruct cache_entry *a = src[1];\n \n+\tremove_entry(remove);\n \tif (o->merge_size != 1)\n \t\treturn error(\"Cannot do a bind merge of %d trees\\n\",\n \t\t\t     o->merge_size);\n@@ -891,11 +906,13 @@ int bind_merge(struct cache_entry **src,\n  * - take the stat information from stage0, take the data from stage1\n  */\n int oneway_merge(struct cache_entry **src,\n-\t\tstruct unpack_trees_options *o)\n+\t\tstruct unpack_trees_options *o,\n+\t\tint remove)\n {\n \tstruct cache_entry *old = src[0];\n \tstruct cache_entry *a = src[1];\n \n+\tremove_entry(remove);\n \tif (o->merge_size != 1)\n \t\treturn error(\"Cannot do a oneway merge of %d trees\",\n \t\t\t     o->merge_size);\ndiff --git a/unpack-trees.h b/unpack-trees.h\nindex 9cd39a2..5517faa 100644\n--- a/unpack-trees.h\n+++ b/unpack-trees.h\n@@ -4,7 +4,8 @@\n struct unpack_trees_options;\n \n typedef int (*merge_fn_t)(struct cache_entry **src,\n-\t\tstruct unpack_trees_options *options);\n+\t\tstruct unpack_trees_options *options,\n+\t\tint remove);\n \n struct unpack_trees_options {\n \tint reset;\n@@ -29,9 +30,9 @@ struct unpack_trees_options {\n extern int unpack_trees(unsigned n, struct tree_desc *t,\n \t\tstruct unpack_trees_options *options);\n \n-int threeway_merge(struct cache_entry **stages, struct unpack_trees_options *o);\n-int twoway_merge(struct cache_entry **src, struct unpack_trees_options *o);\n-int bind_merge(struct cache_entry **src, struct unpack_trees_options *o);\n-int oneway_merge(struct cache_entry **src, struct unpack_trees_options *o);\n+int threeway_merge(struct cache_entry **stages, struct unpack_trees_options *o, int);\n+int twoway_merge(struct cache_entry **src, struct unpack_trees_options *o, int);\n+int bind_merge(struct cache_entry **src, struct unpack_trees_options *o, int);\n+int oneway_merge(struct cache_entry **src, struct unpack_trees_options *o, int);\n \n #endif\n"},{"id":"50436","messageId":"alpine.LFD.0.999.0708101216000.30176@woody.linux-foundation.org","threadId":"9476","inReplyTo":"alpine.LFD.0.999.0708101213560.30176@woody.linux-foundation.org","subject":"[PATCH 2/2] Optimize the common cases of git-read-tree","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-10T19:21:20Z","receivedAt":"2007-08-10T19:21:20Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis optimizes bind_merge() and oneway_merge() to not unnecessarily\nremove and re-add the old index entries when they can just get replaced\nby updated ones.\n\nThis makes these operations much faster for large trees (where \"large\"\nis in the 50,000+ file range), because we don't unnecessarily move index\nentries around in the index array all the time.\n\nUsing the \"bummer\" tree (a test-tree with 100,000 files) we get:\n\nBefore:\n\t[torvalds@woody bummer]$ time git commit -m\"Change one file\" 50/500\n\treal    0m9.470s\n\tuser    0m8.729s\n\tsys     0m0.476s\n\nAfter:\n\t[torvalds@woody bummer]$ time git commit -m\"Change one file\" 50/500\n\treal    0m1.173s\n\tuser    0m0.720s\n\tsys     0m0.452s\n\nso for large trees this is easily very noticeable indeed.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nBtw, these patches are based on top of my \"speedup\" branch, which includes \nthe previous changes (including the change to use \"struct tree_desc\" in \nunpacking). However, apart from some context lines, they really should \nwork fine on top of current master too, so if you don't want to take the \n\"struct tree_desc\" one, these patches should work fine even without it.\n\nAlso: this same \"don't remove unnecessarily\" case could (and should) be \ndone for the two-way and three-way cases too, and it should be trivial to \ndo. However, I didn't bother, since it wasn't the particular timings I was \nworried about. \n\nBut doing that should help branch switching a lot, so I may send a \"patch \n3/2\" soon.\n\n unpack-trees.c |    6 +++---\n 1 files changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 7fed5d2..b4e2618 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -887,7 +887,6 @@ int bind_merge(struct cache_entry **src,\n \tstruct cache_entry *old = src[0];\n \tstruct cache_entry *a = src[1];\n \n-\tremove_entry(remove);\n \tif (o->merge_size != 1)\n \t\treturn error(\"Cannot do a bind merge of %d trees\\n\",\n \t\t\t     o->merge_size);\n@@ -912,13 +911,14 @@ int oneway_merge(struct cache_entry **src,\n \tstruct cache_entry *old = src[0];\n \tstruct cache_entry *a = src[1];\n \n-\tremove_entry(remove);\n \tif (o->merge_size != 1)\n \t\treturn error(\"Cannot do a oneway merge of %d trees\",\n \t\t\t     o->merge_size);\n \n-\tif (!a)\n+\tif (!a) {\n+\t\tremove_entry(remove);\n \t\treturn deleted_entry(old, old, o);\n+\t}\n \tif (old && same(old, a)) {\n \t\tif (o->reset) {\n \t\t\tstruct stat st;\n"},{"id":"50438","messageId":"alpine.LFD.0.999.0708101224110.30176@woody.linux-foundation.org","threadId":"9476","inReplyTo":"alpine.LFD.0.999.0708101216000.30176@woody.linux-foundation.org","subject":"[PATCH 3/2] Optimize the two-way merge of git-read-tree too","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-10T19:31:20Z","receivedAt":"2007-08-10T19:31:20Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis trivially optimizes the two-way merge case of git-read-tree too, \nwhich affects switching branches.\n\nWhen you have tons and tons of files in your repository, but there are \nonly small differences in the branches (maybe just a couple of files \nchanged), the biggest cost of the branch switching was actually just the \nindex calculations.\n\nThis fixes it (timings for switching between the \"testing\" and \"master\" \nbranches in the 100,000 file testing-repo-from-hell, where the branches \nonly differ in one small file).\n\nBefore:\n\t[torvalds@woody bummer]$ time git checkout master\n\treal    0m9.919s\n\tuser    0m8.461s\n\tsys     0m0.264s\n\nAfter:\n\t[torvalds@woody bummer]$ time git checkout testing\n\treal    0m0.576s\n\tuser    0m0.348s\n\tsys     0m0.228s\n\nso it's easily an order of magnitude different.\n\nThis concludes the series. I think we could/should do the three-way merge \ntoo (to speed up merges), but I'm lazy. Somebody else can do it.\n\nThe rule is very simple: you need to remove the old entry if:\n - you want to remove the file entirely\n - you replace it with a \"merge conflict\" entry (ie a non-stage-0 entry)\n\nand you can avoid removing it if you either\n\n - keep the old one\n - or resolve it to a new one.\n\nand these rules should all be valid for the three-way case too.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\ncommit b8d8d6aa12a3ae7e2f7a8cb008413b780e1152ce\nAuthor: Linus Torvalds <torvalds@linux-foundation.org>\nDate:   Fri Aug 10 12:13:41 2007 -0700\n\n    Optimize the common cases of git-read-tree\n    \n    This optimizes bind_merge() and oneway_merge() to not unnecessarily\n    remove and re-add the old index entries when they can just get replaced\n    by updated ones.\n    \n    This makes these operations much faster for large trees (where \"large\"\n    is in the 50,000+ file range), because we don't unnecessarily move index\n    entries around in the index array all the time.\n    \n    Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n unpack-trees.c |    7 ++++---\n 1 files changed, 4 insertions(+), 3 deletions(-)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex b4e2618..810816e 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -827,7 +827,6 @@ int twoway_merge(struct cache_entry **src,\n \tstruct cache_entry *oldtree = src[1];\n \tstruct cache_entry *newtree = src[2];\n \n-\tremove_entry(remove);\n \tif (o->merge_size != 2)\n \t\treturn error(\"Cannot do a twoway merge of %d trees\",\n \t\t\t     o->merge_size);\n@@ -850,6 +849,7 @@ int twoway_merge(struct cache_entry **src,\n \t\t}\n \t\telse if (oldtree && !newtree && same(current, oldtree)) {\n \t\t\t/* 10 or 11 */\n+\t\t\tremove_entry(remove);\n \t\t\treturn deleted_entry(oldtree, current, o);\n \t\t}\n \t\telse if (oldtree && newtree &&\n@@ -859,6 +859,7 @@ int twoway_merge(struct cache_entry **src,\n \t\t}\n \t\telse {\n \t\t\t/* all other failures */\n+\t\t\tremove_entry(remove);\n \t\t\tif (oldtree)\n \t\t\t\treject_merge(oldtree);\n \t\t\tif (current)\n@@ -870,8 +871,8 @@ int twoway_merge(struct cache_entry **src,\n \t}\n \telse if (newtree)\n \t\treturn merged_entry(newtree, current, o);\n-\telse\n-\t\treturn deleted_entry(oldtree, current, o);\n+\tremove_entry(remove);\n+\treturn deleted_entry(oldtree, current, o);\n }\n \n /*\n"},{"id":"50443","messageId":"alpine.LFD.0.999.0708101240200.30176@woody.linux-foundation.org","threadId":"9476","inReplyTo":"alpine.LFD.0.999.0708101224110.30176@woody.linux-foundation.org","subject":"Re: [PATCH 3/2] Optimize the two-way merge of git-read-tree too","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-10T19:53:51Z","receivedAt":"2007-08-10T19:53:51Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nOn Fri, 10 Aug 2007, Linus Torvalds wrote:\n> \n> This trivially optimizes the two-way merge case of git-read-tree too, \n> which affects switching branches.\n\nSide note, if this wasn't obvious: this series of three patches (four, if \nyou count the one in this email) obviates the need for Junio's hacky fix \nfrom yesterday that removed the \"-i -m\" flags from \"git read-tree\" in \ngit-commit.sh, and made builtin-read-tree sometimes use the \"read_tree()\" \nfunction.\n\nNow \"unpack_trees()\" is just fast enough that we don't need to avoid it \n(although it's probably still a good idea to eventually convert it to use \nthe traverse_trees() infrastructure some day - just to avoid having \nextraneous tree traversal functions).\n\nAnd as mentioned, the three-way case *should* be as trivial as the \nfollowing. It passes all the tests, and I verified that a conflicting \nmerge in the 100,000 file horror-case merged correctly (with the conflict \nmarkers) in 0.687 seconds with this, so it works, but I'm lazy and \nsomebody else should double-check it.\n\n(Again - *without* this patch, the merge took 8.355 seconds, so this patch \nreally does make a huge difference for merge performance with lots and \nlots of files, and we're not talking percentages, we're talking \norders-of-magnitude differences!)\n\n\t\tLinus\n\n---\n unpack-trees.c |    7 +++++--\n 1 files changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 810816e..ccfeb6e 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -667,7 +667,6 @@ int threeway_merge(struct cache_entry **stages,\n \tint no_anc_exists = 1;\n \tint i;\n \n-\tremove_entry(remove);\t\t\n \tfor (i = 1; i < o->head_idx; i++) {\n \t\tif (!stages[i] || stages[i] == o->df_conflict_entry)\n \t\t\tany_anc_missing = 1;\n@@ -730,8 +729,10 @@ int threeway_merge(struct cache_entry **stages,\n \t}\n \n \t/* #1 */\n-\tif (!head && !remote && any_anc_missing)\n+\tif (!head && !remote && any_anc_missing) {\n+\t\tremove_entry(remove);\n \t\treturn 0;\n+\t}\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@@ -763,6 +764,7 @@ int threeway_merge(struct cache_entry **stages,\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\tremove_entry(remove);\n \t\t\tif (index)\n \t\t\t\treturn deleted_entry(index, index, o);\n \t\t\telse if (ce && !head_deleted)\n@@ -785,6 +787,7 @@ int threeway_merge(struct cache_entry **stages,\n \t\tverify_uptodate(index, o);\n \t}\n \n+\tremove_entry(remove);\n \to->nontrivial_merge = 1;\n \n \t/* #2, #3, #4, #6, #7, #9, #10, #11. */\n"},{"id":"50459","messageId":"7v8x8ipqa6.fsf@assigned-by-dhcp.cox.net","threadId":"9476","inReplyTo":"alpine.LFD.0.999.0708101240200.30176@woody.linux-foundation.org","subject":"Re: [PATCH 3/2] Optimize the two-way merge of git-read-tree too","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-11T05:57:05Z","receivedAt":"2007-08-11T05:57:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Looks obvious, mostly thanks to the clean rule that you outlined\nin [PATCH 2/2] description.\n\nThanks.\n"},{"id":"50466","messageId":"7vtzr6mnvw.fsf@assigned-by-dhcp.cox.net","threadId":"9476","inReplyTo":"alpine.LFD.0.999.0708101240200.30176@woody.linux-foundation.org","subject":"Re: [PATCH 3/2] Optimize the two-way merge of git-read-tree too","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-11T09:17:07Z","receivedAt":"2007-08-11T09:17:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> And as mentioned, the three-way case *should* be as trivial as the \n> following. It passes all the tests, and I verified that a conflicting \n> merge in the 100,000 file horror-case merged correctly (with the conflict \n> markers) in 0.687 seconds with this, so it works, but I'm lazy and \n> somebody else should double-check it.\n>\n> (Again - *without* this patch, the merge took 8.355 seconds, so this patch \n> really does make a huge difference for merge performance with lots and \n> lots of files, and we're not talking percentages, we're talking \n> orders-of-magnitude differences!)\n\nHmph, this might make what I was hoping to find time to do more\nor less unnecessary.\n\nBut here it is anyway.\n\nI wanted to speed up the three-way merges.  The assumption is\nthat when you do a merge, you are not in the middle of your own\nmessy work.  It is either while you are in a merge binge,\npulling from one subsystem lieutenant after another, or perhaps\napplying patchbombs from people.  In either case, you would\nstart your merge with a clean index that >99% matches the HEAD,\nafter writing your index out as a tree.\n\nThen, the new 3-way read-tree (or unpack_trees) would go like\nthis.\n\nFirst, we scan the index and find locally modified paths;\ninvalidate cache-tree by calling cache_tree_invalidate_path()\nfor such paths.  The expectation is that you will still have\nlargely usable cache-tree after this step.\n\nThe main part of the merge will be done by using tree_desc based\ntraversal that walks over three (ancestor, mine and theirs)\ntrees, instead of the current unpack_trees() that iterates\nmainly over the index entries.\n\n(A) The three trees all may have a subtree at the same path, or\n    the one that does not have a tree where others have does not\n    have a blob at the path either (i.e. the subtree is missing\n    from the tree without a D/F conflict).  If the usual 3-way\n    tree level merge rule (one side changes while the other side\n    does not do anything, or both sides change to the same) can\n    be applied, and if the cache tree entry for that subtree is\n    valid and matches our tree, then...\n\n    - we know the working tree for that entire subdirectory is\n      also clean because of the earlier invalidation;\n\n    - we can simply follow the tree level merge without ever\n      looking at individual paths contained in the subtree.\n\n(B) If the precondition of (A) does not hold, we recurse into\n    the subtree, and perform per-path 3-way merge, like the\n    current unpack_trees() does.\n\nIf your merge does not involve anything in large subdirectories,\ne.g., include/, arch/, or drivers/, this would allow you to skip\nquite a lot of per-path merge computation by doing comparison of\nfour (tree entries and cache-tree) tree object names (the three\nsubdirectories have about 6k paths each, so this could be a huge\nwin).\n\nAnother optimization I was hoping to do was \"git diff --cached\",\nwhich is unrelated to the recent change to use read_tree().\nInstead of reading the tree into the stage #1 of the same index,\nwe could walk the tree and skip the subtree whose cache-tree\nmatches the entry from the tree.  This would have the same scale\nof performance improvement opportunity.\n"},{"id":"50486","messageId":"alpine.LFD.0.999.0708111014210.30176@woody.linux-foundation.org","threadId":"9476","inReplyTo":"7vtzr6mnvw.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 3/2] Optimize the two-way merge of git-read-tree too","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-11T17:27:10Z","receivedAt":"2007-08-11T17:27:10Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 11 Aug 2007, Junio C Hamano wrote:\n> \n> Then, the new 3-way read-tree (or unpack_trees) would go like\n> this.\n> \n> First, we scan the index and find locally modified paths;\n> invalidate cache-tree by calling cache_tree_invalidate_path()\n> for such paths.  The expectation is that you will still have\n> largely usable cache-tree after this step.\n> \n> The main part of the merge will be done by using tree_desc based\n> traversal that walks over three (ancestor, mine and theirs)\n> trees, instead of the current unpack_trees() that iterates\n> mainly over the index entries.\n> \n> (A) The three trees all may have a subtree at the same path, or\n>     the one that does not have a tree where others have does not\n>     have a blob at the path either (i.e. the subtree is missing\n>     from the tree without a D/F conflict).  If the usual 3-way\n>     tree level merge rule (one side changes while the other side\n>     does not do anything, or both sides change to the same) can\n>     be applied, and if the cache tree entry for that subtree is\n>     valid and matches our tree, then...\n> \n>     - we know the working tree for that entire subdirectory is\n>       also clean because of the earlier invalidation;\n> \n>     - we can simply follow the tree level merge without ever\n>       looking at individual paths contained in the subtree.\n> \n> (B) If the precondition of (A) does not hold, we recurse into\n>     the subtree, and perform per-path 3-way merge, like the\n>     current unpack_trees() does.\n\nI'd love to see this, because it would likely speed up merging of really \nbig trees by a huge amount, and because I think it's fundamentally the \n\"right thing(tm)\" to do.\n\nThat said, right now we do so well that it's almost not interesting. The \nkernel tree is so small as to merge in basically zero time even when you \ndo per-file merges, and generatign the diffstat is almost always the \nbiggest component of the merge by far.\n\nBut yes, for bigger trees, and just because it's the right thing to do \nconsidering the data structures we have, we really should plan on doing \nthat some day. I think that with the current optimizations (and at least \nwith current hardware - old hw might change the equation), based on my \ntimings on the \"bummer\" tree, are fine at _least_ to 100,000 files. But if \nwe're talking about slower hardware, or many more files than that, we \nshould _definitely_ eventually do the tree-based optimizations.\n\n> Another optimization I was hoping to do was \"git diff --cached\",\n> which is unrelated to the recent change to use read_tree().\n\nYeah. \"git diff\" is just about the most performance-critical one. That \nsaid, the \"--cached\" case is likely the least used one, and any time you \ndon't use that, you end up having to lstat() the files anyway, so you \ncannot do the tree-based optimizations ;^p\n\nBut it would help \"git status\", I think (which needs to do both --cached \nand the normal one).\n\n\t\tLinus\n"}]}