{"thread":{"id":"45622","subject":"[PATCH v6 0/3] read-cache: speed up add_index_entry","startedAt":"2017-04-06T16:34:56Z","lastAt":"2017-04-08T10:43:35Z","messageCount":9,"participants":["git@jeffhostetler.com","René Scharfe","Jeff King","Jeff Hostetler"],"isPatch":true,"patchVersion":6,"patchTotal":3},"messages":[{"id":"316286","messageId":"20170406163442.36463-1-git@jeffhostetler.com","threadId":"45622","inReplyTo":null,"subject":"[PATCH v6 0/3] read-cache: speed up add_index_entry","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-06T16:34:39Z","receivedAt":"2017-04-06T16:34:56Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nVersion 6 combines the strcmp_offset() function and unit tests\ninto a single commit and places it first in the history, so that\nit can be isolated into a separate patch series if desired. It\nalso clarifies the return value when the strings are equal.  The\ncommit message for the actual speed up now includes the perf\nnumbers (rather than having them here in the cover letter).\n\n================\nTeach add_index_entry_with_check() and has_dir_name()\nto avoid index lookups if the given path sorts after\nthe last entry in the index.\n\nThis saves at least 2 binary searches per entry.\n\nThis improves performance during checkout and read-tree because\nmerge_working_tree() and unpack_trees() processes a list of already\nsorted entries.\n\nJeff Hostetler (3):\n  read-cache: add strcmp_offset function\n  p0004-read-tree: 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                  |  64 ++++++++++++++++++++++-\n t/helper/.gitignore           |   1 +\n t/helper/test-strcmp-offset.c |  64 +++++++++++++++++++++++\n t/perf/p0004-read-tree.sh     | 117 ++++++++++++++++++++++++++++++++++++++++++\n t/t0065-strcmp-offset.sh      |  11 ++++\n 7 files changed, 258 insertions(+), 1 deletion(-)\n create mode 100644 t/helper/test-strcmp-offset.c\n create mode 100755 t/perf/p0004-read-tree.sh\n create mode 100755 t/t0065-strcmp-offset.sh\n\n-- \n2.9.3\n\n"},{"id":"316287","messageId":"20170406163442.36463-2-git@jeffhostetler.com","threadId":"45622","inReplyTo":"20170406163442.36463-1-git@jeffhostetler.com","subject":"[PATCH v6 1/3] read-cache: add strcmp_offset function","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-06T16:34:40Z","receivedAt":"2017-04-06T16:34:58Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\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 <jeffhost@microsoft.com>\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 | 64 +++++++++++++++++++++++++++++++++++++++++++\n t/t0065-strcmp-offset.sh      | 11 ++++++++\n 6 files changed, 98 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..fad194b 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, int *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..e8f1900 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, int *first_change)\n+{\n+\tint 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..887ba7e\n--- /dev/null\n+++ b/t/helper/test-strcmp-offset.c\n@@ -0,0 +1,64 @@\n+#include \"cache.h\"\n+\n+struct test_data {\n+\tconst char *s1;\n+\tconst char *s2;\n+\tint first_change; /* or strlen() when equal */\n+};\n+\n+static struct test_data data[] = {\n+\t{ \"abc\", \"abc\", 3 },\n+\t{ \"abc\", \"def\", 0 },\n+\n+\t{ \"abc\", \"abz\", 2 },\n+\n+\t{ \"abc\", \"abcdef\", 3 },\n+\n+\t{ \"abc\\xF0zzz\", \"abc\\xFFzzz\", 3 },\n+\n+\t{ NULL, NULL, 0 }\n+};\n+\n+int try_pair(const char *sa, const char *sb, int first_change)\n+{\n+\tint failed = 0;\n+\tint offset, r_exp, r_tst;\n+\tint r_exp_sign, r_tst_sign;\n+\n+\t/*\n+\t * Because differnt CRTs behave differently, only rely on signs\n+\t * of the result values.\n+\t */\n+\tr_exp = strcmp(sa, sb);\n+\tr_exp_sign = ((r_exp < 0) ? -1 : ((r_exp == 0) ? 0 : 1));\n+\n+\tr_tst = strcmp_offset(sa, sb, &offset);\n+\tr_tst_sign = ((r_tst < 0) ? -1 : ((r_tst == 0) ? 0 : 1));\n+\n+\tif (r_tst_sign != r_exp_sign) {\n+\t\terror(\"FAIL: '%s' vs '%s', result expect %d, observed %d\\n\",\n+\t\t\t  sa, sb, r_exp_sign, r_tst_sign);\n+\t\tfailed = 1;\n+\t}\n+\n+\tif (offset != first_change) {\n+\t\terror(\"FAIL: '%s' vs '%s', offset expect %d, observed %d\\n\",\n+\t\t\t  sa, sb, first_change, offset);\n+\t\tfailed = 1;\n+\t}\n+\n+\treturn failed;\n+}\n+\n+int cmd_main(int argc, const char **argv)\n+{\n+\tint failed = 0;\n+\tint k;\n+\n+\tfor (k=0; data[k].s1; k++) {\n+\t\tfailed += try_pair(data[k].s1, data[k].s2, data[k].first_change);\n+\t\tfailed += try_pair(data[k].s2, data[k].s1, data[k].first_change);\n+\t}\n+\n+\treturn failed;\n+}\ndiff --git a/t/t0065-strcmp-offset.sh b/t/t0065-strcmp-offset.sh\nnew file mode 100755\nindex 0000000..0176c8c\n--- /dev/null\n+++ b/t/t0065-strcmp-offset.sh\n@@ -0,0 +1,11 @@\n+#!/bin/sh\n+\n+test_description='Test strcmp_offset functionality'\n+\n+. ./test-lib.sh\n+\n+test_expect_success run_helper '\n+\ttest-strcmp-offset\n+'\n+\n+test_done\n-- \n2.9.3\n\n"},{"id":"316288","messageId":"20170406163442.36463-3-git@jeffhostetler.com","threadId":"45622","inReplyTo":"20170406163442.36463-1-git@jeffhostetler.com","subject":"[PATCH v6 2/3] p0004-read-tree: perf test to time read-tree","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-06T16:34:41Z","receivedAt":"2017-04-06T16:35:00Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n---\n t/perf/p0004-read-tree.sh | 117 ++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 117 insertions(+)\n create mode 100755 t/perf/p0004-read-tree.sh\n\ndiff --git a/t/perf/p0004-read-tree.sh b/t/perf/p0004-read-tree.sh\nnew file mode 100755\nindex 0000000..d56020d\n--- /dev/null\n+++ b/t/perf/p0004-read-tree.sh\n@@ -0,0 +1,117 @@\n+#!/bin/sh\n+\n+test_description=\"Tests performance of read-tree\"\n+\n+. ./perf-lib.sh\n+\n+test_perf_default_repo\n+test_checkout_worktree\n+\n+## usage: dir depth width files\n+make_paths () {\n+\tfor f in $(seq $4)\n+\tdo\n+\t\techo $1/file$f\n+\tdone;\n+\tif test $2 -gt 0;\n+\tthen\n+\t\tfor w in $(seq $3)\n+\t\tdo\n+\t\t\tmake_paths $1/dir$w $(($2 - 1)) $3 $4\n+\t\tdone\n+\tfi\n+\treturn 0\n+}\n+\n+fill_index () {\n+\tmake_paths $1 $2 $3 $4 |\n+\tsed \"s/^/100644 $EMPTY_BLOB\t/\" |\n+\tgit update-index --index-info\n+\treturn 0\n+}\n+\n+br_base=xxx_base_xxx\n+br_work1=xxx_work1_xxx\n+br_work2=xxx_work2_xxx\n+br_work3=xxx_work3_xxx\n+\n+new_dir=xxx_dir_xxx\n+\n+## (5, 10, 9) will create 999,999 files.\n+## (4, 10, 9) will create  99,999 files.\n+depth=5\n+width=10\n+files=9\n+\n+export br_base\n+export br_work1\n+export br_work2\n+export br_work3\n+\n+export new_dir\n+\n+export depth\n+export width\n+export files\n+\n+## The number of files in the xxx_base_xxx branch.\n+nr_base=$(git ls-files | wc -l)\n+export nr_base\n+\n+## Inflate the index with thousands of empty files and commit it.\n+## Turn on sparse-checkout so that we don't have to populate them\n+## later when we start switching branches.  Use reset --hard to\n+## quickly checkout the new HEAD with minimum actual files.\n+test_expect_success 'inflate the index' '\n+\tgit reset --hard &&\n+\tgit branch $br_base &&\n+\tgit branch $br_work1 &&\n+\tgit checkout $br_work1 &&\n+\tfill_index $new_dir $depth $width $files &&\n+\tgit commit -m $br_work1 &&\n+\techo $new_dir/file1 >.git/info/sparse-checkout &&\n+\tgit config --local core.sparsecheckout 1 &&\n+\tgit reset --hard\n+'\n+\n+## The number of files in the xxx_work1_xxx branch.\n+nr_work1=$(git ls-files | wc -l)\n+export nr_work1\n+\n+test_perf \"read-tree work1 ($nr_work1)\" '\n+\tgit read-tree -m $br_base $br_work1 -n\n+'\n+\n+## Alternate between base and work branches several\n+## times to measure a large change.\n+test_perf \"switch base work1 ($nr_base $nr_work1)\" '\n+\tgit checkout $br_base &&\n+\tgit checkout $br_work1\n+'\n+\n+## Create work2 by modifying 1 file in work1.\n+## Create work3 as an alias of work2.\n+test_expect_success 'setup work2' '\n+\tgit branch $br_work2 &&\n+\tgit checkout $br_work2 &&\n+\techo x >$new_dir/file1 &&\n+\tgit add $new_dir/file1 &&\n+\tgit commit -m $br_work2 &&\n+\tgit branch $br_work3\n+'\n+\n+## Alternate between work1 and work2 several times\n+## to measure a very small change.\n+test_perf \"switch work1 work2 ($nr_work1)\" '\n+\tgit checkout $br_work1 &&\n+\tgit checkout $br_work2\n+'\n+\n+## Alternate between branches work2 and work3 which\n+## are aliases of the same commit.\n+test_perf \"switch commit aliases ($nr_work1)\" '\n+\tgit checkout $br_work3 &&\n+\tgit checkout $br_work2\n+'\n+\n+test_done\n-- \n2.9.3\n\n"},{"id":"316289","messageId":"20170406163442.36463-4-git@jeffhostetler.com","threadId":"45622","inReplyTo":"20170406163442.36463-1-git@jeffhostetler.com","subject":"[PATCH v6 3/3] read-cache: speed up add_index_entry during checkout","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-06T16:34:42Z","receivedAt":"2017-04-06T16:35:03Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\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\n================\nBefore and after numbers on index with 1M files\n./p0004-read-tree.sh\n0004.2: read-tree work1 (1003037)          3.21(2.54+0.62)\n0004.3: switch base work1 (3038 1003037)   7.49(5.39+1.84)\n0004.5: switch work1 work2 (1003037)       11.91(8.38+3.00)\n0004.6: switch commit aliases (1003037)    12.22(8.30+3.06)\n\n./p0004-read-tree.sh\n0004.2: read-tree work1 (1003040)          2.40(1.65+0.73)\n0004.3: switch base work1 (3041 1003040)   6.07(4.12+1.66)\n0004.5: switch work1 work2 (1003040)       10.23(6.76+2.92)\n0004.6: switch commit aliases (1003040)    10.53(6.97+2.83)\n================\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n---\n read-cache.c | 44 +++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 43 insertions(+), 1 deletion(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex e8f1900..58f69b2 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -918,6 +918,21 @@ 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+\tint 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@@ -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":"316314","messageId":"97be34a6-ecdb-9820-1315-4cb5ed3b9101@web.de","threadId":"45622","inReplyTo":"20170406163442.36463-2-git@jeffhostetler.com","subject":"Re: [PATCH v6 1/3] read-cache: add strcmp_offset function","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-04-06T23:07:38Z","receivedAt":"2017-04-06T23:08:17Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 06.04.2017 um 18:34 schrieb git@jeffhostetler.com:\n> diff --git a/read-cache.c b/read-cache.c\n> index 9054369..e8f1900 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, int *first_change)\n> +{\n> +\tint 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\nI like how this is shaping up to become a reusable function, but I only \nfound one other possible use case (in read-cache.c::ce_write_entry), \nwhich somehow irritates me.  Either I didn't look hard enough (likely), \nwe haven't got fitting code just yet, or this function isn't meant to be \nexported -- in the latter case its interface doesn't have to be polished \nas much.  (Just a thought, don't let me stop you.)\n\nAssuming strcmp_offset() is a library-grade function then its \nfirst_change parameter should point to a size_t instead of an int, no?\n\nCasting away the const qualifier in the return line is a bit iffy.  Why \nnot cast after dereferencing, like this?\n\n\treturn (unsigned char)s1[k] - (unsigned char)s2[k];\n\nRené\n"},{"id":"316317","messageId":"20170407044626.ypsqnyxguw43gprm@sigill.intra.peff.net","threadId":"45622","inReplyTo":"20170406163442.36463-1-git@jeffhostetler.com","subject":"Re: [PATCH v6 0/3] read-cache: speed up add_index_entry","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-07T04:46:27Z","receivedAt":"2017-04-07T04:46:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 06, 2017 at 04:34:39PM +0000, git@jeffhostetler.com wrote:\n\n> Teach add_index_entry_with_check() and has_dir_name()\n> to avoid index lookups if the given path sorts after\n> the last entry in the index.\n> \n> This saves at least 2 binary searches per entry.\n> \n> This improves performance during checkout and read-tree because\n> merge_working_tree() and unpack_trees() processes a list of already\n> sorted entries.\n\nJust thinking about this algorithmically for a moment. You're saving the\nbinary search when the input is given in sorted order. But in other\ncases you're adding an extra strcmp() before the binary search begins.\nSo it's a tradeoff.\n\nHow often is the input sorted?  You save O(log n) strcmps for a \"hit\"\nwith your patch, and one for a \"miss\". So it's a net win if we expect at\nleast 1/log(n) of additions to be sorted (I'm talking about individual\ncalls, but it should scale linearly either way over a set of n calls).\n\nI have no clue if that's a reasonable assumption or not.\n\n-Peff\n"},{"id":"316369","messageId":"2244d0d6-5909-a5b1-6606-4b22331dca59@jeffhostetler.com","threadId":"45622","inReplyTo":"97be34a6-ecdb-9820-1315-4cb5ed3b9101@web.de","subject":"Re: [PATCH v6 1/3] read-cache: add strcmp_offset function","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-07T18:04:57Z","receivedAt":"2017-04-07T18:05:03Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/6/2017 7:07 PM, René Scharfe wrote:\n> Am 06.04.2017 um 18:34 schrieb git@jeffhostetler.com:\n>> diff --git a/read-cache.c b/read-cache.c\n>> index 9054369..e8f1900 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>>       return retval;\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, int *first_change)\n>> +{\n>> +    int k;\n>> +\n>> +    if (!first_change)\n>> +        return strcmp(s1, s2);\n>> +\n>> +    for (k = 0; s1[k] == s2[k]; k++)\n>> +        if (s1[k] == '\\0')\n>> +            break;\n>> +\n>> +    *first_change = k;\n>> +    return ((unsigned char *)s1)[k] - ((unsigned char *)s2)[k];\n>> +}\n>\n> I like how this is shaping up to become a reusable function, but I only\n> found one other possible use case (in read-cache.c::ce_write_entry),\n> which somehow irritates me.  Either I didn't look hard enough (likely),\n> we haven't got fitting code just yet, or this function isn't meant to be\n> exported -- in the latter case its interface doesn't have to be polished\n> as much.  (Just a thought, don't let me stop you.)\n>\n> Assuming strcmp_offset() is a library-grade function then its\n> first_change parameter should point to a size_t instead of an int, no?\n\nyes, size_t. thanks.\n\n>\n> Casting away the const qualifier in the return line is a bit iffy.  Why\n> not cast after dereferencing, like this?\n>\n>     return (unsigned char)s1[k] - (unsigned char)s2[k];\n\nGood point.\n\nThanks\nJeff\n"},{"id":"316370","messageId":"6f31ee65-517e-419c-b0c1-3ccdd3f95b37@jeffhostetler.com","threadId":"45622","inReplyTo":"20170407044626.ypsqnyxguw43gprm@sigill.intra.peff.net","subject":"Re: [PATCH v6 0/3] read-cache: speed up add_index_entry","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-07T18:27:24Z","receivedAt":"2017-04-07T18:27:34Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/7/2017 12:46 AM, Jeff King wrote:\n> On Thu, Apr 06, 2017 at 04:34:39PM +0000, git@jeffhostetler.com wrote:\n>\n>> Teach add_index_entry_with_check() and has_dir_name()\n>> to avoid index lookups if the given path sorts after\n>> the last entry in the index.\n>>\n>> This saves at least 2 binary searches per entry.\n>>\n>> This improves performance during checkout and read-tree because\n>> merge_working_tree() and unpack_trees() processes a list of already\n>> sorted entries.\n>\n> Just thinking about this algorithmically for a moment. You're saving the\n> binary search when the input is given in sorted order. But in other\n> cases you're adding an extra strcmp() before the binary search begins.\n> So it's a tradeoff.\n>\n> How often is the input sorted?  You save O(log n) strcmps for a \"hit\"\n> with your patch, and one for a \"miss\". So it's a net win if we expect at\n> least 1/log(n) of additions to be sorted (I'm talking about individual\n> calls, but it should scale linearly either way over a set of n calls).\n>\n> I have no clue if that's a reasonable assumption or not.\n\nI was seeing checkout call merge_working_tree to iterate over the\nsource index/trees and call add_index_entry() for each.  For example,\nin a \"checkout -b\" like operation where both sides are the same, this\ncalls keep_entry() which appends the entry to the new index array.\nThe append path should always be taken because the iteration is being\ndriven from a sorted list.\n\nI would think calls to add/stage individual files arrive in random\norder, so I'm not suggesting replacing the code -- just checking the\nend first.\n\nJeff\n\n"},{"id":"316395","messageId":"20170408104328.3iuvedkewygkovnb@sigill.intra.peff.net","threadId":"45622","inReplyTo":"6f31ee65-517e-419c-b0c1-3ccdd3f95b37@jeffhostetler.com","subject":"Re: [PATCH v6 0/3] read-cache: speed up add_index_entry","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-08T10:43:28Z","receivedAt":"2017-04-08T10:43:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Apr 07, 2017 at 02:27:24PM -0400, Jeff Hostetler wrote:\n\n> > Just thinking about this algorithmically for a moment. You're saving the\n> > binary search when the input is given in sorted order. But in other\n> > cases you're adding an extra strcmp() before the binary search begins.\n> > So it's a tradeoff.\n> > \n> > How often is the input sorted?  You save O(log n) strcmps for a \"hit\"\n> > with your patch, and one for a \"miss\". So it's a net win if we expect at\n> > least 1/log(n) of additions to be sorted (I'm talking about individual\n> > calls, but it should scale linearly either way over a set of n calls).\n> > \n> > I have no clue if that's a reasonable assumption or not.\n> \n> I was seeing checkout call merge_working_tree to iterate over the\n> source index/trees and call add_index_entry() for each.  For example,\n> in a \"checkout -b\" like operation where both sides are the same, this\n> calls keep_entry() which appends the entry to the new index array.\n> The append path should always be taken because the iteration is being\n> driven from a sorted list.\n> \n> I would think calls to add/stage individual files arrive in random\n> order, so I'm not suggesting replacing the code -- just checking the\n> end first.\n\nRight, what I was wondering is how much this costs in those random-order\ncases. We _know_ it speeds up the cases you care about, but I want to\nmake sure that it is not making some other case worse. How often do the\nrandom-order cases come up, and how much are they slowed?\n\nI suspect in practice that calls here fall into one of two camps:\nfeeding a small-ish (compared to the total number of entries) set of\npaths, or feeding _every_ path. And if you are feeding every path, you\nare likely to do so in sorted order, rather than a random jumble. So it\nhelps in the big cases, and the small cases are presumably small enough\nthat we don't care much.\n\nAt least that seems like a plausible line of reasoning to me. ;)\n\n-Peff\n"}]}