{"thread":{"id":"9458","subject":"git and larger trees, not so fast?","startedAt":"2007-08-09T16:30:26Z","lastAt":"2007-08-23T00:30:46Z","messageCount":37,"participants":["moe","Linus Torvalds","Junio C Hamano","David Kastrup","Sean","Daniel Barkalow","Fernando J. Pereda"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"50329","messageId":"20070809163026.GD568@mbox.bz","threadId":"9458","inReplyTo":null,"subject":"git and larger trees, not so fast?","fromName":"moe","fromEmail":"moe-git@mbox.bz","sentAt":"2007-08-09T16:30:26Z","receivedAt":"2007-08-09T16:30:26Z","isPatch":false,"sender":{"key":"moe-git@mbox.bz","avatar":null},"body":"hi guys,\n\nearlier today i imported one of my larger trees\n(~70k files) into git and was quite disappointed\nby the performance.\n\ni made some tests on latest master branch\n(1.5.3.rc4.29.g74276) and it seems like git\nhits a wall somewhere above ~50k files.\n\ni'm seeing 'commit' timings of 30s and\nup as well as 'status' timings in the 10s\nballpark.\n\nhere's a test-case (should be safe to\ncopy/paste on linux, bash):\n\n#\n# first create a tree of roughly 100k files\n#\nmkdir bummer\ncd bummer\nfor ((i=0;i<100;i++)); do\nmkdir $i && pushd $i;\nfor ((j=0;j<1000;j++)); do\necho \"$j\" >$j; done; popd;\ndone\n\n#\n# init and add this to git\n#\ntime git init\ngit config user.email \"no@thx\"\ngit config user.name \"nothx\"\ntime git add .\ntime git commit -m 'buurrrrn' -a\n\n#\n# git-status, tunes in at around ~10s for me\n#\ntime git-status\ntime git-status\ntime git-status\n\n#\n# git-commit, takes a whopping 52s for me\n#\ndate >50/500\ntime git commit -m 'expose the turtle' 50/500\n\n\nregards,\nmoe\n"},{"id":"50332","messageId":"alpine.LFD.0.999.0708090948250.25146@woody.linux-foundation.org","threadId":"9458","inReplyTo":"20070809163026.GD568@mbox.bz","subject":"Re: git and larger trees, not so fast?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-09T17:11:16Z","receivedAt":"2007-08-09T17:11:16Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 9 Aug 2007, moe wrote:\n> \n> i made some tests on latest master branch\n> (1.5.3.rc4.29.g74276) and it seems like git\n> hits a wall somewhere above ~50k files.\n\nGood catch. Definitely not acceptable performance.\n\nWe seem to spend a lot of our time in memcpy:\n\n\tsamples  %        image name               app name                 symbol name\n\t200527   25.4551  libc-2.6.so              libc-2.6.so              _wordcopy_bwd_aligned\n\t104505   13.2660  libc-2.6.so              libc-2.6.so              _wordcopy_fwd_aligned\n\t99185    12.5907  libz.so.1.2.3            libz.so.1.2.3            (no symbols)\n\t83452    10.5935  libc-2.5.so              libc-2.5.so              (no symbols)\n\t54203     6.8806  git                      git                      assign_blame\n\t46153     5.8587  git                      git                      read_directory_recursive\n\t27665     3.5118  git                      git                      handle_split\n\t21385     2.7146  vmlinux                  vmlinux                  blk_complete_sgv4_hdr_rq\n\t20745     2.6334  git                      git                      read_packed_refs\n\t12709     1.6133  git                      git                      builtin_diffstat\n\t7829      0.9938  git                      git                      show_patch_diff\n\t...\n\nbut the silly thing is, this is only true if you give the filenames \nexplicitly!\n\nLookie here:\n\n\t[torvalds@woody bummer]$ date >50/500\n\t[torvalds@woody bummer]$ time git commit -a -m 'expose the turtle'\n\tCreated commit 25ca22d: expose the turtle\n\t 1 files changed, 1 insertions(+), 1 deletions(-)\n\t\n\treal    0m4.612s\n\tuser    0m4.224s\n\tsys     0m0.412s\n\n\t[torvalds@woody bummer]$ date >50/500\n\t[torvalds@woody bummer]$ time git commit -m 'expose the turtle' 50/500\n\tCreated commit 009f6b5: expose the turtle\n\t 1 files changed, 1 insertions(+), 1 deletions(-)\n\t\n\treal    0m12.464s\n\tuser    0m12.129s\n\tsys     0m0.336s\n\nie we take almost three times longer with explicitly naming the file, than \nwhen just using \"git commit -a\". Oops.\n\nThat said, even the 4.6 seconds is really not acceptable: this is on a \ngood 2.6GHz Core 2 Duo too, so on weaker hardware it would be quite \npainful.\n\nI haven't looked at *why* it's that slow, but it's not anything really \nfundamental, the basic operations are fast:\n\n\t[torvalds@woody bummer]$ time git add 50/500\n\n\treal    0m0.064s\n\tuser    0m0.048s\n\tsys     0m0.016s\n\n\t[torvalds@woody bummer]$ time git write-tree\n\t7480230419e510c93082a4a19e23d928a426973a\n\t\n\treal    0m0.069s\n\tuser    0m0.048s\n\tsys     0m0.024s\n\n\t[torvalds@woody bummer]$ time git diff\n\t\n\treal    0m0.127s\n\tuser    0m0.000s\n\tsys     0m0.000s\n\nso it's not the \"lstat()\" that we do on all files, or the write-tree \n(which are all O(n) in files, with a rather small constant), but some \nO(n**2) behaviour elsewhere.\n\nAnd all the expense seems to be in not the commit itself, but in\n\n\t[torvalds@woody bummer]$ time git 'runstatus' '--nocolor'\n\n\treal    0m4.208s\n\tuser    0m4.068s\n\tsys     0m0.140s\n\nand that thing seems to suck really really hard.\n\nDoing an ltrace on it shows tons and tons of:\n\n\t...\n\tstrlen(\"35\")\n\tstrlen(\"349\")\n\tcalloc(1, 72)\n\tmemcpy(0x73034e, \"10/\", 3)\n\tmemcpy(0x730351, \"349\", 4)\n\tmemmove(0x2ab637f41e80, 0x2ab637f41e78, 781768)\n\t...\n\nbut I haven't looked at where they come from yet.\n\n\t\tLinus\n"},{"id":"50333","messageId":"alpine.LFD.0.999.0708091015500.25146@woody.linux-foundation.org","threadId":"9458","inReplyTo":"alpine.LFD.0.999.0708090948250.25146@woody.linux-foundation.org","subject":"Re: git and larger trees, not so fast?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-09T17:38:53Z","receivedAt":"2007-08-09T17:38:53Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 9 Aug 2007, Linus Torvalds wrote:\n> \n> Doing an ltrace on it shows tons and tons of:\n> \n> \t...\n> \tstrlen(\"35\")\n> \tstrlen(\"349\")\n> \tcalloc(1, 72)\n> \tmemcpy(0x73034e, \"10/\", 3)\n> \tmemcpy(0x730351, \"349\", 4)\n> \tmemmove(0x2ab637f41e80, 0x2ab637f41e78, 781768)\n> \t...\n> \n> but I haven't looked at where they come from yet.\n\nOuch. It's the diffing between HEAD and the index, and it's all from \n\"add_index_entry()\", which sorts the index array using an insertion sort. \nSo when the index array gets large, that sort spends all its time in huge \nmemmove() calls.\n\nThe silly thing, of course, is that we don't even \"need\" to do that: both \nthe index and the trees are really sorted already, so we could just \ninterleave them. But since we read them separately, the thing just sucks.\n\nWe've fixed other similar cases of this we had (diffing trees against each \nother) by walking the trees together, but the \"index vs tree\" diff (and \nmerge) is the one remaining place where we still use the original stupid \nalgorithm. So you'll see this performance problem for \n\n - diff tree against index (\"git diff HEAD\"\n - merge tree into index (\"git read-tree -m HEAD\")\n\nwhich both do the stupid index/tree filling.\n\nSo this is all O(n**2), which is why we haven't reacted very much - it \ndoesn't show up nearly as much with the kernel. Also, with a smaller set \nof files, it would tends to fit in the L2 cache of most competent CPU's. \nSo not only is it n**2, you get the cache trashing behaviour too, and \nthat, I think, is what really causes it to fall off the cliff edge!\n\nGaah. This shouldn't be *that* hard to fix, but I'm not entirely sure I'll \nhave time today.\n\nDiffing the index against the tree *should* be instantaneous. It should be \nno more costly than reading the tree itself (which is 0.191 seconds for \nme: test \"git read-tree -m HEAD\" vs \"git read-tree HEAD\") and reading the \nindex (which is almost instantaneous - the only way I can test it is by \ndoing something like \"git update-index --refresh\", and that's 0.131 \nseconds, but that includes all the 100,000 \"lstat()\" calls).\n\nSo basically, we're spending several seconds just doing stupid \nmake-believe work and moving the index array around. Ouch.\n\nAnyway, the good news is that this is by no means fundamental. It's a \nsmall and stupid detail. The only thing that makes it at all painful is \nthat this is in some low-level crud that we haven't touched in *ages*, so \nI've long since swapped out all my recollection of how we do it.\n\n(We basically do:\n\n\tread_cache();\n\nfollowed by\n\n\tunpack_trees();\n\nand each of those *on*its*own* is pretty cheap, but when we unpack trees \ninto an already populated index, the end result is ugly.\n\n\t\t\tLinus\n"},{"id":"50334","messageId":"alpine.LFD.0.999.0708091051290.25146@woody.linux-foundation.org","threadId":"9458","inReplyTo":"alpine.LFD.0.999.0708090948250.25146@woody.linux-foundation.org","subject":"Re: git and larger trees, not so fast?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-09T17:54:38Z","receivedAt":"2007-08-09T17:54:38Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 9 Aug 2007, Linus Torvalds wrote:\n> \n> We seem to spend a lot of our time in memcpy:\n> \n> \tsamples  %        image name               app name                 symbol name\n> \t200527   25.4551  libc-2.6.so              libc-2.6.so              _wordcopy_bwd_aligned\n> \t104505   13.2660  libc-2.6.so              libc-2.6.so              _wordcopy_fwd_aligned\n\nSorry, that was a bogus trace with some old stuff in it.\n\nThe real profile was this one.\n\n\t102343   73.1377  libc-2.6.so              libc-2.6.so              _wordcopy_bwd_aligned\n\t3573      2.5534  git                      git                      cache_name_compare\n\t2328      1.6637  git                      git                      index_name_pos\n\t...\n\nwhich matches the rest of my emails.. (the \"73%\" is actually really \nsupposed to be about 95%, but I had X running and doing stuff at the same \ntime, so it was only 73% of all the other CPU activity that was going on \nover the time I profiled).\n\n\t\tLinus\n"},{"id":"50335","messageId":"7vr6mcy4dk.fsf@assigned-by-dhcp.cox.net","threadId":"9458","inReplyTo":"alpine.LFD.0.999.0708091015500.25146@woody.linux-foundation.org","subject":"Re: git and larger trees, not so fast?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-09T18:00:55Z","receivedAt":"2007-08-09T18:00:55Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> So this is all O(n**2), which is why we haven't reacted very much - it \n> doesn't show up nearly as much with the kernel. Also, with a smaller set \n> of files, it would tends to fit in the L2 cache of most competent CPU's. \n> So not only is it n**2, you get the cache trashing behaviour too, and \n> that, I think, is what really causes it to fall off the cliff edge!\n>\n> Gaah. This shouldn't be *that* hard to fix, but I'm not entirely sure I'll \n> have time today.\n\nOne thing to keep in mind is that in your earlier test of \"git\nwrite-tree\" (or \"git commit\") followed by \"git add a/file\"\nfollowed by \"git write-tree\" is extremely fast because the\nlast operation optimizes otherwise O(n) behaviour of write-tree\nfrom index extreamely cheap, thanks to cache-tree in the index.\n\n> Diffing the index against the tree *should* be instantaneous.\n\nRight now we do not cull the subdirectory that we _know_ are\nunchanged in \"git diff-index --cached\" using cache-tree, but\ndiffing the index against the tree could be instantaneous.\n"},{"id":"50336","messageId":"alpine.LFD.0.999.0708091056180.25146@woody.linux-foundation.org","threadId":"9458","inReplyTo":"alpine.LFD.0.999.0708091015500.25146@woody.linux-foundation.org","subject":"Re: git and larger trees, not so fast?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-09T18:06:27Z","receivedAt":"2007-08-09T18:06:27Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 9 Aug 2007, Linus Torvalds wrote:\n> \n> Gaah. This shouldn't be *that* hard to fix, but I'm not entirely sure I'll \n> have time today.\n\nIn fact, I'm almost sure I will *not* have time today.\n\nAnyway, the really trivial (and ugly) fix is to handle the cases of adding \n_independent_ stages to the index (which is the case for both \"git \ndiff-index\" and \"git read-tree -m\") differently: instead of using the \nstandard \"add_index_entry()\", which does all the complex sorting and \nchecks that there aren't duplicates, we could do a much simpler one that \njust unconditionally appends to the end of the index.\n\nThis works, because when the stages are independent, there can be no index \nclashes (by definition).\n\nThen, after adding all the stages, we could just do a \"qsort()\" on the \nresult, and rather than having an expensive O(n**2) thing, we'd have a \nmuch nicer and well-behaved (with a smaller constant too) O(n*logn) thing.\n\nI bet it's just ~50 lines of code, it really shouldn't be that hard to do. \nI just won't be able to do it and test it until late tonight or tomorrow, \nI suspect.\n\nSadly, this is an area that is almost exclusively mine and Junio's. I'd \nlove for somebody else to get their feet wet, but doing a\n\n\tgitk read-cache.c\n\nshows that few enough people have done anythign really fundamental in this \nfile..\n\n\t\t\tLinus\n"},{"id":"50337","messageId":"86abt0inv3.fsf@lola.quinscape.zz","threadId":"9458","inReplyTo":"alpine.LFD.0.999.0708090948250.25146@woody.linux-foundation.org","subject":"Re: git and larger trees, not so fast?","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-08-09T18:06:40Z","receivedAt":"2007-08-09T18:06:40Z","isPatch":false,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> On Thu, 9 Aug 2007, moe wrote:\n>> \n>> i made some tests on latest master branch\n>> (1.5.3.rc4.29.g74276) and it seems like git\n>> hits a wall somewhere above ~50k files.\n>\n> Good catch. Definitely not acceptable performance.\n>\n> We seem to spend a lot of our time in memcpy:\n\n[...]\n\n> Doing an ltrace on it shows tons and tons of:\n>\n> \t...\n> \tstrlen(\"35\")\n> \tstrlen(\"349\")\n> \tcalloc(1, 72)\n> \tmemcpy(0x73034e, \"10/\", 3)\n> \tmemcpy(0x730351, \"349\", 4)\n> \tmemmove(0x2ab637f41e80, 0x2ab637f41e78, 781768)\n> \t...\n>\n> but I haven't looked at where they come from yet.\n\nOk, preaching to the pope here, but: moving memory is bad.  Make sure\ndata can stay where it starts.  In particular: don't use realloc.  And\nif you do, grow the size _exponentially_ (like a factor of 1.5).  If\nyou grow the size exponentially, at least the movery hits the\nalgorithm with O(n lg n).  If data stays put, even in badly scattered\nlinear lists, we have O(n).  If you grow realloc _linearly_ (constant\nsize increment), then the algorithm is hit with O(n^2).\n\nTechnically, basically _all_ operations of git can be done by doing\nlist merges of presorted lists.  The index can be kept sorted.  All\nrequests into the index can be collected in readdir order into one\nlinear list, this gets sorted once using a merge sort with O(n lg n),\nthen it gets merged with the index O(n+N).  As long as the whole index\nis read in, it can't be done faster.  It is not necessary to organize\nthe read data into trees or more complicate structures: a single\nlinear list is sufficient.  One can use the hierarchical structure of\na directory to shave off some part of the sorting cost, though, and it\nconsiderably will lessen memory impact (and copying costs) if a\nfile/directory/tree entry can contain a relative file name and a\n\"pointer to prefix\" where the rest of the file path is to be found.\n\nAnyway, so much for some theory.  Now let's look at bad points in the\ncode, judging from your benchmarks.\n\nA grep for realloc is appaling.  Let's see what is actually involved\nhere.\n\nattr.c:\n\nstruct git_attr *git_attr(const char *name, int len)\n{\n\n\ta->attr_nr = attr_nr++;\n\tgit_attr_hash[pos] = a;\n\n\tcheck_all_attr = xrealloc(check_all_attr,\n\t\t\t\t  sizeof(*check_all_attr) * attr_nr);\n\n[...]\n\nFull O(n^2) behavior of the worst kind (increment 1!).\n\nbuiltin-commit-tree.c:\n\nstatic void add_buffer(char **bufp, unsigned int *sizep, const char *fmt, ...)\n{\n\tsize = *sizep;\n\tnewsize = size + len + 1;\n\talloc = (size + 32767) & ~32767;\n\n[size rounded to next 32k (inconsistent! needs to be size+1 rounded up)]\n\n\tbuf = *bufp;\n\tif (newsize > alloc) {\n\t\talloc = (newsize + 32767) & ~32767;\n\n[newsize rounded to next 32k]\n\n\t\tbuf = xrealloc(buf, alloc);\n\n[O(n^2): constant increment.  Important?  No idea.]\n\n\t\t*bufp = buf;\n\t}\n\t*sizep = newsize - 1;\n\n\tmemcpy(buf + size, one_line, len);\n}\n\n[...]\n\nint register_commit_graft(struct commit_graft *graft, int ignore_dups)\n{\n\n[...]\n\tif (commit_graft_alloc <= ++commit_graft_nr) {\n\t\tcommit_graft_alloc = alloc_nr(commit_graft_alloc);\n\t\tcommit_graft = xrealloc(commit_graft,\n\t\t\t\t\tsizeof(*commit_graft) *\n\t\t\t\t\tcommit_graft_alloc);\n\t}\n\tif (pos < commit_graft_nr)\n\t\tmemmove(commit_graft + pos + 1,\n\t\t\tcommit_graft + pos,\n\t\t\t(commit_graft_nr - pos - 1) *\n\t\t\tsizeof(*commit_graft));\n\tcommit_graft[pos] = graft;\n\treturn 0;\n}\n\nEeek.  Start with a linear list, not an array.\n\nobjects.c:\n\n\nvoid add_object_array_with_mode(struct object *obj, const char *name, struct object_array *array, unsigned mode)\n{\n\tunsigned nr = array->nr;\n\tunsigned alloc = array->alloc;\n\tstruct object_array_entry *objects = array->objects;\n\n\tif (nr >= alloc) {\n\t\talloc = (alloc + 32) * 2;\n\t\tobjects = xrealloc(objects, alloc * sizeof(*objects));\n\t\tarray->alloc = alloc;\n\nConstant increment, O(n^2).\n\npathlist.c:\n\nstatic int add_entry(struct path_list *list, const char *path)\n{\n\tint exact_match;\n\tint index = get_entry_index(list, path, &exact_match);\n\n\tif (exact_match)\n\t\treturn -1 - index;\n\n\tif (list->nr + 1 >= list->alloc) {\n\t\tlist->alloc += 32;\n\t\tlist->items = xrealloc(list->items, list->alloc\n\t\t\t\t* sizeof(struct path_list_item));\n\t}\n\nConstant increment, O(n^2).\n\nThat's just a cursory examination.  In my opinion, pretty much every\nrealloc should be replaced by some sort of list structure.  That would\nbe the nicest thing.  I have sped up some awk scripts that built up\nargument lists by a factor of 100 by replacing\na[index] = a[index] \" \" thenewstuff\nwith\na[index,nr[index]++] = thenewstuff\nand then never concatenating the strings, but just outputting them in\na loop.\n\n\nAnyway, short of that, don't realloc by fixed increments, always use\nalloc_nr as soon as multiple reallocs are to be expected.\n\nAnd they certainly are in some of the above cited code passages.\n\n-- \nDavid Kastrup\n"},{"id":"50338","messageId":"7vmyx0y3vp.fsf@assigned-by-dhcp.cox.net","threadId":"9458","inReplyTo":"alpine.LFD.0.999.0708091056180.25146@woody.linux-foundation.org","subject":"Re: git and larger trees, not so fast?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-09T18:11:38Z","receivedAt":"2007-08-09T18:11:38Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> On Thu, 9 Aug 2007, Linus Torvalds wrote:\n>> \n>> Gaah. This shouldn't be *that* hard to fix, but I'm not entirely sure I'll \n>> have time today.\n>\n> In fact, I'm almost sure I will *not* have time today.\n>\n> Anyway, the really trivial (and ugly) fix is to handle the cases of adding \n> _independent_ stages to the index (which is the case for both \"git \n> diff-index\" and \"git read-tree -m\") differently...\n> ...\n> Sadly, this is an area that is almost exclusively mine and Junio's. I'd \n> love for somebody else to get their feet wet,...\n\nI hopefully have some time this evening to look into this, if\nnot earlier.\n"},{"id":"50343","messageId":"7v7io4xwvp.fsf@assigned-by-dhcp.cox.net","threadId":"9458","inReplyTo":"7vmyx0y3vp.fsf@assigned-by-dhcp.cox.net","subject":"Re: git and larger trees, not so fast?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-09T20:42:50Z","receivedAt":"2007-08-09T20:42:50Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Linus Torvalds <torvalds@linux-foundation.org> writes:\n>\n>> In fact, I'm almost sure I will *not* have time today.\n>>\n>> Anyway, the really trivial (and ugly) fix is to handle the cases of adding \n>> _independent_ stages to the index (which is the case for both \"git \n>> diff-index\" and \"git read-tree -m\") differently...\n>> ...\n>> Sadly, this is an area that is almost exclusively mine and Junio's. I'd \n>> love for somebody else to get their feet wet,...\n>\n> I hopefully have some time this evening to look into this, if\n> not earlier.\n\nSo here is what I did during the lunch break.\n\nwt-status has two calls to run_diff_index() to do the equivalent\nof \"git diff --cached\".  This codepath is the sole caller of\nread_tree(), and before calling read_tree(), vacates stage #1\nentries, and reads tree contents to the index at stage #1,\nwithout any funky \"merge\" magic.\n\nThis changes read_tree() to first make sure that there is not\nany existing cache entries at specified stage (from the above\ndescription, you can see this is not strictly needed if we are\nonly interested in supporting existing callers), and if that is\nthe case, it runs add_cache_entry() with ADD_CACHE_JUST_APPEND\nflag (new), and then sort the resulting cache using qsort().\n\nadd_cache_entry() has been taught to omit all the checks such as\n\"Does this path already exist?  Does adding this path remove\nother existing entries because it turns a directory to a file?\"\nand appends the given cache entry straight at the end of the\nactive cache.\n\nThe appending and sorting at the end destroys cache-tree\noptimization, but we are not writing the resulting index out\nanyway, so that is not a problem.\n\nI do not know if this \"fixes\" the performance problem or not (I\ndo not have that much time during the day), so I would not call\nthis a \"fix\" yet, but at least the _change_ looks trivially\ncorrect, and passes all the existing tests.\n\nInterested parties may want to try it and see if it shifts the\nbottleneck.\n\n---\n\n cache.h      |    1 +\n read-cache.c |   20 +++++++++++++++-\n tree.c       |   69 +++++++++++++++++++++++++++++++++++++++++++++++++++++++--\n 3 files changed, 85 insertions(+), 5 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex e97af18..e5276e6 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -258,6 +258,7 @@ extern int index_name_pos(struct index_state *, const char *name, int namelen);\n #define ADD_CACHE_OK_TO_ADD 1\t\t/* Ok to add */\n #define ADD_CACHE_OK_TO_REPLACE 2\t/* Ok to replace file/directory */\n #define ADD_CACHE_SKIP_DFCHECK 4\t/* Ok to skip DF conflict checks */\n+#define ADD_CACHE_JUST_APPEND 8\t\t/* Append only; tree.c::read_tree() */\n extern int add_index_entry(struct index_state *, struct cache_entry *ce, int option);\n extern struct cache_entry *refresh_cache_entry(struct cache_entry *ce, int really);\n extern int remove_index_entry_at(struct index_state *, int pos);\ndiff --git a/read-cache.c b/read-cache.c\nindex e060392..865369d 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -665,7 +665,7 @@ static int check_file_directory_conflict(struct index_state *istate,\n \treturn retval + has_dir_name(istate, ce, pos, ok_to_replace);\n }\n \n-int add_index_entry(struct index_state *istate, struct cache_entry *ce, int option)\n+static int add_index_entry_with_check(struct index_state *istate, struct cache_entry *ce, int option)\n {\n \tint pos;\n \tint ok_to_add = option & ADD_CACHE_OK_TO_ADD;\n@@ -707,6 +707,22 @@ int add_index_entry(struct index_state *istate, struct cache_entry *ce, int opti\n \t\tpos = index_name_pos(istate, ce->name, ntohs(ce->ce_flags));\n \t\tpos = -pos-1;\n \t}\n+\treturn pos + 1;\n+}\n+\n+int add_index_entry(struct index_state *istate, struct cache_entry *ce, int option)\n+{\n+\tint pos;\n+\n+\tif (option & ADD_CACHE_JUST_APPEND)\n+\t\tpos = istate->cache_nr;\n+\telse {\n+\t\tint ret;\n+\t\tret = add_index_entry_with_check(istate, ce, option);\n+\t\tif (ret <= 0)\n+\t\t\treturn ret;\n+\t\tpos = ret - 1;\n+\t}\n \n \t/* Make sure the array is big enough .. */\n \tif (istate->cache_nr == istate->cache_alloc) {\n@@ -717,7 +733,7 @@ int add_index_entry(struct index_state *istate, struct cache_entry *ce, int opti\n \n \t/* Add it in.. */\n \tistate->cache_nr++;\n-\tif (istate->cache_nr > pos)\n+\tif (istate->cache_nr > pos + 1)\n \t\tmemmove(istate->cache + pos + 1,\n \t\t\tistate->cache + pos,\n \t\t\t(istate->cache_nr - pos - 1) * sizeof(ce));\ndiff --git a/tree.c b/tree.c\nindex 04fe653..8c0819f 100644\n--- a/tree.c\n+++ b/tree.c\n@@ -1,4 +1,5 @@\n #include \"cache.h\"\n+#include \"cache-tree.h\"\n #include \"tree.h\"\n #include \"blob.h\"\n #include \"commit.h\"\n@@ -7,7 +8,7 @@\n \n const char *tree_type = \"tree\";\n \n-static int read_one_entry(const unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage)\n+static int read_one_entry_opt(const unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage, int opt)\n {\n \tint len;\n \tunsigned int size;\n@@ -25,7 +26,23 @@ static int read_one_entry(const unsigned char *sha1, const char *base, int basel\n \tmemcpy(ce->name, base, baselen);\n \tmemcpy(ce->name + baselen, pathname, len+1);\n \thashcpy(ce->sha1, sha1);\n-\treturn add_cache_entry(ce, ADD_CACHE_OK_TO_ADD|ADD_CACHE_SKIP_DFCHECK);\n+\treturn add_cache_entry(ce, opt);\n+}\n+\n+static int read_one_entry(const unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage)\n+{\n+\treturn read_one_entry_opt(sha1, base, baselen, pathname, mode, stage,\n+\t\t\t\t  ADD_CACHE_OK_TO_ADD|ADD_CACHE_SKIP_DFCHECK);\n+}\n+\n+/*\n+ * This is used when the caller knows there is no existing entries at\n+ * the stage that will conflict with the entry being added.\n+ */\n+static int read_one_entry_quick(const unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage)\n+{\n+\treturn read_one_entry_opt(sha1, base, baselen, pathname, mode, stage,\n+\t\t\t\t  ADD_CACHE_JUST_APPEND);\n }\n \n static int match_tree_entry(const char *base, int baselen, const char *path, unsigned int mode, const char **paths)\n@@ -119,9 +136,55 @@ int read_tree_recursive(struct tree *tree,\n \treturn 0;\n }\n \n+static int cmp_cache_name_compare(const void *a_, const void *b_)\n+{\n+\tconst struct cache_entry *ce1, *ce2;\n+\n+\tce1 = *((const struct cache_entry **)a_);\n+\tce2 = *((const struct cache_entry **)b_);\n+\treturn cache_name_compare(ce1->name, ntohs(ce1->ce_flags),\n+\t\t\t\t  ce2->name, ntohs(ce2->ce_flags));\n+}\n+\n int read_tree(struct tree *tree, int stage, const char **match)\n {\n-\treturn read_tree_recursive(tree, \"\", 0, stage, match, read_one_entry);\n+\tread_tree_fn_t fn = NULL;\n+\tint i, err;\n+\n+\t/*\n+\t * Currently the only existing callers of this function all\n+\t * call it with stage=1 and after making sure there is nothing\n+\t * at that stage; we could always use read_one_entry_quick().\n+\t *\n+\t * But when we decide to straighten out git-read-tree not to\n+\t * use unpack_trees() in some cases, this will probably start\n+\t * to matter.\n+\t */\n+\n+\t/*\n+\t * See if we have cache entry at the stage.  If so,\n+\t * do it the original slow way, otherwise, append and then\n+\t * sort at the end.\n+\t */\n+\tfor (i = 0; !fn && i < active_nr; i++) {\n+\t\tstruct cache_entry *ce = active_cache[i];\n+\t\tif (ce_stage(ce) == stage)\n+\t\t\tfn = read_one_entry;\n+\t}\n+\n+\tif (!fn)\n+\t\tfn = read_one_entry_quick;\n+\terr = read_tree_recursive(tree, \"\", 0, stage, match, fn);\n+\tif (fn == read_one_entry || err)\n+\t\treturn err;\n+\n+\t/*\n+\t * Sort the cache entry -- we need to nuke the cache tree, though.\n+\t */\n+\tcache_tree_free(&active_cache_tree);\n+\tqsort(active_cache, active_nr, sizeof(active_cache[0]),\n+\t      cmp_cache_name_compare);\n+\treturn 0;\n }\n \n struct tree *lookup_tree(const unsigned char *sha1)\n"},{"id":"50344","messageId":"20070809165218.9b76ebf7.seanlkml@sympatico.ca","threadId":"9458","inReplyTo":"7v7io4xwvp.fsf@assigned-by-dhcp.cox.net","subject":"Re: git and larger trees, not so fast?","fromName":"Sean","fromEmail":"seanlkml@sympatico.ca","sentAt":"2007-08-09T20:52:18Z","receivedAt":"2007-08-09T20:52:18Z","isPatch":false,"sender":{"key":"seanlkml@sympatico.ca","avatar":"https://gravatar.com/avatar/f92923f54fc08c401fc59b71829d4b89e9b8087fbba45ff87c82e6a83aee02ae?d=mp&s=160"},"body":"On Thu, 09 Aug 2007 13:42:50 -0700\nJunio C Hamano <gitster@pobox.com> wrote:\n\n\n> I do not know if this \"fixes\" the performance problem or not (I\n> do not have that much time during the day), so I would not call\n> this a \"fix\" yet, but at least the _change_ looks trivially\n> correct, and passes all the existing tests.\n> \n> Interested parties may want to try it and see if it shifts the\n> bottleneck.\n\nJunio,\n\nThis makes things _much_ better, however the final commit in the \ntest script still shows a lot of user time:\n\n## time git init\nreal    0m0.005s\nuser    0m0.001s\nsys     0m0.004s\n\n## time git add . \nreal    0m3.501s\nuser    0m1.268s\nsys     0m2.159s\n\n## time git commit -q -m 'buurrrrn' -a\nreal    0m2.299s\nuser    0m1.065s\nsys     0m1.317s\n\n## time git status\nreal    0m1.107s\nuser    0m0.548s\nsys     0m0.557s\n\n## time git status\nreal    0m1.122s\nuser    0m0.545s\nsys     0m0.557s\n\n## time git status\nreal    0m1.142s\nuser    0m0.545s\nsys     0m0.576s\n\n## time git commit -q -m 'hurry' 50/500\nreal    0m16.944s\nuser    0m15.466s\nsys     0m1.133s\n\n\nCheers,\nSean\n"},{"id":"50348","messageId":"7vy7gkwfsi.fsf@assigned-by-dhcp.cox.net","threadId":"9458","inReplyTo":"20070809165218.9b76ebf7.seanlkml@sympatico.ca","subject":"Re: git and larger trees, not so fast?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-09T21:37:17Z","receivedAt":"2007-08-09T21:37:17Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Sean <seanlkml@sympatico.ca> writes:\n\n> This makes things _much_ better, however the final commit in the \n> test script still shows a lot of user time:\n\nI really do not have time to look into this for now until late\nin the evening, but it is not surprising at all that per-path\npartial commit is _always_ slower than the whole tree commit.\n\nIt simply needs to do _extra_ work, such as (1) re-initializing\na temporary index from the tree, (2) add the named entries to\nthat temporary index, and (3) add the same named entries to the\nreal index.  After that it writes a tree out of the temporary\nindex but the cost for that is the same as writing out of the\nreal index that is done for the normal commit.\n"},{"id":"50349","messageId":"alpine.LFD.0.999.0708091426050.25146@woody.linux-foundation.org","threadId":"9458","inReplyTo":"20070809165218.9b76ebf7.seanlkml@sympatico.ca","subject":"Re: git and larger trees, not so fast?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-09T21:41:34Z","receivedAt":"2007-08-09T21:41:34Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 9 Aug 2007, Sean wrote:\n> \n> This makes things _much_ better, however the final commit in the \n> test script still shows a lot of user time:\n> \n> ## time git commit -q -m 'buurrrrn' -a\n> real    0m2.299s\n> user    0m1.065s\n> sys     0m1.317s\n>\n> ## time git commit -q -m 'hurry' 50/500\n> real    0m16.944s\n> user    0m15.466s\n> sys     0m1.133s\n\nIn the case where we do a partial commit (never mind that it's all the \nchanges: when you give a path limiter, it's \"partial\"), \"git commit\" one \ngoes through another path, and triggers the same issue with\n\n\tgit read-tree --index-output=tmp-index -i -m HEAD\n\nwhich has the same O(n**2) issue (except it uses \"unpack_trees()\" rather \nthan \"read_tree()\", so Junio's patch does nothing for it).\n\nSo \"builtin-read-tree.c\" (or rather unpack-trees.c) would need the same \nkind of logic.\n\n\t\tLinus\n"},{"id":"50350","messageId":"alpine.LFD.0.999.0708091444550.25146@woody.linux-foundation.org","threadId":"9458","inReplyTo":"alpine.LFD.0.999.0708091426050.25146@woody.linux-foundation.org","subject":"Re: git and larger trees, not so fast?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-09T21:46:41Z","receivedAt":"2007-08-09T21:46:41Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 9 Aug 2007, Linus Torvalds wrote:\n> \n> So \"builtin-read-tree.c\" (or rather unpack-trees.c) would need the same \n> kind of logic.\n\nThe path seems to be:\n\n  cmd_read_tree ->\n    unpack_trees ->\n      unpack_trees_rec ->\n        [ recursive .. unpack_trees_rec ] ->\n\t  oneway_merge ->\n\t    keep_entry ->\n\t      add_index_entry()\n\nand here again we end up having the same insertion sort issue.\n\n\t\tLinus\n"},{"id":"50351","messageId":"7vtzr8wemb.fsf@assigned-by-dhcp.cox.net","threadId":"9458","inReplyTo":"alpine.LFD.0.999.0708091444550.25146@woody.linux-foundation.org","subject":"Re: git and larger trees, not so fast?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-09T22:02:36Z","receivedAt":"2007-08-09T22:02:36Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> On Thu, 9 Aug 2007, Linus Torvalds wrote:\n>> \n>> So \"builtin-read-tree.c\" (or rather unpack-trees.c) would need the same \n>> kind of logic.\n>\n> The path seems to be:\n>\n>   cmd_read_tree ->\n>     unpack_trees ->\n>       unpack_trees_rec ->\n>         [ recursive .. unpack_trees_rec ] ->\n> \t  oneway_merge ->\n> \t    keep_entry ->\n> \t      add_index_entry()\n>\n> and here again we end up having the same insertion sort issue.\n\nQuite honestly, I was this (shows the \"thumb and index finger\nalmost touching\" gesture) close to declare that unpack-trees is\nunsalvageable, and was planning to redo the one-tree (and\nperhaps two-tree) read-tree without using that mess after 1.5.3.\n"},{"id":"50355","messageId":"7vps1wwa5w.fsf@assigned-by-dhcp.cox.net","threadId":"9458","inReplyTo":"7vtzr8wemb.fsf@assigned-by-dhcp.cox.net","subject":"Re: git and larger trees, not so fast?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-09T23:38:51Z","receivedAt":"2007-08-09T23:38:51Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Linus Torvalds <torvalds@linux-foundation.org> writes:\n>\n>> On Thu, 9 Aug 2007, Linus Torvalds wrote:\n>>> \n>>> So \"builtin-read-tree.c\" (or rather unpack-trees.c) would need the same \n>>> kind of logic.\n>>\n>> The path seems to be:\n>>\n>>   cmd_read_tree ->\n>>     unpack_trees ->\n>>       unpack_trees_rec ->\n>>         [ recursive .. unpack_trees_rec ] ->\n>> \t  oneway_merge ->\n>> \t    keep_entry ->\n>> \t      add_index_entry()\n>>\n>> and here again we end up having the same insertion sort issue.\n>\n> Quite honestly, I was this (shows the \"thumb and index finger\n> almost touching\" gesture) close to declare that unpack-trees is\n> unsalvageable, and was planning to redo the one-tree (and\n> perhaps two-tree) read-tree without using that mess after 1.5.3.\n\nWhile I do not think the previous one was hacky at all, this one\nIS a hack, not meant for inclusion.  It makes the partial commit\ncodepath to use vanilla \"git read-tree\" without any single tree\nmerge semantics, and rewrite that codepath to use read_tree()\nwhich was changed with my previous patch.\n\n\n\n---\n\n builtin-read-tree.c |    5 ++++-\n git-commit.sh       |    2 +-\n 2 files changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin-read-tree.c b/builtin-read-tree.c\nindex a3b17a3..61ea15c 100644\n--- a/builtin-read-tree.c\n+++ b/builtin-read-tree.c\n@@ -258,7 +258,10 @@ int cmd_read_tree(int argc, const char **argv, const char *unused_prefix)\n \t\t\topts.head_idx = 1;\n \t}\n \n-\tunpack_trees(trees, &opts);\n+\tif (!opts.merge && !opts.prefix && trees && !trees->next)\n+\t\tread_tree((struct tree*) trees->item, 0, NULL);\n+\telse\n+\t\tunpack_trees(trees, &opts);\n \n \t/*\n \t * When reading only one tree (either the most basic form,\ndiff --git a/git-commit.sh b/git-commit.sh\nindex d7e7028..b50468f 100755\n--- a/git-commit.sh\n+++ b/git-commit.sh\n@@ -386,7 +386,7 @@ t,)\n \t\tif test -z \"$initial_commit\"\n \t\tthen\n \t\t\tGIT_INDEX_FILE=\"$THIS_INDEX\" \\\n-\t\t\tgit read-tree --index-output=\"$TMP_INDEX\" -i -m HEAD\n+\t\t\tgit read-tree --index-output=\"$TMP_INDEX\" HEAD\n \t\telse\n \t\t\trm -f \"$TMP_INDEX\"\n \t\tfi || exit\n"},{"id":"50358","messageId":"7vlkckw8zq.fsf@assigned-by-dhcp.cox.net","threadId":"9458","inReplyTo":"7vps1wwa5w.fsf@assigned-by-dhcp.cox.net","subject":"Re: git and larger trees, not so fast?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-10T00:04:09Z","receivedAt":"2007-08-10T00:04:09Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> While I do not think the previous one was hacky at all, this one\n> IS a hack, not meant for inclusion.  It makes the partial commit\n> codepath to use vanilla \"git read-tree\" without any single tree\n> merge semantics, and rewrite that codepath to use read_tree()\n> which was changed with my previous patch.\n\nJust in case anybody is wondering, this also passed all the\nexisting tests.  Maybe it is going in the right direction of\nslowly moving away from unpack_trees() where we can.  I dunno.\n\nI also do not know if it \"fixes\" the performance issue on that\ntestcase.\n"},{"id":"50363","messageId":"alpine.LFD.0.999.0708091734210.25146@woody.linux-foundation.org","threadId":"9458","inReplyTo":"7vps1wwa5w.fsf@assigned-by-dhcp.cox.net","subject":"Re: git and larger trees, not so fast?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-10T00:44:25Z","receivedAt":"2007-08-10T00:44:25Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 9 Aug 2007, Junio C Hamano wrote:\n> \n> While I do not think the previous one was hacky at all, this one\n> IS a hack, not meant for inclusion.\n\n\nUgh.\n\nI had some time, so I tried to find out *why* that thing is so slow.\n\nThe fact is, \"git read-tree -m HEAD\" should be really really fast, because \nit should never actually insert multiple entries into the same index \nentry: it should just _replace_ the entry.\n\nBut why is it slow?\n\nIt doesn't actually replace the entry with \"add_cache_entry()\" at all. \nWhat it does is to *remove* the entry entirely at unpack-trees.c, line \n154, unpack_trees_rec(), which does a \"remove_cache_entry_at(o->pos);\".\n\nThat causes us to have to condense the index array, and is one big \nmemcpy() for a large index.\n\nIt then ADDS THE NEW ENTRY BACK! Which causes *another* expensive index \narray memmove(), as it now needs to make room (at the same location that \nit just compacted).\n\nSadly, that removal is required for some of the other cases, so it's not \nlike we can remove the remove. But we could *possibly* make things \nridiculously much faster by making the remove a lazy thing, and if the \nnext index operation just adds it back in, we wouldn't move things around.\n\nA bit too subtle for my taste.\n\n\t\tLinus\n"},{"id":"50364","messageId":"7vhcn8w6sw.fsf@assigned-by-dhcp.cox.net","threadId":"9458","inReplyTo":"alpine.LFD.0.999.0708091734210.25146@woody.linux-foundation.org","subject":"Re: git and larger trees, not so fast?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-10T00:51:27Z","receivedAt":"2007-08-10T00:51:27Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> On Thu, 9 Aug 2007, Junio C Hamano wrote:\n>> \n>> While I do not think the previous one was hacky at all, this one\n>> IS a hack, not meant for inclusion.\n> ...\n> Sadly, that removal is required for some of the other cases, so it's not \n> like we can remove the remove. But we could *possibly* make things \n> ridiculously much faster by making the remove a lazy thing, and if the \n> next index operation just adds it back in, we wouldn't move things around.\n\nHeh, that makes the two of us.  I have been wanting to revamp or\nkill off unpack-trees for quite some time, and after all the\npatch you are responding to might be a small first step in the\nright direction ;-).\n"},{"id":"50366","messageId":"alpine.LFD.0.999.0708091754150.25146@woody.linux-foundation.org","threadId":"9458","inReplyTo":"7vhcn8w6sw.fsf@assigned-by-dhcp.cox.net","subject":"Re: git and larger trees, not so fast?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-10T00:57:45Z","receivedAt":"2007-08-10T00:57:45Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 9 Aug 2007, Junio C Hamano wrote:\n> \n> Heh, that makes the two of us.  I have been wanting to revamp or\n> kill off unpack-trees for quite some time, and after all the\n> patch you are responding to might be a small first step in the\n> right direction ;-).\n\nWell, the patch you sent out was not only hacky, it was kind of pointless.\n\nWithout the \"-m\" handling, it means that most users of git-read-tree won't \never see the improvement. The merge with the old index is absolutely \ncritical for things like switching branches, for example. And I think you \nprobably screwed up performance with your change to git-commit to simply \nnot use it, because now the resulting index will be totally stale, and \nwhile the *commit* may be fast as a result, the subsequent operations \nmight be horrible.\n\n(I didn't test it, though, maybe I missed something).\n\nSo I do think that things like \"git checkout <otherbranch>\" need to have a \nfully working (and fast) unpack-trees, and your hack doesn't really help \nexcept for a pretty uninteresting special case.\n\n\t\tLinus\n"},{"id":"50368","messageId":"Pine.LNX.4.64.0708092131030.10711@iabervon.org","threadId":"9458","inReplyTo":"7vtzr8wemb.fsf@assigned-by-dhcp.cox.net","subject":"Re: git and larger trees, not so fast?","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2007-08-10T01:42:30Z","receivedAt":"2007-08-10T01:42:30Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Thu, 9 Aug 2007, Junio C Hamano wrote:\n\n> Linus Torvalds <torvalds@linux-foundation.org> writes:\n> \n> > On Thu, 9 Aug 2007, Linus Torvalds wrote:\n> >> \n> >> So \"builtin-read-tree.c\" (or rather unpack-trees.c) would need the same \n> >> kind of logic.\n> >\n> > The path seems to be:\n> >\n> >   cmd_read_tree ->\n> >     unpack_trees ->\n> >       unpack_trees_rec ->\n> >         [ recursive .. unpack_trees_rec ] ->\n> > \t  oneway_merge ->\n> > \t    keep_entry ->\n> > \t      add_index_entry()\n> >\n> > and here again we end up having the same insertion sort issue.\n> \n> Quite honestly, I was this (shows the \"thumb and index finger\n> almost touching\" gesture) close to declare that unpack-trees is\n> unsalvageable, and was planning to redo the one-tree (and\n> perhaps two-tree) read-tree without using that mess after 1.5.3.\n\nYeah, that's probably the right thing to do; I wrote it with the idea that \nwe'd be doing many-parent merges with it, but merge-recursive turned out \nto be a better idea, so I designed it to be comprehensible for a \ncomplicated case we never actually do.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"50375","messageId":"7v643ovyli.fsf@assigned-by-dhcp.cox.net","threadId":"9458","inReplyTo":"alpine.LFD.0.999.0708091754150.25146@woody.linux-foundation.org","subject":"Re: git and larger trees, not so fast?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-10T03:48:41Z","receivedAt":"2007-08-10T03:48:41Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> (I didn't test it, though, maybe I missed something).\n\nI do not think the change affects the normal codepath.  The\none-liner patch to git-commit.sh touches the codepath that\nupdates the index used only to write out the partial commit, and\nlosing the cached stat info from that index does not matter, as\nthat index is removed immediately after writing the tree out and\nis never compared with working tree as far as I can tell.\n"},{"id":"50378","messageId":"7vy7gkue5s.fsf@assigned-by-dhcp.cox.net","threadId":"9458","inReplyTo":"7v643ovyli.fsf@assigned-by-dhcp.cox.net","subject":"Re: git and larger trees, not so fast?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-10T05:55:27Z","receivedAt":"2007-08-10T05:55:27Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Linus Torvalds <torvalds@linux-foundation.org> writes:\n>\n>> (I didn't test it, though, maybe I missed something).\n>\n> I do not think the change affects the normal codepath.  The\n> one-liner patch to git-commit.sh touches the codepath that\n> updates the index used only to write out the partial commit, and\n> losing the cached stat info from that index does not matter, as\n> that index is removed immediately after writing the tree out and\n> is never compared with working tree as far as I can tell.\n\nFWIW, moe's script with and without two patches gives these\nnumbers for me.\n\n      with patches                      without patches\n----------------------------------------------------------------\n# git init                          | # git init\t\t\t       \nInitialized empty Git repository in | Initialized empty Git repository in  \n                                    | \t\t\t\t       \nreal    0m0.029s                    | real    0m0.004s\t\t       \nuser    0m0.000s                    | user    0m0.000s\t\t       \nsys     0m0.008s                    | sys     0m0.004s\t\t       \n# git add .                         | # git add .\t\t\t       \n                                    | \t\t\t\t       \nreal    0m2.947s                    | real    0m3.038s\t\t       \nuser    0m0.808s                    | user    0m0.876s\t\t       \nsys     0m2.120s                    | sys     0m1.996s\t\t       \n# git commit -a                     | # git commit -a\t\t       \n                                    | \t\t\t\t       \nreal    0m4.537s                    | real    0m4.674s\t\t       \nuser    0m1.980s                    | user    0m1.888s\t\t       \nsys     0m2.356s                    | sys     0m2.332s\t\t       \n# git status (three times)          | # git status (three times)\t       \n# On branch master                  | # On branch master\t\t       \nnothing to commit (working directory| nothing to commit (working directory \n                                    | \t\t\t\t       \nreal    0m0.718s                    | real    0m17.323s\t\t       \nuser    0m0.300s                    | user    0m16.913s\t\t       \nsys     0m0.416s                    | sys     0m0.396s\t\t       \n# On branch master                  | # On branch master\t\t       \nnothing to commit (working directory| nothing to commit (working directory \n                                    | \t\t\t\t       \nreal    0m0.707s                    | real    0m16.994s\t\t       \nuser    0m0.312s                    | user    0m16.573s\t\t       \nsys     0m0.400s                    | sys     0m0.416s\t\t       \n# On branch master                  | # On branch master\t\t       \nnothing to commit (working directory| nothing to commit (working directory \n                                    | \t\t\t\t       \nreal    0m0.720s                    | real    0m18.042s\t\t       \nuser    0m0.344s                    | user    0m17.633s\t\t       \nsys     0m0.376s                    | sys     0m0.408s\t\t       \n# git commit (one path)             | # git commit (one path)\t       \nCreated commit 3483df5: expose the t| Created commit ced664f: expose the t \n 1 files changed, 1 insertions(+), 1|  1 files changed, 1 insertions(+), 1 \n                                    | \t\t\t\t       \nreal    0m3.057s                    | real    0m38.130s\t\t       \nuser    0m0.888s                    | user    0m37.458s\t\t       \nsys     0m0.712s                    | sys     0m0.616s                     \n----------------------------------------------------------------\n"},{"id":"50418","messageId":"alpine.LFD.0.999.0708100836340.30176@woody.linux-foundation.org","threadId":"9458","inReplyTo":"7vy7gkue5s.fsf@assigned-by-dhcp.cox.net","subject":"Re: git and larger trees, not so fast?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-10T15:49:56Z","receivedAt":"2007-08-10T15:49:56Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 9 Aug 2007, Junio C Hamano wrote:\n> \n> FWIW, moe's script with and without two patches gives these\n> numbers for me.\n\nBtw, I really think it's worth doing even just the hacky patches at this \nstage, even though it's late in the game for 1.5.3.\n\nThat performance problem is serious enough that I'd call it a major bug. \nPerformance has always been one of the goals of git, and when you have a \ndifference between 17s and 0.7s for \"git status\", that's a *huge* \nusability thing. It would be sad to release 1.5.3 with a known bug.\n\n[ Some people don't think performance issues are \"real bugs\", and I think \n  such people shouldn't be allowed to program. ]\n\nSide note: your first patch is actually quite noticeable on even just the \nkernel. Not nearly as much, but without it, I get about 0.5s, and with it, \nI get consistently under 0.3s. So it's about a 40% improvement even for \nsmaller projects (and it's probably much more if you have a CPU with a \nsmaller cache: my Core 2 Duo has 4MB of L2 cache, and a lot of the index \nwill even fit in the L1 - a slower CPU with less cache will see a bigger \nimpact, and with smaller repositories, from the unnecessary memory \nmoving).\n\nWhile 0.5s -> 0.3s may not sound like much, on a slower machine where it \nmight otherwise be 2.5s -> 1.5s, that's likely to be quite noticeable.\n\nIn fact, I can tell even on my machine: 0.3s is visible as a \"I'm clearly \nthinking about it\" delay (quite frankly, it would be better at 0.1s, which \nis \"immediate\"), but 0.5s is already approaching the point where you \nactually wait for the answer (rather than just notice that it wasn't quite \nimmediate).\n\n\t\t\t\tLinus\n"},{"id":"50420","messageId":"alpine.LFD.0.999.0708100852540.30176@woody.linux-foundation.org","threadId":"9458","inReplyTo":"7v643ovyli.fsf@assigned-by-dhcp.cox.net","subject":"Re: git and larger trees, not so fast?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-10T16:07:01Z","receivedAt":"2007-08-10T16:07:01Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 9 Aug 2007, Junio C Hamano wrote:\n> > \n> > (I didn't test it, though, maybe I missed something).\n> \n> I do not think the change affects the normal codepath.  The\n> one-liner patch to git-commit.sh touches the codepath that\n> updates the index used only to write out the partial commit, and\n> losing the cached stat info from that index does not matter, as\n> that index is removed immediately after writing the tree out and\n> is never compared with working tree as far as I can tell.\n\nYou are, of course, mostly right. Using \"-m\" there is largely pointless, \nsince it's a throw-away index, and we'll only ever use the exact paths \nthat were given to us.\n\nHowever, it does actually matter for one case: the case where you give a \ndirectory name or other name pattern, resulting in a *lot* of filenames. \nIn that case, the commit will end up piping that (potentially very large) \nlist to \"git update-index --add --remove --stdin\", and that will now mean \nthat they *all* get their SHA1's recomputed.\n\nOf course, that was the other performance bug that we already knew about \n(except we were thining \"git add .\", and fixed that case). So we're \nalready slow at it - but we *shouldn't* be.\n\nTry this on the kernel archive (use a clean one, so these things *should* \nall be no-ops):\n\n\ttime sh -c \"git add . ; git commit\"\n\nwhich is nice and fast and takes just over a second for me, but then try\n\n\ttime git commit .\n\nwhich *should* be nice and fast, but it takes forever, because we now \nre-compute all the SHA1's for *every* file. Of course, if it's all in the \ncache, it's still just 4s for me, but I tried with a cold cache, and it \nwas over half a minute!\n\n(I don't actually ever do something like \"git commit .\", but I could see \npeople doing it. What I *do* do is that if I have multiple independent \nchanges, I may actually do \"git commit fs\" to commit just part of them, \nand rather than list all the files, I literally just say \"commit that \nsub-tree\". So this really is another valid performance issue).\n\nSad.\n\n\t\t\tLinus\n"},{"id":"50426","messageId":"alpine.LFD.0.999.0708100924570.30176@woody.linux-foundation.org","threadId":"9458","inReplyTo":"alpine.LFD.0.999.0708100852540.30176@woody.linux-foundation.org","subject":"Fix \"git commit directory/\" performance anomaly","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-10T16:51:58Z","receivedAt":"2007-08-10T16:51:58Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis trivial patch avoids re-hashing files that are already clean in the \nindex. This mirrors what commit 0781b8a9b2fe760fc4ed519a3a26e4b9bd6ccffe \ndid for \"git add .\", only for \"git commit .\" instead.\n\nThis improves the cold-cache case immensely, since we don't need to bring \nin all the file contents, just the index and any files dirty in the index.\n\nBefore:\n\n\t[torvalds@woody linux]$ time git commit .\n\treal    1m49.537s\n\tuser    0m3.892s\n\tsys     0m2.432s\n\nAfter:\n\n\t[torvalds@woody linux]$ time git commit .\n\treal    0m14.273s\n\tuser    0m1.312s\n\tsys     0m0.516s\n\n(both after doing a \"echo 3 > /proc/sys/vm/drop_caches\" to get cold-cache \nbehaviour - even with the index optimization git still has to \"lstat()\" \nall the files, so with a truly cold cache, bringing all the inodes in \nwill take some time).\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nOn Fri, 10 Aug 2007, Linus Torvalds wrote:\n> \n> Try this on the kernel archive (use a clean one, so these things *should* \n> all be no-ops):\n> \n> \ttime sh -c \"git add . ; git commit\"\n> \n> which is nice and fast and takes just over a second for me, but then try\n> \n> \ttime git commit .\n> \n> which *should* be nice and fast, but it takes forever, because we now \n> re-compute all the SHA1's for *every* file. Of course, if it's all in the \n> cache, it's still just 4s for me, but I tried with a cold cache, and it \n> was over half a minute!\n> \n> (I don't actually ever do something like \"git commit .\", but I could see \n> people doing it. What I *do* do is that if I have multiple independent \n> changes, I may actually do \"git commit fs\" to commit just part of them, \n> and rather than list all the files, I literally just say \"commit that \n> sub-tree\". So this really is another valid performance issue).\n> \n> Sad.\n> \n> \t\t\tLinus\n> \n---\n builtin-update-index.c |   10 ++++++++--\n 1 files changed, 8 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin-update-index.c b/builtin-update-index.c\nindex 509369e..8d22dfa 100644\n--- a/builtin-update-index.c\n+++ b/builtin-update-index.c\n@@ -86,9 +86,15 @@ static int process_lstat_error(const char *path, int err)\n \n static int add_one_path(struct cache_entry *old, const char *path, int len, struct stat *st)\n {\n-\tint option, size = cache_entry_size(len);\n-\tstruct cache_entry *ce = xcalloc(1, size);\n+\tint option, size;\n+\tstruct cache_entry *ce;\n+\n+\t/* Was the old index entry already up-to-date? */\n+\tif (old && !ce_stage(old) && !ce_match_stat(old, st, 0))\n+\t\treturn;\n \n+\tsize = cache_entry_size(len);\n+\tce = xcalloc(1, size);\n \tmemcpy(ce->name, path, len);\n \tce->ce_flags = htons(len);\n \tfill_stat_cache_info(ce, st);\n"},{"id":"50429","messageId":"alpine.LFD.0.999.0708101008230.30176@woody.linux-foundation.org","threadId":"9458","inReplyTo":"alpine.LFD.0.999.0708100924570.30176@woody.linux-foundation.org","subject":"Re: Fix \"git commit directory/\" performance anomaly","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-10T17:14:25Z","receivedAt":"2007-08-10T17:14:25Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 10 Aug 2007, Linus Torvalds wrote:\n>\n> This improves the cold-cache case immensely, since we don't need to bring \n> in all the file contents, just the index and any files dirty in the index.\n\nThe extreme - but not necessarily unusual - case of this is when the index \nand stat information is hot-cache (which is quite normal, in case you've \ndone a \"git diff\" or something like that), but the whole source tree is \notherwise not. Then the numbers look like this:\n\nBefore:\n\t[torvalds@woody linux]$ time git commit .\n\treal    1m33.751s\n\tuser    0m3.864s\n\tsys     0m2.160s\n\n\nAfter:\n\t[torvalds@woody linux]$ time git commit .\n\treal    0m1.415s\n\tuser    0m1.176s\n\tsys     0m0.260s\n\nThe all-hot-cache numbers are better too, of course, just not nearly as \nnoticeable:\n\nBefore:\n\t[torvalds@woody linux]$ time git commit .\n\treal    0m3.960s\n\tuser    0m3.304s\n\tsys     0m0.672s\n\n(and the after case is that 1.415s above, of course, so it's still more \nthan twice as fast - it's just no longer a 60x performance difference!).\n\n(Honesty in advertising: the \"after\" numbers also contain the \"runstatus\" \nspeedup, which is the 0.5s -> 0.3s improvement)\n\n\t\t\tLinus\n"},{"id":"50432","messageId":"7vsl6rs0l5.fsf@assigned-by-dhcp.cox.net","threadId":"9458","inReplyTo":"alpine.LFD.0.999.0708100924570.30176@woody.linux-foundation.org","subject":"Re: Fix \"git commit directory/\" performance anomaly","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-10T18:31:34Z","receivedAt":"2007-08-10T18:31:34Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> This trivial patch avoids re-hashing files that are already clean in the \n> index. This mirrors what commit 0781b8a9b2fe760fc4ed519a3a26e4b9bd6ccffe \n> did for \"git add .\", only for \"git commit .\" instead.\n\nMakes sense.  Thanks.\n"},{"id":"50433","messageId":"alpine.LFD.0.999.0708101154530.30176@woody.linux-foundation.org","threadId":"9458","inReplyTo":"7vsl6rs0l5.fsf@assigned-by-dhcp.cox.net","subject":"Re: Fix \"git commit directory/\" performance anomaly","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-10T18:56:34Z","receivedAt":"2007-08-10T18:56:34Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 10 Aug 2007, Junio C Hamano wrote:\n> Linus Torvalds <torvalds@linux-foundation.org> writes:\n> \n> > This trivial patch avoids re-hashing files that are already clean in the \n> > index. This mirrors what commit 0781b8a9b2fe760fc4ed519a3a26e4b9bd6ccffe \n> > did for \"git add .\", only for \"git commit .\" instead.\n> \n> Makes sense.  Thanks.\n\nPlease don't apply that patch without this trivial fix.\n\nI don't know why I didn't notice. It passed all the tests, but it really \nshouldn't have, and the compiler warned.\n\n\t\tLinus\n\n---\ndiff --git a/builtin-update-index.c b/builtin-update-index.c\nindex 8d22dfa..a7a4574 100644\n--- a/builtin-update-index.c\n+++ b/builtin-update-index.c\n@@ -91,7 +91,7 @@ static int add_one_path(struct cache_entry *old, const char *path, int len, stru\n \n \t/* Was the old index entry already up-to-date? */\n \tif (old && !ce_stage(old) && !ce_match_stat(old, st, 0))\n-\t\treturn;\n+\t\treturn 0;\n \n \tsize = cache_entry_size(len);\n \tce = xcalloc(1, size);\n"},{"id":"50442","messageId":"alpine.LFD.0.999.0708101231580.30176@woody.linux-foundation.org","threadId":"9458","inReplyTo":"20070809163026.GD568@mbox.bz","subject":"Re: git and larger trees, not so fast?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-10T19:39:42Z","receivedAt":"2007-08-10T19:39:42Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 9 Aug 2007, moe wrote:\n> \n> earlier today i imported one of my larger trees\n> (~70k files) into git and was quite disappointed\n> by the performance.\n\nOk, I said I wouldn't have time to fix it yesterday, but today it's all \ndone.\n\nWith the first fix from Junio yesterday (the one that fixed \"git status\"), \nand the fixes I've sent out today, your cases should not all be basically \ninstantaneous (ie we're talking low seconds, even on not-the-fastest- \npossible-machines).\n\nSo with the following patches that were posted over the last 24 hours, you \nshould be ok:\n\n  Junio:\n\tFix performance problem in \"git status\"\n\n  Me:\n\tStart moving unpack-trees to \"struct tree_desc\"\n\tFix \"git commit directory/\" performance anomaly (+ one-liner fix)\n\tMove old index entry removal from \"unpack_trees()\" into the individual functions\n\tOptimize the common cases of git-read-tree\n\tOptimize the two-way merge of git-read-tree too\n\n(that patch from Junio was sent in an email in this thread, with the \nsubject line \"Re: git and larger trees, not so fast?\" and a message ID of \n\"<7v7io4xwvp.fsf@assigned-by-dhcp.cox.net>\": the patches from me should \nall have the appropriate Subject lines and be findable that way).\n\nIf you can test with your real load to make sure, that would be good.\n\n\t\t\tLinus\n"},{"id":"50491","messageId":"alpine.LFD.0.999.0708111137250.30176@woody.linux-foundation.org","threadId":"9458","inReplyTo":"20070809163026.GD568@mbox.bz","subject":"Re: git and larger trees, not so fast?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-11T18:47:42Z","receivedAt":"2007-08-11T18:47:42Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 9 Aug 2007, moe wrote:\n> \n> here's a test-case (should be safe to\n> copy/paste on linux, bash):\n\nmoe: with current git (and thus the 1.5.3 release), the \"git status\" \ncommands now take half a second for me, and the git commit takes just \nunder a second.\n\nThe *initial* commit that adds everything still takes almost 5 seconds, \nbut that was due to generating the diffstat summary - with a \"-q\" on the \ncommit line that too drops down to just under a second.\n\nIn fact, the only thing that took more than a second for me with the \ncurrent git is that initial \"git add .\", which took 1.791s for me. \nConsidering that it had to hash all the 100,000 objects, I'm not \nsurprised.\n\nAnyway, it would be good if you re-did your real work tree with current \ncommit, just to verify. You have slower hardware than I do, but hopefully \nit is now just about as fast as it can be.\n\n\t\t\tLinus\n"},{"id":"50493","messageId":"20070811190201.GB4710@ferdyx.org","threadId":"9458","inReplyTo":"alpine.LFD.0.999.0708111137250.30176@woody.linux-foundation.org","subject":"Re: git and larger trees, not so fast?","fromName":"Fernando J. Pereda","fromEmail":"ferdy@gentoo.org","sentAt":"2007-08-11T19:02:01Z","receivedAt":"2007-08-11T19:02:01Z","isPatch":false,"sender":{"key":"ferdy@gentoo.org","avatar":null},"body":"On Sat, Aug 11, 2007 at 11:47:42AM -0700, Linus Torvalds wrote:\n> Anyway, it would be good if you re-did your real work tree with current \n> commit, just to verify. You have slower hardware than I do, but hopefully \n> it is now just about as fast as it can be.\n\nJust for the record, I tried those patches on a real tree of ~120k files\nand ~25k directories, and Git is now _usable_. (The repository was\ncreated from an old checkout of the gentoo-x86 tree).\n\n- ferdy\n\n-- \nFernando J. Pereda Garcimartín\n20BB BDC3 761A 4781 E6ED  ED0B 0A48 5B0C 60BD 28D4\n"},{"id":"50498","messageId":"20070811200630.GD19284@mbox.bz","threadId":"9458","inReplyTo":"alpine.LFD.0.999.0708111137250.30176@woody.linux-foundation.org","subject":"Re: git and larger trees, not so fast?","fromName":"moe","fromEmail":"moe-git@mbox.bz","sentAt":"2007-08-11T20:06:30Z","receivedAt":"2007-08-11T20:06:30Z","isPatch":false,"sender":{"key":"moe-git@mbox.bz","avatar":null},"body":"On Sat, Aug 11, 2007 at 11:47:42AM -0700, Linus Torvalds wrote:\n> \n> \n> On Thu, 9 Aug 2007, moe wrote:\n> > \n> > here's a test-case (should be safe to\n> > copy/paste on linux, bash):\n> \n> moe: with current git (and thus the 1.5.3 release), the \"git status\" \n> commands now take half a second for me, and the git commit takes just \n> under a second.\n> \n> The *initial* commit that adds everything still takes almost 5 seconds, \n> but that was due to generating the diffstat summary - with a \"-q\" on the \n> commit line that too drops down to just under a second.\n> \n> In fact, the only thing that took more than a second for me with the \n> current git is that initial \"git add .\", which took 1.791s for me. \n> Considering that it had to hash all the 100,000 objects, I'm not \n> surprised.\n> \n> Anyway, it would be good if you re-did your real work tree with current \n> commit, just to verify. You have slower hardware than I do, but hopefully \n> it is now just about as fast as it can be.\n \nhi linus,\n\nthx for your efforts, the figures look very promising.\ni'm out of town right now but will test when i get\nstationary internet again (sometime tomorrow evening\ni think).\n\n\nregards, moe\n"},{"id":"50500","messageId":"alpine.LFD.0.999.0708111337280.30176@woody.linux-foundation.org","threadId":"9458","inReplyTo":"20070811190201.GB4710@ferdyx.org","subject":"Re: git and larger trees, not so fast?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-11T20:38:34Z","receivedAt":"2007-08-11T20:38:34Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 11 Aug 2007, Fernando J. Pereda wrote:\n> \n> Just for the record, I tried those patches on a real tree of ~120k files\n> and ~25k directories, and Git is now _usable_. (The repository was\n> created from an old checkout of the gentoo-x86 tree).\n\nWhat does \"usable\" mean? Is it still slow (\"barely usable\") or is it \nactually fast enough to be truly _nice_ to use?\n\n\t\tLinus\n"},{"id":"50502","messageId":"20070811205137.GC4710@ferdyx.org","threadId":"9458","inReplyTo":"alpine.LFD.0.999.0708111337280.30176@woody.linux-foundation.org","subject":"Re: git and larger trees, not so fast?","fromName":"Fernando J. Pereda","fromEmail":"ferdy@gentoo.org","sentAt":"2007-08-11T20:51:37Z","receivedAt":"2007-08-11T20:51:37Z","isPatch":false,"sender":{"key":"ferdy@gentoo.org","avatar":null},"body":"On Sat, Aug 11, 2007 at 01:38:34PM -0700, Linus Torvalds wrote:\n> \n> \n> On Sat, 11 Aug 2007, Fernando J. Pereda wrote:\n> > \n> > Just for the record, I tried those patches on a real tree of ~120k files\n> > and ~25k directories, and Git is now _usable_. (The repository was\n> > created from an old checkout of the gentoo-x86 tree).\n> \n> What does \"usable\" mean? Is it still slow (\"barely usable\") or is it \n> actually fast enough to be truly _nice_ to use?\n\nVery nice to use considering my hardware is rather old. git status used\nto take >1m and it now takes ~3s and git commit takes ~7s while it used\nto take >1m too. So it makes things nice to use and I guess things are\nMUCH better on faster hardware.\n\n(This is running on a 'AMD Athlon(TM) XP 2000+' and the repo is in a USB\nHard drive)\n\n- ferdy\n\n-- \nFernando J. Pereda Garcimartín\n20BB BDC3 761A 4781 E6ED  ED0B 0A48 5B0C 60BD 28D4\n"},{"id":"50514","messageId":"alpine.LFD.0.999.0708111522570.30176@woody.linux-foundation.org","threadId":"9458","inReplyTo":"20070811205137.GC4710@ferdyx.org","subject":"Re: git and larger trees, not so fast?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-08-11T22:27:20Z","receivedAt":"2007-08-11T22:27:20Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 11 Aug 2007, Fernando J. Pereda wrote:\n> > \n> > What does \"usable\" mean? Is it still slow (\"barely usable\") or is it \n> > actually fast enough to be truly _nice_ to use?\n> \n> Very nice to use considering my hardware is rather old. git status used\n> to take >1m and it now takes ~3s and git commit takes ~7s while it used\n> to take >1m too. So it makes things nice to use and I guess things are\n> MUCH better on faster hardware.\n\nOh, ok. Having a 7s commit sounds fine - certainly not instantaneous, but \nit doesn't sound too painful. Certainly not compared to what people live \nwith normally in some other environments, at least.\n\nThanks go to moe for just giving a trivial script to reproduce the \nperformance anomaly. It wasn't that hard to fix once there was a trivial \nand unambiguous test case.\n\n\t\tLinus\n"},{"id":"50519","messageId":"85k5s1sldz.fsf@lola.goethe.zz","threadId":"9458","inReplyTo":"alpine.LFD.0.999.0708111522570.30176@woody.linux-foundation.org","subject":"Re: git and larger trees, not so fast?","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-08-11T23:26:48Z","receivedAt":"2007-08-11T23:26:48Z","isPatch":false,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> On Sat, 11 Aug 2007, Fernando J. Pereda wrote:\n>> > \n>> > What does \"usable\" mean? Is it still slow (\"barely usable\") or is it \n>> > actually fast enough to be truly _nice_ to use?\n>> \n>> Very nice to use considering my hardware is rather old. git status used\n>> to take >1m and it now takes ~3s and git commit takes ~7s while it used\n>> to take >1m too. So it makes things nice to use and I guess things are\n>> MUCH better on faster hardware.\n>\n> Oh, ok. Having a 7s commit sounds fine - certainly not instantaneous, but \n> it doesn't sound too painful. Certainly not compared to what people live \n> with normally in some other environments, at least.\n>\n> Thanks go to moe for just giving a trivial script to reproduce the \n> performance anomaly. It wasn't that hard to fix once there was a trivial \n> and unambiguous test case.\n\nSince one of the problems is git sorting stuff inefficiently, it might\nmake for an interesting test case to create the test files in reverse\nalphabetic order so that readdir is more likely to deliver them in\nreverse order, too.\n\nOr in random order, by something like\n\ndc -e '2 32^sb69069sc100000sd1se[rlc*le+lb%prle+dld!=a]sa42 0lax'|\nwhile read i;do echo $i > $i;done\n\n(change the 100000 to get a different number of files, change the\n42 to get a different seed).\n\n-- \nDavid Kastrup, Kriemhildstr. 15, 44793 Bochum\n"},{"id":"51312","messageId":"20070823003045.GD27372@mbox.bz","threadId":"9458","inReplyTo":"20070811200630.GD19284@mbox.bz","subject":"Re: git and larger trees, not so fast?","fromName":"moe","fromEmail":"moe-git@mbox.bz","sentAt":"2007-08-23T00:30:46Z","receivedAt":"2007-08-23T00:30:46Z","isPatch":false,"sender":{"key":"moe-git@mbox.bz","avatar":null},"body":"On Sat, Aug 11, 2007 at 10:06:30PM +0200, moe wrote:\n> On Sat, Aug 11, 2007 at 11:47:42AM -0700, Linus Torvalds wrote:\n> > \n> > \n> > On Thu, 9 Aug 2007, moe wrote:\n> > > \n> > > here's a test-case (should be safe to\n> > > copy/paste on linux, bash):\n> > \n> > moe: with current git (and thus the 1.5.3 release), the \"git status\" \n> > commands now take half a second for me, and the git commit takes just \n> > under a second.\n> > \n> > The *initial* commit that adds everything still takes almost 5 seconds, \n> > but that was due to generating the diffstat summary - with a \"-q\" on the \n> > commit line that too drops down to just under a second.\n> > \n> > In fact, the only thing that took more than a second for me with the \n> > current git is that initial \"git add .\", which took 1.791s for me. \n> > Considering that it had to hash all the 100,000 objects, I'm not \n> > surprised.\n> > \n> > Anyway, it would be good if you re-did your real work tree with current \n> > commit, just to verify. You have slower hardware than I do, but hopefully \n> > it is now just about as fast as it can be.\n>  \n> hi linus,\n> \n> thx for your efforts, the figures look very promising.\n> i'm out of town right now but will test when i get\n> stationary internet again (sometime tomorrow evening\n> i think).\n\nsorry for late followup, i was blocked on paid work\nfor longer than i expected.\n\ni can happily confirm what others have already reported;\nwith the patches applied git works well even for my\nbigger repo.\n\ngit status              : 0m1.036s\ngit commit (single file): 0m1.846s\n\nhttp://www.gosimpsons.com/ProdImages/krustysealkeychain.jpg\n\n\nregards, moe\n"}]}