{"thread":{"id":"60317","subject":"[PATCH 0/4] Performance improvement & cleanup in loose ref iteration","startedAt":"2023-10-06T18:09:36Z","lastAt":"2023-10-10T07:21:34Z","messageCount":21,"participants":["Victoria Dye via GitGitGadget","Junio C Hamano","Patrick Steinhardt","Victoria Dye"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"482751","messageId":"pull.1594.git.1696615769.gitgitgadget@gmail.com","threadId":"60317","inReplyTo":null,"subject":"[PATCH 0/4] Performance improvement & cleanup in loose ref iteration","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2023-10-06T18:09:25Z","receivedAt":"2023-10-06T18:09:36Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"While investigating ref iteration performance in builtins like\n'for-each-ref' and 'show-ref', I found two small improvement opportunities.\n\nThe first patch tweaks the logic around prefix matching in\n'cache_ref_iterator_advance' so that we correctly skip refs that do not\nactually match a given prefix. The unnecessary iteration doesn't seem to be\ncausing any bugs in the ref iteration commands that I've tested, but it\ndoesn't hurt to be more precise (and it helps with some other patches I'm\nworking on ;) ).\n\nThe next three patches update how 'loose_fill_ref_dir' determines the type\nof ref cache entry to create (directory or regular). On platforms that\ninclude d_type information in 'struct dirent' (as far as I can tell, all\nexcept NonStop & certain versions of Cygwin), this allows us to skip calling\n'stat'. In ad-hoc testing, this improved performance of 'git for-each-ref'\nby about 20%.\n\nThanks!\n\n * Victoria\n\nVictoria Dye (4):\n  ref-cache.c: fix prefix matching in ref iteration\n  dir.[ch]: expose 'get_dtype'\n  dir.[ch]: add 'follow_symlink' arg to 'get_dtype'\n  files-backend.c: avoid stat in 'loose_fill_ref_dir'\n\n diagnose.c           | 42 +++---------------------------------------\n dir.c                | 33 +++++++++++++++++++++++++++++++++\n dir.h                | 16 ++++++++++++++++\n refs/files-backend.c | 14 +++++---------\n refs/ref-cache.c     |  3 ++-\n 5 files changed, 59 insertions(+), 49 deletions(-)\n\n\nbase-commit: 3a06386e314565108ad56a9bdb8f7b80ac52fb69\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1594%2Fvdye%2Fvdye%2Fref-iteration-cleanup-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1594/vdye/vdye/ref-iteration-cleanup-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/1594\n-- \ngitgitgadget\n"},{"id":"482752","messageId":"59276a5b3fd1fd3b25db73e096cf0e834af2d4f9.1696615769.git.gitgitgadget@gmail.com","threadId":"60317","inReplyTo":"pull.1594.git.1696615769.gitgitgadget@gmail.com","subject":"[PATCH 1/4] ref-cache.c: fix prefix matching in ref iteration","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2023-10-06T18:09:26Z","receivedAt":"2023-10-06T18:09:37Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"From: Victoria Dye <vdye@github.com>\n\nUpdate 'cache_ref_iterator_advance' to skip over refs that are not matched\nby the given prefix.\n\nCurrently, a ref entry is considered \"matched\" if the entry name is fully\ncontained within the prefix:\n\n* prefix: \"refs/heads/v1\"\n* entry: \"refs/heads/v1.0\"\n\nOR if the prefix is fully contained in the entry name:\n\n* prefix: \"refs/heads/v1.0\"\n* entry: \"refs/heads/v1\"\n\nThe first case is always correct, but the second is only correct if the ref\ncache entry is a directory, for example:\n\n* prefix: \"refs/heads/example\"\n* entry: \"refs/heads/\"\n\nModify the logic in 'cache_ref_iterator_advance' to reflect these\nexpectations:\n\n1. If 'overlaps_prefix' returns 'PREFIX_EXCLUDES_DIR', then the prefix and\n   ref cache entry do not overlap at all. Skip this entry.\n2. If 'overlaps_prefix' returns 'PREFIX_WITHIN_DIR', then the prefix matches\n   inside this entry if it is a directory. Skip if the entry is not a\n   directory, otherwise iterate over it.\n3. Otherwise, 'overlaps_prefix' returned 'PREFIX_CONTAINS_DIR', indicating\n   that the cache entry (directory or not) is fully contained by or equal to\n   the prefix. Iterate over this entry.\n\nNote that condition 2 relies on the names of directory entries having the\nappropriate trailing slash. The existing function documentation of\n'create_dir_entry' explicitly calls out the trailing slash requirement, so\nthis is a safe assumption to make.\n\nSigned-off-by: Victoria Dye <vdye@github.com>\n---\n refs/ref-cache.c | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/refs/ref-cache.c b/refs/ref-cache.c\nindex 2294c4564fb..6e3b725245c 100644\n--- a/refs/ref-cache.c\n+++ b/refs/ref-cache.c\n@@ -412,7 +412,8 @@ static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)\n \n \t\tif (level->prefix_state == PREFIX_WITHIN_DIR) {\n \t\t\tentry_prefix_state = overlaps_prefix(entry->name, iter->prefix);\n-\t\t\tif (entry_prefix_state == PREFIX_EXCLUDES_DIR)\n+\t\t\tif (entry_prefix_state == PREFIX_EXCLUDES_DIR ||\n+\t\t\t    (entry_prefix_state == PREFIX_WITHIN_DIR && !(entry->flag & REF_DIR)))\n \t\t\t\tcontinue;\n \t\t} else {\n \t\t\tentry_prefix_state = level->prefix_state;\n-- \ngitgitgadget\n\n"},{"id":"482753","messageId":"a382d2ba652a1ac9b0e39552558fb69a4e2aad5e.1696615769.git.gitgitgadget@gmail.com","threadId":"60317","inReplyTo":"pull.1594.git.1696615769.gitgitgadget@gmail.com","subject":"[PATCH 3/4] dir.[ch]: add 'follow_symlink' arg to 'get_dtype'","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2023-10-06T18:09:28Z","receivedAt":"2023-10-06T18:09:38Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"From: Victoria Dye <vdye@github.com>\n\nAdd a 'follow_symlink' boolean option to 'get_type()'. If 'follow_symlink'\nis enabled, DT_LNK (in addition to DT_UNKNOWN) d_types triggers the\nstat-based d_type resolution, using 'stat' instead of 'lstat' to get the\ntype of the followed symlink. Note that symlinks are not followed\nrecursively, so a symlink pointing to another symlink will still resolve to\nDT_LNK.\n\nUpdate callers in 'diagnose.c' to specify 'follow_symlink = 0' to preserve\ncurrent behavior.\n\nSigned-off-by: Victoria Dye <vdye@github.com>\n---\n diagnose.c |  6 +++---\n dir.c      | 13 +++++++++----\n dir.h      |  7 ++++++-\n 3 files changed, 18 insertions(+), 8 deletions(-)\n\ndiff --git a/diagnose.c b/diagnose.c\nindex fc4d344bd63..4d096c857f1 100644\n--- a/diagnose.c\n+++ b/diagnose.c\n@@ -81,7 +81,7 @@ static int count_files(struct strbuf *path)\n \t\treturn 0;\n \n \twhile ((e = readdir_skip_dot_and_dotdot(dir)) != NULL)\n-\t\tif (get_dtype(e, path) == DT_REG)\n+\t\tif (get_dtype(e, path, 0) == DT_REG)\n \t\t\tcount++;\n \n \tclosedir(dir);\n@@ -110,7 +110,7 @@ static void loose_objs_stats(struct strbuf *buf, const char *path)\n \tbase_path_len = count_path.len;\n \n \twhile ((e = readdir_skip_dot_and_dotdot(dir)) != NULL)\n-\t\tif (get_dtype(e, &count_path) == DT_DIR &&\n+\t\tif (get_dtype(e, &count_path, 0) == DT_DIR &&\n \t\t    strlen(e->d_name) == 2 &&\n \t\t    !hex_to_bytes(&c, e->d_name, 1)) {\n \t\t\tstrbuf_setlen(&count_path, base_path_len);\n@@ -155,7 +155,7 @@ static int add_directory_to_archiver(struct strvec *archiver_args,\n \n \t\tstrbuf_add_absolute_path(&abspath, at_root ? \".\" : path);\n \t\tstrbuf_addch(&abspath, '/');\n-\t\tdtype = get_dtype(e, &abspath);\n+\t\tdtype = get_dtype(e, &abspath, 0);\n \n \t\tstrbuf_setlen(&buf, len);\n \t\tstrbuf_addstr(&buf, e->d_name);\ndiff --git a/dir.c b/dir.c\nindex 5e01af3a25e..16fdb03f2a5 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -2235,19 +2235,24 @@ static int get_index_dtype(struct index_state *istate,\n \treturn DT_UNKNOWN;\n }\n \n-unsigned char get_dtype(struct dirent *e, struct strbuf *path)\n+unsigned char get_dtype(struct dirent *e, struct strbuf *path,\n+\t\t\tint follow_symlink)\n {\n \tstruct stat st;\n \tunsigned char dtype = DTYPE(e);\n \tsize_t base_path_len;\n \n-\tif (dtype != DT_UNKNOWN)\n+\tif (dtype != DT_UNKNOWN && !(follow_symlink && dtype == DT_LNK))\n \t\treturn dtype;\n \n-\t/* d_type unknown in dirent, try to fall back on lstat results */\n+\t/*\n+\t * d_type unknown or unfollowed symlink, try to fall back on [l]stat\n+\t * results. If [l]stat fails, explicitly set DT_UNKNOWN.\n+\t */\n \tbase_path_len = path->len;\n \tstrbuf_addstr(path, e->d_name);\n-\tif (lstat(path->buf, &st))\n+\tif ((follow_symlink && stat(path->buf, &st)) ||\n+\t    (!follow_symlink && lstat(path->buf, &st)))\n \t\tgoto cleanup;\n \n \t/* determine d_type from st_mode */\ndiff --git a/dir.h b/dir.h\nindex 28c630ce806..98aa85fcc0e 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -368,11 +368,16 @@ struct dirent *readdir_skip_dot_and_dotdot(DIR *dirp);\n  * stat.st_mode using the path to the dirent's containing directory (path) and\n  * the name of the dirent itself.\n  *\n+ * If 'follow_symlink' is 1, this function will attempt to follow DT_LNK types\n+ * using 'stat'. Links are *not* followed recursively, so a symlink pointing\n+ * to another symlink will still resolve to 'DT_LNK'.\n+ *\n  * Note that 'path' is assumed to have a trailing slash. It is also modified\n  * in-place during the execution of the function, but is then reverted to its\n  * original value before returning.\n  */\n-unsigned char get_dtype(struct dirent *e, struct strbuf *path);\n+unsigned char get_dtype(struct dirent *e, struct strbuf *path,\n+\t\t\tint follow_symlink);\n \n /*Count the number of slashes for string s*/\n int count_slashes(const char *s);\n-- \ngitgitgadget\n\n"},{"id":"482754","messageId":"24014010ea350a2ea8676b6560ca1d60838c56ef.1696615769.git.gitgitgadget@gmail.com","threadId":"60317","inReplyTo":"pull.1594.git.1696615769.gitgitgadget@gmail.com","subject":"[PATCH 2/4] dir.[ch]: expose 'get_dtype'","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2023-10-06T18:09:27Z","receivedAt":"2023-10-06T18:09:41Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"From: Victoria Dye <vdye@github.com>\n\nMove 'get_dtype()' from 'diagnose.c' to 'dir.c' and add its declaration to\n'dir.h' so that it is accessible to callers in other files. The function and\nits documentation are moved verbatim except for a small addition to the\ndescription clarifying what the 'path' arg represents.\n\nSigned-off-by: Victoria Dye <vdye@github.com>\n---\n diagnose.c | 36 ------------------------------------\n dir.c      | 28 ++++++++++++++++++++++++++++\n dir.h      | 11 +++++++++++\n 3 files changed, 39 insertions(+), 36 deletions(-)\n\ndiff --git a/diagnose.c b/diagnose.c\nindex 8430064000b..fc4d344bd63 100644\n--- a/diagnose.c\n+++ b/diagnose.c\n@@ -71,42 +71,6 @@ static int dir_file_stats(struct object_directory *object_dir, void *data)\n \treturn 0;\n }\n \n-/*\n- * Get the d_type of a dirent. If the d_type is unknown, derive it from\n- * stat.st_mode.\n- *\n- * Note that 'path' is assumed to have a trailing slash. It is also modified\n- * in-place during the execution of the function, but is then reverted to its\n- * original value before returning.\n- */\n-static unsigned char get_dtype(struct dirent *e, struct strbuf *path)\n-{\n-\tstruct stat st;\n-\tunsigned char dtype = DTYPE(e);\n-\tsize_t base_path_len;\n-\n-\tif (dtype != DT_UNKNOWN)\n-\t\treturn dtype;\n-\n-\t/* d_type unknown in dirent, try to fall back on lstat results */\n-\tbase_path_len = path->len;\n-\tstrbuf_addstr(path, e->d_name);\n-\tif (lstat(path->buf, &st))\n-\t\tgoto cleanup;\n-\n-\t/* determine d_type from st_mode */\n-\tif (S_ISREG(st.st_mode))\n-\t\tdtype = DT_REG;\n-\telse if (S_ISDIR(st.st_mode))\n-\t\tdtype = DT_DIR;\n-\telse if (S_ISLNK(st.st_mode))\n-\t\tdtype = DT_LNK;\n-\n-cleanup:\n-\tstrbuf_setlen(path, base_path_len);\n-\treturn dtype;\n-}\n-\n static int count_files(struct strbuf *path)\n {\n \tDIR *dir = opendir(path->buf);\ndiff --git a/dir.c b/dir.c\nindex 8486e4d56ff..5e01af3a25e 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -2235,6 +2235,34 @@ static int get_index_dtype(struct index_state *istate,\n \treturn DT_UNKNOWN;\n }\n \n+unsigned char get_dtype(struct dirent *e, struct strbuf *path)\n+{\n+\tstruct stat st;\n+\tunsigned char dtype = DTYPE(e);\n+\tsize_t base_path_len;\n+\n+\tif (dtype != DT_UNKNOWN)\n+\t\treturn dtype;\n+\n+\t/* d_type unknown in dirent, try to fall back on lstat results */\n+\tbase_path_len = path->len;\n+\tstrbuf_addstr(path, e->d_name);\n+\tif (lstat(path->buf, &st))\n+\t\tgoto cleanup;\n+\n+\t/* determine d_type from st_mode */\n+\tif (S_ISREG(st.st_mode))\n+\t\tdtype = DT_REG;\n+\telse if (S_ISDIR(st.st_mode))\n+\t\tdtype = DT_DIR;\n+\telse if (S_ISLNK(st.st_mode))\n+\t\tdtype = DT_LNK;\n+\n+cleanup:\n+\tstrbuf_setlen(path, base_path_len);\n+\treturn dtype;\n+}\n+\n static int resolve_dtype(int dtype, struct index_state *istate,\n \t\t\t const char *path, int len)\n {\ndiff --git a/dir.h b/dir.h\nindex ad06682fd54..28c630ce806 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -363,6 +363,17 @@ struct dir_struct {\n \n struct dirent *readdir_skip_dot_and_dotdot(DIR *dirp);\n \n+/*\n+ * Get the d_type of a dirent. If the d_type is unknown, derive it from\n+ * stat.st_mode using the path to the dirent's containing directory (path) and\n+ * the name of the dirent itself.\n+ *\n+ * Note that 'path' is assumed to have a trailing slash. It is also modified\n+ * in-place during the execution of the function, but is then reverted to its\n+ * original value before returning.\n+ */\n+unsigned char get_dtype(struct dirent *e, struct strbuf *path);\n+\n /*Count the number of slashes for string s*/\n int count_slashes(const char *s);\n \n-- \ngitgitgadget\n\n"},{"id":"482755","messageId":"e193a45318244d9f8b05dfe2fb1ce57f6a4f6428.1696615769.git.gitgitgadget@gmail.com","threadId":"60317","inReplyTo":"pull.1594.git.1696615769.gitgitgadget@gmail.com","subject":"[PATCH 4/4] files-backend.c: avoid stat in 'loose_fill_ref_dir'","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2023-10-06T18:09:29Z","receivedAt":"2023-10-06T18:09:48Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"From: Victoria Dye <vdye@github.com>\n\nModify the 'readdir' loop in 'loose_fill_ref_dir' to, rather than 'stat' a\nfile to determine whether it is a directory or not, use 'get_dtype'.\n\nCurrently, the loop uses 'stat' to determine whether each dirent is a\ndirectory itself or not in order to construct the appropriate ref cache\nentry. If 'stat' fails (returning a negative value), the dirent is silently\nskipped; otherwise, 'S_ISDIR(st.st_mode)' is used to check whether the entry\nis a directory.\n\nOn platforms that include an entry's d_type in in the 'dirent' struct, this\nextra 'stat' check is redundant. We can use the 'get_dtype' method to\nextract this information on platforms that support it (i.e. where\nNO_D_TYPE_IN_DIRENT is unset), and derive it with 'stat' on platforms that\ndon't. Because 'stat' is an expensive call, this confers a\nmodest-but-noticeable performance improvement when iterating over large\nnumbers of refs (approximately 20% speedup in 'git for-each-ref' in a 30k\nref repo).\n\nUnlike other existing usage of 'get_dtype', the 'follow_symlinks' arg is set\nto 1 to replicate the existing handling of symlink dirents. This\nunfortunately requires calling 'stat' on the associated entry regardless of\nplatform, but symlinks in the loose ref store are highly unlikely since\nthey'd need to be created manually by a user.\n\nNote that this patch also changes the condition for skipping creation of a\nref entry from \"when 'stat' fails\" to \"when the d_type is anything other\nthan DT_REG or DT_DIR\". If a dirent's d_type is DT_UNKNOWN (either because\nthe platform doesn't support d_type in dirents or some other reason) or\nDT_LNK, 'get_dtype' will try to derive the underlying type with 'stat'. If\nthe 'stat' fails, the d_type will remain 'DT_UNKNOWN' and dirent will be\nskipped. However, it will also be skipped if it is any other valid d_type\n(e.g. DT_FIFO for named pipes, DT_LNK for a nested symlink). Git does not\nhandle these properly anyway, so we can safely constrain accepted types to\ndirectories and regular files.\n\nSigned-off-by: Victoria Dye <vdye@github.com>\n---\n refs/files-backend.c | 14 +++++---------\n 1 file changed, 5 insertions(+), 9 deletions(-)\n\ndiff --git a/refs/files-backend.c b/refs/files-backend.c\nindex 341354182bb..db5c0c7a724 100644\n--- a/refs/files-backend.c\n+++ b/refs/files-backend.c\n@@ -246,10 +246,8 @@ static void loose_fill_ref_dir(struct ref_store *ref_store,\n \tint dirnamelen = strlen(dirname);\n \tstruct strbuf refname;\n \tstruct strbuf path = STRBUF_INIT;\n-\tsize_t path_baselen;\n \n \tfiles_ref_path(refs, &path, dirname);\n-\tpath_baselen = path.len;\n \n \td = opendir(path.buf);\n \tif (!d) {\n@@ -262,23 +260,22 @@ static void loose_fill_ref_dir(struct ref_store *ref_store,\n \n \twhile ((de = readdir(d)) != NULL) {\n \t\tstruct object_id oid;\n-\t\tstruct stat st;\n \t\tint flag;\n+\t\tunsigned char dtype;\n \n \t\tif (de->d_name[0] == '.')\n \t\t\tcontinue;\n \t\tif (ends_with(de->d_name, \".lock\"))\n \t\t\tcontinue;\n \t\tstrbuf_addstr(&refname, de->d_name);\n-\t\tstrbuf_addstr(&path, de->d_name);\n-\t\tif (stat(path.buf, &st) < 0) {\n-\t\t\t; /* silently ignore */\n-\t\t} else if (S_ISDIR(st.st_mode)) {\n+\n+\t\tdtype = get_dtype(de, &path, 1);\n+\t\tif (dtype == DT_DIR) {\n \t\t\tstrbuf_addch(&refname, '/');\n \t\t\tadd_entry_to_dir(dir,\n \t\t\t\t\t create_dir_entry(dir->cache, refname.buf,\n \t\t\t\t\t\t\t  refname.len));\n-\t\t} else {\n+\t\t} else if (dtype == DT_REG) {\n \t\t\tif (!refs_resolve_ref_unsafe(&refs->base,\n \t\t\t\t\t\t     refname.buf,\n \t\t\t\t\t\t     RESOLVE_REF_READING,\n@@ -308,7 +305,6 @@ static void loose_fill_ref_dir(struct ref_store *ref_store,\n \t\t\t\t\t create_ref_entry(refname.buf, &oid, flag));\n \t\t}\n \t\tstrbuf_setlen(&refname, dirnamelen);\n-\t\tstrbuf_setlen(&path, path_baselen);\n \t}\n \tstrbuf_release(&refname);\n \tstrbuf_release(&path);\n-- \ngitgitgadget\n"},{"id":"482760","messageId":"xmqqwmvz8t4w.fsf@gitster.g","threadId":"60317","inReplyTo":"pull.1594.git.1696615769.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/4] Performance improvement & cleanup in loose ref iteration","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-10-06T19:09:51Z","receivedAt":"2023-10-06T19:09:56Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Victoria Dye via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> While investigating ref iteration performance in builtins like\n> 'for-each-ref' and 'show-ref', I found two small improvement opportunities.\n>\n> The first patch tweaks the logic around prefix matching in\n> 'cache_ref_iterator_advance' so that we correctly skip refs that do not\n> actually match a given prefix. The unnecessary iteration doesn't seem to be\n> causing any bugs in the ref iteration commands that I've tested, but it\n> doesn't hurt to be more precise (and it helps with some other patches I'm\n> working on ;) ).\n>\n> The next three patches update how 'loose_fill_ref_dir' determines the type\n> of ref cache entry to create (directory or regular). On platforms that\n> include d_type information in 'struct dirent' (as far as I can tell, all\n> except NonStop & certain versions of Cygwin), this allows us to skip calling\n> 'stat'. In ad-hoc testing, this improved performance of 'git for-each-ref'\n> by about 20%.\n\nYay.  That is a very obvious one, once it is pointed out.  Thanks\nfor noticing and improving.  Looking forward to reading the patches\nthemselves.\n\n"},{"id":"482761","messageId":"xmqqfs2n8lnn.fsf@gitster.g","threadId":"60317","inReplyTo":"59276a5b3fd1fd3b25db73e096cf0e834af2d4f9.1696615769.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/4] ref-cache.c: fix prefix matching in ref iteration","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-10-06T21:51:24Z","receivedAt":"2023-10-06T21:51:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Victoria Dye via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> From: Victoria Dye <vdye@github.com>\n>\n> Update 'cache_ref_iterator_advance' to skip over refs that are not matched\n> by the given prefix.\n>\n> Currently, a ref entry is considered \"matched\" if the entry name is fully\n> contained within the prefix:\n>\n> * prefix: \"refs/heads/v1\"\n> * entry: \"refs/heads/v1.0\"\n>\n> OR if the prefix is fully contained in the entry name:\n>\n> * prefix: \"refs/heads/v1.0\"\n> * entry: \"refs/heads/v1\"\n>\n> The first case is always correct, but the second is only correct if the ref\n> cache entry is a directory, for example:\n>\n> * prefix: \"refs/heads/example\"\n> * entry: \"refs/heads/\"\n>\n> Modify the logic in 'cache_ref_iterator_advance' to reflect these\n> expectations:\n>\n> 1. If 'overlaps_prefix' returns 'PREFIX_EXCLUDES_DIR', then the prefix and\n>    ref cache entry do not overlap at all. Skip this entry.\n> 2. If 'overlaps_prefix' returns 'PREFIX_WITHIN_DIR', then the prefix matches\n>    inside this entry if it is a directory. Skip if the entry is not a\n>    directory, otherwise iterate over it.\n> 3. Otherwise, 'overlaps_prefix' returned 'PREFIX_CONTAINS_DIR', indicating\n>    that the cache entry (directory or not) is fully contained by or equal to\n>    the prefix. Iterate over this entry.\n>\n> Note that condition 2 relies on the names of directory entries having the\n> appropriate trailing slash. The existing function documentation of\n> 'create_dir_entry' explicitly calls out the trailing slash requirement, so\n> this is a safe assumption to make.\n\nThanks for explaining it very well and clearly.  \n\nAllowing prefix=\"refs/heads/v1.0\" to yield entry=\"refs/heads/v1\"\n(case #2 above that this patch fixes the behaviour for) would cause\nref_iterator_advance() to return a ref outside the hierarhcy,\nwouldn't it?  So it appears to me that either one of the two would\nbe true:\n\n * the code is structured in such a way that such a condition does\n   not actually happen (in which case this patch would be a no-op),\n   or\n\n * there is a bug in the current code that is fixed by this patch,\n   whose externally observable behaviour can be verified with a\n   test.\n\nIt is not quite clear to me which is the case here.  The code with\nthe patch looks more logical than the original, but I am not sure\nhow to demonstrate the existing breakage (if any).\n\n> Signed-off-by: Victoria Dye <vdye@github.com>\n> ---\n>  refs/ref-cache.c | 3 ++-\n>  1 file changed, 2 insertions(+), 1 deletion(-)\n>\n> diff --git a/refs/ref-cache.c b/refs/ref-cache.c\n> index 2294c4564fb..6e3b725245c 100644\n> --- a/refs/ref-cache.c\n> +++ b/refs/ref-cache.c\n> @@ -412,7 +412,8 @@ static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)\n>  \n>  \t\tif (level->prefix_state == PREFIX_WITHIN_DIR) {\n>  \t\t\tentry_prefix_state = overlaps_prefix(entry->name, iter->prefix);\n> -\t\t\tif (entry_prefix_state == PREFIX_EXCLUDES_DIR)\n> +\t\t\tif (entry_prefix_state == PREFIX_EXCLUDES_DIR ||\n> +\t\t\t    (entry_prefix_state == PREFIX_WITHIN_DIR && !(entry->flag & REF_DIR)))\n>  \t\t\t\tcontinue;\n>  \t\t} else {\n>  \t\t\tentry_prefix_state = level->prefix_state;\n"},{"id":"482762","messageId":"xmqq1qe78l8u.fsf@gitster.g","threadId":"60317","inReplyTo":"24014010ea350a2ea8676b6560ca1d60838c56ef.1696615769.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/4] dir.[ch]: expose 'get_dtype'","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-10-06T22:00:17Z","receivedAt":"2023-10-06T22:00:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Victoria Dye via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> From: Victoria Dye <vdye@github.com>\n>\n> Move 'get_dtype()' from 'diagnose.c' to 'dir.c' and add its declaration to\n> 'dir.h' so that it is accessible to callers in other files. The function and\n> its documentation are moved verbatim except for a small addition to the\n> description clarifying what the 'path' arg represents.\n>\n> Signed-off-by: Victoria Dye <vdye@github.com>\n> ---\n>  diagnose.c | 36 ------------------------------------\n>  dir.c      | 28 ++++++++++++++++++++++++++++\n>  dir.h      | 11 +++++++++++\n>  3 files changed, 39 insertions(+), 36 deletions(-)\n\nOK.  diagnose.c should still have access to the function as it\nincludes <dir.h>, and to anybody that includes <dir.h> and sees the\ndeclaration of get_dtype(), DT_FOO should be visible because <dir.h>\nincludes <statinfo.h> that has fallback definition of DT_FOO.\n\nLooking simple and straight-forward.\n\n\n> diff --git a/diagnose.c b/diagnose.c\n> index 8430064000b..fc4d344bd63 100644\n> --- a/diagnose.c\n> +++ b/diagnose.c\n> @@ -71,42 +71,6 @@ static int dir_file_stats(struct object_directory *object_dir, void *data)\n>  \treturn 0;\n>  }\n>  \n> -/*\n> - * Get the d_type of a dirent. If the d_type is unknown, derive it from\n> - * stat.st_mode.\n> - *\n> - * Note that 'path' is assumed to have a trailing slash. It is also modified\n> - * in-place during the execution of the function, but is then reverted to its\n> - * original value before returning.\n> - */\n> -static unsigned char get_dtype(struct dirent *e, struct strbuf *path)\n> -{\n> -\tstruct stat st;\n> -\tunsigned char dtype = DTYPE(e);\n> -\tsize_t base_path_len;\n> -\n> -\tif (dtype != DT_UNKNOWN)\n> -\t\treturn dtype;\n> -\n> -\t/* d_type unknown in dirent, try to fall back on lstat results */\n> -\tbase_path_len = path->len;\n> -\tstrbuf_addstr(path, e->d_name);\n> -\tif (lstat(path->buf, &st))\n> -\t\tgoto cleanup;\n> -\n> -\t/* determine d_type from st_mode */\n> -\tif (S_ISREG(st.st_mode))\n> -\t\tdtype = DT_REG;\n> -\telse if (S_ISDIR(st.st_mode))\n> -\t\tdtype = DT_DIR;\n> -\telse if (S_ISLNK(st.st_mode))\n> -\t\tdtype = DT_LNK;\n> -\n> -cleanup:\n> -\tstrbuf_setlen(path, base_path_len);\n> -\treturn dtype;\n> -}\n> -\n>  static int count_files(struct strbuf *path)\n>  {\n>  \tDIR *dir = opendir(path->buf);\n> diff --git a/dir.c b/dir.c\n> index 8486e4d56ff..5e01af3a25e 100644\n> --- a/dir.c\n> +++ b/dir.c\n> @@ -2235,6 +2235,34 @@ static int get_index_dtype(struct index_state *istate,\n>  \treturn DT_UNKNOWN;\n>  }\n>  \n> +unsigned char get_dtype(struct dirent *e, struct strbuf *path)\n> +{\n> +\tstruct stat st;\n> +\tunsigned char dtype = DTYPE(e);\n> +\tsize_t base_path_len;\n> +\n> +\tif (dtype != DT_UNKNOWN)\n> +\t\treturn dtype;\n> +\n> +\t/* d_type unknown in dirent, try to fall back on lstat results */\n> +\tbase_path_len = path->len;\n> +\tstrbuf_addstr(path, e->d_name);\n> +\tif (lstat(path->buf, &st))\n> +\t\tgoto cleanup;\n> +\n> +\t/* determine d_type from st_mode */\n> +\tif (S_ISREG(st.st_mode))\n> +\t\tdtype = DT_REG;\n> +\telse if (S_ISDIR(st.st_mode))\n> +\t\tdtype = DT_DIR;\n> +\telse if (S_ISLNK(st.st_mode))\n> +\t\tdtype = DT_LNK;\n> +\n> +cleanup:\n> +\tstrbuf_setlen(path, base_path_len);\n> +\treturn dtype;\n> +}\n> +\n>  static int resolve_dtype(int dtype, struct index_state *istate,\n>  \t\t\t const char *path, int len)\n>  {\n> diff --git a/dir.h b/dir.h\n> index ad06682fd54..28c630ce806 100644\n> --- a/dir.h\n> +++ b/dir.h\n> @@ -363,6 +363,17 @@ struct dir_struct {\n>  \n>  struct dirent *readdir_skip_dot_and_dotdot(DIR *dirp);\n>  \n> +/*\n> + * Get the d_type of a dirent. If the d_type is unknown, derive it from\n> + * stat.st_mode using the path to the dirent's containing directory (path) and\n> + * the name of the dirent itself.\n> + *\n> + * Note that 'path' is assumed to have a trailing slash. It is also modified\n> + * in-place during the execution of the function, but is then reverted to its\n> + * original value before returning.\n> + */\n> +unsigned char get_dtype(struct dirent *e, struct strbuf *path);\n> +\n>  /*Count the number of slashes for string s*/\n>  int count_slashes(const char *s);\n"},{"id":"482771","messageId":"xmqqttr37645.fsf@gitster.g","threadId":"60317","inReplyTo":"e193a45318244d9f8b05dfe2fb1ce57f6a4f6428.1696615769.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 4/4] files-backend.c: avoid stat in 'loose_fill_ref_dir'","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-10-06T22:12:26Z","receivedAt":"2023-10-06T22:12:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Victoria Dye via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n\n> Unlike other existing usage of 'get_dtype', the 'follow_symlinks' arg is set\n> to 1 to replicate the existing handling of symlink dirents. This\n> unfortunately requires calling 'stat' on the associated entry regardless of\n> platform, but symlinks in the loose ref store are highly unlikely since\n> they'd need to be created manually by a user.\n\nYeek.  I wonder what breaks if we do not do this follow_symlinks()\npart, i.e., either just replace stat() with lstat() in the original\nwithout any of these four patches (which would be simple to figure\nout what breaks), or omit [3/4] and let get_dtype() yield DT_LNK.\n\nIt seems that it comes from a7e66ae3 ([PATCH] Make do_each_ref()\nfollow symlinks., 2005-08-16), and just like I commented on there in\nits log message back then, I still doubt that following a symbolic\nlink is a great idea here in this codepath.\n\nBut optimization without behaviour change is a good way to ensure\nthat optimization does not introduce new bugs, and because keeping\nthe historical behaviour like the patches [3/4] and this patch does\nis more work (meaning: if it proves unnecessary to dereference\nsymbolic links, we can remove code instead of having to write new\ncode to support the new behaviour), let's take the series as-is, and\ndefer it to future developers to further clean-up the semantics.\n\n> Note that this patch also changes the condition for skipping creation of a\n> ref entry from \"when 'stat' fails\" to \"when the d_type is anything other\n> than DT_REG or DT_DIR\". If a dirent's d_type is DT_UNKNOWN (either because\n> the platform doesn't support d_type in dirents or some other reason) or\n> DT_LNK, 'get_dtype' will try to derive the underlying type with 'stat'. If\n> the 'stat' fails, the d_type will remain 'DT_UNKNOWN' and dirent will be\n> skipped. However, it will also be skipped if it is any other valid d_type\n> (e.g. DT_FIFO for named pipes, DT_LNK for a nested symlink). Git does not\n> handle these properly anyway, so we can safely constrain accepted types to\n> directories and regular files.\n\nSounds good.\n\n> Signed-off-by: Victoria Dye <vdye@github.com>\n> ---\n>  refs/files-backend.c | 14 +++++---------\n>  1 file changed, 5 insertions(+), 9 deletions(-)\n\nThanks.\n\n"},{"id":"482854","messageId":"ZSPQI2gkLOSdNWLu@tanuki","threadId":"60317","inReplyTo":"pull.1594.git.1696615769.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/4] Performance improvement & cleanup in loose ref iteration","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-10-09T10:04:19Z","receivedAt":"2023-10-09T10:04:34Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Oct 06, 2023 at 06:09:25PM +0000, Victoria Dye via GitGitGadget wrote:\n> While investigating ref iteration performance in builtins like\n> 'for-each-ref' and 'show-ref', I found two small improvement opportunities.\n> \n> The first patch tweaks the logic around prefix matching in\n> 'cache_ref_iterator_advance' so that we correctly skip refs that do not\n> actually match a given prefix. The unnecessary iteration doesn't seem to be\n> causing any bugs in the ref iteration commands that I've tested, but it\n> doesn't hurt to be more precise (and it helps with some other patches I'm\n> working on ;) ).\n> \n> The next three patches update how 'loose_fill_ref_dir' determines the type\n> of ref cache entry to create (directory or regular). On platforms that\n> include d_type information in 'struct dirent' (as far as I can tell, all\n> except NonStop & certain versions of Cygwin), this allows us to skip calling\n> 'stat'. In ad-hoc testing, this improved performance of 'git for-each-ref'\n> by about 20%.\n\nI've done a small set of benchmarks with my usual test repositories,\nwhich is linux.git with a bunch of references added. The repository\ncomes in four sizes:\n\n- small: 50k references\n- medium: 500k references\n- high:  1.1m references\n- huge: 12m references\n\nUnfortunately, I couldn't really reproduce the performance improvements.\nIn fact, the new version runs consistently a tiny bit slower than the\nold version:\n\n    # Old version, which is 3a06386e31 (The fifteenth batch, 2023-10-04).\n\n    Benchmark 1: git for-each-ref (revision=old,refcount=small)\n      Time (mean ± σ):     135.5 ms ±   1.2 ms    [User: 76.4 ms, System: 59.0 ms]\n      Range (min … max):   134.8 ms … 136.9 ms    3 runs\n\n    Benchmark 2: git for-each-ref (revision=old,refcount=medium)\n      Time (mean ± σ):     822.7 ms ±   2.2 ms    [User: 697.4 ms, System: 125.1 ms]\n      Range (min … max):   821.1 ms … 825.2 ms    3 runs\n\n    Benchmark 3: git for-each-ref (revision=old,refcount=high)\n      Time (mean ± σ):      1.960 s ±  0.015 s    [User: 1.702 s, System: 0.257 s]\n      Range (min … max):    1.944 s …  1.973 s    3 runs\n\n    # New version, which is your tip.\n\n    Benchmark 4: git for-each-ref (revision=old,refcount=huge)\n      Time (mean ± σ):     16.815 s ±  0.054 s    [User: 15.091 s, System: 1.722 s]\n      Range (min … max):   16.760 s … 16.869 s    3 runs\n\n    Benchmark 5: git for-each-ref (revision=new,refcount=small)\n      Time (mean ± σ):     136.0 ms ±   0.2 ms    [User: 78.8 ms, System: 57.1 ms]\n      Range (min … max):   135.8 ms … 136.2 ms    3 runs\n\n    Benchmark 6: git for-each-ref (revision=new,refcount=medium)\n      Time (mean ± σ):     830.4 ms ±  21.2 ms    [User: 691.3 ms, System: 138.7 ms]\n      Range (min … max):   814.2 ms … 854.5 ms    3 runs\n\n    Benchmark 7: git for-each-ref (revision=new,refcount=high)\n      Time (mean ± σ):      1.966 s ±  0.013 s    [User: 1.717 s, System: 0.249 s]\n      Range (min … max):    1.952 s …  1.978 s    3 runs\n\n    Benchmark 8: git for-each-ref (revision=new,refcount=huge)\n      Time (mean ± σ):     16.945 s ±  0.037 s    [User: 15.182 s, System: 1.760 s]\n      Range (min … max):   16.910 s … 16.983 s    3 runs\n\n    Summary\n      git for-each-ref (revision=old,refcount=small) ran\n        1.00 ± 0.01 times faster than git for-each-ref (revision=new,refcount=small)\n        6.07 ± 0.06 times faster than git for-each-ref (revision=old,refcount=medium)\n        6.13 ± 0.17 times faster than git for-each-ref (revision=new,refcount=medium)\n       14.46 ± 0.17 times faster than git for-each-ref (revision=old,refcount=high)\n       14.51 ± 0.16 times faster than git for-each-ref (revision=new,refcount=high)\n      124.09 ± 1.15 times faster than git for-each-ref (revision=old,refcount=huge)\n      125.05 ± 1.12 times faster than git for-each-ref (revision=new,refcount=huge)\n\nThe performance regression isn't all that concerning, but it makes me\nwonder why I see things becoming slower rather than faster. My guess is\nthat this is because all my test repositories are well-packed and don't\nhave a lot of loose references. But I just wanted to confirm how you\nbenchmarked your change and what the underlying shape of your test repo\nwas.\n\nPatrick\n\n> Thanks!\n> \n>  * Victoria\n> \n> Victoria Dye (4):\n>   ref-cache.c: fix prefix matching in ref iteration\n>   dir.[ch]: expose 'get_dtype'\n>   dir.[ch]: add 'follow_symlink' arg to 'get_dtype'\n>   files-backend.c: avoid stat in 'loose_fill_ref_dir'\n> \n>  diagnose.c           | 42 +++---------------------------------------\n>  dir.c                | 33 +++++++++++++++++++++++++++++++++\n>  dir.h                | 16 ++++++++++++++++\n>  refs/files-backend.c | 14 +++++---------\n>  refs/ref-cache.c     |  3 ++-\n>  5 files changed, 59 insertions(+), 49 deletions(-)\n> \n> \n> base-commit: 3a06386e314565108ad56a9bdb8f7b80ac52fb69\n> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1594%2Fvdye%2Fvdye%2Fref-iteration-cleanup-v1\n> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1594/vdye/vdye/ref-iteration-cleanup-v1\n> Pull-Request: https://github.com/gitgitgadget/git/pull/1594\n> -- \n> gitgitgadget\n"},{"id":"482855","messageId":"ZSPQLjJwq-7SjsDT@tanuki","threadId":"60317","inReplyTo":"xmqqfs2n8lnn.fsf@gitster.g","subject":"Re: [PATCH 1/4] ref-cache.c: fix prefix matching in ref iteration","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-10-09T10:04:30Z","receivedAt":"2023-10-09T10:04:40Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Oct 06, 2023 at 02:51:24PM -0700, Junio C Hamano wrote:\n> \"Victoria Dye via GitGitGadget\" <gitgitgadget@gmail.com> writes:\n> \n> > From: Victoria Dye <vdye@github.com>\n> >\n> > Update 'cache_ref_iterator_advance' to skip over refs that are not matched\n> > by the given prefix.\n> >\n> > Currently, a ref entry is considered \"matched\" if the entry name is fully\n> > contained within the prefix:\n> >\n> > * prefix: \"refs/heads/v1\"\n> > * entry: \"refs/heads/v1.0\"\n> >\n> > OR if the prefix is fully contained in the entry name:\n> >\n> > * prefix: \"refs/heads/v1.0\"\n> > * entry: \"refs/heads/v1\"\n> >\n> > The first case is always correct, but the second is only correct if the ref\n> > cache entry is a directory, for example:\n> >\n> > * prefix: \"refs/heads/example\"\n> > * entry: \"refs/heads/\"\n> >\n> > Modify the logic in 'cache_ref_iterator_advance' to reflect these\n> > expectations:\n> >\n> > 1. If 'overlaps_prefix' returns 'PREFIX_EXCLUDES_DIR', then the prefix and\n> >    ref cache entry do not overlap at all. Skip this entry.\n> > 2. If 'overlaps_prefix' returns 'PREFIX_WITHIN_DIR', then the prefix matches\n> >    inside this entry if it is a directory. Skip if the entry is not a\n> >    directory, otherwise iterate over it.\n> > 3. Otherwise, 'overlaps_prefix' returned 'PREFIX_CONTAINS_DIR', indicating\n> >    that the cache entry (directory or not) is fully contained by or equal to\n> >    the prefix. Iterate over this entry.\n> >\n> > Note that condition 2 relies on the names of directory entries having the\n> > appropriate trailing slash. The existing function documentation of\n> > 'create_dir_entry' explicitly calls out the trailing slash requirement, so\n> > this is a safe assumption to make.\n> \n> Thanks for explaining it very well and clearly.  \n> \n> Allowing prefix=\"refs/heads/v1.0\" to yield entry=\"refs/heads/v1\"\n> (case #2 above that this patch fixes the behaviour for) would cause\n> ref_iterator_advance() to return a ref outside the hierarhcy,\n> wouldn't it?  So it appears to me that either one of the two would\n> be true:\n> \n>  * the code is structured in such a way that such a condition does\n>    not actually happen (in which case this patch would be a no-op),\n>    or\n> \n>  * there is a bug in the current code that is fixed by this patch,\n>    whose externally observable behaviour can be verified with a\n>    test.\n> \n> It is not quite clear to me which is the case here.  The code with\n> the patch looks more logical than the original, but I am not sure\n> how to demonstrate the existing breakage (if any).\n\nAgreed, I also had a bit of a hard time to figure out whether this is an\nactual bug fix, a performance improvement or merely a refactoring.\n\nPatrick\n\n> > Signed-off-by: Victoria Dye <vdye@github.com>\n> > ---\n> >  refs/ref-cache.c | 3 ++-\n> >  1 file changed, 2 insertions(+), 1 deletion(-)\n> >\n> > diff --git a/refs/ref-cache.c b/refs/ref-cache.c\n> > index 2294c4564fb..6e3b725245c 100644\n> > --- a/refs/ref-cache.c\n> > +++ b/refs/ref-cache.c\n> > @@ -412,7 +412,8 @@ static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)\n> >  \n> >  \t\tif (level->prefix_state == PREFIX_WITHIN_DIR) {\n> >  \t\t\tentry_prefix_state = overlaps_prefix(entry->name, iter->prefix);\n> > -\t\t\tif (entry_prefix_state == PREFIX_EXCLUDES_DIR)\n> > +\t\t\tif (entry_prefix_state == PREFIX_EXCLUDES_DIR ||\n> > +\t\t\t    (entry_prefix_state == PREFIX_WITHIN_DIR && !(entry->flag & REF_DIR)))\n> >  \t\t\t\tcontinue;\n> >  \t\t} else {\n> >  \t\t\tentry_prefix_state = level->prefix_state;\n"},{"id":"482873","messageId":"3585d72f-9f06-d190-ad5a-bec6db3f647f@github.com","threadId":"60317","inReplyTo":"ZSPQLjJwq-7SjsDT@tanuki","subject":"Re: [PATCH 1/4] ref-cache.c: fix prefix matching in ref iteration","fromName":"Victoria Dye","fromEmail":"vdye@github.com","sentAt":"2023-10-09T16:21:53Z","receivedAt":"2023-10-09T16:22:00Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"Patrick Steinhardt wrote:\n>> Allowing prefix=\"refs/heads/v1.0\" to yield entry=\"refs/heads/v1\"\n>> (case #2 above that this patch fixes the behaviour for) would cause\n>> ref_iterator_advance() to return a ref outside the hierarhcy,\n>> wouldn't it?  So it appears to me that either one of the two would\n>> be true:\n>>\n>>  * the code is structured in such a way that such a condition does\n>>    not actually happen (in which case this patch would be a no-op),\n>>    or\n>>\n>>  * there is a bug in the current code that is fixed by this patch,\n>>    whose externally observable behaviour can be verified with a\n>>    test.\n>>\n>> It is not quite clear to me which is the case here.  The code with\n>> the patch looks more logical than the original, but I am not sure\n>> how to demonstrate the existing breakage (if any).\n> \n> Agreed, I also had a bit of a hard time to figure out whether this is an\n> actual bug fix, a performance improvement or merely a refactoring.\n> \n\nI originally operated on the assumption that it was the first case, which is\nwhy I didn't include a test in this patch. Commands like 'for-each-ref',\n'show-ref', etc. either use an empty prefix or a directory prefix with a\ntrailing slash, which won't trigger this issue. I encountered the problem\nwhile working on a builtin that filtered refs by a user-specified prefix -\nthe results included refs that should not have been matched, which led me to\nthis fix.\n\nScanning through the codebase again, though, I do see a way to replicate the\nissue:\n\n$ git update-ref refs/bisect/b HEAD\n$ git rev-parse --abbrev-ref --bisect\nrefs/bisect/b\n\nBecause 'rev-parse --bisect' uses the \"refs/bisect/bad\" prefix (no trailing\nslash) and does no additional filtering in its 'for_each_fullref_in'\ncallback, refs like \"refs/bisect/b\" and \"refs/bisect/ba\" are (incorrectly)\nmatched. I'll re-roll with the added test.\n\n"},{"id":"482888","messageId":"xmqqa5sr1x3p.fsf@gitster.g","threadId":"60317","inReplyTo":"3585d72f-9f06-d190-ad5a-bec6db3f647f@github.com","subject":"Re: [PATCH 1/4] ref-cache.c: fix prefix matching in ref iteration","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-10-09T18:15:06Z","receivedAt":"2023-10-09T18:15:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Victoria Dye <vdye@github.com> writes:\n\n> I originally operated on the assumption that it was the first case, which is\n> why I didn't include a test in this patch. Commands like 'for-each-ref',\n> 'show-ref', etc. either use an empty prefix or a directory prefix with a\n> trailing slash, which won't trigger this issue.\n\nAh, yes, I didn't mention it but I suspected as such (i.e. the code\nis structured in such a way that this broken implementation does not\nmatter to the current callers).\n\n> I encountered the problem\n> while working on a builtin that filtered refs by a user-specified prefix -\n> the results included refs that should not have been matched, which led me to\n> this fix.\n\nOK, perfectly understandable.\n\n> Scanning through the codebase again, though, I do see a way to replicate the\n> issue:\n>\n> $ git update-ref refs/bisect/b HEAD\n> $ git rev-parse --abbrev-ref --bisect\n> refs/bisect/b\n>\n> Because 'rev-parse --bisect' uses the \"refs/bisect/bad\" prefix (no trailing\n> slash) and does no additional filtering in its 'for_each_fullref_in'\n> callback, refs like \"refs/bisect/b\" and \"refs/bisect/ba\" are (incorrectly)\n> matched. I'll re-roll with the added test.\n\nGood find.  Thanks!\n"},{"id":"482927","messageId":"28ae03f5-7091-d3f3-8a70-56aba6639640@github.com","threadId":"60317","inReplyTo":"ZSPQI2gkLOSdNWLu@tanuki","subject":"Re: [PATCH 0/4] Performance improvement & cleanup in loose ref iteration","fromName":"Victoria Dye","fromEmail":"vdye@github.com","sentAt":"2023-10-09T21:49:14Z","receivedAt":"2023-10-09T21:49:26Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"Patrick Steinhardt wrote:\n> On Fri, Oct 06, 2023 at 06:09:25PM +0000, Victoria Dye via GitGitGadget wrote:\n>> While investigating ref iteration performance in builtins like\n>> 'for-each-ref' and 'show-ref', I found two small improvement opportunities.\n>>\n>> The first patch tweaks the logic around prefix matching in\n>> 'cache_ref_iterator_advance' so that we correctly skip refs that do not\n>> actually match a given prefix. The unnecessary iteration doesn't seem to be\n>> causing any bugs in the ref iteration commands that I've tested, but it\n>> doesn't hurt to be more precise (and it helps with some other patches I'm\n>> working on ;) ).\n>>\n>> The next three patches update how 'loose_fill_ref_dir' determines the type\n>> of ref cache entry to create (directory or regular). On platforms that\n>> include d_type information in 'struct dirent' (as far as I can tell, all\n>> except NonStop & certain versions of Cygwin), this allows us to skip calling\n>> 'stat'. In ad-hoc testing, this improved performance of 'git for-each-ref'\n>> by about 20%.\n> \n> I've done a small set of benchmarks with my usual test repositories,\n> which is linux.git with a bunch of references added. The repository\n> comes in four sizes:\n> \n> - small: 50k references\n> - medium: 500k references\n> - high:  1.1m references\n> - huge: 12m references\n> \n> Unfortunately, I couldn't really reproduce the performance improvements.\n> In fact, the new version runs consistently a tiny bit slower than the\n> old version:\n> \n>     # Old version, which is 3a06386e31 (The fifteenth batch, 2023-10-04).\n> \n>     Benchmark 1: git for-each-ref (revision=old,refcount=small)\n>       Time (mean ± σ):     135.5 ms ±   1.2 ms    [User: 76.4 ms, System: 59.0 ms]\n>       Range (min … max):   134.8 ms … 136.9 ms    3 runs\n> \n>     Benchmark 2: git for-each-ref (revision=old,refcount=medium)\n>       Time (mean ± σ):     822.7 ms ±   2.2 ms    [User: 697.4 ms, System: 125.1 ms]\n>       Range (min … max):   821.1 ms … 825.2 ms    3 runs\n> \n>     Benchmark 3: git for-each-ref (revision=old,refcount=high)\n>       Time (mean ± σ):      1.960 s ±  0.015 s    [User: 1.702 s, System: 0.257 s]\n>       Range (min … max):    1.944 s …  1.973 s    3 runs\n> \n>     # New version, which is your tip.\n> \n>     Benchmark 4: git for-each-ref (revision=old,refcount=huge)\n>       Time (mean ± σ):     16.815 s ±  0.054 s    [User: 15.091 s, System: 1.722 s]\n>       Range (min … max):   16.760 s … 16.869 s    3 runs\n> \n>     Benchmark 5: git for-each-ref (revision=new,refcount=small)\n>       Time (mean ± σ):     136.0 ms ±   0.2 ms    [User: 78.8 ms, System: 57.1 ms]\n>       Range (min … max):   135.8 ms … 136.2 ms    3 runs\n> \n>     Benchmark 6: git for-each-ref (revision=new,refcount=medium)\n>       Time (mean ± σ):     830.4 ms ±  21.2 ms    [User: 691.3 ms, System: 138.7 ms]\n>       Range (min … max):   814.2 ms … 854.5 ms    3 runs\n> \n>     Benchmark 7: git for-each-ref (revision=new,refcount=high)\n>       Time (mean ± σ):      1.966 s ±  0.013 s    [User: 1.717 s, System: 0.249 s]\n>       Range (min … max):    1.952 s …  1.978 s    3 runs\n> \n>     Benchmark 8: git for-each-ref (revision=new,refcount=huge)\n>       Time (mean ± σ):     16.945 s ±  0.037 s    [User: 15.182 s, System: 1.760 s]\n>       Range (min … max):   16.910 s … 16.983 s    3 runs\n> \n>     Summary\n>       git for-each-ref (revision=old,refcount=small) ran\n>         1.00 ± 0.01 times faster than git for-each-ref (revision=new,refcount=small)\n>         6.07 ± 0.06 times faster than git for-each-ref (revision=old,refcount=medium)\n>         6.13 ± 0.17 times faster than git for-each-ref (revision=new,refcount=medium)\n>        14.46 ± 0.17 times faster than git for-each-ref (revision=old,refcount=high)\n>        14.51 ± 0.16 times faster than git for-each-ref (revision=new,refcount=high)\n>       124.09 ± 1.15 times faster than git for-each-ref (revision=old,refcount=huge)\n>       125.05 ± 1.12 times faster than git for-each-ref (revision=new,refcount=huge)\n> \n> The performance regression isn't all that concerning, but it makes me\n> wonder why I see things becoming slower rather than faster. My guess is\n> that this is because all my test repositories are well-packed and don't\n> have a lot of loose references. But I just wanted to confirm how you\n> benchmarked your change and what the underlying shape of your test repo\n> was.\n\nI ran my benchmark on my (Intel) Mac with a test repository (single commit,\none file) containing:\n\n- 10k refs/heads/ references\n- 10k refs/tags/ references\n- 10k refs/special/ references \n\nAll refs in the repository are loose. My Mac has historically been somewhat\nslow and inconsistent when it comes to perf testing, though, so I re-ran the\nbenchmark a bit more formally on an Ubuntu VM (3 warmup iterations followed\nby at least 10 iterations per test):\n\n---\n\nBenchmark 1: git for-each-ref (revision=old,refcount=3k)\n  Time (mean ± σ):      40.6 ms ±   3.9 ms    [User: 13.2 ms, System: 27.1 ms]\n  Range (min … max):    37.2 ms …  59.1 ms    76 runs\n \n  Warning: Statistical outliers were detected. Consider re-running this benchmark on a quiet system without any interferences from other programs. It might help to use the '--warmup' or '--prepare' options.\n \nBenchmark 2: git for-each-ref (revision=new,refcount=3k)\n  Time (mean ± σ):      38.7 ms ±   4.4 ms    [User: 13.8 ms, System: 24.5 ms]\n  Range (min … max):    35.1 ms …  57.2 ms    71 runs\n \n  Warning: Statistical outliers were detected. Consider re-running this benchmark on a quiet system without any interferences from other programs. It might help to use the '--warmup' or '--prepare' options.\n \nBenchmark 3: git for-each-ref (revision=old,refcount=30k)\n  Time (mean ± σ):     419.4 ms ±  43.9 ms    [User: 136.4 ms, System: 274.1 ms]\n  Range (min … max):   385.1 ms … 528.7 ms    10 runs\n \nBenchmark 4: git for-each-ref (revision=new,refcount=30k)\n  Time (mean ± σ):     390.4 ms ±  27.2 ms    [User: 133.1 ms, System: 251.6 ms]\n  Range (min … max):   360.3 ms … 447.6 ms    10 runs\n \nBenchmark 5: git for-each-ref (revision=old,refcount=300k)\n  Time (mean ± σ):      4.171 s ±  0.052 s    [User: 1.400 s, System: 2.715 s]\n  Range (min … max):    4.118 s …  4.283 s    10 runs\n \nBenchmark 6: git for-each-ref (revision=new,refcount=300k)\n  Time (mean ± σ):      3.939 s ±  0.054 s    [User: 1.403 s, System: 2.466 s]\n  Range (min … max):    3.858 s …  4.026 s    10 runs\n \nSummary\n  'git for-each-ref (revision=new,refcount=3k)' ran\n    1.05 ± 0.16 times faster than 'git for-each-ref (revision=old,refcount=3k)'\n   10.08 ± 1.34 times faster than 'git for-each-ref (revision=new,refcount=30k)'\n   10.83 ± 1.67 times faster than 'git for-each-ref (revision=old,refcount=30k)'\n  101.68 ± 11.63 times faster than 'git for-each-ref (revision=new,refcount=300k)'\n  107.67 ± 12.30 times faster than 'git for-each-ref (revision=old,refcount=300k)'\n\n---\n\nSo it's not the 20% speedup I saw on my local test repo (it's more like\n5-8%), but there does appear to be a consistent improvement. As for your\nresults, the changes in this series shouldn't affect packed ref operations,\nand the difference between old & new doesn't seem to indicate a regression. \n\n"},{"id":"482928","messageId":"pull.1594.v2.git.1696888736.gitgitgadget@gmail.com","threadId":"60317","inReplyTo":"pull.1594.git.1696615769.gitgitgadget@gmail.com","subject":"[PATCH v2 0/4] Performance improvement & cleanup in loose ref iteration","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2023-10-09T21:58:52Z","receivedAt":"2023-10-09T21:59:04Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"While investigating ref iteration performance in builtins like\n'for-each-ref' and 'show-ref', I found two small improvement opportunities.\n\nThe first patch tweaks the logic around prefix matching in\n'cache_ref_iterator_advance' so that we correctly skip refs that do not\nactually match a given prefix. The unnecessary iteration doesn't seem to be\ncausing any bugs in the ref iteration commands that I've tested, but it\ndoesn't hurt to be more precise (and it helps with some other patches I'm\nworking on ;) ).\n\nThe next three patches update how 'loose_fill_ref_dir' determines the type\nof ref cache entry to create (directory or regular). On platforms that\ninclude d_type information in 'struct dirent' (as far as I can tell, all\nexcept NonStop & certain versions of Cygwin), this allows us to skip calling\n'stat'. Benchmarking against repos with various quantities of loose refs\nindicates a 5-8% speedup from these changes [1].\n\n\nChanges since V1\n================\n\n * Added tests in patch 1 to demonstrate the bugfix\n\nThanks!\n\n * Victoria\n\n[1]\nhttps://lore.kernel.org/git/28ae03f5-7091-d3f3-8a70-56aba6639640@github.com/\n\nVictoria Dye (4):\n  ref-cache.c: fix prefix matching in ref iteration\n  dir.[ch]: expose 'get_dtype'\n  dir.[ch]: add 'follow_symlink' arg to 'get_dtype'\n  files-backend.c: avoid stat in 'loose_fill_ref_dir'\n\n diagnose.c                    | 42 +++--------------------------------\n dir.c                         | 33 +++++++++++++++++++++++++++\n dir.h                         | 16 +++++++++++++\n refs/files-backend.c          | 14 +++++-------\n refs/ref-cache.c              |  3 ++-\n t/t1500-rev-parse.sh          | 23 +++++++++++++++++++\n t/t4205-log-pretty-formats.sh | 30 +++++++++++++++++++++++++\n 7 files changed, 112 insertions(+), 49 deletions(-)\n\n\nbase-commit: 3a06386e314565108ad56a9bdb8f7b80ac52fb69\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1594%2Fvdye%2Fvdye%2Fref-iteration-cleanup-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1594/vdye/vdye/ref-iteration-cleanup-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/1594\n\nRange-diff vs v1:\n\n 1:  59276a5b3fd ! 1:  402176246ea ref-cache.c: fix prefix matching in ref iteration\n     @@ Commit message\n          'create_dir_entry' explicitly calls out the trailing slash requirement, so\n          this is a safe assumption to make.\n      \n     +    This bug generally doesn't have any user-facing impact, since it requires:\n     +\n     +    1. using a non-empty prefix without a trailing slash in an iteration like\n     +       'for_each_fullref_in',\n     +    2. the callback to said iteration not reapplying the original filter (as\n     +       for-each-ref does) to ensure unmatched refs are skipped, and\n     +    3. the repository having one or more refs that match part of, but not all\n     +       of, the prefix.\n     +\n     +    However, there are some niche scenarios that meet those criteria\n     +    (specifically, 'rev-parse --bisect' and '(log|show|shortlog) --bisect'). Add\n     +    tests covering those cases to demonstrate the fix in this patch.\n     +\n          Signed-off-by: Victoria Dye <vdye@github.com>\n      \n       ## refs/ref-cache.c ##\n     @@ refs/ref-cache.c: static int cache_ref_iterator_advance(struct ref_iterator *ref\n       \t\t\t\tcontinue;\n       \t\t} else {\n       \t\t\tentry_prefix_state = level->prefix_state;\n     +\n     + ## t/t1500-rev-parse.sh ##\n     +@@ t/t1500-rev-parse.sh: test_expect_success 'rev-parse --since= unsqueezed ordering' '\n     + \ttest_cmp expect actual\n     + '\n     + \n     ++test_expect_success 'rev-parse --bisect includes bad, excludes good' '\n     ++\ttest_commit_bulk 6 &&\n     ++\n     ++\tgit update-ref refs/bisect/bad-1 HEAD~1 &&\n     ++\tgit update-ref refs/bisect/b HEAD~2 &&\n     ++\tgit update-ref refs/bisect/bad-3 HEAD~3 &&\n     ++\tgit update-ref refs/bisect/good-3 HEAD~3 &&\n     ++\tgit update-ref refs/bisect/bad-4 HEAD~4 &&\n     ++\tgit update-ref refs/bisect/go HEAD~4 &&\n     ++\n     ++\t# Note: refs/bisect/b and refs/bisect/go should be ignored because they\n     ++\t# do not match the refs/bisect/bad or refs/bisect/good prefixes.\n     ++\tcat >expect <<-EOF &&\n     ++\trefs/bisect/bad-1\n     ++\trefs/bisect/bad-3\n     ++\trefs/bisect/bad-4\n     ++\t^refs/bisect/good-3\n     ++\tEOF\n     ++\n     ++\tgit rev-parse --symbolic-full-name --bisect >actual &&\n     ++\ttest_cmp expect actual\n     ++'\n     ++\n     + test_done\n     +\n     + ## t/t4205-log-pretty-formats.sh ##\n     +@@ t/t4205-log-pretty-formats.sh: test_expect_success '%S in git log --format works with other placeholders (part\n     + \ttest_cmp expect actual\n     + '\n     + \n     ++test_expect_success 'setup more commits for %S with --bisect' '\n     ++\ttest_commit four &&\n     ++\ttest_commit five &&\n     ++\n     ++\thead1=$(git rev-parse --verify HEAD~0) &&\n     ++\thead2=$(git rev-parse --verify HEAD~1) &&\n     ++\thead3=$(git rev-parse --verify HEAD~2) &&\n     ++\thead4=$(git rev-parse --verify HEAD~3)\n     ++'\n     ++\n     ++test_expect_success '%S with --bisect labels commits with refs/bisect/bad ref' '\n     ++\tgit update-ref refs/bisect/bad-$head1 $head1 &&\n     ++\tgit update-ref refs/bisect/go $head1 &&\n     ++\tgit update-ref refs/bisect/bad-$head2 $head2 &&\n     ++\tgit update-ref refs/bisect/b $head3 &&\n     ++\tgit update-ref refs/bisect/bad-$head4 $head4 &&\n     ++\tgit update-ref refs/bisect/good-$head4 $head4 &&\n     ++\n     ++\t# We expect to see the range of commits betwee refs/bisect/good-$head4\n     ++\t# and refs/bisect/bad-$head1. The \"source\" ref is the nearest bisect ref\n     ++\t# from which the commit is reachable.\n     ++\tcat >expect <<-EOF &&\n     ++\t$head1 refs/bisect/bad-$head1\n     ++\t$head2 refs/bisect/bad-$head2\n     ++\t$head3 refs/bisect/bad-$head2\n     ++\tEOF\n     ++\tgit log --bisect --format=\"%H %S\" >actual &&\n     ++\ttest_cmp expect actual\n     ++'\n     ++\n     + test_expect_success 'log --pretty=reference' '\n     + \tgit log --pretty=\"tformat:%h (%s, %as)\" >expect &&\n     + \tgit log --pretty=reference >actual &&\n 2:  24014010ea3 = 2:  172538b5e30 dir.[ch]: expose 'get_dtype'\n 3:  a382d2ba652 = 3:  295ca94003b dir.[ch]: add 'follow_symlink' arg to 'get_dtype'\n 4:  e193a453182 = 4:  e89501cb51f files-backend.c: avoid stat in 'loose_fill_ref_dir'\n\n-- \ngitgitgadget\n"},{"id":"482929","messageId":"402176246ea9d722a71a0ca4e970dfce8a4bf776.1696888736.git.gitgitgadget@gmail.com","threadId":"60317","inReplyTo":"pull.1594.v2.git.1696888736.gitgitgadget@gmail.com","subject":"[PATCH v2 1/4] ref-cache.c: fix prefix matching in ref iteration","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2023-10-09T21:58:53Z","receivedAt":"2023-10-09T21:59:07Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"From: Victoria Dye <vdye@github.com>\n\nUpdate 'cache_ref_iterator_advance' to skip over refs that are not matched\nby the given prefix.\n\nCurrently, a ref entry is considered \"matched\" if the entry name is fully\ncontained within the prefix:\n\n* prefix: \"refs/heads/v1\"\n* entry: \"refs/heads/v1.0\"\n\nOR if the prefix is fully contained in the entry name:\n\n* prefix: \"refs/heads/v1.0\"\n* entry: \"refs/heads/v1\"\n\nThe first case is always correct, but the second is only correct if the ref\ncache entry is a directory, for example:\n\n* prefix: \"refs/heads/example\"\n* entry: \"refs/heads/\"\n\nModify the logic in 'cache_ref_iterator_advance' to reflect these\nexpectations:\n\n1. If 'overlaps_prefix' returns 'PREFIX_EXCLUDES_DIR', then the prefix and\n   ref cache entry do not overlap at all. Skip this entry.\n2. If 'overlaps_prefix' returns 'PREFIX_WITHIN_DIR', then the prefix matches\n   inside this entry if it is a directory. Skip if the entry is not a\n   directory, otherwise iterate over it.\n3. Otherwise, 'overlaps_prefix' returned 'PREFIX_CONTAINS_DIR', indicating\n   that the cache entry (directory or not) is fully contained by or equal to\n   the prefix. Iterate over this entry.\n\nNote that condition 2 relies on the names of directory entries having the\nappropriate trailing slash. The existing function documentation of\n'create_dir_entry' explicitly calls out the trailing slash requirement, so\nthis is a safe assumption to make.\n\nThis bug generally doesn't have any user-facing impact, since it requires:\n\n1. using a non-empty prefix without a trailing slash in an iteration like\n   'for_each_fullref_in',\n2. the callback to said iteration not reapplying the original filter (as\n   for-each-ref does) to ensure unmatched refs are skipped, and\n3. the repository having one or more refs that match part of, but not all\n   of, the prefix.\n\nHowever, there are some niche scenarios that meet those criteria\n(specifically, 'rev-parse --bisect' and '(log|show|shortlog) --bisect'). Add\ntests covering those cases to demonstrate the fix in this patch.\n\nSigned-off-by: Victoria Dye <vdye@github.com>\n---\n refs/ref-cache.c              |  3 ++-\n t/t1500-rev-parse.sh          | 23 +++++++++++++++++++++++\n t/t4205-log-pretty-formats.sh | 30 ++++++++++++++++++++++++++++++\n 3 files changed, 55 insertions(+), 1 deletion(-)\n\ndiff --git a/refs/ref-cache.c b/refs/ref-cache.c\nindex 2294c4564fb..6e3b725245c 100644\n--- a/refs/ref-cache.c\n+++ b/refs/ref-cache.c\n@@ -412,7 +412,8 @@ static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)\n \n \t\tif (level->prefix_state == PREFIX_WITHIN_DIR) {\n \t\t\tentry_prefix_state = overlaps_prefix(entry->name, iter->prefix);\n-\t\t\tif (entry_prefix_state == PREFIX_EXCLUDES_DIR)\n+\t\t\tif (entry_prefix_state == PREFIX_EXCLUDES_DIR ||\n+\t\t\t    (entry_prefix_state == PREFIX_WITHIN_DIR && !(entry->flag & REF_DIR)))\n \t\t\t\tcontinue;\n \t\t} else {\n \t\t\tentry_prefix_state = level->prefix_state;\ndiff --git a/t/t1500-rev-parse.sh b/t/t1500-rev-parse.sh\nindex 37ee5091b5c..3f9e7f62e45 100755\n--- a/t/t1500-rev-parse.sh\n+++ b/t/t1500-rev-parse.sh\n@@ -264,4 +264,27 @@ test_expect_success 'rev-parse --since= unsqueezed ordering' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'rev-parse --bisect includes bad, excludes good' '\n+\ttest_commit_bulk 6 &&\n+\n+\tgit update-ref refs/bisect/bad-1 HEAD~1 &&\n+\tgit update-ref refs/bisect/b HEAD~2 &&\n+\tgit update-ref refs/bisect/bad-3 HEAD~3 &&\n+\tgit update-ref refs/bisect/good-3 HEAD~3 &&\n+\tgit update-ref refs/bisect/bad-4 HEAD~4 &&\n+\tgit update-ref refs/bisect/go HEAD~4 &&\n+\n+\t# Note: refs/bisect/b and refs/bisect/go should be ignored because they\n+\t# do not match the refs/bisect/bad or refs/bisect/good prefixes.\n+\tcat >expect <<-EOF &&\n+\trefs/bisect/bad-1\n+\trefs/bisect/bad-3\n+\trefs/bisect/bad-4\n+\t^refs/bisect/good-3\n+\tEOF\n+\n+\tgit rev-parse --symbolic-full-name --bisect >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\ndiff --git a/t/t4205-log-pretty-formats.sh b/t/t4205-log-pretty-formats.sh\nindex 16626e4fe96..62c7bfed5d7 100755\n--- a/t/t4205-log-pretty-formats.sh\n+++ b/t/t4205-log-pretty-formats.sh\n@@ -956,6 +956,36 @@ test_expect_success '%S in git log --format works with other placeholders (part\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'setup more commits for %S with --bisect' '\n+\ttest_commit four &&\n+\ttest_commit five &&\n+\n+\thead1=$(git rev-parse --verify HEAD~0) &&\n+\thead2=$(git rev-parse --verify HEAD~1) &&\n+\thead3=$(git rev-parse --verify HEAD~2) &&\n+\thead4=$(git rev-parse --verify HEAD~3)\n+'\n+\n+test_expect_success '%S with --bisect labels commits with refs/bisect/bad ref' '\n+\tgit update-ref refs/bisect/bad-$head1 $head1 &&\n+\tgit update-ref refs/bisect/go $head1 &&\n+\tgit update-ref refs/bisect/bad-$head2 $head2 &&\n+\tgit update-ref refs/bisect/b $head3 &&\n+\tgit update-ref refs/bisect/bad-$head4 $head4 &&\n+\tgit update-ref refs/bisect/good-$head4 $head4 &&\n+\n+\t# We expect to see the range of commits betwee refs/bisect/good-$head4\n+\t# and refs/bisect/bad-$head1. The \"source\" ref is the nearest bisect ref\n+\t# from which the commit is reachable.\n+\tcat >expect <<-EOF &&\n+\t$head1 refs/bisect/bad-$head1\n+\t$head2 refs/bisect/bad-$head2\n+\t$head3 refs/bisect/bad-$head2\n+\tEOF\n+\tgit log --bisect --format=\"%H %S\" >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_expect_success 'log --pretty=reference' '\n \tgit log --pretty=\"tformat:%h (%s, %as)\" >expect &&\n \tgit log --pretty=reference >actual &&\n-- \ngitgitgadget\n\n"},{"id":"482930","messageId":"172538b5e30fe38f5f37726fd6c31fc63984edba.1696888736.git.gitgitgadget@gmail.com","threadId":"60317","inReplyTo":"pull.1594.v2.git.1696888736.gitgitgadget@gmail.com","subject":"[PATCH v2 2/4] dir.[ch]: expose 'get_dtype'","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2023-10-09T21:58:54Z","receivedAt":"2023-10-09T21:59:10Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"From: Victoria Dye <vdye@github.com>\n\nMove 'get_dtype()' from 'diagnose.c' to 'dir.c' and add its declaration to\n'dir.h' so that it is accessible to callers in other files. The function and\nits documentation are moved verbatim except for a small addition to the\ndescription clarifying what the 'path' arg represents.\n\nSigned-off-by: Victoria Dye <vdye@github.com>\n---\n diagnose.c | 36 ------------------------------------\n dir.c      | 28 ++++++++++++++++++++++++++++\n dir.h      | 11 +++++++++++\n 3 files changed, 39 insertions(+), 36 deletions(-)\n\ndiff --git a/diagnose.c b/diagnose.c\nindex 8430064000b..fc4d344bd63 100644\n--- a/diagnose.c\n+++ b/diagnose.c\n@@ -71,42 +71,6 @@ static int dir_file_stats(struct object_directory *object_dir, void *data)\n \treturn 0;\n }\n \n-/*\n- * Get the d_type of a dirent. If the d_type is unknown, derive it from\n- * stat.st_mode.\n- *\n- * Note that 'path' is assumed to have a trailing slash. It is also modified\n- * in-place during the execution of the function, but is then reverted to its\n- * original value before returning.\n- */\n-static unsigned char get_dtype(struct dirent *e, struct strbuf *path)\n-{\n-\tstruct stat st;\n-\tunsigned char dtype = DTYPE(e);\n-\tsize_t base_path_len;\n-\n-\tif (dtype != DT_UNKNOWN)\n-\t\treturn dtype;\n-\n-\t/* d_type unknown in dirent, try to fall back on lstat results */\n-\tbase_path_len = path->len;\n-\tstrbuf_addstr(path, e->d_name);\n-\tif (lstat(path->buf, &st))\n-\t\tgoto cleanup;\n-\n-\t/* determine d_type from st_mode */\n-\tif (S_ISREG(st.st_mode))\n-\t\tdtype = DT_REG;\n-\telse if (S_ISDIR(st.st_mode))\n-\t\tdtype = DT_DIR;\n-\telse if (S_ISLNK(st.st_mode))\n-\t\tdtype = DT_LNK;\n-\n-cleanup:\n-\tstrbuf_setlen(path, base_path_len);\n-\treturn dtype;\n-}\n-\n static int count_files(struct strbuf *path)\n {\n \tDIR *dir = opendir(path->buf);\ndiff --git a/dir.c b/dir.c\nindex 8486e4d56ff..5e01af3a25e 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -2235,6 +2235,34 @@ static int get_index_dtype(struct index_state *istate,\n \treturn DT_UNKNOWN;\n }\n \n+unsigned char get_dtype(struct dirent *e, struct strbuf *path)\n+{\n+\tstruct stat st;\n+\tunsigned char dtype = DTYPE(e);\n+\tsize_t base_path_len;\n+\n+\tif (dtype != DT_UNKNOWN)\n+\t\treturn dtype;\n+\n+\t/* d_type unknown in dirent, try to fall back on lstat results */\n+\tbase_path_len = path->len;\n+\tstrbuf_addstr(path, e->d_name);\n+\tif (lstat(path->buf, &st))\n+\t\tgoto cleanup;\n+\n+\t/* determine d_type from st_mode */\n+\tif (S_ISREG(st.st_mode))\n+\t\tdtype = DT_REG;\n+\telse if (S_ISDIR(st.st_mode))\n+\t\tdtype = DT_DIR;\n+\telse if (S_ISLNK(st.st_mode))\n+\t\tdtype = DT_LNK;\n+\n+cleanup:\n+\tstrbuf_setlen(path, base_path_len);\n+\treturn dtype;\n+}\n+\n static int resolve_dtype(int dtype, struct index_state *istate,\n \t\t\t const char *path, int len)\n {\ndiff --git a/dir.h b/dir.h\nindex ad06682fd54..28c630ce806 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -363,6 +363,17 @@ struct dir_struct {\n \n struct dirent *readdir_skip_dot_and_dotdot(DIR *dirp);\n \n+/*\n+ * Get the d_type of a dirent. If the d_type is unknown, derive it from\n+ * stat.st_mode using the path to the dirent's containing directory (path) and\n+ * the name of the dirent itself.\n+ *\n+ * Note that 'path' is assumed to have a trailing slash. It is also modified\n+ * in-place during the execution of the function, but is then reverted to its\n+ * original value before returning.\n+ */\n+unsigned char get_dtype(struct dirent *e, struct strbuf *path);\n+\n /*Count the number of slashes for string s*/\n int count_slashes(const char *s);\n \n-- \ngitgitgadget\n\n"},{"id":"482931","messageId":"295ca94003bd0e25c0d4b733010e6474dd091e0e.1696888736.git.gitgitgadget@gmail.com","threadId":"60317","inReplyTo":"pull.1594.v2.git.1696888736.gitgitgadget@gmail.com","subject":"[PATCH v2 3/4] dir.[ch]: add 'follow_symlink' arg to 'get_dtype'","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2023-10-09T21:58:55Z","receivedAt":"2023-10-09T21:59:11Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"From: Victoria Dye <vdye@github.com>\n\nAdd a 'follow_symlink' boolean option to 'get_type()'. If 'follow_symlink'\nis enabled, DT_LNK (in addition to DT_UNKNOWN) d_types triggers the\nstat-based d_type resolution, using 'stat' instead of 'lstat' to get the\ntype of the followed symlink. Note that symlinks are not followed\nrecursively, so a symlink pointing to another symlink will still resolve to\nDT_LNK.\n\nUpdate callers in 'diagnose.c' to specify 'follow_symlink = 0' to preserve\ncurrent behavior.\n\nSigned-off-by: Victoria Dye <vdye@github.com>\n---\n diagnose.c |  6 +++---\n dir.c      | 13 +++++++++----\n dir.h      |  7 ++++++-\n 3 files changed, 18 insertions(+), 8 deletions(-)\n\ndiff --git a/diagnose.c b/diagnose.c\nindex fc4d344bd63..4d096c857f1 100644\n--- a/diagnose.c\n+++ b/diagnose.c\n@@ -81,7 +81,7 @@ static int count_files(struct strbuf *path)\n \t\treturn 0;\n \n \twhile ((e = readdir_skip_dot_and_dotdot(dir)) != NULL)\n-\t\tif (get_dtype(e, path) == DT_REG)\n+\t\tif (get_dtype(e, path, 0) == DT_REG)\n \t\t\tcount++;\n \n \tclosedir(dir);\n@@ -110,7 +110,7 @@ static void loose_objs_stats(struct strbuf *buf, const char *path)\n \tbase_path_len = count_path.len;\n \n \twhile ((e = readdir_skip_dot_and_dotdot(dir)) != NULL)\n-\t\tif (get_dtype(e, &count_path) == DT_DIR &&\n+\t\tif (get_dtype(e, &count_path, 0) == DT_DIR &&\n \t\t    strlen(e->d_name) == 2 &&\n \t\t    !hex_to_bytes(&c, e->d_name, 1)) {\n \t\t\tstrbuf_setlen(&count_path, base_path_len);\n@@ -155,7 +155,7 @@ static int add_directory_to_archiver(struct strvec *archiver_args,\n \n \t\tstrbuf_add_absolute_path(&abspath, at_root ? \".\" : path);\n \t\tstrbuf_addch(&abspath, '/');\n-\t\tdtype = get_dtype(e, &abspath);\n+\t\tdtype = get_dtype(e, &abspath, 0);\n \n \t\tstrbuf_setlen(&buf, len);\n \t\tstrbuf_addstr(&buf, e->d_name);\ndiff --git a/dir.c b/dir.c\nindex 5e01af3a25e..16fdb03f2a5 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -2235,19 +2235,24 @@ static int get_index_dtype(struct index_state *istate,\n \treturn DT_UNKNOWN;\n }\n \n-unsigned char get_dtype(struct dirent *e, struct strbuf *path)\n+unsigned char get_dtype(struct dirent *e, struct strbuf *path,\n+\t\t\tint follow_symlink)\n {\n \tstruct stat st;\n \tunsigned char dtype = DTYPE(e);\n \tsize_t base_path_len;\n \n-\tif (dtype != DT_UNKNOWN)\n+\tif (dtype != DT_UNKNOWN && !(follow_symlink && dtype == DT_LNK))\n \t\treturn dtype;\n \n-\t/* d_type unknown in dirent, try to fall back on lstat results */\n+\t/*\n+\t * d_type unknown or unfollowed symlink, try to fall back on [l]stat\n+\t * results. If [l]stat fails, explicitly set DT_UNKNOWN.\n+\t */\n \tbase_path_len = path->len;\n \tstrbuf_addstr(path, e->d_name);\n-\tif (lstat(path->buf, &st))\n+\tif ((follow_symlink && stat(path->buf, &st)) ||\n+\t    (!follow_symlink && lstat(path->buf, &st)))\n \t\tgoto cleanup;\n \n \t/* determine d_type from st_mode */\ndiff --git a/dir.h b/dir.h\nindex 28c630ce806..98aa85fcc0e 100644\n--- a/dir.h\n+++ b/dir.h\n@@ -368,11 +368,16 @@ struct dirent *readdir_skip_dot_and_dotdot(DIR *dirp);\n  * stat.st_mode using the path to the dirent's containing directory (path) and\n  * the name of the dirent itself.\n  *\n+ * If 'follow_symlink' is 1, this function will attempt to follow DT_LNK types\n+ * using 'stat'. Links are *not* followed recursively, so a symlink pointing\n+ * to another symlink will still resolve to 'DT_LNK'.\n+ *\n  * Note that 'path' is assumed to have a trailing slash. It is also modified\n  * in-place during the execution of the function, but is then reverted to its\n  * original value before returning.\n  */\n-unsigned char get_dtype(struct dirent *e, struct strbuf *path);\n+unsigned char get_dtype(struct dirent *e, struct strbuf *path,\n+\t\t\tint follow_symlink);\n \n /*Count the number of slashes for string s*/\n int count_slashes(const char *s);\n-- \ngitgitgadget\n\n"},{"id":"482932","messageId":"e89501cb51f12b7a49fc6ee03fe6f9e6264ea2b9.1696888736.git.gitgitgadget@gmail.com","threadId":"60317","inReplyTo":"pull.1594.v2.git.1696888736.gitgitgadget@gmail.com","subject":"[PATCH v2 4/4] files-backend.c: avoid stat in 'loose_fill_ref_dir'","fromName":"Victoria Dye via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2023-10-09T21:58:56Z","receivedAt":"2023-10-09T21:59:13Z","isPatch":true,"sender":{"key":"vdye@github.com","avatar":"https://avatars.githubusercontent.com/u/3619353?v=4"},"body":"From: Victoria Dye <vdye@github.com>\n\nModify the 'readdir' loop in 'loose_fill_ref_dir' to, rather than 'stat' a\nfile to determine whether it is a directory or not, use 'get_dtype'.\n\nCurrently, the loop uses 'stat' to determine whether each dirent is a\ndirectory itself or not in order to construct the appropriate ref cache\nentry. If 'stat' fails (returning a negative value), the dirent is silently\nskipped; otherwise, 'S_ISDIR(st.st_mode)' is used to check whether the entry\nis a directory.\n\nOn platforms that include an entry's d_type in in the 'dirent' struct, this\nextra 'stat' check is redundant. We can use the 'get_dtype' method to\nextract this information on platforms that support it (i.e. where\nNO_D_TYPE_IN_DIRENT is unset), and derive it with 'stat' on platforms that\ndon't. Because 'stat' is an expensive call, this confers a\nmodest-but-noticeable performance improvement when iterating over large\nnumbers of refs (approximately 20% speedup in 'git for-each-ref' in a 30k\nref repo).\n\nUnlike other existing usage of 'get_dtype', the 'follow_symlinks' arg is set\nto 1 to replicate the existing handling of symlink dirents. This\nunfortunately requires calling 'stat' on the associated entry regardless of\nplatform, but symlinks in the loose ref store are highly unlikely since\nthey'd need to be created manually by a user.\n\nNote that this patch also changes the condition for skipping creation of a\nref entry from \"when 'stat' fails\" to \"when the d_type is anything other\nthan DT_REG or DT_DIR\". If a dirent's d_type is DT_UNKNOWN (either because\nthe platform doesn't support d_type in dirents or some other reason) or\nDT_LNK, 'get_dtype' will try to derive the underlying type with 'stat'. If\nthe 'stat' fails, the d_type will remain 'DT_UNKNOWN' and dirent will be\nskipped. However, it will also be skipped if it is any other valid d_type\n(e.g. DT_FIFO for named pipes, DT_LNK for a nested symlink). Git does not\nhandle these properly anyway, so we can safely constrain accepted types to\ndirectories and regular files.\n\nSigned-off-by: Victoria Dye <vdye@github.com>\n---\n refs/files-backend.c | 14 +++++---------\n 1 file changed, 5 insertions(+), 9 deletions(-)\n\ndiff --git a/refs/files-backend.c b/refs/files-backend.c\nindex 341354182bb..db5c0c7a724 100644\n--- a/refs/files-backend.c\n+++ b/refs/files-backend.c\n@@ -246,10 +246,8 @@ static void loose_fill_ref_dir(struct ref_store *ref_store,\n \tint dirnamelen = strlen(dirname);\n \tstruct strbuf refname;\n \tstruct strbuf path = STRBUF_INIT;\n-\tsize_t path_baselen;\n \n \tfiles_ref_path(refs, &path, dirname);\n-\tpath_baselen = path.len;\n \n \td = opendir(path.buf);\n \tif (!d) {\n@@ -262,23 +260,22 @@ static void loose_fill_ref_dir(struct ref_store *ref_store,\n \n \twhile ((de = readdir(d)) != NULL) {\n \t\tstruct object_id oid;\n-\t\tstruct stat st;\n \t\tint flag;\n+\t\tunsigned char dtype;\n \n \t\tif (de->d_name[0] == '.')\n \t\t\tcontinue;\n \t\tif (ends_with(de->d_name, \".lock\"))\n \t\t\tcontinue;\n \t\tstrbuf_addstr(&refname, de->d_name);\n-\t\tstrbuf_addstr(&path, de->d_name);\n-\t\tif (stat(path.buf, &st) < 0) {\n-\t\t\t; /* silently ignore */\n-\t\t} else if (S_ISDIR(st.st_mode)) {\n+\n+\t\tdtype = get_dtype(de, &path, 1);\n+\t\tif (dtype == DT_DIR) {\n \t\t\tstrbuf_addch(&refname, '/');\n \t\t\tadd_entry_to_dir(dir,\n \t\t\t\t\t create_dir_entry(dir->cache, refname.buf,\n \t\t\t\t\t\t\t  refname.len));\n-\t\t} else {\n+\t\t} else if (dtype == DT_REG) {\n \t\t\tif (!refs_resolve_ref_unsafe(&refs->base,\n \t\t\t\t\t\t     refname.buf,\n \t\t\t\t\t\t     RESOLVE_REF_READING,\n@@ -308,7 +305,6 @@ static void loose_fill_ref_dir(struct ref_store *ref_store,\n \t\t\t\t\t create_ref_entry(refname.buf, &oid, flag));\n \t\t}\n \t\tstrbuf_setlen(&refname, dirnamelen);\n-\t\tstrbuf_setlen(&path, path_baselen);\n \t}\n \tstrbuf_release(&refname);\n \tstrbuf_release(&path);\n-- \ngitgitgadget\n"},{"id":"482951","messageId":"ZST7aPwZrB5JR2Ig@tanuki","threadId":"60317","inReplyTo":"402176246ea9d722a71a0ca4e970dfce8a4bf776.1696888736.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 1/4] ref-cache.c: fix prefix matching in ref iteration","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-10-10T07:21:12Z","receivedAt":"2023-10-10T07:21:25Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Mon, Oct 09, 2023 at 09:58:53PM +0000, Victoria Dye via GitGitGadget wrote:\n> From: Victoria Dye <vdye@github.com>\n> \n> Update 'cache_ref_iterator_advance' to skip over refs that are not matched\n> by the given prefix.\n> \n> Currently, a ref entry is considered \"matched\" if the entry name is fully\n> contained within the prefix:\n> \n> * prefix: \"refs/heads/v1\"\n> * entry: \"refs/heads/v1.0\"\n> \n> OR if the prefix is fully contained in the entry name:\n> \n> * prefix: \"refs/heads/v1.0\"\n> * entry: \"refs/heads/v1\"\n> \n> The first case is always correct, but the second is only correct if the ref\n> cache entry is a directory, for example:\n> \n> * prefix: \"refs/heads/example\"\n> * entry: \"refs/heads/\"\n> \n> Modify the logic in 'cache_ref_iterator_advance' to reflect these\n> expectations:\n> \n> 1. If 'overlaps_prefix' returns 'PREFIX_EXCLUDES_DIR', then the prefix and\n>    ref cache entry do not overlap at all. Skip this entry.\n> 2. If 'overlaps_prefix' returns 'PREFIX_WITHIN_DIR', then the prefix matches\n>    inside this entry if it is a directory. Skip if the entry is not a\n>    directory, otherwise iterate over it.\n> 3. Otherwise, 'overlaps_prefix' returned 'PREFIX_CONTAINS_DIR', indicating\n>    that the cache entry (directory or not) is fully contained by or equal to\n>    the prefix. Iterate over this entry.\n> \n> Note that condition 2 relies on the names of directory entries having the\n> appropriate trailing slash. The existing function documentation of\n> 'create_dir_entry' explicitly calls out the trailing slash requirement, so\n> this is a safe assumption to make.\n> \n> This bug generally doesn't have any user-facing impact, since it requires:\n> \n> 1. using a non-empty prefix without a trailing slash in an iteration like\n>    'for_each_fullref_in',\n> 2. the callback to said iteration not reapplying the original filter (as\n>    for-each-ref does) to ensure unmatched refs are skipped, and\n> 3. the repository having one or more refs that match part of, but not all\n>    of, the prefix.\n> \n> However, there are some niche scenarios that meet those criteria\n> (specifically, 'rev-parse --bisect' and '(log|show|shortlog) --bisect'). Add\n> tests covering those cases to demonstrate the fix in this patch.\n> \n> Signed-off-by: Victoria Dye <vdye@github.com>\n> ---\n>  refs/ref-cache.c              |  3 ++-\n>  t/t1500-rev-parse.sh          | 23 +++++++++++++++++++++++\n>  t/t4205-log-pretty-formats.sh | 30 ++++++++++++++++++++++++++++++\n>  3 files changed, 55 insertions(+), 1 deletion(-)\n> \n> diff --git a/refs/ref-cache.c b/refs/ref-cache.c\n> index 2294c4564fb..6e3b725245c 100644\n> --- a/refs/ref-cache.c\n> +++ b/refs/ref-cache.c\n> @@ -412,7 +412,8 @@ static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)\n>  \n>  \t\tif (level->prefix_state == PREFIX_WITHIN_DIR) {\n>  \t\t\tentry_prefix_state = overlaps_prefix(entry->name, iter->prefix);\n> -\t\t\tif (entry_prefix_state == PREFIX_EXCLUDES_DIR)\n> +\t\t\tif (entry_prefix_state == PREFIX_EXCLUDES_DIR ||\n> +\t\t\t    (entry_prefix_state == PREFIX_WITHIN_DIR && !(entry->flag & REF_DIR)))\n>  \t\t\t\tcontinue;\n>  \t\t} else {\n>  \t\t\tentry_prefix_state = level->prefix_state;\n> diff --git a/t/t1500-rev-parse.sh b/t/t1500-rev-parse.sh\n> index 37ee5091b5c..3f9e7f62e45 100755\n> --- a/t/t1500-rev-parse.sh\n> +++ b/t/t1500-rev-parse.sh\n> @@ -264,4 +264,27 @@ test_expect_success 'rev-parse --since= unsqueezed ordering' '\n>  \ttest_cmp expect actual\n>  '\n>  \n> +test_expect_success 'rev-parse --bisect includes bad, excludes good' '\n> +\ttest_commit_bulk 6 &&\n> +\n> +\tgit update-ref refs/bisect/bad-1 HEAD~1 &&\n> +\tgit update-ref refs/bisect/b HEAD~2 &&\n> +\tgit update-ref refs/bisect/bad-3 HEAD~3 &&\n> +\tgit update-ref refs/bisect/good-3 HEAD~3 &&\n> +\tgit update-ref refs/bisect/bad-4 HEAD~4 &&\n> +\tgit update-ref refs/bisect/go HEAD~4 &&\n> +\n> +\t# Note: refs/bisect/b and refs/bisect/go should be ignored because they\n> +\t# do not match the refs/bisect/bad or refs/bisect/good prefixes.\n> +\tcat >expect <<-EOF &&\n> +\trefs/bisect/bad-1\n> +\trefs/bisect/bad-3\n> +\trefs/bisect/bad-4\n> +\t^refs/bisect/good-3\n> +\tEOF\n> +\n> +\tgit rev-parse --symbolic-full-name --bisect >actual &&\n> +\ttest_cmp expect actual\n> +'\n> +\n>  test_done\n> diff --git a/t/t4205-log-pretty-formats.sh b/t/t4205-log-pretty-formats.sh\n> index 16626e4fe96..62c7bfed5d7 100755\n> --- a/t/t4205-log-pretty-formats.sh\n> +++ b/t/t4205-log-pretty-formats.sh\n> @@ -956,6 +956,36 @@ test_expect_success '%S in git log --format works with other placeholders (part\n>  \ttest_cmp expect actual\n>  '\n>  \n> +test_expect_success 'setup more commits for %S with --bisect' '\n> +\ttest_commit four &&\n> +\ttest_commit five &&\n> +\n> +\thead1=$(git rev-parse --verify HEAD~0) &&\n> +\thead2=$(git rev-parse --verify HEAD~1) &&\n> +\thead3=$(git rev-parse --verify HEAD~2) &&\n> +\thead4=$(git rev-parse --verify HEAD~3)\n> +'\n> +\n> +test_expect_success '%S with --bisect labels commits with refs/bisect/bad ref' '\n> +\tgit update-ref refs/bisect/bad-$head1 $head1 &&\n> +\tgit update-ref refs/bisect/go $head1 &&\n> +\tgit update-ref refs/bisect/bad-$head2 $head2 &&\n> +\tgit update-ref refs/bisect/b $head3 &&\n> +\tgit update-ref refs/bisect/bad-$head4 $head4 &&\n> +\tgit update-ref refs/bisect/good-$head4 $head4 &&\n> +\n> +\t# We expect to see the range of commits betwee refs/bisect/good-$head4\n\nNit: s/betwee/between. Probably not worth rerolling this series only\nbecause of this typo though.\n\nPatrick\n\n> +\t# and refs/bisect/bad-$head1. The \"source\" ref is the nearest bisect ref\n> +\t# from which the commit is reachable.\n> +\tcat >expect <<-EOF &&\n> +\t$head1 refs/bisect/bad-$head1\n> +\t$head2 refs/bisect/bad-$head2\n> +\t$head3 refs/bisect/bad-$head2\n> +\tEOF\n> +\tgit log --bisect --format=\"%H %S\" >actual &&\n> +\ttest_cmp expect actual\n> +'\n> +\n>  test_expect_success 'log --pretty=reference' '\n>  \tgit log --pretty=\"tformat:%h (%s, %as)\" >expect &&\n>  \tgit log --pretty=reference >actual &&\n> -- \n> gitgitgadget\n> \n"},{"id":"482952","messageId":"ZST7dIYaCEFx4P0E@tanuki","threadId":"60317","inReplyTo":"28ae03f5-7091-d3f3-8a70-56aba6639640@github.com","subject":"Re: [PATCH 0/4] Performance improvement & cleanup in loose ref iteration","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-10-10T07:21:24Z","receivedAt":"2023-10-10T07:21:34Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Mon, Oct 09, 2023 at 02:49:14PM -0700, Victoria Dye wrote:\n> Patrick Steinhardt wrote:\n> > On Fri, Oct 06, 2023 at 06:09:25PM +0000, Victoria Dye via GitGitGadget wrote:\n> >> While investigating ref iteration performance in builtins like\n> >> 'for-each-ref' and 'show-ref', I found two small improvement opportunities.\n> >>\n> >> The first patch tweaks the logic around prefix matching in\n> >> 'cache_ref_iterator_advance' so that we correctly skip refs that do not\n> >> actually match a given prefix. The unnecessary iteration doesn't seem to be\n> >> causing any bugs in the ref iteration commands that I've tested, but it\n> >> doesn't hurt to be more precise (and it helps with some other patches I'm\n> >> working on ;) ).\n> >>\n> >> The next three patches update how 'loose_fill_ref_dir' determines the type\n> >> of ref cache entry to create (directory or regular). On platforms that\n> >> include d_type information in 'struct dirent' (as far as I can tell, all\n> >> except NonStop & certain versions of Cygwin), this allows us to skip calling\n> >> 'stat'. In ad-hoc testing, this improved performance of 'git for-each-ref'\n> >> by about 20%.\n> > \n> > I've done a small set of benchmarks with my usual test repositories,\n> > which is linux.git with a bunch of references added. The repository\n> > comes in four sizes:\n> > \n> > - small: 50k references\n> > - medium: 500k references\n> > - high:  1.1m references\n> > - huge: 12m references\n> > \n> > Unfortunately, I couldn't really reproduce the performance improvements.\n> > In fact, the new version runs consistently a tiny bit slower than the\n> > old version:\n> > \n> >     # Old version, which is 3a06386e31 (The fifteenth batch, 2023-10-04).\n> > \n> >     Benchmark 1: git for-each-ref (revision=old,refcount=small)\n> >       Time (mean ± σ):     135.5 ms ±   1.2 ms    [User: 76.4 ms, System: 59.0 ms]\n> >       Range (min … max):   134.8 ms … 136.9 ms    3 runs\n> > \n> >     Benchmark 2: git for-each-ref (revision=old,refcount=medium)\n> >       Time (mean ± σ):     822.7 ms ±   2.2 ms    [User: 697.4 ms, System: 125.1 ms]\n> >       Range (min … max):   821.1 ms … 825.2 ms    3 runs\n> > \n> >     Benchmark 3: git for-each-ref (revision=old,refcount=high)\n> >       Time (mean ± σ):      1.960 s ±  0.015 s    [User: 1.702 s, System: 0.257 s]\n> >       Range (min … max):    1.944 s …  1.973 s    3 runs\n> > \n> >     # New version, which is your tip.\n> > \n> >     Benchmark 4: git for-each-ref (revision=old,refcount=huge)\n> >       Time (mean ± σ):     16.815 s ±  0.054 s    [User: 15.091 s, System: 1.722 s]\n> >       Range (min … max):   16.760 s … 16.869 s    3 runs\n> > \n> >     Benchmark 5: git for-each-ref (revision=new,refcount=small)\n> >       Time (mean ± σ):     136.0 ms ±   0.2 ms    [User: 78.8 ms, System: 57.1 ms]\n> >       Range (min … max):   135.8 ms … 136.2 ms    3 runs\n> > \n> >     Benchmark 6: git for-each-ref (revision=new,refcount=medium)\n> >       Time (mean ± σ):     830.4 ms ±  21.2 ms    [User: 691.3 ms, System: 138.7 ms]\n> >       Range (min … max):   814.2 ms … 854.5 ms    3 runs\n> > \n> >     Benchmark 7: git for-each-ref (revision=new,refcount=high)\n> >       Time (mean ± σ):      1.966 s ±  0.013 s    [User: 1.717 s, System: 0.249 s]\n> >       Range (min … max):    1.952 s …  1.978 s    3 runs\n> > \n> >     Benchmark 8: git for-each-ref (revision=new,refcount=huge)\n> >       Time (mean ± σ):     16.945 s ±  0.037 s    [User: 15.182 s, System: 1.760 s]\n> >       Range (min … max):   16.910 s … 16.983 s    3 runs\n> > \n> >     Summary\n> >       git for-each-ref (revision=old,refcount=small) ran\n> >         1.00 ± 0.01 times faster than git for-each-ref (revision=new,refcount=small)\n> >         6.07 ± 0.06 times faster than git for-each-ref (revision=old,refcount=medium)\n> >         6.13 ± 0.17 times faster than git for-each-ref (revision=new,refcount=medium)\n> >        14.46 ± 0.17 times faster than git for-each-ref (revision=old,refcount=high)\n> >        14.51 ± 0.16 times faster than git for-each-ref (revision=new,refcount=high)\n> >       124.09 ± 1.15 times faster than git for-each-ref (revision=old,refcount=huge)\n> >       125.05 ± 1.12 times faster than git for-each-ref (revision=new,refcount=huge)\n> > \n> > The performance regression isn't all that concerning, but it makes me\n> > wonder why I see things becoming slower rather than faster. My guess is\n> > that this is because all my test repositories are well-packed and don't\n> > have a lot of loose references. But I just wanted to confirm how you\n> > benchmarked your change and what the underlying shape of your test repo\n> > was.\n> \n> I ran my benchmark on my (Intel) Mac with a test repository (single commit,\n> one file) containing:\n> \n> - 10k refs/heads/ references\n> - 10k refs/tags/ references\n> - 10k refs/special/ references \n> \n> All refs in the repository are loose. My Mac has historically been somewhat\n> slow and inconsistent when it comes to perf testing, though, so I re-ran the\n> benchmark a bit more formally on an Ubuntu VM (3 warmup iterations followed\n> by at least 10 iterations per test):\n> \n> ---\n> \n> Benchmark 1: git for-each-ref (revision=old,refcount=3k)\n>   Time (mean ± σ):      40.6 ms ±   3.9 ms    [User: 13.2 ms, System: 27.1 ms]\n>   Range (min … max):    37.2 ms …  59.1 ms    76 runs\n>  \n>   Warning: Statistical outliers were detected. Consider re-running this benchmark on a quiet system without any interferences from other programs. It might help to use the '--warmup' or '--prepare' options.\n>  \n> Benchmark 2: git for-each-ref (revision=new,refcount=3k)\n>   Time (mean ± σ):      38.7 ms ±   4.4 ms    [User: 13.8 ms, System: 24.5 ms]\n>   Range (min … max):    35.1 ms …  57.2 ms    71 runs\n>  \n>   Warning: Statistical outliers were detected. Consider re-running this benchmark on a quiet system without any interferences from other programs. It might help to use the '--warmup' or '--prepare' options.\n>  \n> Benchmark 3: git for-each-ref (revision=old,refcount=30k)\n>   Time (mean ± σ):     419.4 ms ±  43.9 ms    [User: 136.4 ms, System: 274.1 ms]\n>   Range (min … max):   385.1 ms … 528.7 ms    10 runs\n>  \n> Benchmark 4: git for-each-ref (revision=new,refcount=30k)\n>   Time (mean ± σ):     390.4 ms ±  27.2 ms    [User: 133.1 ms, System: 251.6 ms]\n>   Range (min … max):   360.3 ms … 447.6 ms    10 runs\n>  \n> Benchmark 5: git for-each-ref (revision=old,refcount=300k)\n>   Time (mean ± σ):      4.171 s ±  0.052 s    [User: 1.400 s, System: 2.715 s]\n>   Range (min … max):    4.118 s …  4.283 s    10 runs\n>  \n> Benchmark 6: git for-each-ref (revision=new,refcount=300k)\n>   Time (mean ± σ):      3.939 s ±  0.054 s    [User: 1.403 s, System: 2.466 s]\n>   Range (min … max):    3.858 s …  4.026 s    10 runs\n>  \n> Summary\n>   'git for-each-ref (revision=new,refcount=3k)' ran\n>     1.05 ± 0.16 times faster than 'git for-each-ref (revision=old,refcount=3k)'\n>    10.08 ± 1.34 times faster than 'git for-each-ref (revision=new,refcount=30k)'\n>    10.83 ± 1.67 times faster than 'git for-each-ref (revision=old,refcount=30k)'\n>   101.68 ± 11.63 times faster than 'git for-each-ref (revision=new,refcount=300k)'\n>   107.67 ± 12.30 times faster than 'git for-each-ref (revision=old,refcount=300k)'\n> \n> ---\n> \n> So it's not the 20% speedup I saw on my local test repo (it's more like\n> 5-8%), but there does appear to be a consistent improvement.\n\nThanks a bunch for re-doing the benchmark with a documented setup.\n\n> As for your results, the changes in this series shouldn't affect\n> packed ref operations, and the difference between old & new doesn't\n> seem to indicate a regression. \n\nYeah, I've also been surprised to see the performance regression for\npacked-refs files. The regression is persistent and reproducable on my\nmachine though, so even though I tend to agree that the patches\nshouldn't negatively impact packed-refs performance they somehow do. It\ncould just as well be something like different optimization choices by\nthe compler due to the added patches, or hitting different cache lines.\nI dunno.\n\nAnyway, I agree with your assessment. The regression I see is less than\n1% for packed-refs, while the improvements for loose refs are a lot more\nsignificant and conceptually make a lot of sense. So I didn't intend to\nsay that we shouldn't do these optimizations because of the miniscule\npeformance regression with packed-refs.\n\nOr in other words: this series looks good to me.\n\nThanks!\nPatrick\n"}]}