{"thread":{"id":"7186","subject":"[PATCH 0/3] fast-import slow on large directories","startedAt":"2007-03-10T19:15:15Z","lastAt":"2007-03-12T19:16:39Z","messageCount":15,"participants":["Jeff King","Shawn O. Pearce"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"36756","messageId":"20070310191515.GA3416@coredump.intra.peff.net","threadId":"7186","inReplyTo":null,"subject":"[PATCH 0/3] fast-import slow on large directories","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-03-10T19:15:15Z","receivedAt":"2007-03-10T19:15:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The short story:\n\nI wanted to import into git a dataset consisting of a single directory\nwith 300,000 files. I tried using git-fast-import, but it wasn't able to\nhandle the large directory size. This patchset optimizes the algorithms\nused for tree handling, and I get orders of magnitude improvements in\nmemory and CPU consumption.\n\nThe patches are (see commit messages for more explanation):\n\n 1. grow tree storage more aggressively\n 2. code rearranging to make patch 3 easier to read\n 3. keep tree entries sorted and use binary instead of linear searches\n\nThe long story, with numbers:\n\nOriginally I just tried git-fast-import from 'next'. It built the pack\nfile (about 65M) from the blobs after a few minutes, and then while\nbuilding the commit, consumed all system memory (about 1G) and crashed.\nThe culprit was the constant increase in allocation as the tree size\ngrew, coupled with failure to pass allocated pool memory back to the OS.\nPatch 1 doubles the allocated size each time we run out of space.\n\nWith patch 1, the memory usage was much more reasonable (it ends up\nusing about 46M). However, the process still ran for over an hour before\nI killed it (bear in mind that doing deltas on all of the blobs takes\nabout 5 minutes). The culprit this time was the linear search through\nthe tree entries looking to see if each 'M' line was a new entry or an\nupdate. Patch 3 turns this into a binary search.\n\nTo do some testing, I cut my original dataset down to 20,000 entries,\nwhich I could feasibly do with the stock git-fast-import. Here are the\nnumbers:\n\nFor reference, just adding the blobs using stock git-fast-import without\nmaking a commit (the memory report is the \"Memory total\" from gfi):\nmem: 2673 KiB\n5.86user 3.67system 0:09.57elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+405366minor)pagefaults 0swaps\n\nNow here's stock git-fast-import making the commit (note the memory)\nmem: 101992 KiB\n37.07user 4.15system 0:41.55elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+430469minor)pagefaults 0swaps\n\nNow here's with just patch 1 (better memory, but still slow):\nmem: 3688 KiB\n30.00user 3.73system 0:34.80elapsed 96%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+406064minor)pagefaults 0swaps\n\nAnd with patches 1, 2, and 3:\nmem: 3688 KiB\n6.08user 3.71system 0:10.10elapsed 96%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+406064minor)pagefaults 0swaps\n\nAnd my final 300,000 item dataset with patches 1, 2, and 3:\nmem: 46378 KiB\n414.17user 69.82system 8:11.92elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+7730960minor)pagefaults 0swaps\n\n\nYes, this dataset is pathological. But I suspect the speed improvements\nwill help even modest projects a little, and almost certainly not hurt\n(the aggressive memory growth will probably waste a bit more memory).\n\n-Peff\n"},{"id":"36757","messageId":"20070310191648.GA3596@coredump.intra.peff.net","threadId":"7186","inReplyTo":"20070310191515.GA3416@coredump.intra.peff.net","subject":"[PATCH 1/3] fast-import: grow tree storage more aggressively","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-03-10T19:16:48Z","receivedAt":"2007-03-10T19:16:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When building up a tree for a commit, fast-import\ndynamically allocates memory for the tree entries. When more\nspace is needed, the allocated memory is increased by a\nconstant amount. For very large trees, this means\nre-allocating and memcpy()ing the memory O(n) times.\n\nTo compound this problem, releasing the previous tree\nresource does not free the memory; it is kept in a pool\nfor future trees. This means that each of the O(n)\nallocations will consume increasing amounts of memory,\ngiving O(n^2) memory consumption.\n\nSigned-off-by: Jeff King \n---\n fast-import.c | 4 ++--\n 1 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex fda5018..81bc6ea 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1058,7 +1058,7 @@ static void load_tree(struct tree_entry *root)\n \t\tstruct tree_entry *e = new_tree_entry();\n \n \t\tif (t->entry_count == t->entry_capacity)\n-\t\t\troot->tree = t = grow_tree_content(t, 8);\n+\t\t\troot->tree = t = grow_tree_content(t, t->entry_count);\n \t\tt->entries[t->entry_count++] = e;\n \n \t\te->tree = NULL;\n@@ -1225,7 +1225,7 @@ static int tree_content_set(\n \t}\n \n \tif (t->entry_count == t->entry_capacity)\n-\t\troot->tree = t = grow_tree_content(t, 8);\n+\t\troot->tree = t = grow_tree_content(t, t->entry_count);\n \te = new_tree_entry();\n \te->name = to_atom(p, (unsigned short)n);\n \te->versions[0].mode = 0;\n-- \n1.5.0.3.931.g55c05\n"},{"id":"36758","messageId":"20070310192114.GA3875@coredump.intra.peff.net","threadId":"7186","inReplyTo":"20070310191515.GA3416@coredump.intra.peff.net","subject":"[PATCH 2/3] fast-import: tree allocation cleanups","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-03-10T19:21:14Z","receivedAt":"2007-03-10T19:21:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"These cleanups are in preparation for improving the\nefficiency of the tree-construction code. There should be no\nfunctionality changes.\n\n1. Insert entries into tree_content _after_ they have a name\n assigned. This means that the insertion can use a smarter\n data structure than an unordered list.\n\n2. Factor out the linear search for existing tree entries in\n tree_content_set, which will make it simpler to change.\n Most of the line changes here are simply indentation changes.\n\nSigned-off-by: Jeff King \n---\n fast-import.c | 65 +++++++++++++++++++++++++++++++++-----------------------\n 1 files changed, 38 insertions(+), 27 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 81bc6ea..ac14a5a 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -594,6 +594,15 @@ static struct tree_content *grow_tree_content(\n \treturn r;\n }\n \n+static int find_tree_entry(struct tree_content *t, struct atom_str *s)\n+{\n+\tint i;\n+\tfor (i = 0; i < t->entry_count; i++)\n+\t\tif (!strcmp(t->entries[i]->name->str_dat, s->str_dat))\n+\t\t\treturn i;\n+\treturn -1;\n+}\n+\n static struct tree_entry *new_tree_entry(void)\n {\n \tstruct tree_entry *e;\n@@ -1059,7 +1068,6 @@ static void load_tree(struct tree_entry *root)\n \n \t\tif (t->entry_count == t->entry_capacity)\n \t\t\troot->tree = t = grow_tree_content(t, t->entry_count);\n-\t\tt->entries[t->entry_count++] = e;\n \n \t\te->tree = NULL;\n \t\tc = get_mode(c, &e->versions[1].mode);\n@@ -1071,6 +1079,8 @@ static void load_tree(struct tree_entry *root)\n \t\thashcpy(e->versions[0].sha1, (unsigned char*)c);\n \t\thashcpy(e->versions[1].sha1, (unsigned char*)c);\n \t\tc += 20;\n+\n+\t\tt->entries[t->entry_count++] = e;\n \t}\n \tfree(buf);\n }\n@@ -1187,6 +1197,7 @@ static int tree_content_set(\n \tconst char *slash1;\n \tunsigned int i, n;\n \tstruct tree_entry *e;\n+\tstruct atom_str *name;\n \n \tslash1 = strchr(p, '/');\n \tif (slash1)\n@@ -1194,40 +1205,40 @@ static int tree_content_set(\n \telse\n \t\tn = strlen(p);\n \n-\tfor (i = 0; i < t->entry_count; i++) {\n+\tname = to_atom(p, n);\n+\ti = find_tree_entry(t, name);\n+\tif (i != -1) {\n \t\te = t->entries[i];\n-\t\tif (e->name->str_len == n && !strncmp(p, e->name->str_dat, n)) {\n-\t\t\tif (!slash1) {\n-\t\t\t\tif (e->versions[1].mode == mode\n-\t\t\t\t\t\t&& !hashcmp(e->versions[1].sha1, sha1))\n-\t\t\t\t\treturn 0;\n-\t\t\t\te->versions[1].mode = mode;\n-\t\t\t\thashcpy(e->versions[1].sha1, sha1);\n-\t\t\t\tif (e->tree) {\n-\t\t\t\t\trelease_tree_content_recursive(e->tree);\n-\t\t\t\t\te->tree = NULL;\n-\t\t\t\t}\n-\t\t\t\thashclr(root->versions[1].sha1);\n-\t\t\t\treturn 1;\n-\t\t\t}\n-\t\t\tif (!S_ISDIR(e->versions[1].mode)) {\n-\t\t\t\te->tree = new_tree_content(8);\n-\t\t\t\te->versions[1].mode = S_IFDIR;\n-\t\t\t}\n-\t\t\tif (!e->tree)\n-\t\t\t\tload_tree(e);\n-\t\t\tif (tree_content_set(e, slash1 + 1, sha1, mode)) {\n-\t\t\t\thashclr(root->versions[1].sha1);\n-\t\t\t\treturn 1;\n+\t\tif (!slash1) {\n+\t\t\tif (e->versions[1].mode == mode\n+\t\t\t\t\t&& !hashcmp(e->versions[1].sha1, sha1))\n+\t\t\t\treturn 0;\n+\t\t\te->versions[1].mode = mode;\n+\t\t\thashcpy(e->versions[1].sha1, sha1);\n+\t\t\tif (e->tree) {\n+\t\t\t\trelease_tree_content_recursive(e->tree);\n+\t\t\t\te->tree = NULL;\n \t\t\t}\n-\t\t\treturn 0;\n+\t\t\thashclr(root->versions[1].sha1);\n+\t\t\treturn 1;\n+\t\t}\n+\t\tif (!S_ISDIR(e->versions[1].mode)) {\n+\t\t\te->tree = new_tree_content(8);\n+\t\t\te->versions[1].mode = S_IFDIR;\n+\t\t}\n+\t\tif (!e->tree)\n+\t\t\tload_tree(e);\n+\t\tif (tree_content_set(e, slash1 + 1, sha1, mode)) {\n+\t\t\thashclr(root->versions[1].sha1);\n+\t\t\treturn 1;\n \t\t}\n+\t\treturn 0;\n \t}\n \n \tif (t->entry_count == t->entry_capacity)\n \t\troot->tree = t = grow_tree_content(t, t->entry_count);\n \te = new_tree_entry();\n-\te->name = to_atom(p, (unsigned short)n);\n+\te->name = name;\n \te->versions[0].mode = 0;\n \thashclr(e->versions[0].sha1);\n \tt->entries[t->entry_count++] = e;\n-- \n1.5.0.3.931.g55c05\n"},{"id":"36759","messageId":"20070310192131.GB3875@coredump.intra.peff.net","threadId":"7186","inReplyTo":"20070310191515.GA3416@coredump.intra.peff.net","subject":"[PATCH 3/3] fast-import: improve efficiency of tree_content_set","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-03-10T19:21:31Z","receivedAt":"2007-03-10T19:21:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This patch keeps the tree entries of a tree_content in\norder, sorted by entry name. The lookup in find_tree_entry\nnow performs a binary search instead of a linear search.\n\nSigned-off-by: Jeff King \n---\n fast-import.c | 48 +++++++++++++++++++++++++++++++++++++++++-------\n 1 files changed, 41 insertions(+), 7 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex ac14a5a..4cd01ee 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -594,13 +594,47 @@ static struct tree_content *grow_tree_content(\n \treturn r;\n }\n \n+static int find_tree_entry_bsearch(struct tree_content *t,\n+\t\t\t\t struct atom_str *s,\n+\t\t\t\t int *found)\n+{\n+\tint high, low, mid=0, cmp=-1;\n+\tlow = 0;\n+\thigh = t->entry_count - 1;\n+\twhile (low <= high) {\n+\t\tmid = low + ((high - low) / 2);\n+\t\tcmp = strcmp(s->str_dat, t->entries[mid]->name->str_dat);\n+\t\tif (cmp < 0)\n+\t\t\thigh = mid - 1;\n+\t\telse if (cmp > 0)\n+\t\t\tlow = mid + 1;\n+\t\telse {\n+\t\t\t*found = 1;\n+\t\t\treturn mid;\n+\t\t}\n+\t}\n+\t*found = 0;\n+\treturn cmp < 0 ? mid : mid + 1;\n+}\n+\n static int find_tree_entry(struct tree_content *t, struct atom_str *s)\n {\n-\tint i;\n-\tfor (i = 0; i < t->entry_count; i++)\n-\t\tif (!strcmp(t->entries[i]->name->str_dat, s->str_dat))\n-\t\t\treturn i;\n-\treturn -1;\n+\tint i, found;\n+\ti = find_tree_entry_bsearch(t, s, &found);\n+\treturn found ? i : -1;\n+}\n+\n+static void insert_tree_content(struct tree_content *t, struct tree_entry *e)\n+{\n+\tint i, found;\n+\n+\ti = find_tree_entry_bsearch(t, e->name, &found);\n+\tif (found)\n+\t\tdie(\"BUG: duplicate tree content\");\n+\tmemmove(t->entries + i + 1, t->entries + i,\n+\t\t\tsizeof(t->entries[0]) * (t->entry_count - i));\n+\tt->entries[i] = e;\n+\tt->entry_count++;\n }\n \n static struct tree_entry *new_tree_entry(void)\n@@ -1080,7 +1114,7 @@ static void load_tree(struct tree_entry *root)\n \t\thashcpy(e->versions[1].sha1, (unsigned char*)c);\n \t\tc += 20;\n \n-\t\tt->entries[t->entry_count++] = e;\n+\t\tinsert_tree_content(t, e);\n \t}\n \tfree(buf);\n }\n@@ -1241,7 +1275,7 @@ static int tree_content_set(\n \te->name = name;\n \te->versions[0].mode = 0;\n \thashclr(e->versions[0].sha1);\n-\tt->entries[t->entry_count++] = e;\n+\tinsert_tree_content(t, e);\n \tif (slash1) {\n \t\te->tree = new_tree_content(8);\n \t\te->versions[1].mode = S_IFDIR;\n-- \n1.5.0.3.931.g55c05\n"},{"id":"36760","messageId":"20070310192304.GB3416@coredump.intra.peff.net","threadId":"7186","inReplyTo":"20070310192131.GB3875@coredump.intra.peff.net","subject":"Re: [PATCH 3/3] fast-import: improve efficiency of tree_content_set","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-03-10T19:23:04Z","receivedAt":"2007-03-10T19:23:04Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Mar 10, 2007 at 02:21:31PM -0500, Jeff King wrote:\n\n> This patch keeps the tree entries of a tree_content in\n> order, sorted by entry name. The lookup in find_tree_entry\n> now performs a binary search instead of a linear search.\n\nI should note that this patch doesn't handle removing entries from\ntree_content structs; I will work up a patch for that momentarily.\n\n-Peff\n"},{"id":"36761","messageId":"20070310194012.GA5126@coredump.intra.peff.net","threadId":"7186","inReplyTo":"20070310192304.GB3416@coredump.intra.peff.net","subject":"[PATCH] fast-import: use binary search in tree_content_remove","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-03-10T19:40:13Z","receivedAt":"2007-03-10T19:40:13Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"\nSigned-off-by: Jeff King \n---\n> I should note that this patch doesn't handle removing entries from\n> tree_content structs; I will work up a patch for that momentarily.\n\nAnd here it is. However, I should note that this patch is _not_\nnecessary. I had originally thought that removal might destroy the\nsorting that I added in the last patch, but it looks like the entry\nisn't actually removed. Shawn, can you sanity check this?\n\nThis patch still has value, though, because it improves performance when\ndeleting entries from a large tree (I just didn't do that in my test\ncase, so it wasn't a problem before).\n\n fast-import.c | 33 +++++++++++++++++----------------\n 1 files changed, 17 insertions(+), 16 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 4cd01ee..4322216 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1295,6 +1295,7 @@ static int tree_content_remove(struct tree_entry *root, const char *p)\n \tconst char *slash1;\n \tunsigned int i, n;\n \tstruct tree_entry *e;\n+\tstruct atom_str *name;\n \n \tslash1 = strchr(p, '/');\n \tif (slash1)\n@@ -1302,24 +1303,24 @@ static int tree_content_remove(struct tree_entry *root, const char *p)\n \telse\n \t\tn = strlen(p);\n \n-\tfor (i = 0; i < t->entry_count; i++) {\n-\t\te = t->entries[i];\n-\t\tif (e->name->str_len == n && !strncmp(p, e->name->str_dat, n)) {\n-\t\t\tif (!slash1 || !S_ISDIR(e->versions[1].mode))\n-\t\t\t\tgoto del_entry;\n-\t\t\tif (!e->tree)\n-\t\t\t\tload_tree(e);\n-\t\t\tif (tree_content_remove(e, slash1 + 1)) {\n-\t\t\t\tfor (n = 0; n < e->tree->entry_count; n++) {\n-\t\t\t\t\tif (e->tree->entries[n]->versions[1].mode) {\n-\t\t\t\t\t\thashclr(root->versions[1].sha1);\n-\t\t\t\t\t\treturn 1;\n-\t\t\t\t\t}\n-\t\t\t\t}\n-\t\t\t\tgoto del_entry;\n+\tname = to_atom(p, n);\n+\ti = find_tree_entry(t, name);\n+\tif(i == -1)\n+\t\treturn 0;\n+\te = t->entries[i];\n+\n+\tif (!slash1 || !S_ISDIR(e->versions[1].mode))\n+\t\tgoto del_entry;\n+\tif (!e->tree)\n+\t\tload_tree(e);\n+\tif (tree_content_remove(e, slash1 + 1)) {\n+\t\tfor (n = 0; n < e->tree->entry_count; n++) {\n+\t\t\tif (e->tree->entries[n]->versions[1].mode) {\n+\t\t\t\thashclr(root->versions[1].sha1);\n+\t\t\t\treturn 1;\n \t\t\t}\n-\t\t\treturn 0;\n \t\t}\n+\t\tgoto del_entry;\n \t}\n \treturn 0;\n \n-- \n1.5.0.3.931.g55c05\n"},{"id":"36779","messageId":"20070311032147.GA10781@spearce.org","threadId":"7186","inReplyTo":"20070310192114.GA3875@coredump.intra.peff.net","subject":"Re: [PATCH 2/3] fast-import: tree allocation cleanups","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-11T03:21:47Z","receivedAt":"2007-03-11T03:21:47Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"A nicely done series. Thanks for fixing this performance bug.\n\nJeff King wrote:\n> @@ -1059,7 +1068,6 @@ static void load_tree(struct tree_entry *root)\n> \n> \t\tif (t->entry_count == t->entry_capacity)\n> \t\t\troot->tree = t = grow_tree_content(t, t->entry_count);\n> -\t\tt->entries[t->entry_count++] = e;\n> \n> \t\te->tree = NULL;\n> \t\tc = get_mode(c, &e->versions[1].mode);\n> @@ -1071,6 +1079,8 @@ static void load_tree(struct tree_entry *root)\n> \t\thashcpy(e->versions[0].sha1, (unsigned char*)c);\n> \t\thashcpy(e->versions[1].sha1, (unsigned char*)c);\n> \t\tc += 20;\n> +\n> +\t\tt->entries[t->entry_count++] = e;\n> \t}\n> \tfree(buf);\n> }\n\nThis I wouldn't have bothered to do in this patch. It is just\nunecessary code churning, as you turn around and change this again\nin the next patch. I actually dropped these two hunks from this\npatch (but left the dang commit message comment in, whoops) and\nmoved the first hunk to the next patch.\n\n> @@ -1194,40 +1205,40 @@ static int tree_content_set(\n> \telse\n> \t\tn = strlen(p);\n> \n> -\tfor (i = 0; i < t->entry_count; i++) {\n> +\tname = to_atom(p, n);\n\nYou missed an unsigned short cast here.\n\n> -\te->name = to_atom(p, (unsigned short)n);\n> +\te->name = name;\n\nSee? ;-) I put the correct cast into the patch when I applied it.\n\n\nYour series is applied on top of master and is now in my\nfast-import.git fork on repo.or.cz.\n\n-- \nShawn.\n"},{"id":"36780","messageId":"20070311033833.GB10781@spearce.org","threadId":"7186","inReplyTo":"20070310194012.GA5126@coredump.intra.peff.net","subject":"Re: [PATCH] fast-import: use binary search in tree_content_remove","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-11T03:38:33Z","receivedAt":"2007-03-11T03:38:33Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jeff King wrote:\n> And here it is. However, I should note that this patch is _not_\n> necessary.\n\nWell, its not necessary for you, as you aren't trying to remove\nsomething from your huge tree. ;-)\n\n> I had originally thought that removal might destroy the\n> sorting that I added in the last patch, but it looks like the entry\n> isn't actually removed. Shawn, can you sanity check this?\n\nYour patch is fine. fast-import takes an \"optimization\" here and\ndoes not bother to actually delete entries from a tree until *after*\nwe have written the tree data out to the packfile. The reason\nis we need to retain the version 0 tree entry objects to recreate\nthe delta base. Since these are combined with the version 1 data\n(the \"new\" data) we have to delay the actual deletes until after\nwe store the tree and have its SHA-1.\n\nIt turns out however that your entire series was broken. I had to\ncommit the following on top of it to fix it:\n\n-->8--\nFrom 0af148553a94f7e856089fa68395524932240145 Mon Sep 17 00:00:00 2001\nFrom: Shawn O. Pearce \nDate: Sat, 10 Mar 2007 22:34:12 -0500\nSubject: [PATCH] fast-import: Brown paper bag fix tree sorting\n\nJeff King's recent changes to sort trees by strictly name (and binary\nsearch to locate an entry) works OK up until we have to write a\ntree out that uses the funny name/mode sorting that native Git uses:\n\n b.\n b/\n ba\n\nHere the subtree \"b\" must sort between files \"b.\" and \"ba\", but\nJeff's changes have it sorting before \"b.\". This means we would fail\nto find entries during future modifications to that tree as Jeff's\nbinary search algorithm won't find subtree \"b\" between b. and ba.\n\nI'm plastering over the problem by resorting a tree strictly by\nname after it has been written out and the deleted entries have\nbeen filtered out.\n\nSigned-off-by: Shawn O. Pearce \n---\n fast-import.c | 8 ++++++++\n 1 files changed, 8 insertions(+), 0 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 716819f..fa3b766 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -1136,6 +1136,13 @@ static int tecmp1 (const void *_a, const void *_b)\n \t\tb->name->str_dat, b->name->str_len, b->versions[1].mode);\n }\n \n+static int nmcmp (const void *_a, const void *_b)\n+{\n+\tstruct tree_entry *a = *((struct tree_entry**)_a);\n+\tstruct tree_entry *b = *((struct tree_entry**)_b);\n+\treturn strcmp(a->name->str_dat, b->name->str_dat);\n+}\n+\n static void mktree(struct tree_content *t,\n \tint v,\n \tunsigned long *szp,\n@@ -1218,6 +1225,7 @@ static void store_tree(struct tree_entry *root)\n \t\t}\n \t}\n \tt->entry_count -= del;\n+\tqsort(t->entries, t->entry_count, sizeof(t->entries[0]), nmcmp);\n }\n \n static int tree_content_set(\n-- \n1.5.0.3.942.g299f\n"},{"id":"36812","messageId":"20070311155138.GA7110@coredump.intra.peff.net","threadId":"7186","inReplyTo":"20070311032147.GA10781@spearce.org","subject":"Re: [PATCH 2/3] fast-import: tree allocation cleanups","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-03-11T15:51:38Z","receivedAt":"2007-03-11T15:51:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Mar 10, 2007 at 10:21:47PM -0500, Shawn O. Pearce wrote:\n\n> > +\n> > +\t\tt->entries[t->entry_count++] = e;\n> This I wouldn't have bothered to do in this patch. It is just\n> unecessary code churning, as you turn around and change this again\n> in the next patch. I actually dropped these two hunks from this\n> patch (but left the dang commit message comment in, whoops) and\n> moved the first hunk to the next patch.\n\nOK. There are actually two changes: moving the insertion until after\ne->name is set up (which has no functionality impact) and changing the\nmanner of insertion. I split them up to try to make them more readable,\nbut clearly you figured out what I was going for.\n\n> > +\tname = to_atom(p, n);\n> [...]\n> > -\te->name = to_atom(p, (unsigned short)n);\n> \n> You missed an unsigned short cast here.\n\nActually, I removed it intentionally (though clearly I should have\ndocumented it). It's casting from an unsigned int to an unsigned short.\nSuch a cast is at best pointless (since the compiler performs the exact\nsame cast implicitly -- see C99 6.5.2.2, paragraph 7), and at worst\nmasks an error (e.g., if the type of n is changed).\n\nIs there some subtle issue I'm missing here?\n\n-Peff\n"},{"id":"36814","messageId":"20070311155955.GA7586@coredump.intra.peff.net","threadId":"7186","inReplyTo":"20070311155138.GA7110@coredump.intra.peff.net","subject":"Re: [PATCH 2/3] fast-import: tree allocation cleanups","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-03-11T15:59:55Z","receivedAt":"2007-03-11T15:59:55Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Mar 11, 2007 at 11:51:38AM -0400, Jeff King wrote:\n\n> OK. There are actually two changes: moving the insertion until after\n> e->name is set up (which has no functionality impact) and changing the\n> manner of insertion. I split them up to try to make them more readable,\n> but clearly you figured out what I was going for.\n\nBTW, the commit message for your d4239be9 is now inaccurate (you moved\nthe hunk for my point \"1\" to the next patch). Probably not worth fixing,\nbut I thought I would mention it.\n\n-Peff\n"},{"id":"36820","messageId":"20070311163412.GB7110@coredump.intra.peff.net","threadId":"7186","inReplyTo":"20070311033833.GB10781@spearce.org","subject":"Re: [PATCH] fast-import: use binary search in tree_content_remove","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-03-11T16:34:13Z","receivedAt":"2007-03-11T16:34:13Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Mar 10, 2007 at 10:38:33PM -0500, Shawn O. Pearce wrote:\n\n> Well, its not necessary for you, as you aren't trying to remove\n> something from your huge tree. ;-)\n\nHeh, I meant necessary as in \"Oops, I probably just completely broke\nfast-import\". But I see I managed to do that anyway. :)\n\n> Your patch is fine. fast-import takes an \"optimization\" here and\n> does not bother to actually delete entries from a tree until *after*\n\nOK, that was my reading, as well; thanks for confirming.\n\n> Jeff King's recent changes to sort trees by strictly name (and binary\n> search to locate an entry) works OK up until we have to write a\n> tree out that uses the funny name/mode sorting that native Git uses:\n\nAnd here is a test that I believe triggers the problem (fails with my\npatches, succeeds with your fix):\n\ndiff --git a/t/t9300-fast-import.sh b/t/t9300-fast-import.sh\nindex 2e1a09f..2ec68b0 100755\n--- a/t/t9300-fast-import.sh\n+++ b/t/t9300-fast-import.sh\n@@ -501,4 +501,54 @@ test_expect_success \\\n 'test `git-rev-parse --verify branch^1` \\\n \t\t= `git-rev-parse --verify K^1`'\n \n+###\n+### series L\n+###\n+\n+cat >input < $GIT_COMMITTER_DATE\n+data < $GIT_COMMITTER_DATE\n+data <expect <output &&\n+\t diff -u expect output'\n+\n test_done\n\n> I'm plastering over the problem by resorting a tree strictly by\n> name after it has been written out and the deleted entries have\n> been filtered out.\n\nI wonder if we could make this a bit cleaner by actually using the git\nsort in the first place. I will take a look...\n\n-Peff\n"},{"id":"36821","messageId":"20070311165432.GA13555@coredump.intra.peff.net","threadId":"7186","inReplyTo":"20070311163412.GB7110@coredump.intra.peff.net","subject":"Re: [PATCH] fast-import: use binary search in tree_content_remove","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-03-11T16:54:32Z","receivedAt":"2007-03-11T16:54:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Mar 11, 2007 at 12:34:13PM -0400, Jeff King wrote:\n\n> > I'm plastering over the problem by resorting a tree strictly by\n> > name after it has been written out and the deleted entries have\n> > been filtered out.\n> I wonder if we could make this a bit cleaner by actually using the git\n> sort in the first place. I will take a look...\n\nHrm, it's not that hard to pass the mode around and use\nbase_name_compare, but I don't think that's enough. Any time we turn an\nentry into a tree, we'll have to resort. I think your patch is simpler\nand less error prone.\n\n-Peff\n"},{"id":"36851","messageId":"20070311201912.GA12457@spearce.org","threadId":"7186","inReplyTo":"20070311165432.GA13555@coredump.intra.peff.net","subject":"Re: [PATCH] fast-import: use binary search in tree_content_remove","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-11T20:19:12Z","receivedAt":"2007-03-11T20:19:12Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jeff King wrote:\n> On Sun, Mar 11, 2007 at 12:34:13PM -0400, Jeff King wrote:\n> \n> > > I'm plastering over the problem by resorting a tree strictly by\n> > > name after it has been written out and the deleted entries have\n> > > been filtered out.\n> > I wonder if we could make this a bit cleaner by actually using the git\n> > sort in the first place. I will take a look...\n> \n> Hrm, it's not that hard to pass the mode around and use\n> base_name_compare, but I don't think that's enough. Any time we turn an\n> entry into a tree, we'll have to resort. I think your patch is simpler\n> and less error prone.\n\nYes, but it gets worse. We delete an entry by setting the mode to\n0 in version 1, but leaving the entry in the tree so that the entry\nwill show up in version 0 during delta generation.\n\nSo what happens if we delete the tree entry, then modify it in\nthe same commit? We can't find it if we are searching with mode\nincluded.\n\nSidenote: I have the same sorting problems in jgit. It all comes\ndown to how annoying the tree format is, in that entries are sorted\nby both name and mode, but only name makes the entry be unique.\n\nRight now I'm not sure how to resolve this, short of the bandaid\npatch I put onto the end of your series. :-(\n\n-- \nShawn.\n"},{"id":"36938","messageId":"20070312191313.GC15887@spearce.org","threadId":"7186","inReplyTo":"20070311163412.GB7110@coredump.intra.peff.net","subject":"Re: [PATCH] fast-import: use binary search in tree_content_remove","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-12T19:13:13Z","receivedAt":"2007-03-12T19:13:13Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jeff King wrote:\n> And here is a test that I believe triggers the problem (fails with my\n> patches, succeeds with your fix):\n\nThanks, this is a good test to have. Since the current \"stable\"\nversion passes without your patches I'm applying the test first;\nthat way we can see if/when a change breaks this ordering requirement\nand address it immediately in that patch.\n \n> > I'm plastering over the problem by resorting a tree strictly by\n> > name after it has been written out and the deleted entries have\n> > been filtered out.\n> \n> I wonder if we could make this a bit cleaner by actually using the git\n> sort in the first place. I will take a look...\n\nGood luck. I'm not sure its easily done. Which is why I'm not\nattempting to do it right now.\n\n-- \nShawn.\n"},{"id":"36940","messageId":"20070312191639.GD15887@spearce.org","threadId":"7186","inReplyTo":"20070311155138.GA7110@coredump.intra.peff.net","subject":"Re: [PATCH 2/3] fast-import: tree allocation cleanups","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-12T19:16:39Z","receivedAt":"2007-03-12T19:16:39Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jeff King wrote:\n> On Sat, Mar 10, 2007 at 10:21:47PM -0500, Shawn O. Pearce wrote:\n> > > +\tname = to_atom(p, n);\n> > [...]\n> > > -\te->name = to_atom(p, (unsigned short)n);\n> > \n> > You missed an unsigned short cast here.\n> \n> Actually, I removed it intentionally (though clearly I should have\n> documented it). It's casting from an unsigned int to an unsigned short.\n> Such a cast is at best pointless (since the compiler performs the exact\n> same cast implicitly -- see C99 6.5.2.2, paragraph 7), and at worst\n> masks an error (e.g., if the type of n is changed).\n\nHmm. You are probably right. I had put that cast into place before\nbecause (if I recall correctly) I was getting compiler errors.\nBut today looking at it I'm not, even if I remove the casts. So uh,\nyea... they should probably come out.\n\n-- \nShawn.\n"}]}