{"thread":{"id":"45634","subject":"[PATCH v7 3/3] read-cache: speed up add_index_entry during checkout","startedAt":"2017-04-07T21:21:13Z","lastAt":"2017-04-10T13:34:44Z","messageCount":8,"participants":["git@jeffhostetler.com","Jeff King","Jeff Hostetler"],"isPatch":true,"patchVersion":7,"patchTotal":3},"messages":[{"id":"316379","messageId":"20170407212047.64950-4-git@jeffhostetler.com","threadId":"45634","inReplyTo":"20170407212047.64950-1-git@jeffhostetler.com","subject":"[PATCH v7 3/3] read-cache: speed up add_index_entry during checkout","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-07T21:20:47Z","receivedAt":"2017-04-07T21:21:13Z","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 | 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":"316380","messageId":"20170407212047.64950-1-git@jeffhostetler.com","threadId":"45634","inReplyTo":null,"subject":"[PATCH v7 0/3] read-cache: speed up add_index_entry","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-07T21:20:44Z","receivedAt":"2017-04-07T21:21:14Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nVersion 7 addresses size_t and casting issues in strcmp_offset()\nand replaces shell test function with an awk expression to make\nthe perf test run faster.\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                  |  66 +++++++++++++++++++++++-\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, 259 insertions(+), 2 deletions(-)\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":"316381","messageId":"20170407212047.64950-3-git@jeffhostetler.com","threadId":"45634","inReplyTo":"20170407212047.64950-1-git@jeffhostetler.com","subject":"[PATCH v7 2/3] p0004-read-tree: perf test to time read-tree","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-07T21:20:46Z","receivedAt":"2017-04-07T21:21:16Z","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..a70e969\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+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+' </dev/null |\n+\tsed \"s/^/100644 $EMPTY_BLOB\t/\" |\n+\tgit update-index --index-info\n+\treturn 0\n+}\n+\n+\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":"316382","messageId":"20170407212047.64950-2-git@jeffhostetler.com","threadId":"45634","inReplyTo":"20170407212047.64950-1-git@jeffhostetler.com","subject":"[PATCH v7 1/3] read-cache: add strcmp_offset function","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-07T21:20:45Z","receivedAt":"2017-04-07T21:21:17Z","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..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..03e1eef\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+\tsize_t expected_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, size_t expected_first_change)\n+{\n+\tint failed = 0;\n+\tint r_exp, r_tst, r_exp_sign, r_tst_sign;\n+\tsize_t offset;\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 != expected_first_change) {\n+\t\terror(\"FAIL: '%s' vs '%s', offset expect %lu, observed %lu\\n\",\n+\t\t\t  sa, sb, expected_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].expected_first_change);\n+\t\tfailed += try_pair(data[k].s2, data[k].s1, data[k].expected_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":"316391","messageId":"20170408094021.jdpx5l7kfv423zgj@sigill.intra.peff.net","threadId":"45634","inReplyTo":"20170407212047.64950-4-git@jeffhostetler.com","subject":"Re: [PATCH v7 3/3] read-cache: speed up add_index_entry during checkout","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-08T09:40:21Z","receivedAt":"2017-04-08T09:40:30Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Apr 07, 2017 at 09:20:47PM +0000, git@jeffhostetler.com wrote:\n\n> This helps performance on very large repositories.\n> \n> ================\n> Before and after numbers on index with 1M files\n> ./p0004-read-tree.sh\n> 0004.2: read-tree work1 (1003037)          3.21(2.54+0.62)\n> 0004.3: switch base work1 (3038 1003037)   7.49(5.39+1.84)\n> 0004.5: switch work1 work2 (1003037)       11.91(8.38+3.00)\n> 0004.6: switch commit aliases (1003037)    12.22(8.30+3.06)\n> \n> ./p0004-read-tree.sh\n> 0004.2: read-tree work1 (1003040)          2.40(1.65+0.73)\n> 0004.3: switch base work1 (3041 1003040)   6.07(4.12+1.66)\n> 0004.5: switch work1 work2 (1003040)       10.23(6.76+2.92)\n> 0004.6: switch commit aliases (1003040)    10.53(6.97+2.83)\n> ================\n\nBy the way, you may want to try:\n\n  $ cd t/perf\n  $ ./run HEAD^ HEAD p0004-read-tree.sh\n\nwhich gives you the before/after in a nice table, with percentage\nchanges:\n\n  Test                                       HEAD^             HEAD                  \n  -----------------------------------------------------------------------------------\n  0004.2: read-tree work1 (1003065)          2.34(1.90+0.42)   1.91(1.51+0.38) -18.4%\n  0004.3: switch base work1 (3066 1003065)   5.12(4.14+0.96)   4.45(3.55+0.88) -13.1%\n  0004.5: switch work1 work2 (1003065)       8.55(6.63+1.87)   7.78(5.76+2.00) -9.0% \n  0004.6: switch commit aliases (1003065)    8.59(6.75+1.80)   7.64(5.92+1.70) -11.1%\n\nThe results are stored for each tested version, so you can re-run just a\nsingle test and then re-output the results with \"./aggregate.perl HEAD^\nHEAD p0004-read-tree.sh\".\n\nThe \"run\" script obviously builds each version behind the scenes, so you\nprobably also want to set GIT_PERF_MAKE_OPTS as appropriate (at the very\nleast \"-j16\" makes it more pleasant).\n\n-Peff\n"},{"id":"316393","messageId":"20170408101142.iztq3lxcaayw2w6q@sigill.intra.peff.net","threadId":"45634","inReplyTo":"20170407212047.64950-2-git@jeffhostetler.com","subject":"Re: [PATCH v7 1/3] read-cache: add strcmp_offset function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-08T10:11:42Z","receivedAt":"2017-04-08T10:11:51Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Apr 07, 2017 at 09:20:45PM +0000, git@jeffhostetler.com wrote:\n\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..03e1eef\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> +\tsize_t expected_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\nI've been thinking a bit on the comments on earlier rounds regarding C\ntests. I think in the early days, we generally had plumbing that exposed\nthe C interfaces in a pretty transparent way. I.e., it was reasonable to\nunit-test update-index, because you pretty much know how input to it\nwill map to the code and data structures used.\n\nThese days we have more C infrastructure, and it's sometimes hard to\ntickle the exact inputs to those modules through plumbing commands. So I\ndon't really object to adding module-specific helpers that make it easy\nto unit test these underlying modules.\n\nI'm not sure how I feel about sticking test data in the helpers, though.\nA higher level language like shell is actually pretty good for passing\ndata around. Passing in the input makes it much easier to prod a helper\nwith new test cases, see its output, run it in a debugger for a specific\ncase, etc.\n\nIt also integrates better with our test suite. For instance, here:\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 != expected_first_change) {\n> +\t\terror(\"FAIL: '%s' vs '%s', offset expect %lu, observed %lu\\n\",\n> +\t\t\t  sa, sb, expected_first_change, offset);\n> +\t\tfailed = 1;\n> +\t}\n> +\n> +\treturn failed;\n> +}\n\nYou're essentially rebuilding a test harness just for this one function,\nand the regular test harness only knows \"did anything fail\", and nothing\nabout specific tests.\n\nPerhaps something like:\n\n t/helper/test-strcmp-offset.c | 66 +++++++----------------------------\n t/t0065-strcmp-offset.sh      | 17 +++++++--\n 2 files changed, 26 insertions(+), 57 deletions(-)\n\ndiff --git a/t/helper/test-strcmp-offset.c b/t/helper/test-strcmp-offset.c\nindex 03e1eef8a..1fdf4d137 100644\n--- a/t/helper/test-strcmp-offset.c\n+++ b/t/helper/test-strcmp-offset.c\n@@ -1,64 +1,22 @@\n #include \"cache.h\"\n \n-struct test_data {\n-\tconst char *s1;\n-\tconst char *s2;\n-\tsize_t expected_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, size_t expected_first_change)\n+int cmd_main(int argc, const char **argv)\n {\n-\tint failed = 0;\n-\tint r_exp, r_tst, r_exp_sign, r_tst_sign;\n+\tint result;\n \tsize_t offset;\n \n+\tif (!argv[1] || !argv[2])\n+\t\tdie(\"usage: %s <string1> <string2>\", 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-\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 != expected_first_change) {\n-\t\terror(\"FAIL: '%s' vs '%s', offset expect %lu, observed %lu\\n\",\n-\t\t\t  sa, sb, expected_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].expected_first_change);\n-\t\tfailed += try_pair(data[k].s2, data[k].s1, data[k].expected_first_change);\n-\t}\n-\n-\treturn failed;\n+\tresult = result < 0 ? -1 :\n+\t\t result > 0 ? 1 :\n+\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\nindex 0176c8c92..8c167d24b 100755\n--- a/t/t0065-strcmp-offset.sh\n+++ b/t/t0065-strcmp-offset.sh\n@@ -4,8 +4,19 @@ test_description='Test strcmp_offset functionality'\n \n . ./test-lib.sh\n \n-test_expect_success run_helper '\n-\ttest-strcmp-offset\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+$(printf \"abc\\360zzz\") $(printf \"abc\\377zzz\") -1 3\n+EOF\n \n test_done\n"},{"id":"316394","messageId":"20170408103614.w6xhbdbslonwcr65@sigill.intra.peff.net","threadId":"45634","inReplyTo":"20170407212047.64950-3-git@jeffhostetler.com","subject":"Re: [PATCH v7 2/3] p0004-read-tree: perf test to time read-tree","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-08T10:36:14Z","receivedAt":"2017-04-08T10:36:24Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Apr 07, 2017 at 09:20:46PM +0000, git@jeffhostetler.com wrote:\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..a70e969\n\nI think p0004 is taken by your lazy-init-name-hash script already\n(which, btw, I think is missing its executable bit).\n\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> +' </dev/null |\n> +\tsed \"s/^/100644 $EMPTY_BLOB\t/\" |\n> +\tgit update-index --index-info\n> +\treturn 0\n> +}\n\nI saw some discussion earlier on testing synthetic versus real\nrepositories. The original point of the perf test suite was to find\nperformance regressions between versions. So periodically you'd run:\n\n  cd t/perf\n  ./run v2.10.0 HEAD\n\nand make sure that nothing got inexplicably slower. And for that, using\nreal repositories is nice, because it's showing real user-impacting\nperformance changes, not synthetic benchmarks.\n\nIn an ideal world, people run it against their own real repositories and\ncan report back to the list when they see a problem. So running the\nwhole suite against your monstrous Windows repo would be a nice\nbenchmark to do periodically (I shudder to think how long it might take\nto run, though).\n\nOf course, perf scripts are also a nice way to show off your\nimprovements. And synthetic repos can often exaggerate the improvement\n(which is sometimes good to see changes, but also sometimes bad if\nreal-world repos don't show the improvement). And they also serve as a\nreproduction case for people who don't necessarily have access to the\nextreme repo that motivated the test in the first place.\n\nBut one side effect of writing the perf test the way you have it here is\nthat you _can't_ easily run it against a real repo. I think the perf\nsuite could provide better tools for this. You can already say \"run this\ntest against repo X\" with GIT_PERF_REPO. But there's no way to say\n\"create a synthetic repo with parameters X,Y,Z, and run against that\".\n\nIOW, I think rather than having the perf-scripts themselves create the\nsynthetic repo, we should have a _library_ of synthetic repos that the\ntest-runners can choose from. I'm imagining a world where your repo\nsetup goes into t/perf/repos/many-files.sh (which could even take your\ndepth, width, and files parameters to allow experimenting), and then you\ncould run \"GIT_PERF_REPO=many-files ./p0004-read-tree.sh\".\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\nFWIW, I really dislike the extra level of indirection here. You still\nhave to consistently say $br_base everywhere. Why not just call the\nbranch \"br_base\" in the first place?\n\nMy experience has been that debugging tests is much easier when as\nlittle state is carried in the environment as possible. Because it's\nquite often reasonable to do:\n\n  ./t1234-whatever.sh -v -i\n  cd trash*\n  git cmd-that-failed\n\nwhere you can pick the final line out from the failed test output. When\nthe command involves $br_base, I have to dig into the script to find out\nwhat's in that variable.\n\nI know that perf tests need less debugging than the regular regression\ntests, but I'd hate to see this pattern get applied liberally.\n\n-Peff\n"},{"id":"316487","messageId":"8430c0bf-9330-302b-d3d2-ef3611393d36@jeffhostetler.com","threadId":"45634","inReplyTo":"20170408103614.w6xhbdbslonwcr65@sigill.intra.peff.net","subject":"Re: [PATCH v7 2/3] p0004-read-tree: perf test to time read-tree","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-10T13:34:36Z","receivedAt":"2017-04-10T13:34:44Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/8/2017 6:36 AM, Jeff King wrote:\n> On Fri, Apr 07, 2017 at 09:20:46PM +0000, git@jeffhostetler.com wrote:\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..a70e969\n>\n> I think p0004 is taken by your lazy-init-name-hash script already\n> (which, btw, I think is missing its executable bit).\n>\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>> +' </dev/null |\n>> +\tsed \"s/^/100644 $EMPTY_BLOB\t/\" |\n>> +\tgit update-index --index-info\n>> +\treturn 0\n>> +}\n>\n> I saw some discussion earlier on testing synthetic versus real\n> repositories. The original point of the perf test suite was to find\n> performance regressions between versions. So periodically you'd run:\n>\n>   cd t/perf\n>   ./run v2.10.0 HEAD\n>\n> and make sure that nothing got inexplicably slower. And for that, using\n> real repositories is nice, because it's showing real user-impacting\n> performance changes, not synthetic benchmarks.\n>\n> In an ideal world, people run it against their own real repositories and\n> can report back to the list when they see a problem. So running the\n> whole suite against your monstrous Windows repo would be a nice\n> benchmark to do periodically (I shudder to think how long it might take\n> to run, though).\n>\n> Of course, perf scripts are also a nice way to show off your\n> improvements. And synthetic repos can often exaggerate the improvement\n> (which is sometimes good to see changes, but also sometimes bad if\n> real-world repos don't show the improvement). And they also serve as a\n> reproduction case for people who don't necessarily have access to the\n> extreme repo that motivated the test in the first place.\n>\n> But one side effect of writing the perf test the way you have it here is\n> that you _can't_ easily run it against a real repo. I think the perf\n> suite could provide better tools for this. You can already say \"run this\n> test against repo X\" with GIT_PERF_REPO. But there's no way to say\n> \"create a synthetic repo with parameters X,Y,Z, and run against that\".\n>\n> IOW, I think rather than having the perf-scripts themselves create the\n> synthetic repo, we should have a _library_ of synthetic repos that the\n> test-runners can choose from. I'm imagining a world where your repo\n> setup goes into t/perf/repos/many-files.sh (which could even take your\n> depth, width, and files parameters to allow experimenting), and then you\n> could run \"GIT_PERF_REPO=many-files ./p0004-read-tree.sh\".\n\nAgreed, both types of repos have value.  We've also been discussing\ninternally the need for more test repos with specific data shapes.\nWhether that is a collection of pre-built repos (like what libgit2\ndoes) or scripts to build and persist them I don't know.\n\nLet me take a stab at that separation.\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> FWIW, I really dislike the extra level of indirection here. You still\n> have to consistently say $br_base everywhere. Why not just call the\n> branch \"br_base\" in the first place?\n>\n> My experience has been that debugging tests is much easier when as\n> little state is carried in the environment as possible. Because it's\n> quite often reasonable to do:\n>\n>   ./t1234-whatever.sh -v -i\n>   cd trash*\n>   git cmd-that-failed\n>\n> where you can pick the final line out from the failed test output. When\n> the command involves $br_base, I have to dig into the script to find out\n> what's in that variable.\n>\n> I know that perf tests need less debugging than the regular regression\n> tests, but I'd hate to see this pattern get applied liberally.\n\nThat makes sense.\n\nThanks\nJeff\n\n"}]}