{"thread":{"id":"45749","subject":"[PATCH v12 2/5] p0006-read-tree-checkout: perf test to time read-tree","startedAt":"2017-04-19T17:06:39Z","lastAt":"2020-07-16T17:12:18Z","messageCount":11,"participants":["git@jeffhostetler.com","SZEDER Gábor","René Scharfe","Junio C Hamano","Jeff Hostetler"],"isPatch":true,"patchVersion":12,"patchTotal":5},"messages":[{"id":"317250","messageId":"20170419170618.16535-3-git@jeffhostetler.com","threadId":"45749","inReplyTo":"20170419170618.16535-1-git@jeffhostetler.com","subject":"[PATCH v12 2/5] p0006-read-tree-checkout: perf test to time read-tree","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-19T17:06:15Z","receivedAt":"2017-04-19T17:06:39Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nCreated t/perf/repos/many-files.sh to generate large, but\nartificial repositories.\n\nCreated t/perf/inflate-repo.sh to alter an EXISTING repo\nto have a set of large commits.  This can be used to create\na branch with 1M+ files in repositories like git.git or\nlinux.git, but with more realistic content.  It does this\nby making multiple copies of the entire worktree in a series\nof sub-directories.\n\nThe branch name and ballast structure created by both scripts\nmatch, so either script can be used to generate very large\ntest repositories for the following perf test.\n\nCreated t/perf/p0006-read-tree-checkout.sh to measure\nperformance on various read-tree, checkout, and update-index\noperations.  This test can run using either normal repos or\nones from the above scripts.\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n---\n t/perf/p0006-read-tree-checkout.sh |  67 ++++++++++++++++++++++\n t/perf/repos/.gitignore            |   1 +\n t/perf/repos/inflate-repo.sh       |  86 +++++++++++++++++++++++++++++\n t/perf/repos/many-files.sh         | 110 +++++++++++++++++++++++++++++++++++++\n 4 files changed, 264 insertions(+)\n create mode 100755 t/perf/p0006-read-tree-checkout.sh\n create mode 100644 t/perf/repos/.gitignore\n create mode 100755 t/perf/repos/inflate-repo.sh\n create mode 100755 t/perf/repos/many-files.sh\n\ndiff --git a/t/perf/p0006-read-tree-checkout.sh b/t/perf/p0006-read-tree-checkout.sh\nnew file mode 100755\nindex 0000000..78cc23f\n--- /dev/null\n+++ b/t/perf/p0006-read-tree-checkout.sh\n@@ -0,0 +1,67 @@\n+#!/bin/sh\n+#\n+# This test measures the performance of various read-tree\n+# and checkout operations.  It is primarily interested in\n+# the algorithmic costs of index operations and recursive\n+# tree traversal -- and NOT disk I/O on thousands of files.\n+\n+test_description=\"Tests performance of read-tree\"\n+\n+. ./perf-lib.sh\n+\n+test_perf_default_repo\n+\n+# If the test repo was generated by ./repos/many-files.sh\n+# then we know something about the data shape and branches,\n+# so we can isolate testing to the ballast-related commits\n+# and setup sparse-checkout so we don't have to populate\n+# the ballast files and directories.\n+#\n+# Otherwise, we make some general assumptions about the\n+# repo and consider the entire history of the current\n+# branch to be the ballast.\n+\n+test_expect_success \"setup repo\" '\n+\tif git rev-parse --verify refs/heads/p0006-ballast^{commit}\n+\tthen\n+\t\techo Assuming synthetic repo from many-files.sh\n+\t\tgit branch br_base            master\n+\t\tgit branch br_ballast         p0006-ballast^\n+\t\tgit branch br_ballast_alias   p0006-ballast^\n+\t\tgit branch br_ballast_plus_1  p0006-ballast\n+\t\tgit config --local core.sparsecheckout 1\n+\t\tcat >.git/info/sparse-checkout <<-EOF\n+\t\t/*\n+\t\t!ballast/*\n+\t\tEOF\n+\telse\n+\t\techo Assuming non-synthetic repo...\n+\t\tgit branch br_base            $(git rev-list HEAD | tail -n 1)\n+\t\tgit branch br_ballast         HEAD^ || error \"no ancestor commit from current head\"\n+\t\tgit branch br_ballast_alias   HEAD^\n+\t\tgit branch br_ballast_plus_1  HEAD\n+\tfi &&\n+\tgit checkout -q br_ballast &&\n+\tnr_files=$(git ls-files | wc -l)\n+'\n+\n+test_perf \"read-tree br_base br_ballast ($nr_files)\" '\n+\tgit read-tree -m br_base br_ballast -n\n+'\n+\n+test_perf \"switch between br_base br_ballast ($nr_files)\" '\n+\tgit checkout -q br_base &&\n+\tgit checkout -q br_ballast\n+'\n+\n+test_perf \"switch between br_ballast br_ballast_plus_1 ($nr_files)\" '\n+\tgit checkout -q br_ballast_plus_1 &&\n+\tgit checkout -q br_ballast\n+'\n+\n+test_perf \"switch between aliases ($nr_files)\" '\n+\tgit checkout -q br_ballast_alias &&\n+\tgit checkout -q br_ballast\n+'\n+\n+test_done\ndiff --git a/t/perf/repos/.gitignore b/t/perf/repos/.gitignore\nnew file mode 100644\nindex 0000000..72e3dc3\n--- /dev/null\n+++ b/t/perf/repos/.gitignore\n@@ -0,0 +1 @@\n+gen-*/\ndiff --git a/t/perf/repos/inflate-repo.sh b/t/perf/repos/inflate-repo.sh\nnew file mode 100755\nindex 0000000..64f5d7a\n--- /dev/null\n+++ b/t/perf/repos/inflate-repo.sh\n@@ -0,0 +1,86 @@\n+#!/bin/sh\n+# Inflate the size of an EXISTING repo.\n+#\n+# This script should be run inside the worktree of a TEST repo.\n+# It will use the contents of the current HEAD to generate a\n+# commit containing copies of the current worktree such that the\n+# total size of the commit has at least <target_size> files.\n+#\n+# Usage: [-t target_size] [-b branch_name]\n+\n+set -e\n+\n+target_size=10000\n+branch_name=p0006-ballast\n+ballast=ballast\n+\n+while test \"$#\" -ne 0\n+do\n+    case \"$1\" in\n+\t-b)\n+\t    shift;\n+\t    test \"$#\" -ne 0 || { echo 'error: -b requires an argument' >&2; exit 1; }\n+\t    branch_name=$1;\n+\t    shift ;;\n+\t-t)\n+\t    shift;\n+\t    test \"$#\" -ne 0 || { echo 'error: -t requires an argument' >&2; exit 1; }\n+\t    target_size=$1;\n+\t    shift ;;\n+\t*)\n+\t    echo \"error: unknown option '$1'\" >&2; exit 1 ;;\n+    esac\n+done\n+\n+git ls-tree -r HEAD >GEN_src_list\n+nr_src_files=$(cat GEN_src_list | wc -l)\n+\n+src_branch=$(git symbolic-ref --short HEAD)\n+\n+echo \"Branch $src_branch initially has $nr_src_files files.\"\n+\n+if test $target_size -le $nr_src_files\n+then\n+    echo \"Repository already exceeds target size $target_size.\"\n+    rm GEN_src_list\n+    exit 1\n+fi\n+\n+# Create well-known branch and add 1 file change to start\n+# if off before the ballast.\n+git checkout -b $branch_name HEAD\n+echo \"$target_size\" > inflate-repo.params\n+git add inflate-repo.params\n+git commit -q -m params\n+\n+# Create ballast for in our branch.\n+copy=1\n+nr_files=$nr_src_files\n+while test $nr_files -lt $target_size\n+do\n+    sed -e \"s|\t|\t$ballast/$copy/|\" <GEN_src_list |\n+\tgit update-index --index-info\n+\n+    nr_files=$(expr $nr_files + $nr_src_files)\n+    copy=$(expr $copy + 1)\n+done\n+rm GEN_src_list\n+git commit -q -m \"ballast\"\n+\n+# Modify 1 file and commit.\n+echo \"$target_size\" >> inflate-repo.params\n+git add inflate-repo.params\n+git commit -q -m \"ballast plus 1\"\n+\n+nr_files=$(git ls-files | wc -l)\n+\n+# Checkout master to put repo in canonical state (because\n+# the perf test may need to clone and enable sparse-checkout\n+# before attempting to checkout a commit with the ballast\n+# (because it may contain 100K directories and 1M files)).\n+git checkout $src_branch\n+\n+echo \"Repository inflated. Branch $branch_name has $nr_files files.\"\n+\n+exit 0\n+\ndiff --git a/t/perf/repos/many-files.sh b/t/perf/repos/many-files.sh\nnew file mode 100755\nindex 0000000..28720e4\n--- /dev/null\n+++ b/t/perf/repos/many-files.sh\n@@ -0,0 +1,110 @@\n+#!/bin/sh\n+# Generate test data repository using the given parameters.\n+# When omitted, we create \"gen-many-files-d-w-f.git\".\n+#\n+# Usage: [-r repo] [-d depth] [-w width] [-f files]\n+#\n+# -r repo: path to the new repo to be generated\n+# -d depth: the depth of sub-directories\n+# -w width: the number of sub-directories at each level\n+# -f files: the number of files created in each directory\n+#\n+# Note that all files will have the same SHA-1 and each\n+# directory at a level will have the same SHA-1, so we\n+# will potentially have a large index, but not a large\n+# ODB.\n+#\n+# Ballast will be created under \"ballast/\".\n+\n+EMPTY_BLOB=e69de29bb2d1d6434b8b29ae775ad8c2e48c5391\n+\n+set -e\n+\n+# (5, 10, 9) will create 999,999 ballast files.\n+# (4, 10, 9) will create  99,999 ballast files.\n+depth=5\n+width=10\n+files=9\n+\n+while test \"$#\" -ne 0\n+do\n+    case \"$1\" in\n+\t-r)\n+\t    shift;\n+\t    test \"$#\" -ne 0 || { echo 'error: -r requires an argument' >&2; exit 1; }\n+\t    repo=$1;\n+\t    shift ;;\n+\t-d)\n+\t    shift;\n+\t    test \"$#\" -ne 0 || { echo 'error: -d requires an argument' >&2; exit 1; }\n+\t    depth=$1;\n+\t    shift ;;\n+\t-w)\n+\t    shift;\n+\t    test \"$#\" -ne 0 || { echo 'error: -w requires an argument' >&2; exit 1; }\n+\t    width=$1;\n+\t    shift ;;\n+\t-f)\n+\t    shift;\n+\t    test \"$#\" -ne 0 || { echo 'error: -f requires an argument' >&2; exit 1; }\n+\t    files=$1;\n+\t    shift ;;\n+\t*)\n+\t    echo \"error: unknown option '$1'\" >&2; exit 1 ;;\n+\tesac\n+done\n+\n+# Inflate the index with thousands of empty files.\n+# usage: dir depth width files\n+fill_index() {\n+\tawk -v arg_dir=$1 -v arg_depth=$2 -v arg_width=$3 -v arg_files=$4 '\n+\t\tfunction make_paths(dir, depth, width, files, f, w) {\n+\t\t\tfor (f = 1; f <= files; f++) {\n+\t\t\t\tprint dir \"/file\" f\n+\t\t\t}\n+\t\t\tif (depth > 0) {\n+\t\t\t\tfor (w = 1; w <= width; w++) {\n+\t\t\t\t\tmake_paths(dir \"/dir\" w, depth - 1, width, files)\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\t\tEND { make_paths(arg_dir, arg_depth, arg_width, arg_files) }\n+\t\t' </dev/null |\n+\tsed \"s/^/100644 $EMPTY_BLOB\t/\" |\n+\tgit update-index --index-info\n+\treturn 0\n+}\n+\n+[ -z \"$repo\" ] && repo=gen-many-files-$depth.$width.$files.git\n+\n+mkdir $repo\n+cd $repo\n+git init .\n+\n+# Create an initial commit just to define master.\n+touch many-files.empty\n+echo \"$depth $width $files\" >many-files.params\n+git add many-files.*\n+git commit -q -m params\n+\n+# Create ballast for p0006 based upon the given params and\n+# inflate the index with thousands of empty files and commit.\n+git checkout -b p0006-ballast\n+fill_index \"ballast\" $depth $width $files\n+git commit -q -m \"ballast\"\n+\n+nr_files=$(git ls-files | wc -l)\n+\n+# Modify 1 file and commit.\n+echo \"$depth $width $files\" >>many-files.params\n+git add many-files.params\n+git commit -q -m \"ballast plus 1\"\n+\n+# Checkout master to put repo in canonical state (because\n+# the perf test may need to clone and enable sparse-checkout\n+# before attempting to checkout a commit with the ballast\n+# (because it may contain 100K directories and 1M files)).\n+git checkout master\n+\n+echo \"Repository \"$repo\" ($depth, $width, $files) created.  Ballast $nr_files.\"\n+exit 0\n-- \n2.9.3\n\n"},{"id":"317251","messageId":"20170419170618.16535-2-git@jeffhostetler.com","threadId":"45749","inReplyTo":"20170419170618.16535-1-git@jeffhostetler.com","subject":"[PATCH v12 1/5] read-cache: add strcmp_offset function","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-19T17:06:14Z","receivedAt":"2017-04-19T17:06:40Z","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 | 22 ++++++++++++++++++++++\n t/t0065-strcmp-offset.sh      | 21 +++++++++++++++++++++\n 6 files changed, 66 insertions(+)\n create mode 100644 t/helper/test-strcmp-offset.c\n create mode 100755 t/t0065-strcmp-offset.sh\n\ndiff --git a/Makefile b/Makefile\nindex 9ec6065..4c4c246 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -631,6 +631,7 @@ TEST_PROGRAMS_NEED_X += test-scrap-cache-tree\n TEST_PROGRAMS_NEED_X += test-sha1\n TEST_PROGRAMS_NEED_X += test-sha1-array\n TEST_PROGRAMS_NEED_X += test-sigchain\n+TEST_PROGRAMS_NEED_X += test-strcmp-offset\n TEST_PROGRAMS_NEED_X += test-string-list\n TEST_PROGRAMS_NEED_X += test-submodule-config\n TEST_PROGRAMS_NEED_X += test-subprocess\ndiff --git a/cache.h b/cache.h\nindex 80b6372..3c55047 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -574,6 +574,7 @@ extern int write_locked_index(struct index_state *, struct lock_file *lock, unsi\n extern int discard_index(struct index_state *);\n extern int unmerged_index(const struct index_state *);\n extern int verify_path(const char *path);\n+extern int strcmp_offset(const char *s1, const char *s2, size_t *first_change);\n extern int index_dir_exists(struct index_state *istate, const char *name, int namelen);\n extern void adjust_dirname_case(struct index_state *istate, char *name);\n extern struct cache_entry *index_file_exists(struct index_state *istate, const char *name, int namelen, int igncase);\ndiff --git a/read-cache.c b/read-cache.c\nindex 9054369..97f13a1 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -887,6 +887,26 @@ static int has_file_name(struct index_state *istate,\n \treturn retval;\n }\n \n+\n+/*\n+ * Like strcmp(), but also return the offset of the first change.\n+ * If strings are equal, return the length.\n+ */\n+int strcmp_offset(const char *s1, const char *s2, size_t *first_change)\n+{\n+\tsize_t k;\n+\n+\tif (!first_change)\n+\t\treturn strcmp(s1, s2);\n+\n+\tfor (k = 0; s1[k] == s2[k]; k++)\n+\t\tif (s1[k] == '\\0')\n+\t\t\tbreak;\n+\n+\t*first_change = k;\n+\treturn (unsigned char)s1[k] - (unsigned char)s2[k];\n+}\n+\n /*\n  * Do we have another file with a pathname that is a proper\n  * subset of the name we're trying to add?\ndiff --git a/t/helper/.gitignore b/t/helper/.gitignore\nindex d6e8b36..0a89531 100644\n--- a/t/helper/.gitignore\n+++ b/t/helper/.gitignore\n@@ -25,6 +25,7 @@\n /test-sha1\n /test-sha1-array\n /test-sigchain\n+/test-strcmp-offset\n /test-string-list\n /test-submodule-config\n /test-subprocess\ndiff --git a/t/helper/test-strcmp-offset.c b/t/helper/test-strcmp-offset.c\nnew file mode 100644\nindex 0000000..4a45a54\n--- /dev/null\n+++ b/t/helper/test-strcmp-offset.c\n@@ -0,0 +1,22 @@\n+#include \"cache.h\"\n+\n+int cmd_main(int argc, const char **argv)\n+{\n+\tint result;\n+\tsize_t offset;\n+\n+\tif (!argv[1] || !argv[2])\n+\t\tdie(\"usage: %s <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+\tresult = (result < 0 ? -1 :\n+\t\t\t  result > 0 ? 1 :\n+\t\t\t  0);\n+\tprintf(\"%d %\"PRIuMAX\"\\n\", result, (uintmax_t)offset);\n+\treturn 0;\n+}\ndiff --git a/t/t0065-strcmp-offset.sh b/t/t0065-strcmp-offset.sh\nnew file mode 100755\nindex 0000000..7d6d214\n--- /dev/null\n+++ b/t/t0065-strcmp-offset.sh\n@@ -0,0 +1,21 @@\n+#!/bin/sh\n+\n+test_description='Test strcmp_offset functionality'\n+\n+. ./test-lib.sh\n+\n+while read s1 s2 expect\n+do\n+\ttest_expect_success \"strcmp_offset($s1, $s2)\" '\n+\t\techo \"$expect\" >expect &&\n+\t\ttest-strcmp-offset \"$s1\" \"$s2\" >actual &&\n+\t\ttest_cmp expect actual\n+\t'\n+done <<-EOF\n+abc abc 0 3\n+abc def -1 0\n+abc abz -1 2\n+abc abcdef -1 3\n+EOF\n+\n+test_done\n-- \n2.9.3\n\n"},{"id":"317252","messageId":"20170419170618.16535-1-git@jeffhostetler.com","threadId":"45749","inReplyTo":null,"subject":"[PATCH v12 0/5] read-cache: speed up add_index_entry","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-19T17:06:13Z","receivedAt":"2017-04-19T17:06:41Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nVersion 12 adds a new t/perf/repo/inflate-repo.sh script to let you\ninflate a test repo, such as a copy of git.git or linux.git, to have\na branch containing a very large number of (non-synthetic) files.\n\nIt also fixes the \"##\" comments in the many-files.sh script\nas mentioned on the mailing list.\n\nI've also updated the commit message on part 2 to show the\nresults when run on an inflated copy of linux.git with 1M+ files.\n\nJeff Hostetler (5):\n  read-cache: add strcmp_offset function\n  p0006-read-tree-checkout: perf test to time read-tree\n  read-cache: speed up add_index_entry during checkout\n  read-cache: speed up has_dir_name (part 1)\n  read-cache: speed up has_dir_name (part 2)\n\n Makefile                           |   1 +\n cache.h                            |   1 +\n read-cache.c                       | 139 ++++++++++++++++++++++++++++++++++++-\n t/helper/.gitignore                |   1 +\n t/helper/test-strcmp-offset.c      |  22 ++++++\n t/perf/p0006-read-tree-checkout.sh |  67 ++++++++++++++++++\n t/perf/repos/.gitignore            |   1 +\n t/perf/repos/inflate-repo.sh       |  86 +++++++++++++++++++++++\n t/perf/repos/many-files.sh         | 110 +++++++++++++++++++++++++++++\n t/t0065-strcmp-offset.sh           |  21 ++++++\n 10 files changed, 447 insertions(+), 2 deletions(-)\n create mode 100644 t/helper/test-strcmp-offset.c\n create mode 100755 t/perf/p0006-read-tree-checkout.sh\n create mode 100644 t/perf/repos/.gitignore\n create mode 100755 t/perf/repos/inflate-repo.sh\n create mode 100755 t/perf/repos/many-files.sh\n create mode 100755 t/t0065-strcmp-offset.sh\n\n-- \n2.9.3\n\n"},{"id":"317253","messageId":"20170419170618.16535-4-git@jeffhostetler.com","threadId":"45749","inReplyTo":"20170419170618.16535-1-git@jeffhostetler.com","subject":"[PATCH v12 3/5] read-cache: speed up add_index_entry during checkout","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-19T17:06:16Z","receivedAt":"2017-04-19T17:06:44Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nTeach add_index_entry_with_check() to see if the path\nof the new item is greater than the last path in the\nindex array before attempting to search for it.\n\nDuring checkout, merge_working_tree() populates the new\nindex in sorted order, so this change will save a binary\nlookups per file.  This preserves the original behavior\nbut simply checks the last element before starting the\nsearch.\n\nThis helps performance on very large repositories.\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n---\n read-cache.c | 11 ++++++++++-\n 1 file changed, 10 insertions(+), 1 deletion(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex 97f13a1..6a27688 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1021,7 +1021,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":"317254","messageId":"20170419170618.16535-6-git@jeffhostetler.com","threadId":"45749","inReplyTo":"20170419170618.16535-1-git@jeffhostetler.com","subject":"[PATCH v12 5/5] read-cache: speed up has_dir_name (part 2)","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-19T17:06:18Z","receivedAt":"2017-04-19T17:06:53Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nTeach has_dir_name() to see if the path of the new item\nis greater than the last path in the index array before\nattempting to search for it.\n\nhas_dir_name() is looking for file/directory collisions\nin the index and has to consider each sub-directory\nprefix in turn.  This can cause multiple binary searches\nfor each path.\n\nDuring operations like checkout, merge_working_tree()\npopulates the new index in sorted order, so we expect\nto be able to append in many cases.\n\nThis commit is part 2 of 2.  This commit handles the\nadditional possible short-cuts as we look at each\nsub-directory prefix.\n\nThe net-net gains for add_index_entry_with_check() and\nboth had_dir_name() commits are best seen for very\nlarge repos.\n\nHere are results for an INFLATED version of linux.git\nwith 1M files.\n\n$ GIT_PERF_REPO=/mnt/test/linux_inflated.git/ ./run upstream/base HEAD ./p0006-read-tree-checkout.sh\nTest                                                            upstream/base      HEAD\n0006.2: read-tree br_base br_ballast (1043893)                  3.79(3.63+0.15)    2.68(2.52+0.15) -29.3%\n0006.3: switch between br_base br_ballast (1043893)             7.55(6.58+0.44)    6.03(4.60+0.43) -20.1%\n0006.4: switch between br_ballast br_ballast_plus_1 (1043893)   10.84(9.26+0.59)   8.44(7.06+0.65) -22.1%\n0006.5: switch between aliases (1043893)                        10.93(9.39+0.58)   10.24(7.04+0.63) -6.3%\n\nHere are results for a synthetic repo with 4.2M files.\n\n$ GIT_PERF_REPO=~/work/gfw/t/perf/repos/gen-many-files-10.4.3.git/ ./run HEAD~3 HEAD ./p0006-read-tree-checkout.sh\nTest                                                            HEAD~3               HEAD\n0006.2: read-tree br_base br_ballast (4194305)                  29.96(19.26+10.50)   23.76(13.42+10.12) -20.7%\n0006.3: switch between br_base br_ballast (4194305)             56.95(36.08+16.83)   45.54(25.94+15.68) -20.0%\n0006.4: switch between br_ballast br_ballast_plus_1 (4194305)   90.94(51.50+31.52)   78.22(39.39+30.70) -14.0%\n0006.5: switch between aliases (4194305)                        93.72(51.63+34.09)   77.94(39.00+30.88) -16.8%\n\nResults for medium repos (like linux.git) are mixed and have\nmore variance (probably do to disk IO unrelated to this test.\n\n$ GIT_PERF_REPO=/mnt/test/linux.git/ ./run HEAD~3 HEAD ./p0006-read-tree-checkout.sh\nTest                                                          HEAD~3             HEAD\n0006.2: read-tree br_base br_ballast (57994)                  0.25(0.21+0.03)    0.20(0.17+0.02) -20.0%\n0006.3: switch between br_base br_ballast (57994)             10.67(6.06+2.92)   10.51(5.94+2.91) -1.5%\n0006.4: switch between br_ballast br_ballast_plus_1 (57994)   0.59(0.47+0.16)    0.52(0.40+0.13) -11.9%\n0006.5: switch between aliases (57994)                        0.59(0.44+0.17)    0.51(0.38+0.14) -13.6%\n\n$ GIT_PERF_REPO=/mnt/test/linux.git/ ./run HEAD~3 HEAD ./p0006-read-tree-checkout.sh\nTest                                                          HEAD~3             HEAD\n0006.2: read-tree br_base br_ballast (57994)                  0.24(0.21+0.02)    0.21(0.18+0.02) -12.5%\n0006.3: switch between br_base br_ballast (57994)             10.42(5.98+2.91)   10.66(5.86+3.09) +2.3%\n0006.4: switch between br_ballast br_ballast_plus_1 (57994)   0.59(0.49+0.13)    0.53(0.37+0.16) -10.2%\n0006.5: switch between aliases (57994)                        0.59(0.43+0.17)    0.50(0.37+0.14) -15.3%\n\nResults for smaller repos (like git.git) are not significant.\n$ ./run HEAD~3 HEAD ./p0006-read-tree-checkout.sh\nTest                                                         HEAD~3            HEAD\n0006.2: read-tree br_base br_ballast (3043)                  0.01(0.00+0.00)   0.01(0.00+0.00) +0.0%\n0006.3: switch between br_base br_ballast (3043)             0.31(0.17+0.11)   0.29(0.19+0.08) -6.5%\n0006.4: switch between br_ballast br_ballast_plus_1 (3043)   0.03(0.02+0.00)   0.03(0.02+0.00) +0.0%\n0006.5: switch between aliases (3043)                        0.03(0.02+0.00)   0.03(0.02+0.00) +0.0%\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n---\n read-cache.c | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 file changed, 62 insertions(+), 1 deletion(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex 9af0bd4..c252b6c 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -965,7 +965,7 @@ static int has_dir_name(struct index_state *istate,\n \t}\n \n \tfor (;;) {\n-\t\tint len;\n+\t\tsize_t len;\n \n \t\tfor (;;) {\n \t\t\tif (*--slash == '/')\n@@ -975,6 +975,67 @@ 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 * (len + 1) is a directory boundary (including\n+\t\t\t * the trailing slash).  And since the loop is\n+\t\t\t * decrementing \"slash\", the first iteration is\n+\t\t\t * the longest directory prefix; subsequent\n+\t\t\t * iterations consider parent directories.\n+\t\t\t */\n+\n+\t\t\tif (len + 1 <= len_eq_last) {\n+\t\t\t\t/*\n+\t\t\t\t * The directory prefix (including the trailing\n+\t\t\t\t * slash) also appears as a prefix in the last\n+\t\t\t\t * entry, so the remainder cannot collide (because\n+\t\t\t\t * strcmp said the whole path was greater).\n+\t\t\t\t *\n+\t\t\t\t * EQ: last: xxx/A\n+\t\t\t\t *     this: xxx/B\n+\t\t\t\t *\n+\t\t\t\t * LT: last: xxx/file_A\n+\t\t\t\t *     this: xxx/file_B\n+\t\t\t\t */\n+\t\t\t\treturn retval;\n+\t\t\t}\n+\n+\t\t\tif (len > len_eq_last) {\n+\t\t\t\t/*\n+\t\t\t\t * This part of the directory prefix (excluding\n+\t\t\t\t * the trailing slash) is longer than the known\n+\t\t\t\t * equal portions, so this sub-directory cannot\n+\t\t\t\t * collide with a file.\n+\t\t\t\t *\n+\t\t\t\t * GT: last: xxxA\n+\t\t\t\t *     this: xxxB/file\n+\t\t\t\t */\n+\t\t\t\treturn retval;\n+\t\t\t}\n+\n+\t\t\tif (istate->cache_nr > 0 &&\n+\t\t\t\tce_namelen(istate->cache[istate->cache_nr - 1]) > len) {\n+\t\t\t\t/*\n+\t\t\t\t * The directory prefix lines up with part of\n+\t\t\t\t * a longer file or directory name, but sorts\n+\t\t\t\t * after it, so this sub-directory cannot\n+\t\t\t\t * collide with a file.\n+\t\t\t\t *\n+\t\t\t\t * last: xxx/yy-file (because '-' sorts before '/')\n+\t\t\t\t * this: xxx/yy/abc\n+\t\t\t\t */\n+\t\t\t\treturn retval;\n+\t\t\t}\n+\n+\t\t\t/*\n+\t\t\t * This is a possible collision. Fall through and\n+\t\t\t * let the regular search code handle it.\n+\t\t\t *\n+\t\t\t * last: xxx\n+\t\t\t * this: xxx/file\n+\t\t\t */\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-- \n2.9.3\n\n"},{"id":"317255","messageId":"20170419170618.16535-5-git@jeffhostetler.com","threadId":"45749","inReplyTo":"20170419170618.16535-1-git@jeffhostetler.com","subject":"[PATCH v12 4/5] read-cache: speed up has_dir_name (part 1)","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-19T17:06:17Z","receivedAt":"2017-04-19T17:06:54Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nTeach has_dir_name() to see if the path of the new item\nis greater than the last path in the index array before\nattempting to search for it.\n\nhas_dir_name() is looking for file/directory collisions\nin the index and has to consider each sub-directory\nprefix in turn.  This can cause multiple binary searches\nfor each path.\n\nDuring operations like checkout, merge_working_tree()\npopulates the new index in sorted order, so we expect\nto be able to append in many cases.\n\nThis commit is part 1 of 2.  This commit handles the top\nof has_dir_name() and the trivial optimization.\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n---\n read-cache.c | 45 +++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 45 insertions(+)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex 6a27688..9af0bd4 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -910,6 +910,9 @@ int strcmp_offset(const char *s1, const char *s2, size_t *first_change)\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+ *\n+ * That is, is there another file in the index with a path\n+ * that matches a sub-directory in the given entry?\n  */\n static int has_dir_name(struct index_state *istate,\n \t\t\tconst struct cache_entry *ce, int pos, int ok_to_replace)\n@@ -918,6 +921,48 @@ 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+\t/*\n+\t * We are frequently called during an iteration on a sorted\n+\t * list of pathnames and while building a new index.  Therefore,\n+\t * there is a high probability that this entry will eventually\n+\t * be appended to the index, rather than inserted in the middle.\n+\t * If we can confirm that, we can avoid binary searches on the\n+\t * components of the pathname.\n+\t *\n+\t * Compare the entry's full path with the last path in the index.\n+\t */\n+\tif (istate->cache_nr > 0) {\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) {\n+\t\t\tif (len_eq_last == 0) {\n+\t\t\t\t/*\n+\t\t\t\t * The entry sorts AFTER the last one in the\n+\t\t\t\t * index and their paths have no common prefix,\n+\t\t\t\t * so there cannot be a F/D conflict.\n+\t\t\t\t */\n+\t\t\t\treturn retval;\n+\t\t\t} else {\n+\t\t\t\t/*\n+\t\t\t\t * The entry sorts AFTER the last one in the\n+\t\t\t\t * index, but has a common prefix.  Fall through\n+\t\t\t\t * to the loop below to disect the entry's path\n+\t\t\t\t * and see where the difference is.\n+\t\t\t\t */\n+\t\t\t}\n+\t\t} else if (cmp_last == 0) {\n+\t\t\t/*\n+\t\t\t * The entry exactly matches the last one in the\n+\t\t\t * index, but because of multiple stage and CE_REMOVE\n+\t\t\t * items, we fall through and let the regular search\n+\t\t\t * code handle it.\n+\t\t\t */\n+\t\t}\n+\t}\n \n \tfor (;;) {\n \t\tint len;\n-- \n2.9.3\n\n"},{"id":"401024","messageId":"20200704172708.GC11341@szeder.dev","threadId":"45749","inReplyTo":"20170419170618.16535-6-git@jeffhostetler.com","subject":"Re: [PATCH v12 5/5] read-cache: speed up has_dir_name (part 2)","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2020-07-04T17:27:08Z","receivedAt":"2020-07-04T17:27:15Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Wed, Apr 19, 2017 at 05:06:18PM +0000, git@jeffhostetler.com wrote:\n> From: Jeff Hostetler <jeffhost@microsoft.com>\n> \n> Teach has_dir_name() to see if the path of the new item\n> is greater than the last path in the index array before\n> attempting to search for it.\n> \n> has_dir_name() is looking for file/directory collisions\n> in the index and has to consider each sub-directory\n> prefix in turn.  This can cause multiple binary searches\n> for each path.\n> \n> During operations like checkout, merge_working_tree()\n> populates the new index in sorted order, so we expect\n> to be able to append in many cases.\n> \n> This commit is part 2 of 2.  This commit handles the\n> additional possible short-cuts as we look at each\n> sub-directory prefix.\n> \n> The net-net gains for add_index_entry_with_check() and\n> both had_dir_name() commits are best seen for very\n> large repos.\n> \n> Here are results for an INFLATED version of linux.git\n> with 1M files.\n> \n> $ GIT_PERF_REPO=/mnt/test/linux_inflated.git/ ./run upstream/base HEAD ./p0006-read-tree-checkout.sh\n> Test                                                            upstream/base      HEAD\n> 0006.2: read-tree br_base br_ballast (1043893)                  3.79(3.63+0.15)    2.68(2.52+0.15) -29.3%\n> 0006.3: switch between br_base br_ballast (1043893)             7.55(6.58+0.44)    6.03(4.60+0.43) -20.1%\n> 0006.4: switch between br_ballast br_ballast_plus_1 (1043893)   10.84(9.26+0.59)   8.44(7.06+0.65) -22.1%\n> 0006.5: switch between aliases (1043893)                        10.93(9.39+0.58)   10.24(7.04+0.63) -6.3%\n> \n> Here are results for a synthetic repo with 4.2M files.\n> \n> $ GIT_PERF_REPO=~/work/gfw/t/perf/repos/gen-many-files-10.4.3.git/ ./run HEAD~3 HEAD ./p0006-read-tree-checkout.sh\n> Test                                                            HEAD~3               HEAD\n> 0006.2: read-tree br_base br_ballast (4194305)                  29.96(19.26+10.50)   23.76(13.42+10.12) -20.7%\n> 0006.3: switch between br_base br_ballast (4194305)             56.95(36.08+16.83)   45.54(25.94+15.68) -20.0%\n> 0006.4: switch between br_ballast br_ballast_plus_1 (4194305)   90.94(51.50+31.52)   78.22(39.39+30.70) -14.0%\n> 0006.5: switch between aliases (4194305)                        93.72(51.63+34.09)   77.94(39.00+30.88) -16.8%\n> \n> Results for medium repos (like linux.git) are mixed and have\n> more variance (probably do to disk IO unrelated to this test.\n> \n> $ GIT_PERF_REPO=/mnt/test/linux.git/ ./run HEAD~3 HEAD ./p0006-read-tree-checkout.sh\n> Test                                                          HEAD~3             HEAD\n> 0006.2: read-tree br_base br_ballast (57994)                  0.25(0.21+0.03)    0.20(0.17+0.02) -20.0%\n> 0006.3: switch between br_base br_ballast (57994)             10.67(6.06+2.92)   10.51(5.94+2.91) -1.5%\n> 0006.4: switch between br_ballast br_ballast_plus_1 (57994)   0.59(0.47+0.16)    0.52(0.40+0.13) -11.9%\n> 0006.5: switch between aliases (57994)                        0.59(0.44+0.17)    0.51(0.38+0.14) -13.6%\n> \n> $ GIT_PERF_REPO=/mnt/test/linux.git/ ./run HEAD~3 HEAD ./p0006-read-tree-checkout.sh\n> Test                                                          HEAD~3             HEAD\n> 0006.2: read-tree br_base br_ballast (57994)                  0.24(0.21+0.02)    0.21(0.18+0.02) -12.5%\n> 0006.3: switch between br_base br_ballast (57994)             10.42(5.98+2.91)   10.66(5.86+3.09) +2.3%\n> 0006.4: switch between br_ballast br_ballast_plus_1 (57994)   0.59(0.49+0.13)    0.53(0.37+0.16) -10.2%\n> 0006.5: switch between aliases (57994)                        0.59(0.43+0.17)    0.50(0.37+0.14) -15.3%\n> \n> Results for smaller repos (like git.git) are not significant.\n> $ ./run HEAD~3 HEAD ./p0006-read-tree-checkout.sh\n> Test                                                         HEAD~3            HEAD\n> 0006.2: read-tree br_base br_ballast (3043)                  0.01(0.00+0.00)   0.01(0.00+0.00) +0.0%\n> 0006.3: switch between br_base br_ballast (3043)             0.31(0.17+0.11)   0.29(0.19+0.08) -6.5%\n> 0006.4: switch between br_ballast br_ballast_plus_1 (3043)   0.03(0.02+0.00)   0.03(0.02+0.00) +0.0%\n> 0006.5: switch between aliases (3043)                        0.03(0.02+0.00)   0.03(0.02+0.00) +0.0%\n> \n> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n> ---\n>  read-cache.c | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-\n>  1 file changed, 62 insertions(+), 1 deletion(-)\n> \n> diff --git a/read-cache.c b/read-cache.c\n> index 9af0bd4..c252b6c 100644\n> --- a/read-cache.c\n> +++ b/read-cache.c\n> @@ -965,7 +965,7 @@ static int has_dir_name(struct index_state *istate,\n>  \t}\n>  \n>  \tfor (;;) {\n> -\t\tint len;\n> +\t\tsize_t len;\n>  \n>  \t\tfor (;;) {\n>  \t\t\tif (*--slash == '/')\n> @@ -975,6 +975,67 @@ 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 * (len + 1) is a directory boundary (including\n> +\t\t\t * the trailing slash).  And since the loop is\n> +\t\t\t * decrementing \"slash\", the first iteration is\n> +\t\t\t * the longest directory prefix; subsequent\n> +\t\t\t * iterations consider parent directories.\n> +\t\t\t */\n> +\n> +\t\t\tif (len + 1 <= len_eq_last) {\n> +\t\t\t\t/*\n> +\t\t\t\t * The directory prefix (including the trailing\n> +\t\t\t\t * slash) also appears as a prefix in the last\n> +\t\t\t\t * entry, so the remainder cannot collide (because\n> +\t\t\t\t * strcmp said the whole path was greater).\n> +\t\t\t\t *\n> +\t\t\t\t * EQ: last: xxx/A\n> +\t\t\t\t *     this: xxx/B\n> +\t\t\t\t *\n> +\t\t\t\t * LT: last: xxx/file_A\n> +\t\t\t\t *     this: xxx/file_B\n> +\t\t\t\t */\n> +\t\t\t\treturn retval;\n> +\t\t\t}\n> +\n> +\t\t\tif (len > len_eq_last) {\n> +\t\t\t\t/*\n> +\t\t\t\t * This part of the directory prefix (excluding\n> +\t\t\t\t * the trailing slash) is longer than the known\n> +\t\t\t\t * equal portions, so this sub-directory cannot\n> +\t\t\t\t * collide with a file.\n> +\t\t\t\t *\n> +\t\t\t\t * GT: last: xxxA\n> +\t\t\t\t *     this: xxxB/file\n> +\t\t\t\t */\n> +\t\t\t\treturn retval;\n> +\t\t\t}\n> +\n> +\t\t\tif (istate->cache_nr > 0 &&\n> +\t\t\t\tce_namelen(istate->cache[istate->cache_nr - 1]) > len) {\n> +\t\t\t\t/*\n> +\t\t\t\t * The directory prefix lines up with part of\n> +\t\t\t\t * a longer file or directory name, but sorts\n> +\t\t\t\t * after it, so this sub-directory cannot\n> +\t\t\t\t * collide with a file.\n> +\t\t\t\t *\n> +\t\t\t\t * last: xxx/yy-file (because '-' sorts before '/')\n> +\t\t\t\t * this: xxx/yy/abc\n\nThis is problematic, because the index can already contain 'xxx/yy' as\na file, when adding 'xxx/yy/abc', but since 'xxx/yy' as a file sorts\nbefore 'xxx/yy-file', the short-circuiting here doesn't see it and\nthus leaves the d-f collision undetected.  Consequently, even Git\nporcelain commands can create tree objects with duplicate entries, as\ndemonstrated in the tests below.\n\nBefore this patch the collision is noticed, the colliding file entry\nis removed, and these tests succeed.  Removing this condition make\nthem succeed as well, and FWIW the test suite still passes, but I\nhaven't thought it through and haven't checked the impact on\nperformance.\n\n  ---  >8  ---\n\ndiff --git a/t/t9999-test.sh b/t/t9999-test.sh\nnew file mode 100755\nindex 0000000000..4c802d5940\n--- /dev/null\n+++ b/t/t9999-test.sh\n@@ -0,0 +1,47 @@\n+#!/bin/sh\n+\n+test_description='test'\n+\n+. ./test-lib.sh\n+\n+test_expect_success 'file to dir breakage' '\n+\t>file-to-dir &&\n+\t# This sorts between \"file-to-dir\" as a file and \"file-to-dir\"\n+\t# as a directory (with the trailing / appended implicitly.\n+\t>file-to-dir.uh-oh &&\n+\tgit add file-to-dir file-to-dir.uh-oh &&\n+\tgit commit -m \"add a file\" &&\n+\n+\t# Not \"git rm\", to preserve \"file-to-dir\" in the index.\n+\trm file-to-dir &&\n+\tmkdir file-to-dir &&\n+\t>file-to-dir/file &&\n+\n+\t# It is important to add the file in the directory; adding only\n+\t# the directory doesnt trigger the bug.\n+\tgit add file-to-dir/file &&\n+\n+\tgit diff --cached --no-renames --name-status >actual &&\n+\n+\tcat >expect <<-\\EOF &&\n+\tD\tfile-to-dir\n+\tA\tfile-to-dir/file\n+\tEOF\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'is it committed as-is?' '\n+\tgit commit -m \"replace file with a dir\" &&\n+\tgit ls-tree HEAD >actual &&\n+\n+\t# Hardcoded SHA-1 oid :(, because with this bug present\n+\t# \"git rev-parse HEAD:file-to-dir\" doesnt show the oid of\n+\t# the tree, but the oid of the blob that shouldnt be there.\n+\tcat >expect <<-EOF &&\n+\t100644 blob $EMPTY_BLOB\tfile-to-dir.uh-oh\n+\t040000 tree df2b8fc99e1c1d4dbc0a854d9f72157f1d6ea078\tfile-to-dir\n+\tEOF\n+\ttest_cmp expect actual\n+'\n+\n+test_done\n\n  ---  8<  ---\n\nThe first test fails with:\n\n  + test_cmp expect actual\n  --- expect      2020-07-04 16:52:07.173296314 +0000\n  +++ actual      2020-07-04 16:52:07.173296314 +0000\n  @@ -1,2 +1 @@\n  -D      file-to-dir\n   A      file-to-dir/file\n  error: last command exited with $?=1\n  not ok 1 - file to dir breakage\n  \nAnd the second:\n\n  + test_cmp expect actual\n  --- expect      2020-07-04 16:52:07.185296659 +0000\n  +++ actual      2020-07-04 16:52:07.181296544 +0000\n  @@ -1,2 +1,3 @@\n  +100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391   file-to-dir\n   100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391   file-to-dir.uh-oh\n   040000 tree df2b8fc99e1c1d4dbc0a854d9f72157f1d6ea078   file-to-dir\n  error: last command exited with $?=1\n  not ok 2 - is it committed as-is?\n\n\n> +\t\t\t\t */\n> +\t\t\t\treturn retval;\n> +\t\t\t}\n> +\n> +\t\t\t/*\n> +\t\t\t * This is a possible collision. Fall through and\n> +\t\t\t * let the regular search code handle it.\n> +\t\t\t *\n> +\t\t\t * last: xxx\n> +\t\t\t * this: xxx/file\n> +\t\t\t */\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> -- \n> 2.9.3\n> \n"},{"id":"401028","messageId":"fd593c77-ac40-9c4a-7556-2f10d60e2cee@web.de","threadId":"45749","inReplyTo":"20200704172708.GC11341@szeder.dev","subject":"Re: [PATCH v12 5/5] read-cache: speed up has_dir_name (part 2)","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2020-07-05T05:27:57Z","receivedAt":"2020-07-05T05:28:26Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 04.07.20 um 19:27 schrieb SZEDER Gábor:\n> diff --git a/t/t9999-test.sh b/t/t9999-test.sh\n> new file mode 100755\n> index 0000000000..4c802d5940\n> --- /dev/null\n> +++ b/t/t9999-test.sh\n> @@ -0,0 +1,47 @@\n> +#!/bin/sh\n> +\n> +test_description='test'\n> +\n> +. ./test-lib.sh\n> +\n> +test_expect_success 'file to dir breakage' '\n> +\t>file-to-dir &&\n> +\t# This sorts between \"file-to-dir\" as a file and \"file-to-dir\"\n> +\t# as a directory (with the trailing / appended implicitly.\n> +\t>file-to-dir.uh-oh &&\n> +\tgit add file-to-dir file-to-dir.uh-oh &&\n> +\tgit commit -m \"add a file\" &&\n> +\n> +\t# Not \"git rm\", to preserve \"file-to-dir\" in the index.\n> +\trm file-to-dir &&\n> +\tmkdir file-to-dir &&\n> +\t>file-to-dir/file &&\n> +\n> +\t# It is important to add the file in the directory; adding only\n> +\t# the directory doesnt trigger the bug.\n> +\tgit add file-to-dir/file &&\n> +\n> +\tgit diff --cached --no-renames --name-status >actual &&\n> +\n> +\tcat >expect <<-\\EOF &&\n> +\tD\tfile-to-dir\n> +\tA\tfile-to-dir/file\n> +\tEOF\n> +\ttest_cmp expect actual\n> +'\n> +\n> +test_expect_success 'is it committed as-is?' '\n> +\tgit commit -m \"replace file with a dir\" &&\n> +\tgit ls-tree HEAD >actual &&\n> +\n> +\t# Hardcoded SHA-1 oid :(, because with this bug present\n> +\t# \"git rev-parse HEAD:file-to-dir\" doesnt show the oid of\n> +\t# the tree, but the oid of the blob that shouldnt be there.\n> +\tcat >expect <<-EOF &&\n> +\t100644 blob $EMPTY_BLOB\tfile-to-dir.uh-oh\n> +\t040000 tree df2b8fc99e1c1d4dbc0a854d9f72157f1d6ea078\tfile-to-dir\n\nYou can get the hash of the tree with:\n\n  echo \"100644 blob $EMPTY_BLOB\tfile\" | git mktree\n\n(TAB before \"file\", the rest of the whitespace are regular spaces)\n\n> +\tEOF\n> +\ttest_cmp expect actual\n> +'\n> +\n> +test_done\n>\n"},{"id":"401038","messageId":"xmqqr1tp9mf8.fsf@gitster.c.googlers.com","threadId":"45749","inReplyTo":"20200704172708.GC11341@szeder.dev","subject":"Re: [PATCH v12 5/5] read-cache: speed up has_dir_name (part 2)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-07-06T06:39:55Z","receivedAt":"2020-07-06T06:39:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"SZEDER Gábor <szeder.dev@gmail.com> writes:\n\n>> +\t\t\t\t * last: xxx/yy-file (because '-' sorts before '/')\n>> +\t\t\t\t * this: xxx/yy/abc\n>\n> This is problematic, because the index can already contain 'xxx/yy' as\n> a file, when adding 'xxx/yy/abc', but since 'xxx/yy' as a file sorts\n> before 'xxx/yy-file', the short-circuiting here doesn't see it and\n> thus leaves the d-f collision undetected.  Consequently, even Git\n> porcelain commands can create tree objects with duplicate entries, as\n> demonstrated in the tests below.\n\nYeah, the \"optimization\" is quite bogus.  Thanks for catching it.\n"},{"id":"401185","messageId":"be8dec3e-087e-b973-280d-3d0d2e481de6@jeffhostetler.com","threadId":"45749","inReplyTo":"xmqqr1tp9mf8.fsf@gitster.c.googlers.com","subject":"Re: [PATCH v12 5/5] read-cache: speed up has_dir_name (part 2)","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2020-07-08T13:49:05Z","receivedAt":"2020-07-08T13:58:22Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 7/6/20 2:39 AM, Junio C Hamano wrote:\n> SZEDER Gábor <szeder.dev@gmail.com> writes:\n> \n>>> +\t\t\t\t * last: xxx/yy-file (because '-' sorts before '/')\n>>> +\t\t\t\t * this: xxx/yy/abc\n>>\n>> This is problematic, because the index can already contain 'xxx/yy' as\n>> a file, when adding 'xxx/yy/abc', but since 'xxx/yy' as a file sorts\n>> before 'xxx/yy-file', the short-circuiting here doesn't see it and\n>> thus leaves the d-f collision undetected.  Consequently, even Git\n>> porcelain commands can create tree objects with duplicate entries, as\n>> demonstrated in the tests below.\n> \n> Yeah, the \"optimization\" is quite bogus.  Thanks for catching it.\n> \n\nyes, thanks!\nJeff\n"},{"id":"401644","messageId":"6d769a78-72aa-5b5d-9cc7-41b8c0ddf9d8@web.de","threadId":"45749","inReplyTo":"be8dec3e-087e-b973-280d-3d0d2e481de6@jeffhostetler.com","subject":"Re: [PATCH v12 5/5] read-cache: speed up has_dir_name (part 2)","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2020-07-16T17:11:48Z","receivedAt":"2020-07-16T17:12:18Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 08.07.20 um 15:49 schrieb Jeff Hostetler:\n>\n>\n> On 7/6/20 2:39 AM, Junio C Hamano wrote:\n>> SZEDER Gábor <szeder.dev@gmail.com> writes:\n>>\n>>>> +                 * last: xxx/yy-file (because '-' sorts before '/')\n>>>> +                 * this: xxx/yy/abc\n>>>\n>>> This is problematic, because the index can already contain 'xxx/yy' as\n>>> a file, when adding 'xxx/yy/abc', but since 'xxx/yy' as a file sorts\n>>> before 'xxx/yy-file', the short-circuiting here doesn't see it and\n>>> thus leaves the d-f collision undetected.  Consequently, even Git\n>>> porcelain commands can create tree objects with duplicate entries, as\n>>> demonstrated in the tests below.\n>>\n>> Yeah, the \"optimization\" is quite bogus.  Thanks for catching it.\n>>\n>\n> yes, thanks!\n\nOK, so now we just need to fix it.  Like this perhaps?\n\n-- >8 --\nFrom f4b2c70a34bb612e2ccc23a31e2ba8e01dedc373 Mon Sep 17 00:00:00 2001\nSubject: [PATCH] read-cache: remove bogus shortcut\n\nhas_dir_name() has some optimizations for the case where entries are\nadded to an index in the correct order.  They kick in if the new entry\nsorts after the last one.  One of them exits early if the last entry has\na longer name than the directory of the new entry.  Here's its comment:\n\n/*\n * The directory prefix lines up with part of\n * a longer file or directory name, but sorts\n * after it, so this sub-directory cannot\n * collide with a file.\n *\n * last: xxx/yy-file (because '-' sorts before '/')\n * this: xxx/yy/abc\n */\n\nHowever, a file named xxx/yy would be sorted before xxx/yy-file because\n'-' sorts after NUL, so the length check against the last entry is not\nsufficient to rule out a collision.  Remove it.\n\nReported-by: SZEDER Gábor <szeder.dev@gmail.com>\nSuggested-by: SZEDER Gábor <szeder.dev@gmail.com>\nSigned-off-by: René Scharfe <l.s.r@web.de>\n---\n read-cache.c | 14 --------------\n 1 file changed, 14 deletions(-)\n\ndiff --git a/read-cache.c b/read-cache.c\nindex aa427c5c17..8ed1c29b54 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -1171,20 +1171,6 @@ static int has_dir_name(struct index_state *istate,\n \t\t\t\treturn retval;\n \t\t\t}\n\n-\t\t\tif (istate->cache_nr > 0 &&\n-\t\t\t\tce_namelen(istate->cache[istate->cache_nr - 1]) > len) {\n-\t\t\t\t/*\n-\t\t\t\t * The directory prefix lines up with part of\n-\t\t\t\t * a longer file or directory name, but sorts\n-\t\t\t\t * after it, so this sub-directory cannot\n-\t\t\t\t * collide with a file.\n-\t\t\t\t *\n-\t\t\t\t * last: xxx/yy-file (because '-' sorts before '/')\n-\t\t\t\t * this: xxx/yy/abc\n-\t\t\t\t */\n-\t\t\t\treturn retval;\n-\t\t\t}\n-\n \t\t\t/*\n \t\t\t * This is a possible collision. Fall through and\n \t\t\t * let the regular search code handle it.\n--\n2.27.0\n"}]}