{"thread":{"id":"11056","subject":"Some git performance measurements..","startedAt":"2007-11-29T02:49:04Z","lastAt":"2007-12-08T23:04:03Z","messageCount":28,"participants":["Linus Torvalds","Nicolas Pitre","Junio C Hamano","Jakub Narebski","Steffen Prohaska","Joachim B Haga","Federico Mena Quintero","Mike Ralphson","Johannes Schindelin","Brian Downing"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"61356","messageId":"alpine.LFD.0.9999.0711281747450.8458@woody.linux-foundation.org","threadId":"11056","inReplyTo":null,"subject":"Some git performance measurements..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-29T02:49:04Z","receivedAt":"2007-11-29T02:49:04Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nSo, today, I finally started looking a bit at one of the only remaining \nperformance issues that I'm aware of: git behaviour under cold-cache and \nparticularly with a slow laptop harddisk isn't as nice as I wish it should \nbe.\n\nSadly, one big reason for performance downsides is actually hard to \nmeasure: since we mmap() all the really critical data structures (the \npack-file index and data), it doesn't show up really well in any of the \notherwise really useful performance tools (eg strace and ltrace), because \nthe bulk of the time is actually spent not in libraries or in system \ncalls, but simply on regular instructions that take a page fault.\n\nNot a lot that I see we can do about that, unless we can make the \npack-files even denser.\n\nBut one very interesting thing I did notice: some loads open the \n\".gitignore\" files *way* too much. Even in cases where we really don't \ncare. And when the caches are cold, that's actually very expensive, even \nif - and perhaps _especially_when_ - the file doesn't exist at all (ie \nsome filesystems that don't use hashes will look through the whole \ndirectory before they see that it's empty).\n\nAn example of totally unnecessary .gitignore files is what a plain \"git \ncheckout\" with no arguments ends up doing:\n\n\tgit read-tree -m -u --exclude-per-directory=.gitignore HEAD HEAD\n\nwhich is *really* quite expensive, and a lot of the cost is trying to open \na .gitignore file in each subdirectory that are never even used.\n\nJust to give a feel for *how* expensive that stupid .gitignore thing is, \nhere's a pretty telling comparison of using --exclude-per-directory and \nnot using it:\n\nWith totally pointless --exclude-per-directory (aka \"git checkout\"):\n\n\t[torvalds@woody linux]$ time git read-tree -m -u --exclude-per-directory=.gitignore HEAD HEAD\n\treal    0m13.475s\n\tuser    0m0.108s\n\tsys     0m0.228s\n\nWithout:\n\n\t[torvalds@woody linux]$ time git read-tree -m -u HEAD HEAD\n\treal    0m5.923s\n\tuser    0m0.100s\n\tsys     0m0.044s\n\nnow, I'm not all that happy about that latter six-second time either, but \nboth of the above numbers were done with completely cold caches (ie after \nhaving done a \"echo 3 > /proc/sys/vm/drop_caches\" as root).\n\nWith hot caches, both of the numbers are under a tenth of a second (in \nfact, they are very close: 0.092s and 0.096s respectively), but the \ncold-cache case really shows just how horrible it is to (try to) open many \nfiles.\n\nDoing an open (or an lstat) on individual files will be a totally \nsynchronous operation, with no room for read-ahead etc, so even if your \ndisk in *theory* gets 80MB/s off the platter, when you do an open() or \nlstat(), you're basically doing three or four small data-dependent IO \noperations, and as a result even a fast disk will take almost a hundredth \nof a second per open/lstat operation.\n\nLess than a hundredth of a second may not sound much, but when we have \n1700+ directories in the kernel trees, doing that for each possible \n.gitignore file is really really expensive!\n\n(Doing an \"lstat()\" of each file is much cheaper in comparison, because at \nleast you'll get several director entries and probably a few related \ninodes with each IO. But opening just _one_ file per directory like the \n.gitignore code does, really kills your IO throughput)\n\nNow, timings like these are why I'm looking forward to SSD's. They may \nhave the same throughput as a disk, but they can do thousands of dependent \nIOPS, and help latency-bound cases like this by an order of magnitude. But \nwhen we're doing those .gitignore file reads totally unnecassarily, that \njust hurts..\n\n\t\t\tLinus\n"},{"id":"61357","messageId":"alpine.LFD.0.9999.0711281852160.8458@woody.linux-foundation.org","threadId":"11056","inReplyTo":"alpine.LFD.0.9999.0711281747450.8458@woody.linux-foundation.org","subject":"Re: Some git performance measurements..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-29T03:14:50Z","receivedAt":"2007-11-29T03:14:50Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 28 Nov 2007, Linus Torvalds wrote:\n> \n> Sadly, one big reason for performance downsides is actually hard to \n> measure: since we mmap() all the really critical data structures (the \n> pack-file index and data), it doesn't show up really well in any of the \n> otherwise really useful performance tools (eg strace and ltrace), because \n> the bulk of the time is actually spent not in libraries or in system \n> calls, but simply on regular instructions that take a page fault.\n\nSide note: while the \".gitignore\" issue actually overshadowed everything \nelse for things like \"git checkout\" and \"git merge\", I do have some traces \nfor page faults too. They're kind of interesting, but actually show that \nwe do reasonably well in this area - certainly much better than if we \ntried to keep things in multiple independent files.\n\nThe pack-files (both index and data) are accessed somewhat randomly, but \nthere is still enough locality that doing read-ahead and clustering really \ndoes help.\n\nSo while \"git checkout\" actually end up reading a lot of git \"tree\" \nobjects (as many tree objects as there are .gitignore files that we try to \nopen unnecessarily!), we actually spend a *lot* less time on the pack-file \noperations than we do on trying to do the futile \".gitignore\" opens in \nevery directory. \n\nIf somebody cares, I do have the page fault traces on those things for the \nsame \"git checkout\" that had the horrid .gitignore behaviour. What's \ninteresting is:\n\n - the pack-file really does get accessed in nice increasing patterns for \n   the top-of-tree. So the fact that we sort objects \"topologically\" does \n   actually seem to work pretty well (yeah, it was obvious, but it's nice \n   to have a real page fault trace that shows the effect!)\n\n   The accesses seemed to be *totally* ordered. There were obvously gaps \n   (ie they weren't *dense*, since we only looked at one version of the \n   trees in \"git checkout\"), but at the same time, it certainly wasn't \n   random or causing any horrible seeking back-and-forth.\n\n - we're *reasonably* dense in pack-file accesses. Not wonderful, but not \n   horrible. That in turn means that read-ahead kicks in and works ok. The \n   pattern for the pack-file hat I caught looks like this (the format is \n   \"pageindex: cycles-to-fill-in-kernel\"):\n\n\t6810: 15202545\n\t6811: 353\n\t6812: 267\n\t6813: 476\n\t6814: 559\n\t6826: 1086510\n\t6878: 13948057\n\t6894: 9756446\n\t6896: 300\n\t6899: 307\n\t6903: 319\n\t6907: 293\n\t6910: 666120\n\t6912: 401\n\t6913: 330\n\t6916: 401\n\t6918: 303\n\t6919: 330\n\t6931: 784373\n\t6943: 405\n\t6944: 187\n\t6945: 315\n\t...\n\n   and here you can see that read-ahead works fine about 60% of the time,\n   with most pages taking just 300-500 CPU cycles (no actual IO, of \n   course!) to find/lookup, but then when there are discontinuities we \n   have the cost of the real IO, and the cost for those obviously then \n   jumps into the tens of millions of cycles (ie we're talking \n   several milliseconds).\n\n - the index accesses are much more \"random\": the initial 256-way fan-out \n   followed by the binary search causes the access patterns to look very \n   different:\n\n\t0: 28367707\n\t136: 18867574\n\t140: 221280\n\t141: 745890\n\t142: 284427\n\t143: 338\n\t381: 9787459\n\t377: 394\n\t375: 255\n\t376: 248\n\t3344: 29885989\n\t3347: 334\n\t3346: 255\n\t3684: 7251911\n\t1055: 12954064\n\t1052: 386\n\t1050: 251\n\t1049: 240\n\t1947: 10501455\n\t1944: 382\n\t1946: 262\n\n   where it doesn't even read-ahead at all in the beginning (because it \n   looks entirely random), but the kernel eventually *does* actually go \n   into read-ahead mode pretty soon simply because once it gets into the \n   binary search thing, the data entries are close enough to be in \n   adjacent pages, and it all looks ok.\n\n   As a result, by the end of the run, all the index file pages have been \n   cached, and we're getting uniformly low numbers (ie in the hundreds of \n   cycles, not millions):\n\n\t...\n\t490: 810\n\t489: 352\n\t488: 334\n\t2254: 907\n\t91: 484\n\t3580: 776\n\t962: 806\n\t522: 761\n\t2494: 514\n\t805: 653\n\t177: 495\n\t176: 375\n\t2861: 439\n\t649: 660\n\t648: 518\n\t...\n\n   so the pack index file access patterns are much less predictable, but \n   since the pack index is so dense and relatively small, that doesn't end \n   up being a problem in the long run, and only in the beginning do we pay \n   a highish cost for having to read it into memory.\n\nIn other words: we do ok. I think we could do better (and an SSD would \ncertainly help, since we're never going to do long and 100% contiguous \nIO), but I was expecting to see *big* trouble, and it really wasn't that \nhorrid.\n\nThat said, I think there's something subtly wrong in our pack-file \nsorting, and it should be more contiguous when we just do tree object \naccesses on the top commit. I was really hoping that all the top-level \ntrees should be written entirely together, but I wonder if the \"write out \ndeltas first\" thing causes us to have those big gaps in between.\n\n\t\t\tLinus\n"},{"id":"61362","messageId":"alpine.LFD.0.99999.0711282244190.9605@xanadu.home","threadId":"11056","inReplyTo":"alpine.LFD.0.9999.0711281852160.8458@woody.linux-foundation.org","subject":"Re: Some git performance measurements..","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-11-29T03:59:37Z","receivedAt":"2007-11-29T03:59:37Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 28 Nov 2007, Linus Torvalds wrote:\n\n>  - the index accesses are much more \"random\": the initial 256-way fan-out \n>    followed by the binary search causes the access patterns to look very \n>    different:\n> \n> \t0: 28367707\n> \t136: 18867574\n> \t140: 221280\n> \t141: 745890\n> \t142: 284427\n> \t143: 338\n> \t381: 9787459\n> \t377: 394\n> \t375: 255\n> \t376: 248\n> \t3344: 29885989\n> \t3347: 334\n> \t3346: 255\n> \t3684: 7251911\n> \t1055: 12954064\n> \t1052: 386\n> \t1050: 251\n> \t1049: 240\n> \t1947: 10501455\n> \t1944: 382\n> \t1946: 262\n> \n>    where it doesn't even read-ahead at all in the beginning (because it \n>    looks entirely random), but the kernel eventually *does* actually go \n>    into read-ahead mode pretty soon simply because once it gets into the \n>    binary search thing, the data entries are close enough to be in \n>    adjacent pages, and it all looks ok.\n\nDid you try with version 2 of the pack index?  Because it should have \nsomewhat better locality as the object SHA1 and their offset are split \ninto separate tables.\n\n> That said, I think there's something subtly wrong in our pack-file \n> sorting, and it should be more contiguous when we just do tree object \n> accesses on the top commit. I was really hoping that all the top-level \n> trees should be written entirely together, but I wonder if the \"write out \n> deltas first\" thing causes us to have those big gaps in between.\n\nTree objects aren't all together.  Related blob objects are interlaced \nwith those tree objects.  But for a checkout that should actually \ncorrespond to a nice linear access.\n\nAnd deltas aren't written first, but rather their base object.  And \nbecause deltas are based on newer objects, in theory the top commit \nshouldn't have any delta at all, and the second commit should have all \nthe base objects for its deltas already written out a part of the first \ncommit.  At least that's what a perfect data set would produce.  Last \ntime I checked, there was about 20% of the deltas that happened to be in \nthe other direction, i.e. the deltified object was younger than its base \nobject, most probably because the new version of the file shrunk instead \nof growing which is against the assumption in the delta search \nobject sort.  But again, because the base object is needed to resolve \nthe delta, it will be read anyway.\n\n\nNicolas\n"},{"id":"61364","messageId":"alpine.LFD.0.9999.0711282022470.8458@woody.linux-foundation.org","threadId":"11056","inReplyTo":"alpine.LFD.0.99999.0711282244190.9605@xanadu.home","subject":"Re: Some git performance measurements..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-29T04:32:21Z","receivedAt":"2007-11-29T04:32:21Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 28 Nov 2007, Nicolas Pitre wrote:\n> \n> Tree objects aren't all together.  Related blob objects are interlaced \n> with those tree objects.\n\nYeah, I noticed that a few minutes after saying this.\n\n> But for a checkout that should actually correspond to a nice linear \n> access.\n\nFor the initial check-out, yes. But the thing I timed was just a plain \n\"git checkout\", which won't actually do any of the blobs if they already \nexist checked-out (which I obviously had), which explains the non-dense \npatterns.\n\nThe reason I care about \"git checkout\" (which is totally uninteresting in \nitself) is that it is a trivial use-case that fairly closely approximates \ntwo common cases that are *not* uninteresting: switching branches with \nmost files unaffected and a fast-forward merge (both of which are the \n\"two-way merge\" special case).\n\nI also suspect it is pretty close to a real three-way merge (again, with \njust a few files changed).\n\nIOW, there's a lot of these \"tree operations\" that actually leave 99% of \nthe tree totally unchanged, at least in the kernel. Even a fairly big \nmerge tends to change just a few hundred files. And when there are 23,000 \nfiles in the tree, a few hundred files is a fairly small percentage!\n\nSo it's actually fairly common to have \"git checkout\"-like behaviour with \nno blobs needing to be updated, and the \"initial checkout\" is in fact \nlikely a less usual case. I wonder if we should make the pack-file have \nall the object types in separate regions (we already do that for commits, \nsince \"git rev-list\" kind of operations are dense in the commit).\n\nMaking the tree objects dense (the same way the commit objects are) might \nalso conceivably speed up \"git blame\" and path history simplification, \nsince those also tend to be \"dense\" in the tree history but don't actually \nlook at the blobs themselves until they change.\n\n\t\tLinus\n"},{"id":"61365","messageId":"7vr6i9y6ju.fsf@gitster.siamese.dyndns.org","threadId":"11056","inReplyTo":"alpine.LFD.0.9999.0711281747450.8458@woody.linux-foundation.org","subject":"Re: Some git performance measurements..","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-11-29T05:17:09Z","receivedAt":"2007-11-29T05:17:09Z","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> Less than a hundredth of a second may not sound much, but when we have \n> 1700+ directories in the kernel trees, doing that for each possible \n> .gitignore file is really really expensive!\n\nThe only thing that wants to use excluded() in the unpack_trees()\ncodepath is the code to allow overwriting an existing, untracked file in\nverify_absent().  When we find an untracked file at the same path as we\nare just trying to check out a file, we allow overwriting it only if\nthat file is \"ignored\".\n\nBut the way the unpack_trees_rec() and the gitignore handling in dir.c\nare structured currently means we do push/pop exclude-per-directory\nstack as we enter and leave a new subdirectory.  We do not do this\nlazily on demand.\n\nThe newer gitattributes subsystem maintains a similar per-directory data\nstructure but this is purely done on-demand; until somebody asks \"what\nare the attrs for this path\", we do not read .gitattributes file.  We\nshould be able to restructure exclude-per-directory code in a similar\nway.\n"},{"id":"61387","messageId":"7vy7chuzhz.fsf_-_@gitster.siamese.dyndns.org","threadId":"11056","inReplyTo":"7vr6i9y6ju.fsf@gitster.siamese.dyndns.org","subject":"[PATCH] per-directory-exclude: lazily read .gitignore files","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-11-29T10:17:44Z","receivedAt":"2007-11-29T10:17:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Operations that walk directories or trees, which potentially need to\nconsult the .gitignore files, used to always try to open the .gitignore\nfile every time they entered a new directory, even when they ended up\nnot needing to call excluded() function to see if a path in the\ndirectory is ignored.\n\nThis changes the directory walking API to remove the need to call these\ntwo functions.  Instead, the directory walk data structure caches the\ndata used by excluded() function the last time, and lazily reuses it as\nmuch as possible.  Among the data the last check used, the ones from\ndeeper directories that the path we are checking is outside are\ndiscarded, data from the common leading directories are reused, and then\nthe directories between the common directory and the directory the path\nbeing checked is in are checked for .gitignore file.  This is very\nsimilar to the way gitattributes are handled.\n\nThis API change also fixes \"ls-files -c -i\", which called excluded()\nwithout setting up the gitignore data via the old push/pop functions.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n\n Junio C Hamano <gitster@pobox.com> writes:\n > Linus Torvalds <torvalds@linux-foundation.org> writes:\n >\n >> Less than a hundredth of a second may not sound much, but when we have \n >> 1700+ directories in the kernel trees, doing that for each possible \n >> .gitignore file is really really expensive!\n >\n > The only thing that wants to use excluded() in the unpack_trees()\n > codepath is the code to allow overwriting an existing, untracked file in\n > verify_absent().  When we find an untracked file at the same path as we\n > are just trying to check out a file, we allow overwriting it only if\n > that file is \"ignored\".\n > ...\n > The newer gitattributes subsystem maintains a similar per-directory data\n > structure but this is purely done on-demand; until somebody asks \"what\n > are the attrs for this path\", we do not read .gitattributes file.  We\n > should be able to restructure exclude-per-directory code in a similar\n > way.\n\n I haven't seriously benched this, other than the same read-tree test\n you mentioned.  With the good locality the directory walking (both by\n read_directory() aka ls-files and unpack_trees() aka read-tree) tends\n to have, checks for paths from the same directory come next to each\n other, and that seems to help.\n\n dir.c          |  103 +++++++++++++++++++++++++++++---------------------------\n dir.h          |   32 ++++++++++-------\n unpack-trees.c |    6 ---\n 3 files changed, 72 insertions(+), 69 deletions(-)\n\ndiff --git a/dir.c b/dir.c\nindex 7c97483..d448902 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -151,6 +151,7 @@ void add_exclude(const char *string, const char *base,\n static int add_excludes_from_file_1(const char *fname,\n \t\t\t\t    const char *base,\n \t\t\t\t    int baselen,\n+\t\t\t\t    char **buf_p,\n \t\t\t\t    struct exclude_list *which)\n {\n \tstruct stat st;\n@@ -171,6 +172,8 @@ static int add_excludes_from_file_1(const char *fname,\n \t\tgoto err;\n \tclose(fd);\n \n+\tif (buf_p)\n+\t\t*buf_p = buf;\n \tbuf[size++] = '\\n';\n \tentry = buf;\n \tfor (i = 0; i < size; i++) {\n@@ -192,31 +195,63 @@ static int add_excludes_from_file_1(const char *fname,\n \n void add_excludes_from_file(struct dir_struct *dir, const char *fname)\n {\n-\tif (add_excludes_from_file_1(fname, \"\", 0,\n+\tif (add_excludes_from_file_1(fname, \"\", 0, NULL,\n \t\t\t\t     &dir->exclude_list[EXC_FILE]) < 0)\n \t\tdie(\"cannot use %s as an exclude file\", fname);\n }\n \n-int push_exclude_per_directory(struct dir_struct *dir, const char *base, int baselen)\n+static void prep_exclude(struct dir_struct *dir, const char *base, int baselen)\n {\n-\tchar exclude_file[PATH_MAX];\n-\tstruct exclude_list *el = &dir->exclude_list[EXC_DIRS];\n-\tint current_nr = el->nr;\n-\n-\tif (dir->exclude_per_dir) {\n-\t\tmemcpy(exclude_file, base, baselen);\n-\t\tstrcpy(exclude_file + baselen, dir->exclude_per_dir);\n-\t\tadd_excludes_from_file_1(exclude_file, base, baselen, el);\n+\tstruct exclude_list *el;\n+\tstruct exclude_stack *stk = NULL;\n+\tint current;\n+\n+\tif ((!dir->exclude_per_dir) ||\n+\t    (baselen + strlen(dir->exclude_per_dir) >= PATH_MAX))\n+\t\treturn; /* too long a path -- ignore */\n+\n+\t/* Pop the ones that are not the prefix of the path being checked. */\n+\tel = &dir->exclude_list[EXC_DIRS];\n+\twhile ((stk = dir->exclude_stack) != NULL) {\n+\t\tif (stk->baselen <= baselen &&\n+\t\t    !strncmp(dir->basebuf, base, stk->baselen))\n+\t\t\tbreak;\n+\t\tdir->exclude_stack = stk->prev;\n+\t\twhile (stk->exclude_ix < el->nr)\n+\t\t\tfree(el->excludes[--el->nr]);\n+\t\tfree(stk->filebuf);\n+\t\tfree(stk);\n \t}\n-\treturn current_nr;\n-}\n \n-void pop_exclude_per_directory(struct dir_struct *dir, int stk)\n-{\n-\tstruct exclude_list *el = &dir->exclude_list[EXC_DIRS];\n+\t/* Read from the parent directories and push them down. */\n+\tcurrent = stk ? stk->baselen : -1;\n+\twhile (current < baselen) {\n+\t\tstruct exclude_stack *stk = xcalloc(1, sizeof(*stk));\n+\t\tconst char *cp;\n \n-\twhile (stk < el->nr)\n-\t\tfree(el->excludes[--el->nr]);\n+\t\tif (current < 0) {\n+\t\t\tcp = base;\n+\t\t\tcurrent = 0;\n+\t\t}\n+\t\telse {\n+\t\t\tcp = strchr(base + current + 1, '/');\n+\t\t\tif (!cp)\n+\t\t\t\tdie(\"oops in prep_exclude\");\n+\t\t\tcp++;\n+\t\t}\n+\t\tstk->prev = dir->exclude_stack;\n+\t\tstk->baselen = cp - base;\n+\t\tstk->exclude_ix = el->nr;\n+\t\tmemcpy(dir->basebuf + current, base + current,\n+\t\t       stk->baselen - current);\n+\t\tstrcpy(dir->basebuf + stk->baselen, dir->exclude_per_dir);\n+\t\tadd_excludes_from_file_1(dir->basebuf,\n+\t\t\t\t\t dir->basebuf, stk->baselen,\n+\t\t\t\t\t &stk->filebuf, el);\n+\t\tdir->exclude_stack = stk;\n+\t\tcurrent = stk->baselen;\n+\t}\n+\tdir->basebuf[baselen] = '\\0';\n }\n \n /* Scan the list and let the last match determines the fate.\n@@ -283,6 +318,7 @@ int excluded(struct dir_struct *dir, const char *pathname)\n \tconst char *basename = strrchr(pathname, '/');\n \tbasename = (basename) ? basename+1 : pathname;\n \n+\tprep_exclude(dir, pathname, basename-pathname);\n \tfor (st = EXC_CMDL; st <= EXC_FILE; st++) {\n \t\tswitch (excluded_1(pathname, pathlen, basename, &dir->exclude_list[st])) {\n \t\tcase 0:\n@@ -500,13 +536,10 @@ static int read_directory_recursive(struct dir_struct *dir, const char *path, co\n \tint contents = 0;\n \n \tif (fdir) {\n-\t\tint exclude_stk;\n \t\tstruct dirent *de;\n \t\tchar fullname[PATH_MAX + 1];\n \t\tmemcpy(fullname, base, baselen);\n \n-\t\texclude_stk = push_exclude_per_directory(dir, base, baselen);\n-\n \t\twhile ((de = readdir(fdir)) != NULL) {\n \t\t\tint len, dtype;\n \t\t\tint exclude;\n@@ -580,8 +613,6 @@ static int read_directory_recursive(struct dir_struct *dir, const char *path, co\n \t\t}\n exit_early:\n \t\tclosedir(fdir);\n-\n-\t\tpop_exclude_per_directory(dir, exclude_stk);\n \t}\n \n \treturn contents;\n@@ -650,37 +681,9 @@ static void free_simplify(struct path_simplify *simplify)\n int read_directory(struct dir_struct *dir, const char *path, const char *base, int baselen, const char **pathspec)\n {\n \tstruct path_simplify *simplify = create_simplify(pathspec);\n-\tchar *pp = NULL;\n-\n-\t/*\n-\t * Make sure to do the per-directory exclude for all the\n-\t * directories leading up to our base.\n-\t */\n-\tif (baselen) {\n-\t\tif (dir->exclude_per_dir) {\n-\t\t\tchar *p;\n-\t\t\tpp = xmalloc(baselen+1);\n-\t\t\tmemcpy(pp, base, baselen+1);\n-\t\t\tp = pp;\n-\t\t\twhile (1) {\n-\t\t\t\tchar save = *p;\n-\t\t\t\t*p = 0;\n-\t\t\t\tpush_exclude_per_directory(dir, pp, p-pp);\n-\t\t\t\t*p++ = save;\n-\t\t\t\tif (!save)\n-\t\t\t\t\tbreak;\n-\t\t\t\tp = strchr(p, '/');\n-\t\t\t\tif (p)\n-\t\t\t\t\tp++;\n-\t\t\t\telse\n-\t\t\t\t\tp = pp + baselen;\n-\t\t\t}\n-\t\t}\n-\t}\n \n \tread_directory_recursive(dir, path, base, baselen, 0, simplify);\n \tfree_simplify(simplify);\n-\tfree(pp);\n \tqsort(dir->entries, dir->nr, sizeof(struct dir_entry *), cmp_name);\n \tqsort(dir->ignored, dir->ignored_nr, sizeof(struct dir_entry *), cmp_name);\n \treturn dir->nr;\ndiff --git a/dir.h b/dir.h\nindex 82009dc..d8814dc 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -1,17 +1,6 @@\n #ifndef DIR_H\n #define DIR_H\n \n-/*\n- * We maintain three exclude pattern lists:\n- * EXC_CMDL lists patterns explicitly given on the command line.\n- * EXC_DIRS lists patterns obtained from per-directory ignore files.\n- * EXC_FILE lists patterns from fallback ignore files.\n- */\n-#define EXC_CMDL 0\n-#define EXC_DIRS 1\n-#define EXC_FILE 2\n-\n-\n struct dir_entry {\n \tunsigned int len;\n \tchar name[FLEX_ARRAY]; /* more */\n@@ -34,6 +23,13 @@ struct exclude_list {\n \t} **excludes;\n };\n \n+struct exclude_stack {\n+\tstruct exclude_stack *prev;\n+\tchar *filebuf;\n+\tint baselen;\n+\tint exclude_ix;\n+};\n+\n struct dir_struct {\n \tint nr, alloc;\n \tint ignored_nr, ignored_alloc;\n@@ -48,6 +44,18 @@ struct dir_struct {\n \t/* Exclude info */\n \tconst char *exclude_per_dir;\n \tstruct exclude_list exclude_list[3];\n+\t/*\n+\t * We maintain three exclude pattern lists:\n+\t * EXC_CMDL lists patterns explicitly given on the command line.\n+\t * EXC_DIRS lists patterns obtained from per-directory ignore files.\n+\t * EXC_FILE lists patterns from fallback ignore files.\n+\t */\n+#define EXC_CMDL 0\n+#define EXC_DIRS 1\n+#define EXC_FILE 2\n+\n+\tstruct exclude_stack *exclude_stack;\n+\tchar basebuf[PATH_MAX];\n };\n \n extern int common_prefix(const char **pathspec);\n@@ -58,8 +66,6 @@ extern int common_prefix(const char **pathspec);\n extern int match_pathspec(const char **pathspec, const char *name, int namelen, int prefix, char *seen);\n \n extern int read_directory(struct dir_struct *, const char *path, const char *base, int baselen, const char **pathspec);\n-extern int push_exclude_per_directory(struct dir_struct *, const char *, int);\n-extern void pop_exclude_per_directory(struct dir_struct *, int);\n \n extern int excluded(struct dir_struct *, const char *);\n extern void add_excludes_from_file(struct dir_struct *, const char *fname);\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex aea16ad..e9eb795 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -71,12 +71,8 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len,\n \tint remove;\n \tint baselen = strlen(base);\n \tint src_size = len + 1;\n-\tint i_stk = i_stk;\n \tint retval = 0;\n \n-\tif (o->dir)\n-\t\ti_stk = push_exclude_per_directory(o->dir, base, strlen(base));\n-\n \tdo {\n \t\tint i;\n \t\tconst char *first;\n@@ -255,8 +251,6 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len,\n \t} while (1);\n \n  leave_directory:\n-\tif (o->dir)\n-\t\tpop_exclude_per_directory(o->dir, i_stk);\n \treturn retval;\n }\n \n-- \n1.5.3.6.2064.g2e22f\n"},{"id":"61409","messageId":"alpine.LFD.0.99999.0711291208060.9605@xanadu.home","threadId":"11056","inReplyTo":"alpine.LFD.0.9999.0711282022470.8458@woody.linux-foundation.org","subject":"Re: Some git performance measurements..","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-11-29T17:25:39Z","receivedAt":"2007-11-29T17:25:39Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 28 Nov 2007, Linus Torvalds wrote:\n\n> On Wed, 28 Nov 2007, Nicolas Pitre wrote:\n> \n> > But for a checkout that should actually correspond to a nice linear \n> > access.\n> \n> For the initial check-out, yes. But the thing I timed was just a plain \n> \"git checkout\", which won't actually do any of the blobs if they already \n> exist checked-out (which I obviously had), which explains the non-dense \n> patterns.\n> \n> The reason I care about \"git checkout\" (which is totally uninteresting in \n> itself) is that it is a trivial use-case that fairly closely approximates \n> two common cases that are *not* uninteresting: switching branches with \n> most files unaffected and a fast-forward merge (both of which are the \n> \"two-way merge\" special case).\n\n[...]\n\n> So it's actually fairly common to have \"git checkout\"-like behaviour with \n> no blobs needing to be updated, and the \"initial checkout\" is in fact \n> likely a less usual case. I wonder if we should make the pack-file have \n> all the object types in separate regions (we already do that for commits, \n> since \"git rev-list\" kind of operations are dense in the commit).\n> \n> Making the tree objects dense (the same way the commit objects are) might \n> also conceivably speed up \"git blame\" and path history simplification, \n> since those also tend to be \"dense\" in the tree history but don't actually \n> look at the blobs themselves until they change.\n\nWell, see below for the patch that actually split the pack data into \nobjects of the same type.  Doing that \"git checkout\" on the kernel tree \ndid improve things for me although not spectacularly.\n\nCurrent Git warm cache:\t\t0.532s\nCurrent Git cold cache:\t\t17.4s\n\nPatched Git warm cache:\t\t0.521s\nPatched Git cold cache:\t\t14.2s\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 4f44658..b655efd 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -585,22 +585,43 @@ static off_t write_one(struct sha1file *f,\n \treturn offset + size;\n }\n \n+static int sort_by_type(const void *_a, const void *_b)\n+{\n+\tconst struct object_entry *a = *(struct object_entry **)_a;\n+\tconst struct object_entry *b = *(struct object_entry **)_b;\n+\n+\t/*\n+\t * Preserve recency order for objects of the same type  and reused deltas.\n+\t */\n+\tif(a->type == OBJ_REF_DELTA || a->type == OBJ_OFS_DELTA ||\n+\t   b->type == OBJ_REF_DELTA || b->type == OBJ_OFS_DELTA ||\n+\t   a->type == b->type)\n+\t\treturn (a < b) ? -1 : 1;\n+\treturn a->type - b->type;\n+}\n+\n /* forward declaration for write_pack_file */\n static int adjust_perm(const char *path, mode_t mode);\n \n static void write_pack_file(void)\n {\n-\tuint32_t i = 0, j;\n+\tuint32_t i, j;\n \tstruct sha1file *f;\n \toff_t offset, offset_one, last_obj_offset = 0;\n \tstruct pack_header hdr;\n \tint do_progress = progress >> pack_to_stdout;\n \tuint32_t nr_remaining = nr_result;\n+\tstruct object_entry **sorted_by_type;\n \n \tif (do_progress)\n \t\tprogress_state = start_progress(\"Writing objects\", nr_result);\n \twritten_list = xmalloc(nr_objects * sizeof(*written_list));\n+\tsorted_by_type = xmalloc(nr_objects * sizeof(*sorted_by_type));\n+\tfor (i = 0; i < nr_objects; i++)\n+\t\tsorted_by_type[i] = objects + i;\n+\tqsort(sorted_by_type, nr_objects, sizeof(*sorted_by_type), sort_by_type);\n \n+\ti = 0;\n \tdo {\n \t\tunsigned char sha1[20];\n \t\tchar *pack_tmp_name = NULL;\n@@ -625,7 +646,7 @@ static void write_pack_file(void)\n \t\tnr_written = 0;\n \t\tfor (; i < nr_objects; i++) {\n \t\t\tlast_obj_offset = offset;\n-\t\t\toffset_one = write_one(f, objects + i, offset);\n+\t\t\toffset_one = write_one(f, sorted_by_type[i], offset);\n \t\t\tif (!offset_one)\n \t\t\t\tbreak;\n \t\t\toffset = offset_one;\n@@ -681,6 +702,7 @@ static void write_pack_file(void)\n \t\tnr_remaining -= nr_written;\n \t} while (nr_remaining && i < nr_objects);\n \n+\tfree(sorted_by_type);\n \tfree(written_list);\n \tstop_progress(&progress_state);\n \tif (written != nr_result)\n"},{"id":"61412","messageId":"alpine.LFD.0.9999.0711290945060.8458@woody.linux-foundation.org","threadId":"11056","inReplyTo":"alpine.LFD.0.99999.0711291208060.9605@xanadu.home","subject":"Re: Some git performance measurements..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-29T17:48:19Z","receivedAt":"2007-11-29T17:48:19Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 29 Nov 2007, Nicolas Pitre wrote:\n> \n> Well, see below for the patch that actually split the pack data into \n> objects of the same type.  Doing that \"git checkout\" on the kernel tree \n> did improve things for me although not spectacularly.\n\nUmm. See my earlier numbers. For \"git checkout\" with cold cache, the \n*bulk* of the time is actually the \".gitignore\" file lookups, so if you \nsee a three-second improvement out of 17s, it may not look spectacular, \nbut considering that probably 10s of those 17s were something *else* going \non, I suspect that if you really did just a plain \"git checkout\", you \nactually *do* have a spectacular improvement of roughly 7s -> 4s!\n\nTry with\n\n\ttime git read-tree -m -u HEAD HEAD > /dev/null\n\ninstead.\n\nBut if that is what you already did, then yeah, the performance \nimprovement for cold-cache wasn't as big as I was hoping for.\n\n\t\tLinus\n"},{"id":"61414","messageId":"alpine.LFD.0.99999.0711291333460.9605@xanadu.home","threadId":"11056","inReplyTo":"alpine.LFD.0.9999.0711290945060.8458@woody.linux-foundation.org","subject":"Re: Some git performance measurements..","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-11-29T18:52:55Z","receivedAt":"2007-11-29T18:52:55Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 29 Nov 2007, Linus Torvalds wrote:\n\n> \n> \n> On Thu, 29 Nov 2007, Nicolas Pitre wrote:\n> > \n> > Well, see below for the patch that actually split the pack data into \n> > objects of the same type.  Doing that \"git checkout\" on the kernel tree \n> > did improve things for me although not spectacularly.\n> \n> Umm. See my earlier numbers. For \"git checkout\" with cold cache, the \n> *bulk* of the time is actually the \".gitignore\" file lookups, so if you \n> see a three-second improvement out of 17s, it may not look spectacular, \n> but considering that probably 10s of those 17s were something *else* going \n> on, I suspect that if you really did just a plain \"git checkout\", you \n> actually *do* have a spectacular improvement of roughly 7s -> 4s!\n> \n> Try with\n> \n> \ttime git read-tree -m -u HEAD HEAD > /dev/null\n> \n> instead.\n\nOh!  OK then.\n\nCurrent, cold cache:\t\t5.248s\nCurrent, warm cache:\t\t0.185s\n\nPatched, cold cache:\t\t3.337s\nPatched, warm cache:\t\t0.183s\n\nSo yes, the improvement is more significant then, although the cold \ncache timings vary quite a lot between successive tries.\n\n\nNicolas\n"},{"id":"61449","messageId":"finmvm$da8$1@ger.gmane.org","threadId":"11056","inReplyTo":"alpine.LFD.0.99999.0711291208060.9605@xanadu.home","subject":"Re: Some git performance measurements..","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2007-11-30T00:54:13Z","receivedAt":"2007-11-30T00:54:13Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"<opublikowany i wysłany>\n\n[Cc: git@vger.kernel.org, Nicolas Pitre <nico@cam.org>, \n Linus Torvalds <torvalds@linux-foundation.org>]\n\nNicolas Pitre wrote:\n\n> Well, see below for the patch that actually split the pack data into \n> objects of the same type.  Doing that \"git checkout\" on the kernel tree \n> did improve things for me although not spectacularly.\n\n> +static int sort_by_type(const void *_a, const void *_b)\n> +{\n> +     const struct object_entry *a = *(struct object_entry **)_a;\n> +     const struct object_entry *b = *(struct object_entry **)_b;\n> +\n> +     /*\n> +      * Preserve recency order for objects of the same type  and reused deltas.\n> +      */\n> +     if(a->type == OBJ_REF_DELTA || a->type == OBJ_OFS_DELTA ||\n> +        b->type == OBJ_REF_DELTA || b->type == OBJ_OFS_DELTA ||\n> +        a->type == b->type)\n> +             return (a < b) ? -1 : 1;\n> +     return a->type - b->type;\n> +}\n\n> +     qsort(sorted_by_type, nr_objects, sizeof(*sorted_by_type), sort_by_type);\n\nIsn't there a better way to do this sorting? What is needed here is\n(stable) _bucket_ sort / _pigeonhole_ sort (or counting sort), which\nis O(n); quicksort is perhaps simpler to use, but I'm not sure if\nfaster in this situation.\n\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"61466","messageId":"alpine.LFD.0.9999.0711291812530.8458@woody.linux-foundation.org","threadId":"11056","inReplyTo":"finmvm$da8$1@ger.gmane.org","subject":"Re: Some git performance measurements..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-30T02:21:06Z","receivedAt":"2007-11-30T02:21:06Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 30 Nov 2007, Jakub Narebski wrote:\n> \n> Isn't there a better way to do this sorting? What is needed here is\n> (stable) _bucket_ sort / _pigeonhole_ sort (or counting sort), which\n> is O(n); quicksort is perhaps simpler to use, but I'm not sure if\n> faster in this situation.\n\nActually, I doubt you need to do any sorting at all: what would be easiest \nwould be to simply change \"traverse_commit_list()\" to use different lists \nfor different object types, and just output them in type order (semi-sane \norder choice: commits first, then tags, then trees, and finally blobs).\n\nTa-daa! All done! Magic! No sorting required, because all the objects got \noutput in the right order without any extra sort phase!\n\nSomething like the appended (untested! lots of! exclamation marks! \nReally!)\n\n\t\tLinus\n\n---\n list-objects.c |   36 ++++++++++++++++++++++--------------\n 1 files changed, 22 insertions(+), 14 deletions(-)\n\ndiff --git a/list-objects.c b/list-objects.c\nindex 4ef58e7..a046f37 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -49,7 +49,6 @@ static void process_blob(struct rev_info *revs,\n  */\n static void process_gitlink(struct rev_info *revs,\n \t\t\t    const unsigned char *sha1,\n-\t\t\t    struct object_array *p,\n \t\t\t    struct name_path *path,\n \t\t\t    const char *name)\n {\n@@ -58,7 +57,8 @@ static void process_gitlink(struct rev_info *revs,\n \n static void process_tree(struct rev_info *revs,\n \t\t\t struct tree *tree,\n-\t\t\t struct object_array *p,\n+\t\t\t struct object_array *trees,\n+\t\t\t struct object_array *blobs,\n \t\t\t struct name_path *path,\n \t\t\t const char *name)\n {\n@@ -75,7 +75,7 @@ static void process_tree(struct rev_info *revs,\n \t\tdie(\"bad tree object %s\", sha1_to_hex(obj->sha1));\n \tobj->flags |= SEEN;\n \tname = xstrdup(name);\n-\tadd_object(obj, p, path, name);\n+\tadd_object(obj, trees, path, name);\n \tme.up = path;\n \tme.elem = name;\n \tme.elem_len = strlen(name);\n@@ -86,14 +86,14 @@ static void process_tree(struct rev_info *revs,\n \t\tif (S_ISDIR(entry.mode))\n \t\t\tprocess_tree(revs,\n \t\t\t\t     lookup_tree(entry.sha1),\n-\t\t\t\t     p, &me, entry.path);\n+\t\t\t\t     trees, blobs, &me, entry.path);\n \t\telse if (S_ISGITLINK(entry.mode))\n \t\t\tprocess_gitlink(revs, entry.sha1,\n-\t\t\t\t\tp, &me, entry.path);\n+\t\t\t\t\t&me, entry.path);\n \t\telse\n \t\t\tprocess_blob(revs,\n \t\t\t\t     lookup_blob(entry.sha1),\n-\t\t\t\t     p, &me, entry.path);\n+\t\t\t\t     blobs, &me, entry.path);\n \t}\n \tfree(tree->buffer);\n \ttree->buffer = NULL;\n@@ -138,10 +138,12 @@ void traverse_commit_list(struct rev_info *revs,\n {\n \tint i;\n \tstruct commit *commit;\n-\tstruct object_array objects = { 0, 0, NULL };\n+\tstruct object_array tags = { 0, 0, NULL };\n+\tstruct object_array trees = { 0, 0, NULL };\n+\tstruct object_array blobs = { 0, 0, NULL };\n \n \twhile ((commit = get_revision(revs)) != NULL) {\n-\t\tprocess_tree(revs, commit->tree, &objects, NULL, \"\");\n+\t\tprocess_tree(revs, commit->tree, &trees, &blobs, NULL, \"\");\n \t\tshow_commit(commit);\n \t}\n \tfor (i = 0; i < revs->pending.nr; i++) {\n@@ -152,25 +154,31 @@ void traverse_commit_list(struct rev_info *revs,\n \t\t\tcontinue;\n \t\tif (obj->type == OBJ_TAG) {\n \t\t\tobj->flags |= SEEN;\n-\t\t\tadd_object_array(obj, name, &objects);\n+\t\t\tadd_object_array(obj, name, &tags);\n \t\t\tcontinue;\n \t\t}\n \t\tif (obj->type == OBJ_TREE) {\n-\t\t\tprocess_tree(revs, (struct tree *)obj, &objects,\n+\t\t\tprocess_tree(revs, (struct tree *)obj, &trees, &blobs,\n \t\t\t\t     NULL, name);\n \t\t\tcontinue;\n \t\t}\n \t\tif (obj->type == OBJ_BLOB) {\n-\t\t\tprocess_blob(revs, (struct blob *)obj, &objects,\n+\t\t\tprocess_blob(revs, (struct blob *)obj, &blobs,\n \t\t\t\t     NULL, name);\n \t\t\tcontinue;\n \t\t}\n \t\tdie(\"unknown pending object %s (%s)\",\n \t\t    sha1_to_hex(obj->sha1), name);\n \t}\n-\tfor (i = 0; i < objects.nr; i++)\n-\t\tshow_object(&objects.objects[i]);\n-\tfree(objects.objects);\n+\tfor (i = 0; i < tags.nr; i++)\n+\t\tshow_object(&tags.objects[i]);\n+\tfor (i = 0; i < trees.nr; i++)\n+\t\tshow_object(&trees.objects[i]);\n+\tfor (i = 0; i < blobs.nr; i++)\n+\t\tshow_object(&blobs.objects[i]);\n+\tfree(tags.objects);\n+\tfree(trees.objects);\n+\tfree(blobs.objects);\n \tif (revs->pending.nr) {\n \t\tfree(revs->pending.objects);\n \t\trevs->pending.nr = 0;\n"},{"id":"61470","messageId":"200711300339.56867.jnareb@gmail.com","threadId":"11056","inReplyTo":"alpine.LFD.0.9999.0711291812530.8458@woody.linux-foundation.org","subject":"Re: Some git performance measurements..","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2007-11-30T02:39:56Z","receivedAt":"2007-11-30T02:39:56Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On Fri, 30 Nov 2007, Linus Torvalds wrote:\n> \n> On Fri, 30 Nov 2007, Jakub Narebski wrote:\n>> \n>> Isn't there a better way to do this sorting? What is needed here is\n>> (stable) _bucket_ sort / _pigeonhole_ sort (or counting sort), which\n>> is O(n); quicksort is perhaps simpler to use, but I'm not sure if\n>> faster in this situation.\n> \n> Actually, I doubt you need to do any sorting at all: what would be easiest \n> would be to simply change \"traverse_commit_list()\" to use different lists \n> for different object types, and just output them in type order (semi-sane \n> order choice: commits first, then tags, then trees, and finally blobs).\n> \n> Ta-daa! All done! Magic! No sorting required, because all the objects got \n> output in the right order without any extra sort phase!\n\nActually this algorithm has the fancy name of \"pigeonhole sort\" algorithm,\nand is a subcase (special case) of bucket sort. Well, sort of, as there\nis no final sorted list, only output in \"sorted\" order.\n\n-- \nJakub Narebski\nPoland\n"},{"id":"61471","messageId":"alpine.LFD.0.99999.0711292131350.9605@xanadu.home","threadId":"11056","inReplyTo":"alpine.LFD.0.9999.0711291812530.8458@woody.linux-foundation.org","subject":"Re: Some git performance measurements..","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-11-30T02:40:13Z","receivedAt":"2007-11-30T02:40:13Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 29 Nov 2007, Linus Torvalds wrote:\n\n> On Fri, 30 Nov 2007, Jakub Narebski wrote:\n> > \n> > Isn't there a better way to do this sorting? What is needed here is\n> > (stable) _bucket_ sort / _pigeonhole_ sort (or counting sort), which\n> > is O(n); quicksort is perhaps simpler to use, but I'm not sure if\n> > faster in this situation.\n\nThat particular sort takes under a second here with the Linux repo.\nPretty insignificant compared to the time required to repack.\n\n> Actually, I doubt you need to do any sorting at all: what would be easiest \n> would be to simply change \"traverse_commit_list()\" to use different lists \n> for different object types, and just output them in type order (semi-sane \n> order choice: commits first, then tags, then trees, and finally blobs).\n\nYes!  That's what I thought initially, but since list-objects.c is \ncompletely unknown territory to me, I sorted them in pack-object.c \ninstead, out of pure laziness.\n\n\nNicolas\n"},{"id":"61472","messageId":"alpine.LFD.0.9999.0711291836230.8458@woody.linux-foundation.org","threadId":"11056","inReplyTo":"alpine.LFD.0.9999.0711291812530.8458@woody.linux-foundation.org","subject":"Re: Some git performance measurements..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-30T02:54:01Z","receivedAt":"2007-11-30T02:54:01Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 29 Nov 2007, Linus Torvalds wrote:\n> \n> Something like the appended (untested!\n\nOk, tested now. It does seem to work. The page fault trace for the \npack-file shows that we now get basically perfect IO patterns for my \"git \ncheckout\" testcase, and while I'm not sure that's necessarily a test-case \nthat really deserves this kind of attention, it's certainly potentially \ninteresting.\n\nTo check the performance impact of this, though, you'd need to pack the \nsame repository two different ways - with this kind of sorting change and \nwithout - and then test different cold-cache timings for things like \"git \nblame\" etc that might care.\n\nThe timing of the commands itself could be done with either a pre-change \nor post-change version of git, it's only the resulting order in the \npack-file that matters.\n\nMy very unscientific tests says that \"git read-tree\" is speed up by the \nchange (from 5.2s to 3.3s, so it's quite noticeable), but \"git blame\" \nslows down (from 8.7s to 12.9s, so that's quite noticeable too). But as \nJakub pointed out, the cold-cache numbers do fluctuate a lot, and while \nthey were reasonably stable over runs, the \"git blame\" numbers in \nparticular probably depend a fair amount on whether the file is commonly \nchanged or not.\n\nAnybody interested in trying to do something more scientific?\n\n\t\t\tLinus\n"},{"id":"61475","messageId":"7v3auos4yi.fsf@gitster.siamese.dyndns.org","threadId":"11056","inReplyTo":"alpine.LFD.0.9999.0711290945060.8458@woody.linux-foundation.org","subject":"Re: Some git performance measurements..","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-11-30T05:00:21Z","receivedAt":"2007-11-30T05:00:21Z","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> Umm. See my earlier numbers. For \"git checkout\" with cold cache, the \n> *bulk* of the time is actually the \".gitignore\" file lookups, so if you \n> see a three-second improvement out of 17s, it may not look spectacular, \n> but considering that probably 10s of those 17s were something *else* going \n> on, I suspect that if you really did just a plain \"git checkout\", you \n> actually *do* have a spectacular improvement of roughly 7s -> 4s!\n\nI am hoping that \"probably 10s of those 17s\" can actually be measured\nwith the patch I sent out last night.  Has anybody took a look at it?\n\nPartitioning the pack data by object type shifts the tradeoffs from the\ncurrent \"the data in the same tree are mostly together, except commits\nare treated differently because rev walk is done quite often\" layout.\nBecause we do not ever look at blob objects while pruning the history\n(unless the -Spickaxe option is used, I think), partitioned layout would\noptimize ancestry walking even more than the current packfile layout.\n\nOn the other hand, any operation that wants to look at the contents are\npenalized.  A two-tree diff that inspects the contents (e.g. fuzzy\nrenames and pickaxe) needs to read from the tree section to find which\nblob to compare with which other blob, and and then needs to seek to the\nblob section to actually read the contents, while the current layout\ntends to group both trees and blobs that belong to the same tree\ntogether.  It is natural that blame is penalized by the new layout,\nmostly because it needs to grab two blobs to compare from parent-child\npair, but also because it needs to find two-tree diffs for parent-child\npair it traverses whenever it needs to follow across renames (that is,\nwhen it sees there is no corresponding path in the parent).  I would\nexpect to see similar slowdown from grep which wants to inspect blobs\nthat are in the same tree.\n\nWhen I do archaeology, I think I often run blame first to see which\nchange made the block of text into the current shape first, and then run\na path limited \"git log -p\" either starting or ending at that revision.\nIn that workflow, the initial blame may get slower with the new layout,\nbut I suspect it would help by speeding up the latter \"git log -p\" step.\n"},{"id":"61478","messageId":"alpine.LFD.0.9999.0711292145110.8458@woody.linux-foundation.org","threadId":"11056","inReplyTo":"7v3auos4yi.fsf@gitster.siamese.dyndns.org","subject":"Re: Some git performance measurements..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-11-30T06:03:00Z","receivedAt":"2007-11-30T06:03:00Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 29 Nov 2007, Junio C Hamano wrote:\n> \n> I am hoping that \"probably 10s of those 17s\" can actually be measured\n> with the patch I sent out last night.  Has anybody took a look at it?\n\nSorry, I missed it. But I just did timings.\n\nYour patch helps\n\n\tgit read-tree -m -u --exclude-per-directory=.gitignore HEAD HEAD\n\ntimings enormously, and it's now down to 3s for me (which is the same \nspeed as it is without any per-directory-excludes). That's a big \nimprovement from the ~10s I see without your patch (I've repacked my \ntree, I have to admit that I don't even know if it's the new or the old \nolder, but I can state that 7s for me was just those .gitignore files).\n\nSadly, the full \"git checkout\" itself is not actually improved, due to the\n\n\tgit update-index --refresh\n\nthere, which will end up populating the whole directory cache anyway.\n\nI wonder why I didn't see that as the expensive operation when I timed \n\"git checkout\". Probably because I narrowed down on the \"git read-tree\" as \nthe operation that actually accesses the pack-file and the object \ndirectory, while the \"git update-index\" never touches the actual objects.\n\nAnyway, I think your patch is great. It just doesn't help the full case of \na \"git checkout\", only the read-tree portion of it ;(\n\nAs to partitioning the data according to types:\n\n> When I do archaeology, I think I often run blame first to see which\n> change made the block of text into the current shape first, and then run\n> a path limited \"git log -p\" either starting or ending at that revision.\n> In that workflow, the initial blame may get slower with the new layout,\n> but I suspect it would help by speeding up the latter \"git log -p\" step.\n\nI really cannot convince myself one way or the other. I have a suspicion \nthat sometimes it helps to have objects (regardless of type) close to each \nother, and sometimes it helps to have the trees packed densely. A lot of \noperations *do* work on both blobs and trees (a *raw* diff doesn't, but \nthey are fairly rare), so this is not at all clear-cut like the commit \ncase.\n\nSo sorting the commits together is a no-brainer, since a lot of really \nimportant ops only look at them. But blobs and trees? The numbers \ncertainly go both ways, and I suspect we are probably better off not \nmessing with the sort order unless we have some unambiguous real results.\n\nOh, well. I was hoping that I'd have a number of cases that showed good \nimprovements, with perhaps the bulk of it not showing much difference at \nall. But while I saw the good improvements, the very first try at \"git \nblame\" also showed quite worse numbers, so I think we should consider it \nan interesting idea, but probably shelve it.\n\n\t\t\tLinus\n"},{"id":"61479","messageId":"B161871F-E812-44B4-A699-44341B5783D3@zib.de","threadId":"11056","inReplyTo":"alpine.LFD.0.99999.0711292131350.9605@xanadu.home","subject":"Re: Some git performance measurements..","fromName":"Steffen Prohaska","fromEmail":"prohaska@zib.de","sentAt":"2007-11-30T06:11:35Z","receivedAt":"2007-11-30T06:11:35Z","isPatch":false,"sender":{"key":"prohaska@zib.de","avatar":"https://avatars.githubusercontent.com/u/217580?v=4"},"body":"\nOn Nov 30, 2007, at 3:40 AM, Nicolas Pitre wrote:\n\n> On Thu, 29 Nov 2007, Linus Torvalds wrote:\n>\n>> On Fri, 30 Nov 2007, Jakub Narebski wrote:\n>>>\n>>> Isn't there a better way to do this sorting? What is needed here is\n>>> (stable) _bucket_ sort / _pigeonhole_ sort (or counting sort), which\n>>> is O(n); quicksort is perhaps simpler to use, but I'm not sure if\n>>> faster in this situation.\n>\n> That particular sort takes under a second here with the Linux repo.\n> Pretty insignificant compared to the time required to repack.\n\n\nBrian Downing measured horrid performance of qsort on Windows\n2000 [1].  qsort seems to show worst case behaviour.\n\nThis resulted in a patch replacing Window's qsort implementation\nfor the mingw port [2].\n\n[1] http://thread.gmane.org/gmane.comp.version-control.msysgit/1084\n[2] http://thread.gmane.org/gmane.comp.version-control.msysgit/1086\n\n\nAvoiding qsort would even be better.  I'm not sure, though,\nif the particular qsort call that triggered the current\ndiscussion, is the very same qsort call that Brian was hit by.\nI'm only claiming that in general avoiding qsort on Windows\nis a good idea.\n\n\tSteffen\n"},{"id":"61573","messageId":"85abou8x5n.fsf@lupus.ig3.net","threadId":"11056","inReplyTo":"alpine.LFD.0.9999.0711281852160.8458@woody.linux-foundation.org","subject":"Re: Some git performance measurements..","fromName":"Joachim B Haga","fromEmail":"cjhaga@fys.uio.no","sentAt":"2007-12-01T11:36:04Z","receivedAt":"2007-12-01T11:36:04Z","isPatch":false,"sender":{"key":"cjhaga@fys.uio.no","avatar":null},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> The pack-files (both index and data) are accessed somewhat randomly, but \n> there is still enough locality that doing read-ahead and clustering really \n> does help.\n\nThey are dense enough that slurping them in whole is 20% faster, at \nleast here. And much less noisy! These are both cache-cold tests.\n\n$ time git read-tree -m -u HEAD HEAD\n\nreal    0m9.255s\nuser    0m0.832s\nsys     0m0.196s\n\n$ time (cat .git/objects/pack/* .git/index >/dev/null; git read-tree -m -u HEAD HEAD)\n\nreal    0m7.141s\nuser    0m0.936s\nsys     0m1.912s\n\n\nNow, I don't know how useful this is since git doesn't know if the\ndata are cached. Is it perhaps possible to give a hint to the\nreadahead logic that it should try to read as far as possible?\n\n\n-j.\n"},{"id":"61589","messageId":"alpine.LFD.0.9999.0712010843520.8458@woody.linux-foundation.org","threadId":"11056","inReplyTo":"85abou8x5n.fsf@lupus.ig3.net","subject":"Re: Some git performance measurements..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-12-01T17:19:26Z","receivedAt":"2007-12-01T17:19:26Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 1 Dec 2007, Joachim B Haga wrote:\n>\n> Linus Torvalds <torvalds@linux-foundation.org> writes:\n> > The pack-files (both index and data) are accessed somewhat randomly, but \n> > there is still enough locality that doing read-ahead and clustering really \n> > does help.\n> \n> They are dense enough that slurping them in whole is 20% faster, at \n> least here. And much less noisy! These are both cache-cold tests.\n\nWith BK, I used to have a \"readahead\" script to something close to this.\n\nThe problem with that approach is that it works wonderfully well for \npeople who (a) have tons of memory and (b) really only care about the \nsource tree and almost nothing else, but it doesn't work that well at all \nfor others.\n\nSo yes, for me, forcing a page-in of all the data is actually worth it. I \ncommonly do something like\n\n\tgit grep quieuiueriueirue &\n\non my main machine when I reboot it for testing - just to bring in the \nworking tree into cache, so that subsequent \"git diff\" and \"git grep\" \noperations will be faster.\n\n> $ time git read-tree -m -u HEAD HEAD\n> \n> real    0m9.255s\n> user    0m0.832s\n> sys     0m0.196s\n> \n> $ time (cat .git/objects/pack/* .git/index >/dev/null; git read-tree -m -u HEAD HEAD)\n> \n> real    0m7.141s\n> user    0m0.936s\n> sys     0m1.912s\n> \n> Now, I don't know how useful this is since git doesn't know if the\n> data are cached. Is it perhaps possible to give a hint to the\n> readahead logic that it should try to read as far as possible?\n\nYou have a much faster disk drive than I do on that slow laptop that I \nwanted to optimize for.\n\nI get\n\n\t[torvalds@hp linux]$ time git read-tree -m -u HEAD HEAD\n\treal    0m12.849s\n\tuser    0m0.232s\n\tsys     0m0.124s\n\nfor the cold-cache case, but then for populating the whole thing:\n\n\ttime cat .git/objects/pack/* .git/index >/dev/null\n\treal    0m31.350s\n\tuser    0m0.040s\n\tsys     0m0.468s\n\nwhoops. Can you say \"pitiful\"?\n\n(In contrast, my desktop does the same it in seven seconds - laptop disks \nreally are *much* slower than a reasonable desktop one).\n\n\t\tLinus\n"},{"id":"61960","messageId":"1196816688.23870.2.camel@cacharro.xalalinux.org","threadId":"11056","inReplyTo":"alpine.LFD.0.9999.0711291836230.8458@woody.linux-foundation.org","subject":"Re: Some git performance measurements..","fromName":"Federico Mena Quintero","fromEmail":"federico@novell.com","sentAt":"2007-12-05T01:04:48Z","receivedAt":"2007-12-05T01:04:48Z","isPatch":false,"sender":{"key":"federico@novell.com","avatar":null},"body":"On Thu, 2007-11-29 at 18:54 -0800, Linus Torvalds wrote:\n\n> Jakub pointed out, the cold-cache numbers do fluctuate a lot, and while \n\nYou may want to try iogrind:\n\nhttp://live.gnome.org/iogrind\n\nIt's a valgrind skin to record I/O operations (including \"implicit\" ones\nlike touching mmap()ed pages), plus a graphical tool to visualize the\nlogs, similar to kcachegrind.\n\n  Federico\n"},{"id":"62285","messageId":"e2b179460712070535x2eb10710s75a581664139e0cf@mail.gmail.com","threadId":"11056","inReplyTo":"B161871F-E812-44B4-A699-44341B5783D3@zib.de","subject":"Re: Some git performance measurements..","fromName":"Mike Ralphson","fromEmail":"mike.ralphson@gmail.com","sentAt":"2007-12-07T13:35:18Z","receivedAt":"2007-12-07T13:35:18Z","isPatch":false,"sender":{"key":"mike.ralphson@gmail.com","avatar":"https://avatars.githubusercontent.com/u/21603?v=4"},"body":"On Nov 30, 2007 6:11 AM, Steffen Prohaska <prohaska@zib.de> wrote:\n> Brian Downing measured horrid performance of qsort on Windows\n> 2000 [1].  qsort seems to show worst case behaviour.\n>\n> This resulted in a patch replacing Window's qsort implementation\n> for the mingw port [2].\n>\n> [1] http://thread.gmane.org/gmane.comp.version-control.msysgit/1084\n> [2] http://thread.gmane.org/gmane.comp.version-control.msysgit/1086\n>\n>\n> Avoiding qsort would even be better.  I'm not sure, though,\n> if the particular qsort call that triggered the current\n> discussion, is the very same qsort call that Brian was hit by.\n> I'm only claiming that in general avoiding qsort on Windows\n> is a good idea.\n\nThis is a vote for pulling this into mainline git. AIX (at least 5.3) also\nhas the horrible worst-case performance of the libc qsort on sorted or\nnear-sorted lists (such as those provided by some filesystems, or a\ndirectory which has been rsynced).\n\nSome versions of Solaris have the same problem [1]\n\nI benchmarked 3 alternative qsorts, qsortG [2] was the fastest on my system\nbut has funky licensing, the NetBSD qsort was middle-range and the glibc one\nthe slowest of the three (but that could be due to it being tuned for a \"Sun\n4/260\"). All of them show over 100x speed improvements on a git-status of my\nmain repo (104s -> ~0.7s)\n\nI like the idea of a BROKEN_QSORT make variable. I was trying to come up\nwith a patch which would discover the problem in a performance/regression\ntest and suggest the setting, but have had insufficient free time so far.\n\nCheers, Mike\n\n[1] http://bugs.opensolaris.org/view_bug.do?bug_id=1258570\n\n[2] http://www.mccaughan.org.uk/g/software.html#qsort\n"},{"id":"62286","messageId":"Pine.LNX.4.64.0712071348100.27959@racer.site","threadId":"11056","inReplyTo":"e2b179460712070535x2eb10710s75a581664139e0cf@mail.gmail.com","subject":"Re: Some git performance measurements..","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-12-07T13:49:56Z","receivedAt":"2007-12-07T13:49:56Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 7 Dec 2007, Mike Ralphson wrote:\n\n> I benchmarked 3 alternative qsorts, qsortG [2] was the fastest on my \n> system but has funky licensing, the NetBSD qsort was middle-range and \n> the glibc one the slowest of the three (but that could be due to it \n> being tuned for a \"Sun 4/260\"). All of them show over 100x speed \n> improvements on a git-status of my main repo (104s -> ~0.7s)\n\nHow is \"You may use it in anything you like;\" funky licensing?  It is \neffectively public domain.\n\nBTW if you need a starting point (easing on your time constraints):\nhttp://repo.or.cz/w/git/mingw/4msysgit.git?a=commitdiff;h=bba554dd0114dc436cfdd3f17edc836bbaf3d95f\n\nCiao,\nDscho\n"},{"id":"62292","messageId":"alpine.LFD.0.9999.0712070800370.7274@woody.linux-foundation.org","threadId":"11056","inReplyTo":"Pine.LNX.4.64.0712071348100.27959@racer.site","subject":"Re: Some git performance measurements..","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-12-07T16:07:14Z","receivedAt":"2007-12-07T16:07:14Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 7 Dec 2007, Johannes Schindelin wrote:\n> \n> How is \"You may use it in anything you like;\" funky licensing?  It is \n> effectively public domain.\n\nNo, it has a long list of requirements that my not be onerous, but they \naren't compatible with GPL (ie they require that you make changes in \ncertain ways).\n\nThat said, if somebody wants to use that qsort, the thing to do is to ask \nGareth for permission, maybe he just says \"sure\". For example, for git, \nyou might as well remove the whole unaligned case, and quite frankly, that \n#ifdef DEBUG_QSORT is some of the ugliest I've ever seen and should be \ncleaned up (why didn't he just use a \"dbg_printf()\" macro like everybody \nelse? Even if it requires double parenthesis for ols-style C portability, \nit's cleaner than what is there now).\n\n\t\t\tLinus\n"},{"id":"62293","messageId":"e2b179460712070809r4127dc0br8dc20f55b1076501@mail.gmail.com","threadId":"11056","inReplyTo":"Pine.LNX.4.64.0712071348100.27959@racer.site","subject":"Re: Some git performance measurements..","fromName":"Mike Ralphson","fromEmail":"mike.ralphson@gmail.com","sentAt":"2007-12-07T16:09:30Z","receivedAt":"2007-12-07T16:09:30Z","isPatch":false,"sender":{"key":"mike.ralphson@gmail.com","avatar":"https://avatars.githubusercontent.com/u/21603?v=4"},"body":"On Dec 7, 2007 1:49 PM, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:\n> On Fri, 7 Dec 2007, Mike Ralphson wrote:\n>\n> > I benchmarked 3 alternative qsorts, qsortG [2] was the fastest on my\n> > system but has funky licensing, the NetBSD qsort was middle-range and\n> > the glibc one the slowest of the three (but that could be due to it\n> > being tuned for a \"Sun 4/260\"). All of them show over 100x speed\n> > improvements on a git-status of my main repo (104s -> ~0.7s)\n>\n> How is \"You may use it in anything you like;\" funky licensing?  It is\n> effectively public domain.\n\nI did ask what the git licensing policy was (GPL2 or GPL2-compatible)\nbut got no response. The author's wishes state:\n\n * This code may be reproduced freely provided\n *   - this file is retained unaltered apart from minor\n *     changes for portability and efficiency\n *   - no changes are made to this comment\n *   - any changes that *are* made are clearly flagged\n *   - the _ID string below is altered by inserting, after\n *     the date, the string \" altered\" followed at your option\n *     by other material. (Exceptions: you may change the name\n *     of the exported routine without changing the ID string.\n *     You may change the values of the macros TRUNC_* and\n *     PIVOT_THRESHOLD without changing the ID string, provided\n *     they remain constants with TRUNC_nonaligned, TRUNC_aligned\n *     and TRUNC_words/WORD_BYTES between 8 and 24, and\n *     PIVOT_THRESHOLD between 32 and 200.)\n\nand they should be respected. \"retained unaltered apart from\" sounds a\nlittle bit more restrictive than we might like. I haven't pinged him\nabout relicensing though. [Edit, I see Linus has just made those\npoints].\n\n> BTW if you need a starting point (easing on your time constraints):\n> http://repo.or.cz/w/git/mingw/4msysgit.git?a=commitdiff;h=bba554dd0114dc436cfdd3f17edc836bbaf3d95f\n\nMany thanks, the gmane links I bookmarked are just complaining about\nwefts producing no weaves or somesuch, so that's helpful. I'll try the\nmergesort and report back.\n\nCheers, Mike\n"},{"id":"62300","messageId":"Pine.LNX.4.64.0712071816100.27959@racer.site","threadId":"11056","inReplyTo":"e2b179460712070809r4127dc0br8dc20f55b1076501@mail.gmail.com","subject":"Re: Some git performance measurements..","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-12-07T18:37:30Z","receivedAt":"2007-12-07T18:37:30Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 7 Dec 2007, Mike Ralphson wrote:\n\n> On Dec 7, 2007 1:49 PM, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:\n> > On Fri, 7 Dec 2007, Mike Ralphson wrote:\n> >\n> > > I benchmarked 3 alternative qsorts, qsortG [2] was the fastest on my \n> > > system but has funky licensing, the NetBSD qsort was middle-range \n> > > and the glibc one the slowest of the three (but that could be due to \n> > > it being tuned for a \"Sun 4/260\"). All of them show over 100x speed \n> > > improvements on a git-status of my main repo (104s -> ~0.7s)\n> >\n> > How is \"You may use it in anything you like;\" funky licensing?  It is \n> > effectively public domain.\n> \n> I did ask what the git licensing policy was (GPL2 or GPL2-compatible) \n> but got no response. The author's wishes state:\n> \n>  * This code may be reproduced freely provided\n> [long list]\n\nOkay, sorry, I did not bother reading further when I read \"You may use it \nin anything you like;\".\n\nBut if the author did not respond, it might be a better idea to just \nreimplement it.\n\nCiao,\nDscho\n"},{"id":"62304","messageId":"e2b179460712071115k369dddcatb0f6456d0028acbb@mail.gmail.com","threadId":"11056","inReplyTo":"Pine.LNX.4.64.0712071816100.27959@racer.site","subject":"Re: Some git performance measurements..","fromName":"Mike Ralphson","fromEmail":"mike.ralphson@gmail.com","sentAt":"2007-12-07T19:15:36Z","receivedAt":"2007-12-07T19:15:36Z","isPatch":false,"sender":{"key":"mike.ralphson@gmail.com","avatar":"https://avatars.githubusercontent.com/u/21603?v=4"},"body":"On Dec 7, 2007 6:37 PM, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:\n> On Fri, 7 Dec 2007, Mike Ralphson wrote:\n>\n> > On Dec 7, 2007 1:49 PM, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:\n> > > On Fri, 7 Dec 2007, Mike Ralphson wrote:\n> > >\n> > > > I benchmarked 3 alternative qsorts, qsortG [2] was the fastest on my\n> > > > system but has funky licensing, the NetBSD qsort was middle-range\n> > > > and the glibc one the slowest of the three (but that could be due to\n> > > > it being tuned for a \"Sun 4/260\"). All of them show over 100x speed\n> > > > improvements on a git-status of my main repo (104s -> ~0.7s)\n> > >\n>\n> Okay, sorry, I did not bother reading further when I read \"You may use it\n> in anything you like;\".\n>\n> But if the author did not respond, it might be a better idea to just\n> reimplement it.\n>\n\nI've just tried the mergesort implementation as used in msysgit and\nthat performs faster for me. It's simpler, and compatibly licensed. It\nlooks good.\n\nMike\n"},{"id":"62399","messageId":"Pine.LNX.4.64.0712081103430.27959@racer.site","threadId":"11056","inReplyTo":"e2b179460712071115k369dddcatb0f6456d0028acbb@mail.gmail.com","subject":"Re: Some git performance measurements..","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-12-08T11:05:35Z","receivedAt":"2007-12-08T11:05:35Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 7 Dec 2007, Mike Ralphson wrote:\n\n> On Dec 7, 2007 6:37 PM, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:\n> > On Fri, 7 Dec 2007, Mike Ralphson wrote:\n> >\n> > > On Dec 7, 2007 1:49 PM, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:\n> > > > On Fri, 7 Dec 2007, Mike Ralphson wrote:\n> > > >\n> > > > > I benchmarked 3 alternative qsorts, qsortG [2] was the fastest \n> > > > > on my system but has funky licensing, the NetBSD qsort was \n> > > > > middle-range and the glibc one the slowest of the three (but \n> > > > > that could be due to it being tuned for a \"Sun 4/260\"). All of \n> > > > > them show over 100x speed improvements on a git-status of my \n> > > > > main repo (104s -> ~0.7s)\n> > > >\n> >\n> > Okay, sorry, I did not bother reading further when I read \"You may use \n> > it in anything you like;\".\n> >\n> > But if the author did not respond, it might be a better idea to just \n> > reimplement it.\n> >\n> \n> I've just tried the mergesort implementation as used in msysgit and that \n> performs faster for me. It's simpler, and compatibly licensed. It looks \n> good.\n\nNow I'm confused.  You said you tested qsortG, NetBSD qsort and qlibc, \nwith glibc performing the slowest.  Now, 4msysgit's implementation is \nbased on glibc (Thanks Brian!), so I wonder if you could redo the \nperformance tests and say if qsortG still is substantially faster than \n4msysgit's qsort?\n\nCiao,\nDscho\n"},{"id":"62437","messageId":"20071208230402.GK6212@lavos.net","threadId":"11056","inReplyTo":"Pine.LNX.4.64.0712081103430.27959@racer.site","subject":"Re: Some git performance measurements..","fromName":"Brian Downing","fromEmail":"bdowning@lavos.net","sentAt":"2007-12-08T23:04:03Z","receivedAt":"2007-12-08T23:04:03Z","isPatch":false,"sender":{"key":"bdowning@lavos.net","avatar":"https://avatars.githubusercontent.com/u/366426?v=4"},"body":"On Sat, Dec 08, 2007 at 11:05:35AM +0000, Johannes Schindelin wrote:\n> On Fri, 7 Dec 2007, Mike Ralphson wrote:\n> > I've just tried the mergesort implementation as used in msysgit and that \n> > performs faster for me. It's simpler, and compatibly licensed. It looks \n> > good.\n> \n> Now I'm confused.  You said you tested qsortG, NetBSD qsort and qlibc, \n> with glibc performing the slowest.  Now, 4msysgit's implementation is \n> based on glibc (Thanks Brian!), so I wonder if you could redo the \n> performance tests and say if qsortG still is substantially faster than \n> 4msysgit's qsort?\n\nThis is just me guessing, but when he said:\n\n> I benchmarked 3 alternative qsorts, qsortG [2] was the fastest on my\n> system but has funky licensing, the NetBSD qsort was middle-range and\n> the glibc one the slowest of the three (but that could be due to it\n> being tuned for a \"Sun 4/260\"). All of them show over 100x speed\n> improvements on a git-status of my main repo (104s -> ~0.7s)\n\nIt's possible he tried glibc's actual quicksort implementation, rather\nthan their \"qsort.\"  Their qsort basically has the following behavior:\n\nif size < 1024\n    mergesort with temporary array on stack\nif allocating size bytes would likely cause swapping\n    quicksort in place\nelse\n    mergesort with temporary array in heap\n\nI removed the \"quicksort in place\" possibility, as it would have added\nanother sort algorithm and I had no way to easily determine whether\n\"allocating size bytes would likely cause swapping.\"\n\n-bcd\n"}]}