{"thread":{"id":"45666","subject":"[PATCH v9 0/3] read-cache: speed up add_index_entry","startedAt":"2017-04-11T19:17:21Z","lastAt":"2017-04-14T13:06:20Z","messageCount":7,"participants":["git@jeffhostetler.com","Jeff King","Junio C Hamano","Jeff Hostetler"],"isPatch":true,"patchVersion":9,"patchTotal":3},"messages":[{"id":"316620","messageId":"20170411191702.20134-1-git@jeffhostetler.com","threadId":"45666","inReplyTo":null,"subject":"[PATCH v9 0/3] read-cache: speed up add_index_entry","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-11T19:16:59Z","receivedAt":"2017-04-11T19:17:21Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nVersion 9 addresses the following:\n () p0006 perf test can now run using either synthetic repos\n from t/perf/repos/many-repos.sh -OR- an actual real-world\n repo.\n () The commit message has been updated to include results of\n p0006 on linux.git.\n () Line 0006.3 shows a positive value, but results for that\n line had a lot of variance between runs. I measured the\n blocks of code I added and they only added 0.007 to 0.015\n seconds. I suspect the overall time difference and variance\n is due to file I/O to update the worktree when switching\n branches.\n\nI think this version has addressed everything raise so far,\nso I think I'm ready to let this one rest. Thanks for all\nthe help and feedback.\n\n\nJeff Hostetler (3):\n read-cache: add strcmp_offset function\n p0006-read-tree-checkout: perf test to time read-tree\n read-cache: speed up add_index_entry during checkout\n\n Makefile | 1 +\n cache.h | 1 +\n read-cache.c | 66 +++++++++++++++++++++-\n t/helper/.gitignore | 1 +\n t/helper/test-strcmp-offset.c | 22 ++++++++\n t/perf/p0006-read-tree-checkout.sh | 69 +++++++++++++++++++++++\n t/perf/repos/.gitignore | 1 +\n t/perf/repos/many-files.sh | 110 +++++++++++++++++++++++++++++++++++++\n t/t0065-strcmp-offset.sh | 21 +++++++\n 9 files changed, 290 insertions(+), 2 deletions(-)\n create mode 100644 t/helper/test-strcmp-offset.c\n create mode 100755 t/perf/p0006-read-tree-checkout.sh\n create mode 100644 t/perf/repos/.gitignore\n create mode 100755 t/perf/repos/many-files.sh\n create mode 100755 t/t0065-strcmp-offset.sh\n\n-- \n2.9.3\n\n"},{"id":"316621","messageId":"20170411191702.20134-2-git@jeffhostetler.com","threadId":"45666","inReplyTo":"20170411191702.20134-1-git@jeffhostetler.com","subject":"[PATCH v9 1/3] read-cache: add strcmp_offset function","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-11T19:17:00Z","receivedAt":"2017-04-11T19:17:23Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nAdd strcmp_offset() function to also return the offset of the\nfirst change.\n\nAdd unit test and helper to verify.\n\nSigned-off-by: Jeff Hostetler \n---\n Makefile | 1 +\n cache.h | 1 +\n read-cache.c | 20 ++++++++++++++++++++\n t/helper/.gitignore | 1 +\n t/helper/test-strcmp-offset.c | 22 ++++++++++++++++++++++\n t/t0065-strcmp-offset.sh | 21 +++++++++++++++++++++\n 6 files changed, 66 insertions(+)\n create mode 100644 t/helper/test-strcmp-offset.c\n create mode 100755 t/t0065-strcmp-offset.sh\n\ndiff --git a/Makefile b/Makefile\nindex 9ec6065..4c4c246 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -631,6 +631,7 @@ TEST_PROGRAMS_NEED_X += test-scrap-cache-tree\n TEST_PROGRAMS_NEED_X += test-sha1\n TEST_PROGRAMS_NEED_X += test-sha1-array\n TEST_PROGRAMS_NEED_X += test-sigchain\n+TEST_PROGRAMS_NEED_X += test-strcmp-offset\n TEST_PROGRAMS_NEED_X += test-string-list\n TEST_PROGRAMS_NEED_X += test-submodule-config\n TEST_PROGRAMS_NEED_X += test-subprocess\ndiff --git a/cache.h b/cache.h\nindex 80b6372..3c55047 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -574,6 +574,7 @@ extern int write_locked_index(struct index_state *, struct lock_file *lock, unsi\n extern int discard_index(struct index_state *);\n extern int unmerged_index(const struct index_state *);\n extern int verify_path(const char *path);\n+extern int strcmp_offset(const char *s1, const char *s2, size_t *first_change);\n extern int index_dir_exists(struct index_state *istate, const char *name, int namelen);\n extern void adjust_dirname_case(struct index_state *istate, char *name);\n extern struct cache_entry *index_file_exists(struct index_state *istate, const char *name, int namelen, int igncase);\ndiff --git a/read-cache.c b/read-cache.c\nindex 9054369..97f13a1 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -887,6 +887,26 @@ static int has_file_name(struct index_state *istate,\n \treturn retval;\n }\n \n+\n+/*\n+ * Like strcmp(), but also return the offset of the first change.\n+ * If strings are equal, return the length.\n+ */\n+int strcmp_offset(const char *s1, const char *s2, size_t *first_change)\n+{\n+\tsize_t k;\n+\n+\tif (!first_change)\n+\t\treturn strcmp(s1, s2);\n+\n+\tfor (k = 0; s1[k] == s2[k]; k++)\n+\t\tif (s1[k] == '\\0')\n+\t\t\tbreak;\n+\n+\t*first_change = k;\n+\treturn (unsigned char)s1[k] - (unsigned char)s2[k];\n+}\n+\n /*\n * Do we have another file with a pathname that is a proper\n * subset of the name we're trying to add?\ndiff --git a/t/helper/.gitignore b/t/helper/.gitignore\nindex d6e8b36..0a89531 100644\n--- a/t/helper/.gitignore\n+++ b/t/helper/.gitignore\n@@ -25,6 +25,7 @@\n /test-sha1\n /test-sha1-array\n /test-sigchain\n+/test-strcmp-offset\n /test-string-list\n /test-submodule-config\n /test-subprocess\ndiff --git a/t/helper/test-strcmp-offset.c b/t/helper/test-strcmp-offset.c\nnew file mode 100644\nindex 0000000..4a45a54\n--- /dev/null\n+++ b/t/helper/test-strcmp-offset.c\n@@ -0,0 +1,22 @@\n+#include \"cache.h\"\n+\n+int cmd_main(int argc, const char **argv)\n+{\n+\tint result;\n+\tsize_t offset;\n+\n+\tif (!argv[1] || !argv[2])\n+\t\tdie(\"usage: %s \", argv[0]);\n+\n+\tresult = strcmp_offset(argv[1], argv[2], &offset);\n+\n+\t/*\n+\t * Because differnt CRTs behave differently, only rely on signs\n+\t * of the result values.\n+\t */\n+\tresult = (result < 0 ? -1 :\n+\t\t\t result > 0 ? 1 :\n+\t\t\t 0);\n+\tprintf(\"%d %\"PRIuMAX\"\\n\", result, (uintmax_t)offset);\n+\treturn 0;\n+}\ndiff --git a/t/t0065-strcmp-offset.sh b/t/t0065-strcmp-offset.sh\nnew file mode 100755\nindex 0000000..7d6d214\n--- /dev/null\n+++ b/t/t0065-strcmp-offset.sh\n@@ -0,0 +1,21 @@\n+#!/bin/sh\n+\n+test_description='Test strcmp_offset functionality'\n+\n+. ./test-lib.sh\n+\n+while read s1 s2 expect\n+do\n+\ttest_expect_success \"strcmp_offset($s1, $s2)\" '\n+\t\techo \"$expect\" >expect &&\n+\t\ttest-strcmp-offset \"$s1\" \"$s2\" >actual &&\n+\t\ttest_cmp expect actual\n+\t'\n+done <<-EOF\n+abc abc 0 3\n+abc def -1 0\n+abc abz -1 2\n+abc abcdef -1 3\n+EOF\n+\n+test_done\n-- \n2.9.3\n\n"},{"id":"316622","messageId":"20170411191702.20134-4-git@jeffhostetler.com","threadId":"45666","inReplyTo":"20170411191702.20134-1-git@jeffhostetler.com","subject":"[PATCH v9 3/3] read-cache: speed up add_index_entry during checkout","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-11T19:17:02Z","receivedAt":"2017-04-11T19:17:26Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nTeach add_index_entry_with_check() and has_dir_name()\nto see if the path of the new item is greater than the\nlast path in the index array before attempting to search\nfor it.\n\nDuring checkout, merge_working_tree() populates the new\nindex in sorted order, so this change will save at least 2\nbinary lookups per file. This preserves the original\nbehavior but simply checks the last element before starting\nthe search.\n\nThis helps performance on very large repositories.\n\nThis can be seen using p0006-read-tree-checkout.sh and the\nartificial repository created by t/perf/repos/many-files.sh\nwith parameters (5, 10, 9). (1M files in index.)\n\nTest HEAD^ HEAD\n----------------------------------------------------------------------------------------------------------\n0006.2: read-tree br_base br_ballast (1000001) 4.15(2.72+1.41) 3.21(1.97+1.22) -22.7%\n0006.3: switch between br_base br_ballast (1000001) 8.11(5.57+2.28) 6.77(4.36+2.14) -16.5%\n0006.4: switch between br_ballast br_ballast_plus_1 (1000001) 13.52(8.68+4.35) 11.80(7.38+3.96) -12.7%\n0006.5: switch between aliases (1000001) 13.59(8.75+4.43) 11.85(7.49+3.87) -12.8%\n\nOn linux.git, results are:\nTest HEAD^ HEAD\n------------------------------------------------------------------------------------------------------\n0006.2: read-tree br_base br_ballast (57994) 0.24(0.22+0.01) 0.20(0.17+0.02) -16.7%\n0006.3: switch between br_base br_ballast (57994) 9.91(5.82+2.79) 10.26(5.92+2.77) +3.5%\n0006.4: switch between br_ballast br_ballast_plus_1 (57994) 0.59(0.44+0.16) 0.50(0.34+0.18) -15.3%\n0006.5: switch between aliases (57994) 0.62(0.48+0.16) 0.50(0.35+0.16) -19.4%\n\nSigned-off-by: Jeff Hostetler \n---\n read-cache.c | 46 ++++++++++++++++++++++++++++++++++++++++++++--\n 1 file changed, 44 insertions(+), 2 deletions(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex 97f13a1..a8ef823 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -918,9 +918,24 @@ static int has_dir_name(struct index_state *istate,\n \tint stage = ce_stage(ce);\n \tconst char *name = ce->name;\n \tconst char *slash = name + ce_namelen(ce);\n+\tsize_t len_eq_last;\n+\tint cmp_last = 0;\n+\n+\tif (istate->cache_nr > 0) {\n+\t\t/*\n+\t\t * Compare the entry's full path with the last path in the index.\n+\t\t * If it sorts AFTER the last entry in the index and they have no\n+\t\t * common prefix, then there cannot be any F/D name conflicts.\n+\t\t */\n+\t\tcmp_last = strcmp_offset(name,\n+\t\t\tistate->cache[istate->cache_nr-1]->name,\n+\t\t\t&len_eq_last);\n+\t\tif (cmp_last > 0 && len_eq_last == 0)\n+\t\t\treturn retval;\n+\t}\n \n \tfor (;;) {\n-\t\tint len;\n+\t\tsize_t len;\n \n \t\tfor (;;) {\n \t\t\tif (*--slash == '/')\n@@ -930,6 +945,24 @@ static int has_dir_name(struct index_state *istate,\n \t\t}\n \t\tlen = slash - name;\n \n+\t\tif (cmp_last > 0) {\n+\t\t\t/*\n+\t\t\t * If this part of the directory prefix (including the trailing\n+\t\t\t * slash) already appears in the path of the last entry in the\n+\t\t\t * index, then we cannot also have a file with this prefix (or\n+\t\t\t * any parent directory prefix).\n+\t\t\t */\n+\t\t\tif (len+1 <= len_eq_last)\n+\t\t\t\treturn retval;\n+\t\t\t/*\n+\t\t\t * If this part of the directory prefix (excluding the trailing\n+\t\t\t * slash) is longer than the known equal portions, then this part\n+\t\t\t * of the prefix cannot collide with a file. Go on to the parent.\n+\t\t\t */\n+\t\t\tif (len > len_eq_last)\n+\t\t\t\tcontinue;\n+\t\t}\n+\n \t\tpos = index_name_stage_pos(istate, name, len, stage);\n \t\tif (pos >= 0) {\n \t\t\t/*\n@@ -1021,7 +1054,16 @@ static int add_index_entry_with_check(struct index_state *istate, struct cache_e\n \n \tif (!(option & ADD_CACHE_KEEP_CACHE_TREE))\n \t\tcache_tree_invalidate_path(istate, ce->name);\n-\tpos = index_name_stage_pos(istate, ce->name, ce_namelen(ce), ce_stage(ce));\n+\n+\t/*\n+\t * If this entry's path sorts after the last entry in the index,\n+\t * we can avoid searching for it.\n+\t */\n+\tif (istate->cache_nr > 0 &&\n+\t\tstrcmp(ce->name, istate->cache[istate->cache_nr - 1]->name) > 0)\n+\t\tpos = -istate->cache_nr - 1;\n+\telse\n+\t\tpos = index_name_stage_pos(istate, ce->name, ce_namelen(ce), ce_stage(ce));\n \n \t/* existing match? Just replace it. */\n \tif (pos >= 0) {\n-- \n2.9.3\n\n"},{"id":"316623","messageId":"20170411191702.20134-3-git@jeffhostetler.com","threadId":"45666","inReplyTo":"20170411191702.20134-1-git@jeffhostetler.com","subject":"[PATCH v9 2/3] p0006-read-tree-checkout: perf test to time read-tree","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-11T19:17:01Z","receivedAt":"2017-04-11T19:17:28Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nCreated t/perf/repos/many-files.sh to generate large, but\nartificial repositories.\n\nCreated t/perf/p0006-read-tree-checkout.sh to measure\nperformance on various read-tree, checkout, and update-index\noperations. This test can run using either artificial repos\ndescribed above or normal repos.\n\nSigned-off-by: Jeff Hostetler \n---\n t/perf/p0006-read-tree-checkout.sh | 69 +++++++++++++++++++++++\n t/perf/repos/.gitignore | 1 +\n t/perf/repos/many-files.sh | 110 +++++++++++++++++++++++++++++++++++++\n 3 files changed, 180 insertions(+)\n create mode 100755 t/perf/p0006-read-tree-checkout.sh\n create mode 100644 t/perf/repos/.gitignore\n create mode 100755 t/perf/repos/many-files.sh\n\ndiff --git a/t/perf/p0006-read-tree-checkout.sh b/t/perf/p0006-read-tree-checkout.sh\nnew file mode 100755\nindex 0000000..5881251\n--- /dev/null\n+++ b/t/perf/p0006-read-tree-checkout.sh\n@@ -0,0 +1,69 @@\n+#!/bin/sh\n+##\n+## This test measures the performance of various read-tree\n+## and checkout operations. It is primarily interested in\n+## the algorithmic costs of index operations and recursive\n+## tree traversal -- and NOT disk I/O on thousands of files.\n+\n+test_description=\"Tests performance of read-tree\"\n+\n+. ./perf-lib.sh\n+\n+test_perf_default_repo\n+\n+## If the test repo was generated by ./repos/many-files.sh\n+## then we know something about the data shape and branches,\n+## so we can isolate testing to the ballast-related commits\n+## and setup sparse-checkout so we don't have to populate\n+## the ballast files and directories.\n+##\n+## Otherwise, we make some general assumptions about the\n+## repo and consider the entire history of the current\n+## branch to be the ballast.\n+\n+git branch | grep p0006-ballast >/dev/null 2>&1\n+synthetic=$?\n+if test \"$synthetic\" = 0\n+then\n+ echo Assuming synthetic repo from many-files.sh\n+ git branch br_base master\n+ git branch br_ballast p0006-ballast^\n+ git branch br_ballast_alias p0006-ballast^\n+ git branch br_ballast_plus_1 p0006-ballast\n+ echo '/*' >.git/info/sparse-checkout\n+ echo '!ballast/*' >>.git/info/sparse-checkout\n+ git config --local core.sparsecheckout 1\n+else\n+ echo Assuming non-synthetic repo...\n+ git branch br_base $(git rev-list HEAD | tail -n 1)\n+ git branch br_ballast HEAD^ || error \"no ancestor commit from current head\"\n+ git branch br_ballast_alias HEAD^\n+ git branch br_ballast_plus_1 HEAD\n+fi\n+\n+test_expect_success 'setup' '\n+\tgit checkout -q br_ballast\n+'\n+\n+nr_files=$(git ls-files | wc -l)\n+\n+test_perf \"read-tree br_base br_ballast ($nr_files)\" '\n+\tgit read-tree -m br_base br_ballast -n\n+'\n+\n+test_perf \"switch between br_base br_ballast ($nr_files)\" '\n+\tgit checkout -q br_base &&\n+\tgit checkout -q br_ballast\n+'\n+\n+test_perf \"switch between br_ballast br_ballast_plus_1 ($nr_files)\" '\n+\tgit checkout -q br_ballast_plus_1 &&\n+\tgit checkout -q br_ballast\n+'\n+\n+test_perf \"switch between aliases ($nr_files)\" '\n+\tgit checkout -q br_ballast_alias &&\n+\tgit checkout -q br_ballast\n+'\n+\n+test_done\ndiff --git a/t/perf/repos/.gitignore b/t/perf/repos/.gitignore\nnew file mode 100644\nindex 0000000..72e3dc3\n--- /dev/null\n+++ b/t/perf/repos/.gitignore\n@@ -0,0 +1 @@\n+gen-*/\ndiff --git a/t/perf/repos/many-files.sh b/t/perf/repos/many-files.sh\nnew file mode 100755\nindex 0000000..5a1d25e\n--- /dev/null\n+++ b/t/perf/repos/many-files.sh\n@@ -0,0 +1,110 @@\n+#!/bin/sh\n+## Generate test data repository using the given parameters.\n+## When omitted, we create \"gen-many-files-d-w-f.git\".\n+##\n+## Usage: [-r repo] [-d depth] [-w width] [-f files]\n+##\n+## -r repo: path to the new repo to be generated\n+## -d depth: the depth of sub-directories\n+## -w width: the number of sub-directories at each level\n+## -f files: the number of files created in each directory\n+##\n+## Note that all files will have the same SHA-1 and each\n+## directory at a level will have the same SHA-1, so we\n+## will potentially have a large index, but not a large\n+## ODB.\n+##\n+## Ballast will be created under \"ballast/\".\n+\n+EMPTY_BLOB=e69de29bb2d1d6434b8b29ae775ad8c2e48c5391\n+\n+set -e\n+\n+## (5, 10, 9) will create 999,999 ballast files.\n+## (4, 10, 9) will create 99,999 ballast files.\n+depth=5\n+width=10\n+files=9\n+\n+while test \"$#\" -ne 0\n+do\n+ case \"$1\" in\n+\t-r)\n+\t shift;\n+\t test \"$#\" -ne 0 || { echo 'error: -r requires an argument' >&2; exit 1; }\n+\t repo=$1;\n+\t shift ;;\n+\t-d)\n+\t shift;\n+\t test \"$#\" -ne 0 || { echo 'error: -d requires an argument' >&2; exit 1; }\n+\t depth=$1;\n+\t shift ;;\n+\t-w)\n+\t shift;\n+\t test \"$#\" -ne 0 || { echo 'error: -w requires an argument' >&2; exit 1; }\n+\t width=$1;\n+\t shift ;;\n+\t-f)\n+\t shift;\n+\t test \"$#\" -ne 0 || { echo 'error: -f requires an argument' >&2; exit 1; }\n+\t files=$1;\n+\t shift ;;\n+\t*)\n+\t echo \"error: unknown option '$1'\" >&2; exit 1 ;;\n+\tesac\n+done\n+\n+## Inflate the index with thousands of empty files.\n+## usage: dir depth width files\n+fill_index() {\n+\tawk -v arg_dir=$1 -v arg_depth=$2 -v arg_width=$3 -v arg_files=$4 '\n+\t\tfunction make_paths(dir, depth, width, files, f, w) {\n+\t\t\tfor (f = 1; f <= files; f++) {\n+\t\t\t\tprint dir \"/file\" f\n+\t\t\t}\n+\t\t\tif (depth > 0) {\n+\t\t\t\tfor (w = 1; w <= width; w++) {\n+\t\t\t\t\tmake_paths(dir \"/dir\" w, depth - 1, width, files)\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\t\tEND { make_paths(arg_dir, arg_depth, arg_width, arg_files) }\n+\t\t' many-files.params\n+git add many-files.*\n+git commit -q -m params\n+\n+## Create ballast for p0006 based upon the given params and\n+## inflate the index with thousands of empty files and commit.\n+git checkout -b p0006-ballast\n+fill_index \"ballast\" $depth $width $files\n+git commit -q -m \"ballast\"\n+\n+nr_files=$(git ls-files | wc -l)\n+\n+## Modify 1 file and commit.\n+echo \"$depth $width $files\" >>many-files.params\n+git add many-files.params\n+git commit -q -m \"ballast plus 1\"\n+\n+## Checkout master to put repo in canonical state (because\n+## the perf test may need to clone and enable sparse-checkout\n+## before attempting to checkout a commit with the ballast\n+## (because it may contain 100K directories and 1M files)).\n+git checkout master\n+\n+echo \"Repository \"$repo\" ($depth, $width, $files) created. Ballast $nr_files.\"\n+exit 0\n-- \n2.9.3\n\n"},{"id":"316624","messageId":"20170411192633.kprye72cqy4fggi7@sigill.intra.peff.net","threadId":"45666","inReplyTo":"20170411191702.20134-1-git@jeffhostetler.com","subject":"Re: [PATCH v9 0/3] read-cache: speed up add_index_entry","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-11T19:26:33Z","receivedAt":"2017-04-11T19:26:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 11, 2017 at 07:16:59PM +0000, git@jeffhostetler.com wrote:\n\n> I think this version has addressed everything raise so far,\n> so I think I'm ready to let this one rest. Thanks for all\n> the help and feedback.\n\nYeah, this addresses my nitpicks with the perf stuff. Thanks for\nsticking with it.\n\n-Peff\n"},{"id":"316666","messageId":"xmqq37deqpyw.fsf@gitster.mtv.corp.google.com","threadId":"45666","inReplyTo":"20170411191702.20134-4-git@jeffhostetler.com","subject":"Re: [PATCH v9 3/3] read-cache: speed up add_index_entry during checkout","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-04-12T03:12:07Z","receivedAt":"2017-04-12T03:12:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"git@jeffhostetler.com writes:\n\n> From: Jeff Hostetler \n>\n> Teach add_index_entry_with_check() and has_dir_name()\n> to see if the path of the new item is greater than the\n> last path in the index array before attempting to search\n> for it.\n>\n> During checkout, merge_working_tree() populates the new\n> index in sorted order, so this change will save at least 2\n> binary lookups per file.\n\nSmart and simple.\n\n> diff --git a/read-cache.c b/read-cache.c\n> index 97f13a1..a8ef823 100644\n> --- a/read-cache.c\n> +++ b/read-cache.c\n> @@ -918,9 +918,24 @@ static int has_dir_name(struct index_state *istate,\n> \tint stage = ce_stage(ce);\n> \tconst char *name = ce->name;\n> \tconst char *slash = name + ce_namelen(ce);\n> +\tsize_t len_eq_last;\n> +\tint cmp_last = 0;\n> +\n> +\tif (istate->cache_nr > 0) {\n> +\t\t/*\n> +\t\t * Compare the entry's full path with the last path in the index.\n> +\t\t * If it sorts AFTER the last entry in the index and they have no\n> +\t\t * common prefix, then there cannot be any F/D name conflicts.\n> +\t\t */\n> +\t\tcmp_last = strcmp_offset(name,\n> +\t\t\tistate->cache[istate->cache_nr-1]->name,\n\nStyle? \"istate->cache[istate->cache_nr - 1]->name\"\n\n> +\t\t\t&len_eq_last);\n> +\t\tif (cmp_last > 0 && len_eq_last == 0)\n> +\t\t\treturn retval;\n> +\t}\n\nLet me follow the logic aloud. Say the last entry in the cache is\n\"x/y\". If we came here with ce->name == \"x\", we need to worry about\nnuking the existing entry \"x/y\". But if we have \"zoo\", that cannot\npossibly overlap and we can safely return 0.\n\nThat sounds correct, except that it might be playing overly safe.\nIf we came here with \"xx\", we still are safe, but len_eq_last would\nbe non-zero. Probably it is not worth the extra complexity to catch\nit here (rather than letting the loop below to handle it).\n\n> \tfor (;;) {\n> -\t\tint len;\n> +\t\tsize_t len;\n> \n> \t\tfor (;;) {\n> \t\t\tif (*--slash == '/')\n> @@ -930,6 +945,24 @@ static int has_dir_name(struct index_state *istate,\n> \t\t}\n> \t\tlen = slash - name;\n\nMental note: cmp_last may be 0, >0 or <0 at this point in the very\nfirst iteration of the loop. It is not updated in the loop. The\nvariable len_eq_last are used to carry the information about the\nlast entry we learned at the beginning of this function---the new\nspecial case happens only when the path we are adding sorts later\nthan the last existing entry (i.e. cmp_last > 0).\n\n> +\t\tif (cmp_last > 0) {\n> +\t\t\t/*\n> +\t\t\t * If this part of the directory prefix (including the trailing\n> +\t\t\t * slash) already appears in the path of the last entry in the\n> +\t\t\t * index, then we cannot also have a file with this prefix (or\n> +\t\t\t * any parent directory prefix).\n> +\t\t\t */\n> +\t\t\tif (len+1 <= len_eq_last)\n\nStyle? \"len + 1\".\n\n> +\t\t\t\treturn retval;\n> +\t\t\t/*\n> +\t\t\t * If this part of the directory prefix (excluding the trailing\n> +\t\t\t * slash) is longer than the known equal portions, then this part\n> +\t\t\t * of the prefix cannot collide with a file. Go on to the parent.\n> +\t\t\t */\n> +\t\t\tif (len > len_eq_last)\n> +\t\t\t\tcontinue;\n\nHmph, is the reasoning used in the two conditionals above sound?\nDoes this work correctly even when the last existing entry in the\ncache is marked with CE_REMOVE?\n\n> +\t\t}\n> +\n> \t\tpos = index_name_stage_pos(istate, name, len, stage);\n> \t\tif (pos >= 0) {\n> \t\t\t/*\n> @@ -1021,7 +1054,16 @@ static int add_index_entry_with_check(struct index_state *istate, struct cache_e\n> \n> \tif (!(option & ADD_CACHE_KEEP_CACHE_TREE))\n> \t\tcache_tree_invalidate_path(istate, ce->name);\n> -\tpos = index_name_stage_pos(istate, ce->name, ce_namelen(ce), ce_stage(ce));\n> +\n> +\t/*\n> +\t * If this entry's path sorts after the last entry in the index,\n> +\t * we can avoid searching for it.\n> +\t */\n> +\tif (istate->cache_nr > 0 &&\n> +\t\tstrcmp(ce->name, istate->cache[istate->cache_nr - 1]->name) > 0)\n> +\t\tpos = -istate->cache_nr - 1;\n> +\telse\n> +\t\tpos = index_name_stage_pos(istate, ce->name, ce_namelen(ce), ce_stage(ce));\n\nThis one (unlike the change to has_dir_name()) is trivially and\nobviously correct.\n\n> \t/* existing match? Just replace it. */\n> \tif (pos >= 0) {\n"},{"id":"316815","messageId":"d233feed-2494-e68b-5fe6-4e1bd43ef423@jeffhostetler.com","threadId":"45666","inReplyTo":"xmqq37deqpyw.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v9 3/3] read-cache: speed up add_index_entry during checkout","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-14T13:06:14Z","receivedAt":"2017-04-14T13:06:20Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/11/2017 11:12 PM, Junio C Hamano wrote:\n> git@jeffhostetler.com writes:\n>\n>> From: Jeff Hostetler \n>>\n>> Teach add_index_entry_with_check() and has_dir_name()\n>> to see if the path of the new item is greater than the\n>> last path in the index array before attempting to search\n>> for it.\n>>\n>> During checkout, merge_working_tree() populates the new\n>> index in sorted order, so this change will save at least 2\n>> binary lookups per file.\n>\n> Smart and simple.\n>\n>> diff --git a/read-cache.c b/read-cache.c\n>> index 97f13a1..a8ef823 100644\n>> --- a/read-cache.c\n>> +++ b/read-cache.c\n>> @@ -918,9 +918,24 @@ static int has_dir_name(struct index_state *istate,\n>> \tint stage = ce_stage(ce);\n>> \tconst char *name = ce->name;\n>> \tconst char *slash = name + ce_namelen(ce);\n>> +\tsize_t len_eq_last;\n>> +\tint cmp_last = 0;\n>> +\n>> +\tif (istate->cache_nr > 0) {\n>> +\t\t/*\n>> +\t\t * Compare the entry's full path with the last path in the index.\n>> +\t\t * If it sorts AFTER the last entry in the index and they have no\n>> +\t\t * common prefix, then there cannot be any F/D name conflicts.\n>> +\t\t */\n>> +\t\tcmp_last = strcmp_offset(name,\n>> +\t\t\tistate->cache[istate->cache_nr-1]->name,\n>\n> Style? \"istate->cache[istate->cache_nr - 1]->name\"\n>\n>> +\t\t\t&len_eq_last);\n>> +\t\tif (cmp_last > 0 && len_eq_last == 0)\n>> +\t\t\treturn retval;\n>> +\t}\n>\n> Let me follow the logic aloud. Say the last entry in the cache is\n> \"x/y\". If we came here with ce->name == \"x\", we need to worry about\n> nuking the existing entry \"x/y\". But if we have \"zoo\", that cannot\n> possibly overlap and we can safely return 0.\n>\n> That sounds correct, except that it might be playing overly safe.\n> If we came here with \"xx\", we still are safe, but len_eq_last would\n> be non-zero. Probably it is not worth the extra complexity to catch\n> it here (rather than letting the loop below to handle it).\n>\n>> \tfor (;;) {\n>> -\t\tint len;\n>> +\t\tsize_t len;\n>>\n>> \t\tfor (;;) {\n>> \t\t\tif (*--slash == '/')\n>> @@ -930,6 +945,24 @@ static int has_dir_name(struct index_state *istate,\n>> \t\t}\n>> \t\tlen = slash - name;\n>\n> Mental note: cmp_last may be 0, >0 or <0 at this point in the very\n> first iteration of the loop. It is not updated in the loop. The\n> variable len_eq_last are used to carry the information about the\n> last entry we learned at the beginning of this function---the new\n> special case happens only when the path we are adding sorts later\n> than the last existing entry (i.e. cmp_last > 0).\n>\n>> +\t\tif (cmp_last > 0) {\n>> +\t\t\t/*\n>> +\t\t\t * If this part of the directory prefix (including the trailing\n>> +\t\t\t * slash) already appears in the path of the last entry in the\n>> +\t\t\t * index, then we cannot also have a file with this prefix (or\n>> +\t\t\t * any parent directory prefix).\n>> +\t\t\t */\n>> +\t\t\tif (len+1 <= len_eq_last)\n>\n> Style? \"len + 1\".\n>\n>> +\t\t\t\treturn retval;\n>> +\t\t\t/*\n>> +\t\t\t * If this part of the directory prefix (excluding the trailing\n>> +\t\t\t * slash) is longer than the known equal portions, then this part\n>> +\t\t\t * of the prefix cannot collide with a file. Go on to the parent.\n>> +\t\t\t */\n>> +\t\t\tif (len > len_eq_last)\n>> +\t\t\t\tcontinue;\n>\n> Hmph, is the reasoning used in the two conditionals above sound?\n> Does this work correctly even when the last existing entry in the\n> cache is marked with CE_REMOVE?\n\nI'll double check my math here. I also want to think about\nthe \"too conservative\" comment above.\n\nWRT if the last entry is CE_REMOVE, I think we are still OK\nbecause we are asking if the given ce is strictly greater than\nthe last entry so that we can append it rather than searching\nfor a collision or insertion point.\n\nThanks,\nJeff\n"}]}