{"thread":{"id":"45604","subject":"[PATCH v4 0/4] read-cache: speed up add_index_entry","startedAt":"2017-04-04T21:09:07Z","lastAt":"2017-04-04T21:09:17Z","messageCount":5,"participants":["git@jeffhostetler.com"],"isPatch":true,"patchVersion":4,"patchTotal":4},"messages":[{"id":"316168","messageId":"20170404210847.50860-1-git@jeffhostetler.com","threadId":"45604","inReplyTo":null,"subject":"[PATCH v4 0/4] read-cache: speed up add_index_entry","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-04T21:08:43Z","receivedAt":"2017-04-04T21:09:07Z","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 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\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 (1003037)              3.24(2.46+0.72)\n0004.3: switch branches (3038 1003037)   7.53(5.66+1.56)\n\n$ ./p0004-read-tree.sh\n0004.2: read-tree (1003040)              2.45(1.79+0.61)\n0004.3: switch branches (3041 1003040)   6.65(4.22+1.60)\n\n================\nBefore and after numbers on index with 100K files.\n\n./p0004-read-tree.sh\n0004.2: read-tree (103037)              0.30(0.20+0.08)\n0004.3: switch branches (3038 103037)   0.65(0.47+0.16)\n\n$ ./p0004-read-tree.sh\n0004.2: read-tree (103040)              0.25(0.16+0.07)\n0004.3: switch branches (3041 103040)   0.58(0.44+0.13)\n================\n\n\nJeff Hostetler (4):\n  p0004-read-tree: perf test to time read-tree\n  read-cache: add strcmp_offset function\n  test-strcmp-offset: created test for strcmp_offset\n  read-cache: speed up add_index_entry during checkout\n\n Makefile                      |  1 +\n cache.h                       |  1 +\n read-cache.c                  | 73 ++++++++++++++++++++++++++++++++++++-\n t/helper/.gitignore           |  1 +\n t/helper/test-strcmp-offset.c | 64 +++++++++++++++++++++++++++++++++\n t/perf/p0004-read-tree.sh     | 84 +++++++++++++++++++++++++++++++++++++++++++\n t/t0065-strcmp-offset.sh      | 11 ++++++\n 7 files changed, 234 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":"316169","messageId":"20170404210847.50860-2-git@jeffhostetler.com","threadId":"45604","inReplyTo":"20170404210847.50860-1-git@jeffhostetler.com","subject":"[PATCH v4 1/4] p0004-read-tree: perf test to time read-tree","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-04T21:08:44Z","receivedAt":"2017-04-04T21:09:12Z","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 | 84 +++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 84 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..ffbbf8e\n--- /dev/null\n+++ b/t/perf/p0004-read-tree.sh\n@@ -0,0 +1,84 @@\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_work=xxx_work_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_work\n+export new_dir\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.\n+test_expect_success 'inflate the index' '\n+\tgit reset --hard &&\n+\tgit branch $br_base &&\n+\tgit branch $br_work &&\n+\tgit checkout $br_work &&\n+\tfill_index $new_dir $depth $width $files &&\n+\tgit commit -m $br_work &&\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_work_xxx branch.\n+nr_work=$(git ls-files | wc -l)\n+export nr_work\n+\n+test_perf \"read-tree ($nr_work)\" '\n+\tgit read-tree -m $br_base $br_work -n\n+'\n+\n+test_perf \"switch branches ($nr_base $nr_work)\" '\n+\tgit checkout $br_base &&\n+\tgit checkout $br_work\n+'\n+\n+\n+test_done\n-- \n2.9.3\n\n"},{"id":"316170","messageId":"20170404210847.50860-5-git@jeffhostetler.com","threadId":"45604","inReplyTo":"20170404210847.50860-1-git@jeffhostetler.com","subject":"[PATCH v4 4/4] read-cache: speed up add_index_entry during checkout","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-04T21:08:47Z","receivedAt":"2017-04-04T21:09:14Z","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 saves at least 2\nlookups per file.\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 b3fc77d..bf9fc53 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -927,6 +927,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@@ -939,6 +954,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@@ -1030,7 +1063,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":"316171","messageId":"20170404210847.50860-3-git@jeffhostetler.com","threadId":"45604","inReplyTo":"20170404210847.50860-1-git@jeffhostetler.com","subject":"[PATCH v4 2/4] read-cache: add strcmp_offset function","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-04T21:08:45Z","receivedAt":"2017-04-04T21:09:15Z","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\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n---\n cache.h      |  1 +\n read-cache.c | 29 +++++++++++++++++++++++++++++\n 2 files changed, 30 insertions(+)\n\ndiff --git a/cache.h b/cache.h\nindex 80b6372..4d82490 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_in, const char *s2_in, 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..b3fc77d 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -887,6 +887,35 @@ 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+ */\n+int strcmp_offset(const char *s1_in, const char *s2_in, int *first_change)\n+{\n+\tconst unsigned char *s1 = (const unsigned char *)s1_in;\n+\tconst unsigned char *s2 = (const unsigned char *)s2_in;\n+\tint diff = 0;\n+\tint k;\n+\n+\t*first_change = 0;\n+\tfor (k=0; s1[k]; k++)\n+\t\tif ((diff = (s1[k] - s2[k])))\n+\t\t\tgoto found_it;\n+\tif (!s2[k])\n+\t\treturn 0;\n+\tdiff = -1;\n+\n+found_it:\n+\t*first_change = k;\n+\tif (diff > 0)\n+\t\treturn 1;\n+\telse if (diff < 0)\n+\t\treturn -1;\n+\telse\n+\t\treturn 0;\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?\n-- \n2.9.3\n\n"},{"id":"316172","messageId":"20170404210847.50860-4-git@jeffhostetler.com","threadId":"45604","inReplyTo":"20170404210847.50860-1-git@jeffhostetler.com","subject":"[PATCH v4 3/4] test-strcmp-offset: created test for strcmp_offset","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-04T21:08:46Z","receivedAt":"2017-04-04T21:09:17Z","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 Makefile                      |  1 +\n t/helper/.gitignore           |  1 +\n t/helper/test-strcmp-offset.c | 64 +++++++++++++++++++++++++++++++++++++++++++\n t/t0065-strcmp-offset.sh      | 11 ++++++++\n 4 files changed, 77 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/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..fe01318\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;\n+};\n+\n+static struct test_data data[] = {\n+\t{ \"abc\", \"abc\", 0 },\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"}]}