{"thread":{"id":"45608","subject":"[PATCH v5 0/4] read-cache: speed up add_index_entry","startedAt":"2017-04-05T17:39:37Z","lastAt":"2017-04-06T20:42:29Z","messageCount":16,"participants":["git@jeffhostetler.com","SZEDER Gábor","Johannes Schindelin","Jeff Hostetler","René Scharfe"],"isPatch":true,"patchVersion":5,"patchTotal":4},"messages":[{"id":"316213","messageId":"20170405173809.3098-1-git@jeffhostetler.com","threadId":"45608","inReplyTo":null,"subject":"[PATCH v5 0/4] read-cache: speed up add_index_entry","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-05T17:38:05Z","receivedAt":"2017-04-05T17:39:37Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\n[This is labeled as version 5 because of a cut-n-paste\naccident where my first version of this patch was labeled\nversion 4.]\n\nThis version adds more perf tests to p0004-read-tree.sh\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\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\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 | 116 ++++++++++++++++++++++++++++++++++++++++++\n t/t0065-strcmp-offset.sh | 11 ++++\n 7 files changed, 266 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":"316214","messageId":"20170405173809.3098-5-git@jeffhostetler.com","threadId":"45608","inReplyTo":"20170405173809.3098-1-git@jeffhostetler.com","subject":"[PATCH v5 4/4] read-cache: speed up add_index_entry during checkout","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-05T17:38:09Z","receivedAt":"2017-04-05T17:39:46Z","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 saves at least 2\nlookups per file.\n\nSigned-off-by: Jeff Hostetler \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":"316215","messageId":"20170405173809.3098-4-git@jeffhostetler.com","threadId":"45608","inReplyTo":"20170405173809.3098-1-git@jeffhostetler.com","subject":"[PATCH v5 3/4] test-strcmp-offset: created test for strcmp_offset","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-05T17:38:08Z","receivedAt":"2017-04-05T17:39:48Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nSigned-off-by: Jeff Hostetler \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"},{"id":"316216","messageId":"20170405173809.3098-2-git@jeffhostetler.com","threadId":"45608","inReplyTo":"20170405173809.3098-1-git@jeffhostetler.com","subject":"[PATCH v5 1/4] p0004-read-tree: perf test to time read-tree","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-05T17:38:06Z","receivedAt":"2017-04-05T17:40:01Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nSigned-off-by: Jeff Hostetler \n---\n t/perf/p0004-read-tree.sh | 116 ++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 116 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..5d8bbf5\n--- /dev/null\n+++ b/t/perf/p0004-read-tree.sh\n@@ -0,0 +1,116 @@\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.\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":"316217","messageId":"20170405173809.3098-3-git@jeffhostetler.com","threadId":"45608","inReplyTo":"20170405173809.3098-1-git@jeffhostetler.com","subject":"[PATCH v5 2/4] read-cache: add strcmp_offset function","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-05T17:38:07Z","receivedAt":"2017-04-05T17:40:04Z","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\nSigned-off-by: Jeff Hostetler \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":"316242","messageId":"20170405224752.2242-1-szeder.dev@gmail.com","threadId":"45608","inReplyTo":"20170405173809.3098-4-git@jeffhostetler.com","subject":"Re: [PATCH v5 3/4] test-strcmp-offset: created test for strcmp_offset","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2017-04-05T22:47:52Z","receivedAt":"2017-04-05T22:48:18Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"I think this patch should be squashed into the previous commit; I\ndon't see any reason why the tests should be added in a different\ncommit than the function they are testing. However...\n\n> Signed-off-by: Jeff Hostetler \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\nSure, tests are good, but I have to wonder how this would scale in the\nlong term, when even such simple functions would get their own\nt/helper/test-func executable and t/tNNNN-func.sh script.\n\n"},{"id":"316243","messageId":"20170405225453.2632-1-szeder.dev@gmail.com","threadId":"45608","inReplyTo":"20170405173809.3098-5-git@jeffhostetler.com","subject":"Re: [PATCH v5 4/4] read-cache: speed up add_index_entry during checkout","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2017-04-05T22:54:53Z","receivedAt":"2017-04-05T22:55:06Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"> 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 saves at least 2\n> lookups per file.\n\nI think the performance numbers from the cover letter should be\nincluded here, so they will be included in the history.\n\n> Signed-off-by: Jeff Hostetler \n\n\n"},{"id":"316260","messageId":"alpine.DEB.2.20.1704061014120.4268@virtualbox","threadId":"45608","inReplyTo":"20170405224752.2242-1-szeder.dev@gmail.com","subject":"Re: [PATCH v5 3/4] test-strcmp-offset: created test for strcmp_offset","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-04-06T08:21:38Z","receivedAt":"2017-04-06T08:22:07Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Gábor,\n\nOn Thu, 6 Apr 2017, SZEDER Gábor wrote:\n\n> I think this patch should be squashed into the previous commit; I\n> don't see any reason why the tests should be added in a different\n> commit than the function they are testing.\n\nI am of two minds there. In some cases, the newly added test demonstrates\nthe intended usage, and therefore makes for a nice documentation. In other\ncases, the new test is large enough to stand on its own, i.e. to merit a\nseparate patch (also to make reviewing easier).\n\nIn this particular case, I tend to the latter: it is large enough a patch\nthat it is easier to review as a separate patch.\n\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> \n> Sure, tests are good, but I have to wonder how this would scale in the\n> long term, when even such simple functions would get their own\n> t/helper/test-func executable and t/tNNNN-func.sh script.\n\nTrue. The proliferation of executables in t/helper/ got a little out of\nhand.\n\nBut there is nothing preventing us from consolidating a few of them into a\nsingle executable, using our wonderful option parsing function with\nOPT_CMDMODE to switch between the different functions.\n\nI could see, for example, how we could consolidate all string-related\ntest helpers into a single one, say, test-strings:\n\nt/helper/test-ctype.c\nt/helper/test-regex.c\nt/helper/test-strcmp-offset.c\nt/helper/test-string-list.c\nt/helper/test-line-buffer.c\nt/helper/test-urlmatch-normalization.c\nt/helper/test-wildmatch.c\n\nAlso, these helpers seem to be related to index handling and could go into\na new test-index helper:\n\nt/helper/test-dump-cache-tree.c\nt/helper/test-dump-split-index.c\nt/helper/test-dump-untracked-cache.c\nt/helper/test-index-version.c\nt/helper/test-scrap-cache-tree.c\n\nCiao,\nJohannes"},{"id":"316277","messageId":"75c1724f-f0af-6b3e-71b1-97d486d94396@jeffhostetler.com","threadId":"45608","inReplyTo":"20170405225453.2632-1-szeder.dev@gmail.com","subject":"Re: [PATCH v5 4/4] read-cache: speed up add_index_entry during checkout","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-06T14:05:17Z","receivedAt":"2017-04-06T14:05:24Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/5/2017 6:54 PM, SZEDER Gábor wrote:\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 saves at least 2\n>> lookups per file.\n>\n> I think the performance numbers from the cover letter should be\n> included here, so they will be included in the history.\n\nGood point.\n\n"},{"id":"316279","messageId":"20170406141912.14536-1-szeder.dev@gmail.com","threadId":"45608","inReplyTo":"20170405173809.3098-3-git@jeffhostetler.com","subject":"Re: [PATCH v5 2/4] read-cache: add strcmp_offset function","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2017-04-06T14:19:12Z","receivedAt":"2017-04-06T14:19:30Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"> Add strcmp_offset() function to also return the offset of the\n> first change.\n> \n> Signed-off-by: Jeff Hostetler \n> ---\n> cache.h | 1 +\n> read-cache.c | 29 +++++++++++++++++++++++++++++\n> 2 files changed, 30 insertions(+)\n> \n> diff --git a/cache.h b/cache.h\n> index 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);\n> diff --git a/read-cache.c b/read-cache.c\n> index 9054369..b3fc77d 100644\n> --- a/read-cache.c\n> +++ b/read-cache.c\n\nread-cache.c is probably not the best place for such a general string\nutility function, though I'm not sure where its most apropriate place\nwould be.\n\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\nThis comment doesn't tell us what will happen with the offset\nparameter if it is NULL or if the two strings are equal. I don't\nreally care about the safety check for NULL: a callsite not interested\nin the offset should just call strcmp() instead. I'm fine either way.\nHowever, setting it to 0 when the strings are equal doesn't seem quite\nright, does it.\n\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\nThe implementation seems to me a bit long-winded, with more\nconditional statements than necessary. How about something like this\ninstead? Much shorter, no goto and only half the number of\nconditionals to reason about, leaves *first_change untouched when the\ntwo strings are equal, and deals with it being NULL.\n\nint strcmp_offset(const char *s1, const char *s2, int *first_change)\n{\n\tint k;\n\n\tfor (k = 0; s1[k] == s2[k]; k++)\n\t\tif (s1[k] == '\\0')\n\t\t\treturn 0;\n\n\tif (first_change)\n\t\t*first_change = k;\n\treturn ((unsigned char *)s1)[k] - ((unsigned char *)s2)[k];\n}\n\n"},{"id":"316280","messageId":"afdbf105-9dee-3779-6c1b-a6c65c773f23@jeffhostetler.com","threadId":"45608","inReplyTo":"alpine.DEB.2.20.1704061014120.4268@virtualbox","subject":"Re: [PATCH v5 3/4] test-strcmp-offset: created test for strcmp_offset","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-06T14:25:05Z","receivedAt":"2017-04-06T14:25:11Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/6/2017 4:21 AM, Johannes Schindelin wrote:\n> Hi Gábor,\n>\n> On Thu, 6 Apr 2017, SZEDER Gábor wrote:\n>\n>> I think this patch should be squashed into the previous commit; I\n>> don't see any reason why the tests should be added in a different\n>> commit than the function they are testing.\n\nWill do.\n\n>\n> I am of two minds there. In some cases, the newly added test demonstrates\n> the intended usage, and therefore makes for a nice documentation. In other\n> cases, the new test is large enough to stand on its own, i.e. to merit a\n> separate patch (also to make reviewing easier).\n>\n> In this particular case, I tend to the latter: it is large enough a patch\n> that it is easier to review as a separate patch.\n>\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>>\n>> Sure, tests are good, but I have to wonder how this would scale in the\n>> long term, when even such simple functions would get their own\n>> t/helper/test-func executable and t/tNNNN-func.sh script.\n\nI think this is the start of a larger conversation on\nhow we want to handle function-level unit-testing and\noutside the scope of this patch series.\n\n>\n> True. The proliferation of executables in t/helper/ got a little out of\n> hand.\n>\n> But there is nothing preventing us from consolidating a few of them into a\n> single executable, using our wonderful option parsing function with\n> OPT_CMDMODE to switch between the different functions.\n>\n> I could see, for example, how we could consolidate all string-related\n> test helpers into a single one, say, test-strings:\n>\n> t/helper/test-ctype.c\n> t/helper/test-regex.c\n> t/helper/test-strcmp-offset.c\n> t/helper/test-string-list.c\n> t/helper/test-line-buffer.c\n> t/helper/test-urlmatch-normalization.c\n> t/helper/test-wildmatch.c\n>\n> Also, these helpers seem to be related to index handling and could go into\n> a new test-index helper:\n>\n> t/helper/test-dump-cache-tree.c\n> t/helper/test-dump-split-index.c\n> t/helper/test-dump-untracked-cache.c\n> t/helper/test-index-version.c\n> t/helper/test-scrap-cache-tree.c\n\nThis is an interesting proposal. I could go one further and\nsay we have a single \"t/helper/unit-test.c\" that has series\nof \"t/helper/builtin/*.c\" commands (using the same mechanism\nas the builtin commands in git.exe). The question then is\nhow much of the test logic and/or parameters go into the shell\nscripts.\n\nBut again, all of that is outside my scope here.\nJeff\n\n"},{"id":"316284","messageId":"3f88c428-6d04-6ef5-f7bc-952daad2703a@jeffhostetler.com","threadId":"45608","inReplyTo":"20170406141912.14536-1-szeder.dev@gmail.com","subject":"Re: [PATCH v5 2/4] read-cache: add strcmp_offset function","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-06T15:58:10Z","receivedAt":"2017-04-06T15:58:18Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/6/2017 10:19 AM, SZEDER Gábor wrote:\n>> Add strcmp_offset() function to also return the offset of the\n>> first change.\n>>\n>> Signed-off-by: Jeff Hostetler \n>> ---\n>> cache.h | 1 +\n>> read-cache.c | 29 +++++++++++++++++++++++++++++\n>> 2 files changed, 30 insertions(+)\n>>\n>> diff --git a/cache.h b/cache.h\n>> index 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);\n>> diff --git a/read-cache.c b/read-cache.c\n>> index 9054369..b3fc77d 100644\n>> --- a/read-cache.c\n>> +++ b/read-cache.c\n>\n> read-cache.c is probably not the best place for such a general string\n> utility function, though I'm not sure where its most apropriate place\n> would be.\n\nYeah, I looked and didn't see any place so I left it here\nnear it's first usage for now.\n\n>\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> This comment doesn't tell us what will happen with the offset\n> parameter if it is NULL or if the two strings are equal. I don't\n> really care about the safety check for NULL: a callsite not interested\n> in the offset should just call strcmp() instead. I'm fine either way.\n> However, setting it to 0 when the strings are equal doesn't seem quite\n> right, does it.\n\nGood catch. I'll add a null check.\n\nWhen the strings are equal, I'm not sure any one value is\nbetter than another. I could leave it undefined or set it\nto the length. That might be more useful since we have it on\nhand and it might save the caller a strlen() later.\n\n>\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> The implementation seems to me a bit long-winded, with more\n> conditional statements than necessary. How about something like this\n> instead? Much shorter, no goto and only half the number of\n> conditionals to reason about, leaves *first_change untouched when the\n> two strings are equal, and deals with it being NULL.\n>\n> int strcmp_offset(const char *s1, const char *s2, int *first_change)\n> {\n> \tint k;\n>\n> \tfor (k = 0; s1[k] == s2[k]; k++)\n> \t\tif (s1[k] == '\\0')\n> \t\t\treturn 0;\n>\n> \tif (first_change)\n> \t\t*first_change = k;\n> \treturn ((unsigned char *)s1)[k] - ((unsigned char *)s2)[k];\n> }\n>\n\nLet me give that a try. Thanks!\nJeff\n\n"},{"id":"316300","messageId":"4da78dff-7caa-b560-8af9-f5a3dfc0bed2@web.de","threadId":"45608","inReplyTo":"20170405173809.3098-4-git@jeffhostetler.com","subject":"Re: [PATCH v5 3/4] test-strcmp-offset: created test for strcmp_offset","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-04-06T20:20:35Z","receivedAt":"2017-04-06T20:21:02Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 05.04.2017 um 19:38 schrieb git@jeffhostetler.com:\n> diff --git a/t/helper/test-strcmp-offset.c b/t/helper/test-strcmp-offset.c\n> new file mode 100644\n> index 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\nThis should be static, right? Found with -Wmissing-prototypes.\n\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\ns/differnt/different/\n\nRené\n"},{"id":"316301","messageId":"6937b76e-9bbf-7ce5-8605-e09f556f8a26@web.de","threadId":"45608","inReplyTo":"20170405173809.3098-2-git@jeffhostetler.com","subject":"Re: [PATCH v5 1/4] p0004-read-tree: perf test to time read-tree","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-04-06T20:20:49Z","receivedAt":"2017-04-06T20:21:08Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 05.04.2017 um 19:38 schrieb git@jeffhostetler.com:\n> From: Jeff Hostetler \n> \n> Signed-off-by: Jeff Hostetler \n> ---\n> t/perf/p0004-read-tree.sh | 116 ++++++++++++++++++++++++++++++++++++++++++++++\n> 1 file changed, 116 insertions(+)\n> create mode 100755 t/perf/p0004-read-tree.sh\n> \n> diff --git a/t/perf/p0004-read-tree.sh b/t/perf/p0004-read-tree.sh\n> new file mode 100755\n> index 0000000..5d8bbf5\n> --- /dev/null\n> +++ b/t/perf/p0004-read-tree.sh\n> @@ -0,0 +1,116 @@\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\"make_paths xxx_dir_xxx 5 10 9\" takes more than a minute for me.\nProviding its results as a file would be quicker but less flexible.\nThe following command prints the same result in less than a second.\n\n\tawk -v dir=xxx_dir_xxx -v depth=5 -v width=10 -v files=9 '\n \tfunction make_paths(dir, depth, width, files, i)\n\t {\n \t for (i = 1; i <= files; i++) {\n\t print dir \"/file\" i\n \t }\n\t if (depth > 0) {\n \t for (i = 1; i <= width; i++) {\n\t make_paths(dir \"/dir\" i, depth - 1, width, files)\n \t }\n \t}\n\t }\n\t END {make_paths(dir, depth, width, files)}\n\t' +\n> +fill_index () {\n> +\tmake_paths $1 $2 $3 $4 |\n> +\tsed \"s/^/100644 $EMPTY_BLOB\t/\" |\n\nYou could add the prefix to the script above and avoid this sed call\nas well.\n\nRené\n"},{"id":"316305","messageId":"6286a37f-aa22-ff70-3127-c417a6920c35@jeffhostetler.com","threadId":"45608","inReplyTo":"6937b76e-9bbf-7ce5-8605-e09f556f8a26@web.de","subject":"Re: [PATCH v5 1/4] p0004-read-tree: perf test to time read-tree","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-06T20:41:03Z","receivedAt":"2017-04-06T20:41:17Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/6/2017 4:20 PM, René Scharfe wrote:\n> Am 05.04.2017 um 19:38 schrieb git@jeffhostetler.com:\n>> From: Jeff Hostetler \n>>\n>> Signed-off-by: Jeff Hostetler \n>> ---\n>> t/perf/p0004-read-tree.sh | 116 ++++++++++++++++++++++++++++++++++++++++++++++\n>> 1 file changed, 116 insertions(+)\n>> create mode 100755 t/perf/p0004-read-tree.sh\n>>\n>> diff --git a/t/perf/p0004-read-tree.sh b/t/perf/p0004-read-tree.sh\n>> new file mode 100755\n>> index 0000000..5d8bbf5\n>> --- /dev/null\n>> +++ b/t/perf/p0004-read-tree.sh\n>> @@ -0,0 +1,116 @@\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> \"make_paths xxx_dir_xxx 5 10 9\" takes more than a minute for me.\n> Providing its results as a file would be quicker but less flexible.\n> The following command prints the same result in less than a second.\n>\n> \tawk -v dir=xxx_dir_xxx -v depth=5 -v width=10 -v files=9 '\n> \tfunction make_paths(dir, depth, width, files, i)\n> \t {\n> \t for (i = 1; i <= files; i++) {\n> \t print dir \"/file\" i\n> \t }\n> \t if (depth > 0) {\n> \t for (i = 1; i <= width; i++) {\n> \t make_paths(dir \"/dir\" i, depth - 1, width, files)\n> \t }\n> \t}\n> \t }\n> \t END {make_paths(dir, depth, width, files)}\n> \t' \n> It's faster because it avoids calling seq thousands of times.\n\nVery nice!!! I'll give that a try. Thanks!\n\n>\n>> +\n>> +fill_index () {\n>> +\tmake_paths $1 $2 $3 $4 |\n>> +\tsed \"s/^/100644 $EMPTY_BLOB\t/\" |\n>\n> You could add the prefix to the script above and avoid this sed call\n> as well.\n>\n> René\n>\n"},{"id":"316307","messageId":"0b27bff5-53a1-51f3-aeb4-6bd7bcd6fddc@jeffhostetler.com","threadId":"45608","inReplyTo":"4da78dff-7caa-b560-8af9-f5a3dfc0bed2@web.de","subject":"Re: [PATCH v5 3/4] test-strcmp-offset: created test for strcmp_offset","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-06T20:42:22Z","receivedAt":"2017-04-06T20:42:29Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/6/2017 4:20 PM, René Scharfe wrote:\n> Am 05.04.2017 um 19:38 schrieb git@jeffhostetler.com:\n>> diff --git a/t/helper/test-strcmp-offset.c\n>> b/t/helper/test-strcmp-offset.c\n>> new file mode 100644\n>> index 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>> + const char *s1;\n>> + const char *s2;\n>> + int first_change;\n>> +};\n>> +\n>> +static struct test_data data[] = {\n>> + { \"abc\", \"abc\", 0 },\n>> + { \"abc\", \"def\", 0 },\n>> +\n>> + { \"abc\", \"abz\", 2 },\n>> +\n>> + { \"abc\", \"abcdef\", 3 },\n>> +\n>> + { \"abc\\xF0zzz\", \"abc\\xFFzzz\", 3 },\n>> +\n>> + { NULL, NULL, 0 }\n>> +};\n>> +\n>> +int try_pair(const char *sa, const char *sb, int first_change)\n>\n> This should be static, right? Found with -Wmissing-prototypes.\n\nright. thanks.\n\n>\n>> +{\n>> + int failed = 0;\n>> + int offset, r_exp, r_tst;\n>> + int r_exp_sign, r_tst_sign;\n>> +\n>> + /*\n>> + * Because differnt CRTs behave differently, only rely on signs\n>\n> s/differnt/different/\n>\n> René\n"}]}