{"thread":{"id":"29852","subject":"[RFC HACK] refresh_index: lstat() in inode order","startedAt":"2012-03-06T08:27:50Z","lastAt":"2012-03-06T18:37:30Z","messageCount":2,"participants":["Thomas Rast","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"186178","messageId":"871up6cewp.fsf@thomas.inf.ethz.ch","threadId":"29852","inReplyTo":null,"subject":"[RFC HACK] refresh_index: lstat() in inode order","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2012-03-06T08:27:50Z","receivedAt":"2012-03-06T08:27:50Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Hi,\n\nThis is prompted by a recent lkml discussion[1] which is also backed up\nby old stuff threads like[2] where Theodore Ts'o writes about\nspd_readdir.\n\nAs explained at the links, ext3&4 seem to show suboptimal performance if\nyou do the common pattern of lstat()'ing everything returned by\nreaddir() and the corresponding inodes must be fetched from disk.  They\nsuggest (and spd_readdir does just this, in an LD_PRELOADable format)\nsorting the entries by inode.\n\nLet me emphasise: inodes fetched from disk.  This does not matter at all\nfor the cached case.\n\nProbably this also applies to us in the search for untracked files, but\nright now I don't care about that too much because I have git-status\nconfigured not to show them.\n\nHowever, a similar trick could be applied to lstat() across the index,\nwhich *is* a big part of the work required to accurately display\nrepository status in git-status and git-diff.\n\nThe dirty hack below uses the inode field in the index to sort the index\nentries prior to the real work of refresh_index.  I have been able to\nmeasure a significant (in the statistical sense) speedup using\nmeasurements like\n\n  ( for i in $(seq 1 30); do\n      sudo sh -c 'echo 3 >/proc/sys/vm/drop_caches'\n      /usr/bin/time -f \"time %U %S %E\" ~/dev/git/git-status 2>&1 | grep time\n    done ) | tee results-patched\n\nIn numbers, across 30 trials for unpatched and patched git, my time\nneeded to get a cache-cold 'git status' went from 4.24s to 3.97s on\naverage, at p=0.006.\n\nNote that this only has an effect if your directory has the inodes all\njumbled.  I tried doing bigger trials, but I do not have a realistic\nwork repository bigger than git.git.  You can look at the lstat() order\nyou are currently getting with\n\n  strace -e lstat -v git status 2>&1 | egrep -o 'st_ino=[0-9]+'\n\nWith the patch it should be in good sorted order.  Note, however, that\nat the very end it also runs lstat() on .git/refs/*; those will still be\nout of order.\n\nSo I'd be interested to hear success (or non-success) stories from\npeople who are actively working with larger repos, perhaps linux-2.6 or\nyour favourite corporate repo.  The lkml posts also seem to say that it\nonly matters on ext3&4, not on btrfs, but perhaps other FSes also suffer\nin this area.\n\nI'd also be interested to hear from the refresh_index experts whether my\nchange works in principle, or is already flawed in some major way.  You\nwill note I sort by (inode,stage) to handle the search forward for the\nhighest stage entry, but maybe this is not the only twist.  (As written\nit is also not thread-safe.)\n\nI did run the test suite and it passes, so it can't be *that* bad.\n\n\nFootnotes: \n[1]  https://lkml.org/lkml/2012/2/29/210\n\n[2]  http://lkml.indiana.edu/hypermail/linux/kernel/0802.2/1076.html\n\n\n---- 8< ----\ndiff --git i/read-cache.c w/read-cache.c\nindex 274e54b..b0d1942 100644\n--- i/read-cache.c\n+++ w/read-cache.c\n@@ -1092,10 +1092,28 @@ static void show_file(const char * fmt, const char * name, int in_porcelain,\n \tprintf(fmt, name);\n }\n \n+static struct index_state *istate_for_cmp;\n+\n+int cmp_by_inode(const void *a, const void *b)\n+{\n+\tstruct cache_entry *ca, *cb;\n+\n+\tca = istate_for_cmp->cache[*(const int *)a];\n+\tcb = istate_for_cmp->cache[*(const int *)b];\n+\n+\tif (ca->ce_ino < cb->ce_ino)\n+\t\treturn -1;\n+\tif (ca->ce_ino > cb->ce_ino)\n+\t\treturn 1;\n+\tif (ce_stage(ca) < ce_stage(cb))\n+\t\treturn -1;\n+\treturn 1;\n+}\n+\n int refresh_index(struct index_state *istate, unsigned int flags, const char **pathspec,\n \t\t  char *seen, const char *header_msg)\n {\n-\tint i;\n+\tint i, j;\n \tint has_errors = 0;\n \tint really = (flags & REFRESH_REALLY) != 0;\n \tint allow_unmerged = (flags & REFRESH_UNMERGED) != 0;\n@@ -1110,18 +1128,28 @@ int refresh_index(struct index_state *istate, unsigned int flags, const char **p\n \tconst char *typechange_fmt;\n \tconst char *added_fmt;\n \tconst char *unmerged_fmt;\n+\tint *by_inode_idx;\n \n \tmodified_fmt = (in_porcelain ? \"M\\t%s\\n\" : \"%s: needs update\\n\");\n \tdeleted_fmt = (in_porcelain ? \"D\\t%s\\n\" : \"%s: needs update\\n\");\n \ttypechange_fmt = (in_porcelain ? \"T\\t%s\\n\" : \"%s needs update\\n\");\n \tadded_fmt = (in_porcelain ? \"A\\t%s\\n\" : \"%s needs update\\n\");\n \tunmerged_fmt = (in_porcelain ? \"U\\t%s\\n\" : \"%s: needs merge\\n\");\n-\tfor (i = 0; i < istate->cache_nr; i++) {\n+\n+\tby_inode_idx = xmalloc(istate->cache_nr * sizeof(int));\n+\tfor (i = 0; i < istate->cache_nr; i++)\n+\t\tby_inode_idx[i] = i;\n+\tistate_for_cmp = istate;\n+\tqsort(by_inode_idx, istate->cache_nr, sizeof(int), cmp_by_inode);\n+\n+\tfor (j = 0; j < istate->cache_nr; j++) {\n \t\tstruct cache_entry *ce, *new;\n \t\tint cache_errno = 0;\n \t\tint changed = 0;\n \t\tint filtered = 0;\n \n+\t\ti = by_inode_idx[j];\n+\n \t\tce = istate->cache[i];\n \t\tif (ignore_submodules && S_ISGITLINK(ce->ce_mode))\n \t\t\tcontinue;\n\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"186234","messageId":"7vipihtw2d.fsf@alter.siamese.dyndns.org","threadId":"29852","inReplyTo":"871up6cewp.fsf@thomas.inf.ethz.ch","subject":"Re: [RFC HACK] refresh_index: lstat() in inode order","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-03-06T18:37:30Z","receivedAt":"2012-03-06T18:37:30Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast <trast@inf.ethz.ch> writes:\n\n> The dirty hack below uses the inode field in the index to sort the index\n> entries prior to the real work of refresh_index.\n\nI think we do something similar in fsck to touch loose object files\nin clusters, and would not be surprised if you see performance boost\nby running lstat(2) in clusters for the purpose of refresh_index().\n\nRight now, preload_index() partitions the index entries by offset\nand hands them out to worker threads, but it _might_ make sense to\nuse fewer number of threads and give them entries sorted by the inum.\n"}]}