Performance improvement & cleanup in loose ref iteration
cover Performance improvement & cleanup in loose ref iteration
While investigating ref iteration performance in builtins like 'for-each-ref' and 'show-ref', I found two small improvement opportunities.
The first patch tweaks the logic around prefix matching in 'cache_ref_iterator_advance' so that we correctly skip refs that do not actually match a given prefix. The unnecessary iteration doesn't seem to be causing any bugs in the ref iteration commands that I've tested, but it doesn't hurt to be more precise (and it helps with some other patches I'm working on ;) ).
The next three patches update how 'loose_fill_ref_dir' determines the type of ref cache entry to create (directory or regular). On platforms that include d_type information in 'struct dirent' (as far as I can tell, all except NonStop & certain versions of Cygwin), this allows us to skip calling 'stat'. In ad-hoc testing, this improved performance of 'git for-each-ref' by about 20%.
Thanks!
* Victoria
Victoria Dye (4):
ref-cache.c: fix prefix matching in ref iteration dir.[ch]: expose 'get_dtype'
dir.[ch]: add 'follow_symlink' arg to 'get_dtype' files-backend.c: avoid stat in 'loose_fill_ref_dir'
diagnose.c | 42 +++--------------------------------------- dir.c | 33 +++++++++++++++++++++++++++++++++ dir.h | 16 ++++++++++++++++ refs/files-backend.c | 14 +++++--------- refs/ref-cache.c | 3 ++- 5 files changed, 59 insertions(+), 49 deletions(-)
base-commit: 3a06386e314565108ad56a9bdb8f7b80ac52fb69
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1594%2Fvdye%2Fvdye%2Fref-iteration-cleanup-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1594/vdye/vdye/ref-iteration-cleanup-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1594
Signature · 1 line
gitgitgadget
PATCH 1/4 ref-cache.c: fix prefix matching in ref iteration
From: Victoria Dye <[email protected]>
Update 'cache_ref_iterator_advance' to skip over refs that are not matched by the given prefix.
Currently, a ref entry is considered "matched" if the entry name is fully contained within the prefix:
* prefix: "refs/heads/v1"
* entry: "refs/heads/v1.0"
OR if the prefix is fully contained in the entry name:
* prefix: "refs/heads/v1.0"
* entry: "refs/heads/v1"
The first case is always correct, but the second is only correct if the ref cache entry is a directory, for example:
* prefix: "refs/heads/example"
* entry: "refs/heads/"
Modify the logic in 'cache_ref_iterator_advance' to reflect these expectations:
1. If 'overlaps_prefix' returns 'PREFIX_EXCLUDES_DIR', then the prefix and ref cache entry do not overlap at all. Skip this entry.
2. If 'overlaps_prefix' returns 'PREFIX_WITHIN_DIR', then the prefix matches inside this entry if it is a directory. Skip if the entry is not a directory, otherwise iterate over it.
3. Otherwise, 'overlaps_prefix' returned 'PREFIX_CONTAINS_DIR', indicating that the cache entry (directory or not) is fully contained by or equal to the prefix. Iterate over this entry.
Note that condition 2 relies on the names of directory entries having the appropriate trailing slash. The existing function documentation of 'create_dir_entry' explicitly calls out the trailing slash requirement, so this is a safe assumption to make.
--- refs/ref-cache.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
refs/ref-cache.c +2 -1
@@ -412,7 +412,8 @@ static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)if (level->prefix_state ==PREFIX_WITHIN_DIR ) { entry_prefix_state =overlaps_prefix (entry->name, iter->prefix); -if (entry_prefix_state ==PREFIX_EXCLUDES_DIR ) +if (entry_prefix_state ==PREFIX_EXCLUDES_DIR || + (entry_prefix_state ==PREFIX_WITHIN_DIR && !(entry->flag &REF_DIR )))continue ; }else { entry_prefix_state = level->prefix_state;
Signature · 1 line
gitgitgadget
Re: [PATCH 1/4] ref-cache.c: fix prefix matching in ref iteration
Quoted 34 lines · Victoria Dye via GitGitGadget
From: Victoria Dye <[email protected]>
Update '
cache_ref_iterator_advance' to skip over refs that are not matched by the given prefix.Currently, a ref entry is considered "matched" if the entry name is fully contained within the prefix:
* prefix: "refs/heads/v1"
* entry: "refs/heads/v1.0"OR if the prefix is fully contained in the entry name:
* prefix: "refs/heads/v1.0"
* entry: "refs/heads/v1"The first case is always correct, but the second is only correct if the ref cache entry is a directory, for example:
* prefix: "refs/heads/example"
* entry: "refs/heads/"Modify the logic in '
cache_ref_iterator_advance' to reflect these expectations:1. If '
overlaps_prefix' returns 'PREFIX_EXCLUDES_DIR', then the prefix and ref cache entry do not overlap at all. Skip this entry.
2. If 'overlaps_prefix' returns 'PREFIX_WITHIN_DIR', then the prefix matches inside this entry if it is a directory. Skip if the entry is not a directory, otherwise iterate over it.
3. Otherwise, 'overlaps_prefix' returned 'PREFIX_CONTAINS_DIR', indicating that the cache entry (directory or not) is fully contained by or equal to the prefix. Iterate over this entry.
Quoted 4 lines
Note that condition 2 relies on the names of directory entries having the appropriate trailing slash. The existing function documentation of '
create_dir_entry' explicitly calls out the trailing slash requirement, so this is a safe assumption to make.
Thanks for explaining it very well and clearly.
Allowing prefix="refs/heads/v1.0" to yield entry="refs/heads/v1" (case #2 above that this patch fixes the behaviour for) would cause ref_iterator_advance() to return a ref outside the hierarhcy, wouldn't it? So it appears to me that either one of the two would be true:
* the code is structured in such a way that such a condition does not actually happen (in which case this patch would be a no-op), or
* there is a bug in the current code that is fixed by this patch, whose externally observable behaviour can be verified with a test.
It is not quite clear to me which is the case here. The code with the patch looks more logical than the original, but I am not sure how to demonstrate the existing breakage (if any).
Quoted 19 lines
Signed-off-by Victoria Dye <[email protected]>--- refs/ref-cache.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)refs/ref-cache.c +2
-1@@ -412,7 +412,8 @@ static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)if (level->prefix_state ==PREFIX_WITHIN_DIR ) { entry_prefix_state =overlaps_prefix (entry->name, iter->prefix); -if (entry_prefix_state ==PREFIX_EXCLUDES_DIR ) +if (entry_prefix_state ==PREFIX_EXCLUDES_DIR || + (entry_prefix_state ==PREFIX_WITHIN_DIR && !(entry->flag &REF_DIR )))continue ; }else { entry_prefix_state = level->prefix_state;
Re: [PATCH 1/4] ref-cache.c: fix prefix matching in ref iteration
Quoted 53 lines · Junio C Hamano
Quoted 34 lines · Victoria Dye via GitGitGadget
From: Victoria Dye <[email protected]>
Update '
cache_ref_iterator_advance' to skip over refs that are not matched by the given prefix.Currently, a ref entry is considered "matched" if the entry name is fully contained within the prefix:
* prefix: "refs/heads/v1"
* entry: "refs/heads/v1.0"OR if the prefix is fully contained in the entry name:
* prefix: "refs/heads/v1.0"
* entry: "refs/heads/v1"The first case is always correct, but the second is only correct if the ref cache entry is a directory, for example:
* prefix: "refs/heads/example"
* entry: "refs/heads/"Modify the logic in '
cache_ref_iterator_advance' to reflect these expectations:1. If '
overlaps_prefix' returns 'PREFIX_EXCLUDES_DIR', then the prefix and ref cache entry do not overlap at all. Skip this entry.
2. If 'overlaps_prefix' returns 'PREFIX_WITHIN_DIR', then the prefix matches inside this entry if it is a directory. Skip if the entry is not a directory, otherwise iterate over it.
3. Otherwise, 'overlaps_prefix' returned 'PREFIX_CONTAINS_DIR', indicating that the cache entry (directory or not) is fully contained by or equal to the prefix. Iterate over this entry.Quoted 4 lines
Note that condition 2 relies on the names of directory entries having the appropriate trailing slash. The existing function documentation of '
create_dir_entry' explicitly calls out the trailing slash requirement, so this is a safe assumption to make.Thanks for explaining it very well and clearly.
Allowing prefix="refs/heads/v1.0" to yield entry="refs/heads/v1" (case #2 above that this patch fixes the behaviour for) would cause
ref_iterator_advance()to return a ref outside the hierarhcy, wouldn't it? So it appears to me that either one of the two would be true:* the code is structured in such a way that such a condition does not actually happen (in which case this patch would be a no-op), or
Quoted 7 lines
* there is a bug in the current code that is fixed by this patch, whose externally observable behaviour can be verified with a test.
It is not quite clear to me which is the case here. The code with the patch looks more logical than the original, but I am not sure how to demonstrate the existing breakage (if any).
Agreed, I also had a bit of a hard time to figure out whether this is an actual bug fix, a performance improvement or merely a refactoring.
Patrick
Quoted 19 lines
Quoted 19 lines
Signed-off-by Victoria Dye <[email protected]>--- refs/ref-cache.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)refs/ref-cache.c +2
-1@@ -412,7 +412,8 @@ static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)if (level->prefix_state ==PREFIX_WITHIN_DIR ) { entry_prefix_state =overlaps_prefix (entry->name, iter->prefix); -if (entry_prefix_state ==PREFIX_EXCLUDES_DIR ) +if (entry_prefix_state ==PREFIX_EXCLUDES_DIR || + (entry_prefix_state ==PREFIX_WITHIN_DIR && !(entry->flag &REF_DIR )))continue ; }else { entry_prefix_state = level->prefix_state;
Re: [PATCH 1/4] ref-cache.c: fix prefix matching in ref iteration
Quoted 14 lines · Patrick Steinhardt
Quoted 14 lines
Allowing prefix="refs/heads/v1.0" to yield entry="refs/heads/v1" (case #2 above that this patch fixes the behaviour for) would cause
ref_iterator_advance()to return a ref outside the hierarhcy, wouldn't it? So it appears to me that either one of the two would be true:* the code is structured in such a way that such a condition does not actually happen (in which case this patch would be a no-op), or
* there is a bug in the current code that is fixed by this patch, whose externally observable behaviour can be verified with a test.
Quoted 7 lines
Quoted 3 lines
It is not quite clear to me which is the case here. The code with the patch looks more logical than the original, but I am not sure how to demonstrate the existing breakage (if any).
Agreed, I also had a bit of a hard time to figure out whether this is an actual bug fix, a performance improvement or merely a refactoring.
I originally operated on the assumption that it was the first case, which is why I didn't include a test in this patch. Commands like 'for-each-ref', 'show-ref', etc. either use an empty prefix or a directory prefix with a trailing slash, which won't trigger this issue. I encountered the problem while working on a builtin that filtered refs by a user-specified prefix - the results included refs that should not have been matched, which led me to this fix.
Scanning through the codebase again, though, I do see a way to replicate the issue:
$ git update-ref refs/bisect/b HEAD $ git rev-parse --abbrev-ref --bisect refs/bisect/b
Because 'rev-parse --bisect' uses the "refs/bisect/bad" prefix (no trailing slash) and does no additional filtering in its 'for_each_fullref_in' callback, refs like "refs/bisect/b" and "refs/bisect/ba" are (incorrectly) matched. I'll re-roll with the added test.
Re: [PATCH 1/4] ref-cache.c: fix prefix matching in ref iteration
Quoted 4 lines · Victoria Dye
I originally operated on the assumption that it was the first case, which is why I didn't include a test in this patch. Commands like 'for-each-ref', 'show-ref', etc. either use an empty prefix or a directory prefix with a trailing slash, which won't trigger this issue.
Ah, yes, I didn't mention it but I suspected as such (i.e. the code is structured in such a way that this broken implementation does not matter to the current callers).
Quoted 4 lines
I encountered the problem
while working on a builtin that filtered refs by a user-specified prefix - the results included refs that should not have been matched, which led me to this fix.
OK, perfectly understandable.
Quoted 11 lines
Scanning through the codebase again, though, I do see a way to replicate the issue:
$ git update-ref refs/bisect/b HEAD $ git rev-parse --abbrev-ref --bisect refs/bisect/bBecause 'rev-parse --bisect' uses the "refs/bisect/bad" prefix (no trailing slash) and does no additional filtering in its '
for_each_fullref_in' callback, refs like "refs/bisect/b" and "refs/bisect/ba" are (incorrectly) matched. I'll re-roll with the added test.
Good find. Thanks!
PATCH 2/4 dir.[ch]: expose 'get_dtype'
In reply to Victoria Dye via GitGitGadgetFrom: Victoria Dye <[email protected]>
Move 'get_dtype()' from 'diagnose.c' to 'dir.c' and add its declaration to 'dir.h' so that it is accessible to callers in other files. The function and its documentation are moved verbatim except for a small addition to the description clarifying what the 'path' arg represents.
--- diagnose.c | 36 ------------------------------------ dir.c | 28 ++++++++++++++++++++++++++++ dir.h | 11 +++++++++++ 3 files changed, 39 insertions(+), 36 deletions(-)
diagnose.c +0 -36
@@ -71,42 +71,6 @@ static int dir_file_stats(struct object_directory *object_dir, void *data)return 0 ; } -/* -* Get the d_type of a dirent. If the d_type is unknown, derive it from -* stat.st_mode. -* -* Note that 'path' is assumed to have a trailing slash. It is also modified -* in-place during the execution of the function, but is then reverted to its -* original value before returning. -*/ -static unsigned char get_dtype (struct dirent *e,struct strbuf *path) -{ -struct stat st; -unsigned char dtype =DTYPE (e); -size_t base_path_len; - -if (dtype !=DT_UNKNOWN ) -return dtype; - -/* d_type unknown in dirent, try to fall back on lstat results */ - base_path_len = path->len; -strbuf_addstr (path, e->d_name); -if (lstat (path->buf, &st)) - goto cleanup; - -/* determine d_type from st_mode */ -if (S_ISREG (st.st_mode)) - dtype =DT_REG ; -else if (S_ISDIR (st.st_mode)) - dtype =DT_DIR ; -else if (S_ISLNK (st.st_mode)) - dtype =DT_LNK ; - -cleanup: -strbuf_setlen (path, base_path_len); -return dtype; -} -static int count_files (struct strbuf *path) {DIR *dir =opendir (path->buf);
dir.c +28 -0
@@ -2235,6 +2235,34 @@ static int get_index_dtype(struct index_state *istate,return DT_UNKNOWN ; } +unsigned char get_dtype (struct dirent *e,struct strbuf *path) +{ +struct stat st; +unsigned char dtype =DTYPE (e); +size_t base_path_len; + +if (dtype !=DT_UNKNOWN ) +return dtype; + +/* d_type unknown in dirent, try to fall back on lstat results */ + base_path_len = path->len; +strbuf_addstr (path, e->d_name); +if (lstat (path->buf, &st)) + goto cleanup; + +/* determine d_type from st_mode */ +if (S_ISREG (st.st_mode)) + dtype =DT_REG ; +else if (S_ISDIR (st.st_mode)) + dtype =DT_DIR ; +else if (S_ISLNK (st.st_mode)) + dtype =DT_LNK ; + +cleanup: +strbuf_setlen (path, base_path_len); +return dtype; +} +static int resolve_dtype (int dtype,struct index_state *istate,const char *path,int len) {
dir.h +11 -0
@@ -363,6 +363,17 @@ struct dir_struct {struct dirent *readdir_skip_dot_and_dotdot (DIR *dirp); +/* +* Get the d_type of a dirent. If the d_type is unknown, derive it from +* stat.st_mode using the path to the dirent's containing directory (path) and +* the name of the dirent itself. +* +* Note that 'path' is assumed to have a trailing slash. It is also modified +* in-place during the execution of the function, but is then reverted to its +* original value before returning. +*/ +unsigned char get_dtype (struct dirent *e,struct strbuf *path); +/*Count the number of slashes for string s*/ int count_slashes (const char *s);
Signature · 1 line
gitgitgadget
Re: [PATCH 2/4] dir.[ch]: expose 'get_dtype'
Quoted 7 lines · Victoria Dye via GitGitGadget
From: Victoria Dye <[email protected]>
Move '
get_dtype()' from 'diagnose.c' to 'dir.c' and add its declaration to 'dir.h' so that it is accessible to callers in other files. The function and its documentation are moved verbatim except for a small addition to the description clarifying what the 'path' arg represents.
Quoted 6 lines
Signed-off-by Victoria Dye <[email protected]>--- diagnose.c | 36 ------------------------------------ dir.c | 28 ++++++++++++++++++++++++++++ dir.h | 11 +++++++++++ 3 files changed, 39 insertions(+), 36 deletions(-)
OK. diagnose.c should still have access to the function as it includes <dir.h>, and to anybody that includes <dir.h> and sees the declaration of get_dtype(), DT_FOO should be visible because <dir.h> includes <statinfo.h> that has fallback definition of DT_FOO.
Looking simple and straight-forward.
Quoted 107 lines
diagnose.c +0
-36@@ -71,42 +71,6 @@ static int dir_file_stats(struct object_directory *object_dir, void *data)return 0 ; } -/* -* Get the d_type of a dirent. If the d_type is unknown, derive it from -* stat.st_mode. -* -* Note that 'path' is assumed to have a trailing slash. It is also modified -* in-place during the execution of the function, but is then reverted to its -* original value before returning. -*/ -static unsigned char get_dtype (struct dirent *e,struct strbuf *path) -{ -struct stat st; -unsigned char dtype =DTYPE (e); -size_t base_path_len; - -if (dtype !=DT_UNKNOWN ) -return dtype; - -/* d_type unknown in dirent, try to fall back on lstat results */ - base_path_len = path->len; -strbuf_addstr (path, e->d_name); -if (lstat (path->buf, &st)) - goto cleanup; - -/* determine d_type from st_mode */ -if (S_ISREG (st.st_mode)) - dtype =DT_REG ; -else if (S_ISDIR (st.st_mode)) - dtype =DT_DIR ; -else if (S_ISLNK (st.st_mode)) - dtype =DT_LNK ; - -cleanup: -strbuf_setlen (path, base_path_len); -return dtype; -} -static int count_files (struct strbuf *path) {DIR *dir =opendir (path->buf);dir.c +28
-0@@ -2235,6 +2235,34 @@ static int get_index_dtype(struct index_state *istate,return DT_UNKNOWN ; } +unsigned char get_dtype (struct dirent *e,struct strbuf *path) +{ +struct stat st; +unsigned char dtype =DTYPE (e); +size_t base_path_len; + +if (dtype !=DT_UNKNOWN ) +return dtype; + +/* d_type unknown in dirent, try to fall back on lstat results */ + base_path_len = path->len; +strbuf_addstr (path, e->d_name); +if (lstat (path->buf, &st)) + goto cleanup; + +/* determine d_type from st_mode */ +if (S_ISREG (st.st_mode)) + dtype =DT_REG ; +else if (S_ISDIR (st.st_mode)) + dtype =DT_DIR ; +else if (S_ISLNK (st.st_mode)) + dtype =DT_LNK ; + +cleanup: +strbuf_setlen (path, base_path_len); +return dtype; +} +static int resolve_dtype (int dtype,struct index_state *istate,const char *path,int len) {dir.h +11
-0@@ -363,6 +363,17 @@ struct dir_struct {struct dirent *readdir_skip_dot_and_dotdot (DIR *dirp); +/* +* Get the d_type of a dirent. If the d_type is unknown, derive it from +* stat.st_mode using the path to the dirent's containing directory (path) and +* the name of the dirent itself. +* +* Note that 'path' is assumed to have a trailing slash. It is also modified +* in-place during the execution of the function, but is then reverted to its +* original value before returning. +*/ +unsigned char get_dtype (struct dirent *e,struct strbuf *path); +/*Count the number of slashes for string s*/ int count_slashes (const char *s);
PATCH 3/4 dir.[ch]: add 'follow_symlink' arg to 'get_dtype'
In reply to Victoria Dye via GitGitGadgetFrom: Victoria Dye <[email protected]>
Add a 'follow_symlink' boolean option to 'get_type()'. If 'follow_symlink' is enabled, DT_LNK (in addition to DT_UNKNOWN) d_types triggers the stat-based d_type resolution, using 'stat' instead of 'lstat' to get the type of the followed symlink. Note that symlinks are not followed recursively, so a symlink pointing to another symlink will still resolve to DT_LNK.
Update callers in 'diagnose.c' to specify 'follow_symlink = 0' to preserve current behavior.
--- diagnose.c | 6 +++--- dir.c | 13 +++++++++---- dir.h | 7 ++++++- 3 files changed, 18 insertions(+), 8 deletions(-)
diagnose.c +3 -3
@@ -81,7 +81,7 @@ static int count_files(struct strbuf *path)return 0 ;while ((e =readdir_skip_dot_and_dotdot (dir)) !=NULL ) -if (get_dtype (e, path) ==DT_REG ) +if (get_dtype (e, path,0 ) ==DT_REG ) count++;closedir (dir);
@@ -110,7 +110,7 @@ static void loose_objs_stats(struct strbuf *buf, const char *path) base_path_len = count_path.len;while ((e =readdir_skip_dot_and_dotdot (dir)) !=NULL ) -if (get_dtype (e, &count_path) ==DT_DIR && +if (get_dtype (e, &count_path,0 ) ==DT_DIR &&strlen (e->d_name) ==2 && !hex_to_bytes (&c, e->d_name,1 )) {strbuf_setlen (&count_path, base_path_len);
@@ -155,7 +155,7 @@ static int add_directory_to_archiver(struct strvec *archiver_args,strbuf_add_absolute_path (&abspath, at_root ?"." : path);strbuf_addch (&abspath,'/' ); - dtype =get_dtype (e, &abspath); + dtype =get_dtype (e, &abspath,0 );strbuf_setlen (&buf, len);strbuf_addstr (&buf, e->d_name);
dir.c +9 -4
@@ -2235,19 +2235,24 @@ static int get_index_dtype(struct index_state *istate,return DT_UNKNOWN ; } -unsigned char get_dtype (struct dirent *e,struct strbuf *path) +unsigned char get_dtype (struct dirent *e,struct strbuf *path, +int follow_symlink) {struct stat st;unsigned char dtype =DTYPE (e);size_t base_path_len; -if (dtype !=DT_UNKNOWN ) +if (dtype !=DT_UNKNOWN && !(follow_symlink && dtype ==DT_LNK ))return dtype; -/* d_type unknown in dirent, try to fall back on lstat results */ +/* +* d_type unknown or unfollowed symlink, try to fall back on [l]stat +* results. If [l]stat fails, explicitly set DT_UNKNOWN. +*/ base_path_len = path->len;strbuf_addstr (path, e->d_name); -if (lstat (path->buf, &st)) +if ((follow_symlink &&stat (path->buf, &st)) || + (!follow_symlink &&lstat (path->buf, &st))) goto cleanup;/* determine d_type from st_mode */
dir.h +6 -1
@@ -368,11 +368,16 @@ struct dirent *readdir_skip_dot_and_dotdot(DIR *dirp);* stat.st_mode using the path to the dirent's containing directory (path) and * the name of the dirent itself. * +* If 'follow_symlink' is 1, this function will attempt to follow DT_LNK types +* using 'stat'. Links are *not* followed recursively, so a symlink pointing +* to another symlink will still resolve to 'DT_LNK'. +* * Note that 'path' is assumed to have a trailing slash. It is also modified * in-place during the execution of the function, but is then reverted to its * original value before returning. */ -unsigned char get_dtype (struct dirent *e,struct strbuf *path); +unsigned char get_dtype (struct dirent *e,struct strbuf *path, +int follow_symlink);/*Count the number of slashes for string s*/ int count_slashes (const char *s);
Signature · 1 line
gitgitgadget
PATCH 4/4 files-backend.c: avoid stat in 'loose_fill_ref_dir'
In reply to Victoria Dye via GitGitGadgetFrom: Victoria Dye <[email protected]>
Modify the 'readdir' loop in 'loose_fill_ref_dir' to, rather than 'stat' a file to determine whether it is a directory or not, use 'get_dtype'.
Currently, the loop uses 'stat' to determine whether each dirent is a directory itself or not in order to construct the appropriate ref cache entry. If 'stat' fails (returning a negative value), the dirent is silently skipped; otherwise, 'S_ISDIR(st.st_mode)' is used to check whether the entry is a directory.
On platforms that include an entry's d_type in in the 'dirent' struct, this extra 'stat' check is redundant. We can use the 'get_dtype' method to extract this information on platforms that support it (i.e. where NO_D_TYPE_IN_DIRENT is unset), and derive it with 'stat' on platforms that don't. Because 'stat' is an expensive call, this confers a modest-but-noticeable performance improvement when iterating over large numbers of refs (approximately 20% speedup in 'git for-each-ref' in a 30k ref repo).
Unlike other existing usage of 'get_dtype', the 'follow_symlinks' arg is set to 1 to replicate the existing handling of symlink dirents. This unfortunately requires calling 'stat' on the associated entry regardless of platform, but symlinks in the loose ref store are highly unlikely since they'd need to be created manually by a user.
Note that this patch also changes the condition for skipping creation of a ref entry from "when 'stat' fails" to "when the d_type is anything other than DT_REG or DT_DIR". If a dirent's d_type is DT_UNKNOWN (either because the platform doesn't support d_type in dirents or some other reason) or DT_LNK, 'get_dtype' will try to derive the underlying type with 'stat'. If the 'stat' fails, the d_type will remain 'DT_UNKNOWN' and dirent will be skipped. However, it will also be skipped if it is any other valid d_type (e.g. DT_FIFO for named pipes, DT_LNK for a nested symlink). Git does not handle these properly anyway, so we can safely constrain accepted types to directories and regular files.
--- refs/files-backend.c | 14 +++++--------- 1 file changed, 5 insertions(+), 9 deletions(-)
refs/files-backend.c +5 -9
@@ -246,10 +246,8 @@ static void loose_fill_ref_dir(struct ref_store *ref_store,int dirnamelen =strlen (dirname);struct strbuf refname;struct strbuf path =STRBUF_INIT ; -size_t path_baselen;files_ref_path (refs, &path, dirname); - path_baselen = path.len; d =opendir (path.buf);if (!d) {
@@ -262,23 +260,22 @@ static void loose_fill_ref_dir(struct ref_store *ref_store, while ((de = readdir(d)) != NULL) { struct object_id oid; - struct stat st; int flag; + unsigned char dtype; if (de->d_name[0] == '.') continue; if (ends_with(de->d_name, ".lock")) continue; strbuf_addstr(&refname, de->d_name); - strbuf_addstr(&path, de->d_name); - if (stat(path.buf, &st) < 0) { - ; /* silently ignore */ - } else if (S_ISDIR(st.st_mode)) { + + dtype = get_dtype(de, &path, 1); + if (dtype == DT_DIR) { strbuf_addch(&refname, '/'); add_entry_to_dir(dir, create_dir_entry(dir->cache, refname.buf, refname.len)); - } else { + } else if (dtype == DT_REG) { if (!refs_resolve_ref_unsafe(&refs->base, refname.buf, RESOLVE_REF_READING,
@@ -308,7 +305,6 @@ static void loose_fill_ref_dir(struct ref_store *ref_store, create_ref_entry(refname.buf, &oid, flag)); }strbuf_setlen (&refname, dirnamelen); -strbuf_setlen (&path, path_baselen); }strbuf_release (&refname);strbuf_release (&path);
Signature · 1 line
gitgitgadget
Re: [PATCH 4/4] files-backend.c: avoid stat in 'loose_fill_ref_dir'
Quoted 5 lines · Victoria Dye via GitGitGadget
Unlike other existing usage of '
get_dtype', the 'follow_symlinks' arg is set to 1 to replicate the existing handling of symlink dirents. This unfortunately requires calling 'stat' on the associated entry regardless of platform, but symlinks in the loose ref store are highly unlikely since they'd need to be created manually by a user.
Yeek. I wonder what breaks if we do not do this follow_symlinks() part, i.e., either just replace stat() with lstat() in the original without any of these four patches (which would be simple to figure out what breaks), or omit [3/4] and let get_dtype() yield DT_LNK.
It seems that it comes from a7e66ae3 ([PATCH] Make do_each_ref() follow symlinks., 2005-08-16), and just like I commented on there in its log message back then, I still doubt that following a symbolic link is a great idea here in this codepath.
But optimization without behaviour change is a good way to ensure that optimization does not introduce new bugs, and because keeping the historical behaviour like the patches [3/4] and this patch does is more work (meaning: if it proves unnecessary to dereference symbolic links, we can remove code instead of having to write new code to support the new behaviour), let's take the series as-is, and defer it to future developers to further clean-up the semantics.
Quoted 10 lines
Note that this patch also changes the condition for skipping creation of a ref entry from "when 'stat' fails" to "when the
d_typeis anything other thanDT_REGorDT_DIR". If a dirent'sd_typeisDT_UNKNOWN(either because the platform doesn't supportd_typein dirents or some other reason) orDT_LNK, 'get_dtype' will try to derive the underlying type with 'stat'. If the 'stat' fails, thed_typewill remain 'DT_UNKNOWN' and dirent will be skipped. However, it will also be skipped if it is any other validd_type(e.g.DT_FIFOfor named pipes,DT_LNKfor a nested symlink). Git does not handle these properly anyway, so we can safely constrain accepted types to directories and regular files.
Sounds good.
Quoted 4 lines
Signed-off-by Victoria Dye <[email protected]>--- refs/files-backend.c | 14 +++++--------- 1 file changed, 5 insertions(+), 9 deletions(-)
Thanks.
Quoted 10 lines · Victoria Dye via GitGitGadget
While investigating ref iteration performance in builtins like 'for-each-ref' and 'show-ref', I found two small improvement opportunities.
The first patch tweaks the logic around prefix matching in '
cache_ref_iterator_advance' so that we correctly skip refs that do not actually match a given prefix. The unnecessary iteration doesn't seem to be causing any bugs in the ref iteration commands that I've tested, but it doesn't hurt to be more precise (and it helps with some other patches I'm working on ;) ).
Quoted 6 lines
The next three patches update how '
loose_fill_ref_dir' determines the type of ref cache entry to create (directory or regular). On platforms that included_typeinformation in 'struct dirent' (as far as I can tell, all except NonStop & certain versions of Cygwin), this allows us to skip calling 'stat'. In ad-hoc testing, this improved performance of 'git for-each-ref' by about 20%.
Yay. That is a very obvious one, once it is pointed out. Thanks for noticing and improving. Looking forward to reading the patches themselves.
Quoted 10 lines · Victoria Dye via GitGitGadget
While investigating ref iteration performance in builtins like 'for-each-ref' and 'show-ref', I found two small improvement opportunities.
The first patch tweaks the logic around prefix matching in '
cache_ref_iterator_advance' so that we correctly skip refs that do not actually match a given prefix. The unnecessary iteration doesn't seem to be causing any bugs in the ref iteration commands that I've tested, but it doesn't hurt to be more precise (and it helps with some other patches I'm working on ;) ).
Quoted 6 lines
The next three patches update how '
loose_fill_ref_dir' determines the type of ref cache entry to create (directory or regular). On platforms that included_typeinformation in 'struct dirent' (as far as I can tell, all except NonStop & certain versions of Cygwin), this allows us to skip calling 'stat'. In ad-hoc testing, this improved performance of 'git for-each-ref' by about 20%.
I've done a small set of benchmarks with my usual test repositories, which is linux.git with a bunch of references added. The repository comes in four sizes:
- small: 50k references
- medium: 500k references
- high: 1.1m references
- huge: 12m references
Unfortunately, I couldn't really reproduce the performance improvements. In fact, the new version runs consistently a tiny bit slower than the old version:
# Old version, which is 3a06386e31 (The fifteenth batch, 2023-10-04).
Benchmark 1: git for-each-ref (revision=old,refcount=small)
Time (mean ± σ): 135.5 ms ± 1.2 ms [User: 76.4 ms, System: 59.0 ms]
Range (min … max): 134.8 ms … 136.9 ms 3 runs
Benchmark 2: git for-each-ref (revision=old,refcount=medium)
Time (mean ± σ): 822.7 ms ± 2.2 ms [User: 697.4 ms, System: 125.1 ms]
Range (min … max): 821.1 ms … 825.2 ms 3 runs
Benchmark 3: git for-each-ref (revision=old,refcount=high)
Time (mean ± σ): 1.960 s ± 0.015 s [User: 1.702 s, System: 0.257 s]
Range (min … max): 1.944 s … 1.973 s 3 runs
# New version, which is your tip.
Benchmark 4: git for-each-ref (revision=old,refcount=huge)
Time (mean ± σ): 16.815 s ± 0.054 s [User: 15.091 s, System: 1.722 s]
Range (min … max): 16.760 s … 16.869 s 3 runs
Benchmark 5: git for-each-ref (revision=new,refcount=small)
Time (mean ± σ): 136.0 ms ± 0.2 ms [User: 78.8 ms, System: 57.1 ms]
Range (min … max): 135.8 ms … 136.2 ms 3 runs
Benchmark 6: git for-each-ref (revision=new,refcount=medium)
Time (mean ± σ): 830.4 ms ± 21.2 ms [User: 691.3 ms, System: 138.7 ms]
Range (min … max): 814.2 ms … 854.5 ms 3 runs
Benchmark 7: git for-each-ref (revision=new,refcount=high)
Time (mean ± σ): 1.966 s ± 0.013 s [User: 1.717 s, System: 0.249 s]
Range (min … max): 1.952 s … 1.978 s 3 runs
Benchmark 8: git for-each-ref (revision=new,refcount=huge)
Time (mean ± σ): 16.945 s ± 0.037 s [User: 15.182 s, System: 1.760 s]
Range (min … max): 16.910 s … 16.983 s 3 runs
Summary
git for-each-ref (revision=old,refcount=small) ran
1.00 ± 0.01 times faster than git for-each-ref (revision=new,refcount=small) 6.07 ± 0.06 times faster than git for-each-ref (revision=old,refcount=medium) 6.13 ± 0.17 times faster than git for-each-ref (revision=new,refcount=medium)
14.46 ± 0.17 times faster than git for-each-ref (revision=old,refcount=high) 14.51 ± 0.16 times faster than git for-each-ref (revision=new,refcount=high)
124.09 ± 1.15 times faster than git for-each-ref (revision=old,refcount=huge) 125.05 ± 1.12 times faster than git for-each-ref (revision=new,refcount=huge)
The performance regression isn't all that concerning, but it makes me wonder why I see things becoming slower rather than faster. My guess is that this is because all my test repositories are well-packed and don't have a lot of loose references. But I just wanted to confirm how you benchmarked your change and what the underlying shape of your test repo was.
Patrick
Quoted 24 lines
Thanks!
* Victoria
Victoria Dye (4):
ref-cache.c: fix prefix matching in ref iteration dir.[ch]: expose 'get_dtype'
dir.[ch]: add 'follow_symlink' arg to 'get_dtype'files-backend.c: avoid stat in 'loose_fill_ref_dir'diagnose.c | 42 +++--------------------------------------- dir.c | 33 +++++++++++++++++++++++++++++++++ dir.h | 16 ++++++++++++++++ refs/files-backend.c | 14 +++++--------- refs/ref-cache.c | 3 ++- 5 files changed, 59 insertions(+), 49 deletions(-)base-commit:
3a06386e314565108ad56a9bdb8f7b80ac52fb69
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1594%2Fvdye%2Fvdye%2Fref-iteration-cleanup-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1594/vdye/vdye/ref-iteration-cleanup-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1594Signature · 1 line
gitgitgadget
Quoted 77 lines · Patrick Steinhardt
Quoted 10 lines · Victoria Dye via GitGitGadget
While investigating ref iteration performance in builtins like 'for-each-ref' and 'show-ref', I found two small improvement opportunities.
The first patch tweaks the logic around prefix matching in '
cache_ref_iterator_advance' so that we correctly skip refs that do not actually match a given prefix. The unnecessary iteration doesn't seem to be causing any bugs in the ref iteration commands that I've tested, but it doesn't hurt to be more precise (and it helps with some other patches I'm working on ;) ).Quoted 6 lines
The next three patches update how '
loose_fill_ref_dir' determines the type of ref cache entry to create (directory or regular). On platforms that included_typeinformation in 'struct dirent' (as far as I can tell, all except NonStop & certain versions of Cygwin), this allows us to skip calling 'stat'. In ad-hoc testing, this improved performance of 'git for-each-ref' by about 20%.I've done a small set of benchmarks with my usual test repositories, which is linux.git with a bunch of references added. The repository comes in four sizes:
- small: 50k references
- medium: 500k references
- high: 1.1m references
- huge: 12m referencesUnfortunately, I couldn't really reproduce the performance improvements. In fact, the new version runs consistently a tiny bit slower than the old version:
# Old version, which is
3a06386e31(The fifteenth batch, 2023-10-04).Benchmark 1: git for-each-ref (revision=old,refcount=small)
Time (mean ± σ): 135.5 ms ± 1.2 ms [User: 76.4 ms, System: 59.0 ms]
Range (min … max): 134.8 ms … 136.9 ms 3 runsBenchmark 2: git for-each-ref (revision=old,refcount=medium)
Time (mean ± σ): 822.7 ms ± 2.2 ms [User: 697.4 ms, System: 125.1 ms]
Range (min … max): 821.1 ms … 825.2 ms 3 runsBenchmark 3: git for-each-ref (revision=old,refcount=high)
Time (mean ± σ): 1.960 s ± 0.015 s [User: 1.702 s, System: 0.257 s]
Range (min … max): 1.944 s … 1.973 s 3 runs# New version, which is your tip.
Benchmark 4: git for-each-ref (revision=old,refcount=huge)
Time (mean ± σ): 16.815 s ± 0.054 s [User: 15.091 s, System: 1.722 s]
Range (min … max): 16.760 s … 16.869 s 3 runsBenchmark 5: git for-each-ref (revision=new,refcount=small)
Time (mean ± σ): 136.0 ms ± 0.2 ms [User: 78.8 ms, System: 57.1 ms]
Range (min … max): 135.8 ms … 136.2 ms 3 runsBenchmark 6: git for-each-ref (revision=new,refcount=medium)
Time (mean ± σ): 830.4 ms ± 21.2 ms [User: 691.3 ms, System: 138.7 ms]
Range (min … max): 814.2 ms … 854.5 ms 3 runsBenchmark 7: git for-each-ref (revision=new,refcount=high)
Time (mean ± σ): 1.966 s ± 0.013 s [User: 1.717 s, System: 0.249 s]
Range (min … max): 1.952 s … 1.978 s 3 runsBenchmark 8: git for-each-ref (revision=new,refcount=huge)
Time (mean ± σ): 16.945 s ± 0.037 s [User: 15.182 s, System: 1.760 s]
Range (min … max): 16.910 s … 16.983 s 3 runsSummary
git for-each-ref (revision=old,refcount=small) ran
1.00 ± 0.01 times faster than git for-each-ref (revision=new,refcount=small) 6.07 ± 0.06 times faster than git for-each-ref (revision=old,refcount=medium) 6.13 ± 0.17 times faster than git for-each-ref (revision=new,refcount=medium)
14.46 ± 0.17 times faster than git for-each-ref (revision=old,refcount=high) 14.51 ± 0.16 times faster than git for-each-ref (revision=new,refcount=high)
124.09 ± 1.15 times faster than git for-each-ref (revision=old,refcount=huge) 125.05 ± 1.12 times faster than git for-each-ref (revision=new,refcount=huge)
Quoted 6 lines
The performance regression isn't all that concerning, but it makes me wonder why I see things becoming slower rather than faster. My guess is that this is because all my test repositories are well-packed and don't have a lot of loose references. But I just wanted to confirm how you benchmarked your change and what the underlying shape of your test repo was.
I ran my benchmark on my (Intel) Mac with a test repository (single commit, one file) containing:
- 10k refs/heads/ references
- 10k refs/tags/ references
- 10k refs/special/ references
All refs in the repository are loose. My Mac has historically been somewhat slow and inconsistent when it comes to perf testing, though, so I re-ran the benchmark a bit more formally on an Ubuntu VM (3 warmup iterations followed by at least 10 iterations per test):
---
Benchmark 1: git for-each-ref (revision=old,refcount=3k)
Time (mean ± σ): 40.6 ms ± 3.9 ms [User: 13.2 ms, System: 27.1 ms] Range (min … max): 37.2 ms … 59.1 ms 76 runs
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.
Benchmark 2: git for-each-ref (revision=new,refcount=3k)
Time (mean ± σ): 38.7 ms ± 4.4 ms [User: 13.8 ms, System: 24.5 ms] Range (min … max): 35.1 ms … 57.2 ms 71 runs
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.
Benchmark 3: git for-each-ref (revision=old,refcount=30k)
Time (mean ± σ): 419.4 ms ± 43.9 ms [User: 136.4 ms, System: 274.1 ms]
Range (min … max): 385.1 ms … 528.7 ms 10 runs
Benchmark 4: git for-each-ref (revision=new,refcount=30k)
Time (mean ± σ): 390.4 ms ± 27.2 ms [User: 133.1 ms, System: 251.6 ms]
Range (min … max): 360.3 ms … 447.6 ms 10 runs
Benchmark 5: git for-each-ref (revision=old,refcount=300k)
Time (mean ± σ): 4.171 s ± 0.052 s [User: 1.400 s, System: 2.715 s]
Range (min … max): 4.118 s … 4.283 s 10 runs
Benchmark 6: git for-each-ref (revision=new,refcount=300k)
Time (mean ± σ): 3.939 s ± 0.054 s [User: 1.403 s, System: 2.466 s]
Range (min … max): 3.858 s … 4.026 s 10 runs
Summary
'git for-each-ref (revision=new,refcount=3k)' ran
1.05 ± 0.16 times faster than 'git for-each-ref (revision=old,refcount=3k)'
10.08 ± 1.34 times faster than 'git for-each-ref (revision=new,refcount=30k)' 10.83 ± 1.67 times faster than 'git for-each-ref (revision=old,refcount=30k)'
101.68 ± 11.63 times faster than 'git for-each-ref (revision=new,refcount=300k)' 107.67 ± 12.30 times faster than 'git for-each-ref (revision=old,refcount=300k)'
---
So it's not the 20% speedup I saw on my local test repo (it's more like 5-8%), but there does appear to be a consistent improvement. As for your results, the changes in this series shouldn't affect packed ref operations, and the difference between old & new doesn't seem to indicate a regression.
Quoted 135 lines · Victoria Dye
Quoted 77 lines · Patrick Steinhardt
Quoted 10 lines · Victoria Dye via GitGitGadget
While investigating ref iteration performance in builtins like 'for-each-ref' and 'show-ref', I found two small improvement opportunities.
The first patch tweaks the logic around prefix matching in '
cache_ref_iterator_advance' so that we correctly skip refs that do not actually match a given prefix. The unnecessary iteration doesn't seem to be causing any bugs in the ref iteration commands that I've tested, but it doesn't hurt to be more precise (and it helps with some other patches I'm working on ;) ).Quoted 6 lines
The next three patches update how '
loose_fill_ref_dir' determines the type of ref cache entry to create (directory or regular). On platforms that included_typeinformation in 'struct dirent' (as far as I can tell, all except NonStop & certain versions of Cygwin), this allows us to skip calling 'stat'. In ad-hoc testing, this improved performance of 'git for-each-ref' by about 20%.I've done a small set of benchmarks with my usual test repositories, which is linux.git with a bunch of references added. The repository comes in four sizes:
- small: 50k references
- medium: 500k references
- high: 1.1m references
- huge: 12m referencesUnfortunately, I couldn't really reproduce the performance improvements. In fact, the new version runs consistently a tiny bit slower than the old version:
# Old version, which is
3a06386e31(The fifteenth batch, 2023-10-04).Benchmark 1: git for-each-ref (revision=old,refcount=small)
Time (mean ± σ): 135.5 ms ± 1.2 ms [User: 76.4 ms, System: 59.0 ms]
Range (min … max): 134.8 ms … 136.9 ms 3 runsBenchmark 2: git for-each-ref (revision=old,refcount=medium)
Time (mean ± σ): 822.7 ms ± 2.2 ms [User: 697.4 ms, System: 125.1 ms]
Range (min … max): 821.1 ms … 825.2 ms 3 runsBenchmark 3: git for-each-ref (revision=old,refcount=high)
Time (mean ± σ): 1.960 s ± 0.015 s [User: 1.702 s, System: 0.257 s]
Range (min … max): 1.944 s … 1.973 s 3 runs# New version, which is your tip.
Benchmark 4: git for-each-ref (revision=old,refcount=huge)
Time (mean ± σ): 16.815 s ± 0.054 s [User: 15.091 s, System: 1.722 s]
Range (min … max): 16.760 s … 16.869 s 3 runsBenchmark 5: git for-each-ref (revision=new,refcount=small)
Time (mean ± σ): 136.0 ms ± 0.2 ms [User: 78.8 ms, System: 57.1 ms]
Range (min … max): 135.8 ms … 136.2 ms 3 runsBenchmark 6: git for-each-ref (revision=new,refcount=medium)
Time (mean ± σ): 830.4 ms ± 21.2 ms [User: 691.3 ms, System: 138.7 ms]
Range (min … max): 814.2 ms … 854.5 ms 3 runsBenchmark 7: git for-each-ref (revision=new,refcount=high)
Time (mean ± σ): 1.966 s ± 0.013 s [User: 1.717 s, System: 0.249 s]
Range (min … max): 1.952 s … 1.978 s 3 runsBenchmark 8: git for-each-ref (revision=new,refcount=huge)
Time (mean ± σ): 16.945 s ± 0.037 s [User: 15.182 s, System: 1.760 s]
Range (min … max): 16.910 s … 16.983 s 3 runsSummary
git for-each-ref (revision=old,refcount=small) ran
1.00 ± 0.01 times faster than git for-each-ref (revision=new,refcount=small) 6.07 ± 0.06 times faster than git for-each-ref (revision=old,refcount=medium) 6.13 ± 0.17 times faster than git for-each-ref (revision=new,refcount=medium)
14.46 ± 0.17 times faster than git for-each-ref (revision=old,refcount=high) 14.51 ± 0.16 times faster than git for-each-ref (revision=new,refcount=high)
124.09 ± 1.15 times faster than git for-each-ref (revision=old,refcount=huge) 125.05 ± 1.12 times faster than git for-each-ref (revision=new,refcount=huge)Quoted 6 lines
The performance regression isn't all that concerning, but it makes me wonder why I see things becoming slower rather than faster. My guess is that this is because all my test repositories are well-packed and don't have a lot of loose references. But I just wanted to confirm how you benchmarked your change and what the underlying shape of your test repo was.
I ran my benchmark on my (Intel) Mac with a test repository (single commit, one file) containing:
- 10k refs/heads/ references
- 10k refs/tags/ references
- 10k refs/special/ referencesAll refs in the repository are loose. My Mac has historically been somewhat slow and inconsistent when it comes to perf testing, though, so I re-ran the benchmark a bit more formally on an Ubuntu VM (3 warmup iterations followed by at least 10 iterations per test):
---
Benchmark 1: git for-each-ref (revision=old,refcount=3k)
Time (mean ± σ): 40.6 ms ± 3.9 ms [User: 13.2 ms, System: 27.1 ms] Range (min … max): 37.2 ms … 59.1 ms 76 runsWarning: 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.
Benchmark 2: git for-each-ref (revision=new,refcount=3k)
Time (mean ± σ): 38.7 ms ± 4.4 ms [User: 13.8 ms, System: 24.5 ms] Range (min … max): 35.1 ms … 57.2 ms 71 runsWarning: 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.
Benchmark 3: git for-each-ref (revision=old,refcount=30k)
Time (mean ± σ): 419.4 ms ± 43.9 ms [User: 136.4 ms, System: 274.1 ms]
Range (min … max): 385.1 ms … 528.7 ms 10 runsBenchmark 4: git for-each-ref (revision=new,refcount=30k)
Time (mean ± σ): 390.4 ms ± 27.2 ms [User: 133.1 ms, System: 251.6 ms]
Range (min … max): 360.3 ms … 447.6 ms 10 runsBenchmark 5: git for-each-ref (revision=old,refcount=300k)
Time (mean ± σ): 4.171 s ± 0.052 s [User: 1.400 s, System: 2.715 s]
Range (min … max): 4.118 s … 4.283 s 10 runsBenchmark 6: git for-each-ref (revision=new,refcount=300k)
Time (mean ± σ): 3.939 s ± 0.054 s [User: 1.403 s, System: 2.466 s]
Range (min … max): 3.858 s … 4.026 s 10 runsSummary
'git for-each-ref (revision=new,refcount=3k)' ran
1.05 ± 0.16 times faster than 'git for-each-ref (revision=old,refcount=3k)'
10.08 ± 1.34 times faster than 'git for-each-ref (revision=new,refcount=30k)' 10.83 ± 1.67 times faster than 'git for-each-ref (revision=old,refcount=30k)'
101.68 ± 11.63 times faster than 'git for-each-ref (revision=new,refcount=300k)' 107.67 ± 12.30 times faster than 'git for-each-ref (revision=old,refcount=300k)'
Quoted 4 lines
---
So it's not the 20% speedup I saw on my local test repo (it's more like 5-8%), but there does appear to be a consistent improvement.
Thanks a bunch for re-doing the benchmark with a documented setup.
Quoted 3 lines
As for your results, the changes in this series shouldn't affect packed ref operations, and the difference between old & new doesn't seem to indicate a regression.
Yeah, I've also been surprised to see the performance regression for packed-refs files. The regression is persistent and reproducable on my machine though, so even though I tend to agree that the patches shouldn't negatively impact packed-refs performance they somehow do. It could just as well be something like different optimization choices by the compler due to the added patches, or hitting different cache lines. I dunno.
Anyway, I agree with your assessment. The regression I see is less than 1% for packed-refs, while the improvements for loose refs are a lot more significant and conceptually make a lot of sense. So I didn't intend to say that we shouldn't do these optimizations because of the miniscule peformance regression with packed-refs.
Or in other words: this series looks good to me.
Thanks!
Patrick
v2 cover Performance improvement & cleanup in loose ref iteration
In reply to Victoria Dye via GitGitGadgetWhile investigating ref iteration performance in builtins like 'for-each-ref' and 'show-ref', I found two small improvement opportunities.
The first patch tweaks the logic around prefix matching in 'cache_ref_iterator_advance' so that we correctly skip refs that do not actually match a given prefix. The unnecessary iteration doesn't seem to be causing any bugs in the ref iteration commands that I've tested, but it doesn't hurt to be more precise (and it helps with some other patches I'm working on ;) ).
The next three patches update how 'loose_fill_ref_dir' determines the type of ref cache entry to create (directory or regular). On platforms that include d_type information in 'struct dirent' (as far as I can tell, all except NonStop & certain versions of Cygwin), this allows us to skip calling 'stat'. Benchmarking against repos with various quantities of loose refs indicates a 5-8% speedup from these changes [1].
Changes since V1
================
* Added tests in patch 1 to demonstrate the bugfix
Thanks!
* Victoria
[1]
https://lore.kernel.org/git/[email protected]/
Victoria Dye (4):
ref-cache.c: fix prefix matching in ref iteration dir.[ch]: expose 'get_dtype'
dir.[ch]: add 'follow_symlink' arg to 'get_dtype' files-backend.c: avoid stat in 'loose_fill_ref_dir'
diagnose.c | 42 +++-------------------------------- dir.c | 33 +++++++++++++++++++++++++++ dir.h | 16 +++++++++++++ refs/files-backend.c | 14 +++++------- refs/ref-cache.c | 3 ++- t/t1500-rev-parse.sh | 23 +++++++++++++++++++ t/t4205-log-pretty-formats.sh | 30 +++++++++++++++++++++++++ 7 files changed, 112 insertions(+), 49 deletions(-)
base-commit: 3a06386e314565108ad56a9bdb8f7b80ac52fb69
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1594%2Fvdye%2Fvdye%2Fref-iteration-cleanup-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1594/vdye/vdye/ref-iteration-cleanup-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1594
Range-diff vs v1:
1: 59276a5b3fd ! 1: 402176246ea ref-cache.c: fix prefix matching in ref iteration
@@ Commit message
'create_dir_entry' explicitly calls out the trailing slash requirement, so
this is a safe assumption to make.
+ This bug generally doesn't have any user-facing impact, since it requires:
+
+ 1. using a non-empty prefix without a trailing slash in an iteration like
+ 'for_each_fullref_in',
+ 2. the callback to said iteration not reapplying the original filter (as
+ for-each-ref does) to ensure unmatched refs are skipped, and
+ 3. the repository having one or more refs that match part of, but not all
+ of, the prefix.
+
+ However, there are some niche scenarios that meet those criteria
+ (specifically, 'rev-parse --bisect' and '(log|show|shortlog) --bisect'). Add
+ tests covering those cases to demonstrate the fix in this patch.
+
Signed-off-by: Victoria Dye <[email protected]>
## refs/ref-cache.c ##
@@ refs/ref-cache.c: static int cache_ref_iterator_advance(struct ref_iterator *ref
continue;
} else {
entry_prefix_state = level->prefix_state;
+
+ ## t/t1500-rev-parse.sh ##
+@@ t/t1500-rev-parse.sh: test_expect_success 'rev-parse --since= unsqueezed ordering' '
+ test_cmp expect actual
+ '
+
++test_expect_success 'rev-parse --bisect includes bad, excludes good' '
++ test_commit_bulk 6 &&
++
++ git update-ref refs/bisect/bad-1 HEAD~1 &&
++ git update-ref refs/bisect/b HEAD~2 &&
++ git update-ref refs/bisect/bad-3 HEAD~3 &&
++ git update-ref refs/bisect/good-3 HEAD~3 &&
++ git update-ref refs/bisect/bad-4 HEAD~4 &&
++ git update-ref refs/bisect/go HEAD~4 &&
++
++ # Note: refs/bisect/b and refs/bisect/go should be ignored because they
++ # do not match the refs/bisect/bad or refs/bisect/good prefixes.
++ cat >expect <<-EOF &&
++ refs/bisect/bad-1
++ refs/bisect/bad-3
++ refs/bisect/bad-4
++ ^refs/bisect/good-3
++ EOF
++
++ git rev-parse --symbolic-full-name --bisect >actual &&
++ test_cmp expect actual
++'
++
+ test_done
+
+ ## t/t4205-log-pretty-formats.sh ##
+@@ t/t4205-log-pretty-formats.sh: test_expect_success '%S in git log --format works with other placeholders (part
+ test_cmp expect actual
+ '
+
++test_expect_success 'setup more commits for %S with --bisect' '
++ test_commit four &&
++ test_commit five &&
++
++ head1=$(git rev-parse --verify HEAD~0) &&
++ head2=$(git rev-parse --verify HEAD~1) &&
++ head3=$(git rev-parse --verify HEAD~2) &&
++ head4=$(git rev-parse --verify HEAD~3)
++'
++
++test_expect_success '%S with --bisect labels commits with refs/bisect/bad ref' '
++ git update-ref refs/bisect/bad-$head1 $head1 &&
++ git update-ref refs/bisect/go $head1 &&
++ git update-ref refs/bisect/bad-$head2 $head2 &&
++ git update-ref refs/bisect/b $head3 &&
++ git update-ref refs/bisect/bad-$head4 $head4 &&
++ git update-ref refs/bisect/good-$head4 $head4 &&
++
++ # We expect to see the range of commits betwee refs/bisect/good-$head4
++ # and refs/bisect/bad-$head1. The "source" ref is the nearest bisect ref
++ # from which the commit is reachable.
++ cat >expect <<-EOF &&
++ $head1 refs/bisect/bad-$head1
++ $head2 refs/bisect/bad-$head2
++ $head3 refs/bisect/bad-$head2
++ EOF
++ git log --bisect --format="%H %S" >actual &&
++ test_cmp expect actual
++'
++
+ test_expect_success 'log --pretty=reference' '
+ git log --pretty="tformat:%h (%s, %as)" >expect &&
+ git log --pretty=reference >actual &&
2: 24014010ea3 = 2: 172538b5e30 dir.[ch]: expose 'get_dtype'
3: a382d2ba652 = 3: 295ca94003b dir.[ch]: add 'follow_symlink' arg to 'get_dtype'
4: e193a453182 = 4: e89501cb51f files-backend.c: avoid stat in 'loose_fill_ref_dir'Signature · 1 line
gitgitgadget
PATCH v2 1/4 ref-cache.c: fix prefix matching in ref iteration
From: Victoria Dye <[email protected]>
Update 'cache_ref_iterator_advance' to skip over refs that are not matched by the given prefix.
Currently, a ref entry is considered "matched" if the entry name is fully contained within the prefix:
* prefix: "refs/heads/v1"
* entry: "refs/heads/v1.0"
OR if the prefix is fully contained in the entry name:
* prefix: "refs/heads/v1.0"
* entry: "refs/heads/v1"
The first case is always correct, but the second is only correct if the ref cache entry is a directory, for example:
* prefix: "refs/heads/example"
* entry: "refs/heads/"
Modify the logic in 'cache_ref_iterator_advance' to reflect these expectations:
1. If 'overlaps_prefix' returns 'PREFIX_EXCLUDES_DIR', then the prefix and ref cache entry do not overlap at all. Skip this entry.
2. If 'overlaps_prefix' returns 'PREFIX_WITHIN_DIR', then the prefix matches inside this entry if it is a directory. Skip if the entry is not a directory, otherwise iterate over it.
3. Otherwise, 'overlaps_prefix' returned 'PREFIX_CONTAINS_DIR', indicating that the cache entry (directory or not) is fully contained by or equal to the prefix. Iterate over this entry.
Note that condition 2 relies on the names of directory entries having the appropriate trailing slash. The existing function documentation of 'create_dir_entry' explicitly calls out the trailing slash requirement, so this is a safe assumption to make.
This bug generally doesn't have any user-facing impact, since it requires:
1. using a non-empty prefix without a trailing slash in an iteration like 'for_each_fullref_in',
2. the callback to said iteration not reapplying the original filter (as for-each-ref does) to ensure unmatched refs are skipped, and
3. the repository having one or more refs that match part of, but not all of, the prefix.
However, there are some niche scenarios that meet those criteria (specifically, 'rev-parse --bisect' and '(log|show|shortlog) --bisect'). Add tests covering those cases to demonstrate the fix in this patch.
--- refs/ref-cache.c | 3 ++- t/t1500-rev-parse.sh | 23 +++++++++++++++++++++++ t/t4205-log-pretty-formats.sh | 30 ++++++++++++++++++++++++++++++ 3 files changed, 55 insertions(+), 1 deletion(-)
refs/ref-cache.c +2 -1
@@ -412,7 +412,8 @@ static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)if (level->prefix_state ==PREFIX_WITHIN_DIR ) { entry_prefix_state =overlaps_prefix (entry->name, iter->prefix); -if (entry_prefix_state ==PREFIX_EXCLUDES_DIR ) +if (entry_prefix_state ==PREFIX_EXCLUDES_DIR || + (entry_prefix_state ==PREFIX_WITHIN_DIR && !(entry->flag &REF_DIR )))continue ; }else { entry_prefix_state = level->prefix_state;
t/t1500-rev-parse.sh +23 -0
@@ -264,4 +264,27 @@ test_expect_success 'rev-parse --since= unsqueezed ordering' ' test_cmp expect actual ' +test_expect_success 'rev-parse --bisect includes bad, excludes good' ' + test_commit_bulk 6 && + + git update-ref refs/bisect/bad-1 HEAD~1 && + git update-ref refs/bisect/b HEAD~2 && + git update-ref refs/bisect/bad-3 HEAD~3 && + git update-ref refs/bisect/good-3 HEAD~3 && + git update-ref refs/bisect/bad-4 HEAD~4 && + git update-ref refs/bisect/go HEAD~4 && + + # Note: refs/bisect/b and refs/bisect/go should be ignored because they + # do not match the refs/bisect/bad or refs/bisect/good prefixes. + cat >expect <<-EOF && + refs/bisect/bad-1 + refs/bisect/bad-3 + refs/bisect/bad-4 + ^refs/bisect/good-3 + EOF + + git rev-parse --symbolic-full-name --bisect >actual && + test_cmp expect actual +' + test_done
t/t4205-log-pretty-formats.sh +30 -0
@@ -956,6 +956,36 @@ test_expect_success '%S in git log --format works with other placeholders (part test_cmp expect actual ' +test_expect_success 'setup more commits for %S with --bisect' ' + test_commit four && + test_commit five && + + head1=$(git rev-parse --verify HEAD~0) && + head2=$(git rev-parse --verify HEAD~1) && + head3=$(git rev-parse --verify HEAD~2) && + head4=$(git rev-parse --verify HEAD~3) +' + +test_expect_success '%S with --bisect labels commits with refs/bisect/bad ref' ' + git update-ref refs/bisect/bad-$head1 $head1 && + git update-ref refs/bisect/go $head1 && + git update-ref refs/bisect/bad-$head2 $head2 && + git update-ref refs/bisect/b $head3 && + git update-ref refs/bisect/bad-$head4 $head4 && + git update-ref refs/bisect/good-$head4 $head4 && + + # We expect to see the range of commits betwee refs/bisect/good-$head4 + # and refs/bisect/bad-$head1. The "source" ref is the nearest bisect ref + # from which the commit is reachable. + cat >expect <<-EOF && + $head1 refs/bisect/bad-$head1 + $head2 refs/bisect/bad-$head2 + $head3 refs/bisect/bad-$head2 + EOF + git log --bisect --format="%H %S" >actual && + test_cmp expect actual +' + test_expect_success 'log --pretty=reference' ' git log --pretty="tformat:%h (%s, %as)" >expect && git log --pretty=reference >actual &&
Signature · 1 line
gitgitgadget
Re: [PATCH v2 1/4] ref-cache.c: fix prefix matching in ref iteration
Quoted 122 lines · Victoria Dye via GitGitGadget
From: Victoria Dye <[email protected]>
Update '
cache_ref_iterator_advance' to skip over refs that are not matched by the given prefix.Currently, a ref entry is considered "matched" if the entry name is fully contained within the prefix:
* prefix: "refs/heads/v1"
* entry: "refs/heads/v1.0"OR if the prefix is fully contained in the entry name:
* prefix: "refs/heads/v1.0"
* entry: "refs/heads/v1"The first case is always correct, but the second is only correct if the ref cache entry is a directory, for example:
* prefix: "refs/heads/example"
* entry: "refs/heads/"Modify the logic in '
cache_ref_iterator_advance' to reflect these expectations:1. If '
overlaps_prefix' returns 'PREFIX_EXCLUDES_DIR', then the prefix and ref cache entry do not overlap at all. Skip this entry.
2. If 'overlaps_prefix' returns 'PREFIX_WITHIN_DIR', then the prefix matches inside this entry if it is a directory. Skip if the entry is not a directory, otherwise iterate over it.
3. Otherwise, 'overlaps_prefix' returned 'PREFIX_CONTAINS_DIR', indicating that the cache entry (directory or not) is fully contained by or equal to the prefix. Iterate over this entry.Note that condition 2 relies on the names of directory entries having the appropriate trailing slash. The existing function documentation of '
create_dir_entry' explicitly calls out the trailing slash requirement, so this is a safe assumption to make.This bug generally doesn't have any user-facing impact, since it requires:
1. using a non-empty prefix without a trailing slash in an iteration like '
for_each_fullref_in',
2. the callback to said iteration not reapplying the original filter (as for-each-ref does) to ensure unmatched refs are skipped, and
3. the repository having one or more refs that match part of, but not all of, the prefix.However, there are some niche scenarios that meet those criteria (specifically, 'rev-parse --bisect' and '(log|show|shortlog) --bisect'). Add tests covering those cases to demonstrate the fix in this patch.
Signed-off-by Victoria Dye <[email protected]>--- refs/ref-cache.c | 3 ++- t/t1500-rev-parse.sh | 23 +++++++++++++++++++++++ t/t4205-log-pretty-formats.sh | 30 ++++++++++++++++++++++++++++++ 3 files changed, 55 insertions(+), 1 deletion(-)refs/ref-cache.c +2
-1@@ -412,7 +412,8 @@ static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)if (level->prefix_state ==PREFIX_WITHIN_DIR ) { entry_prefix_state =overlaps_prefix (entry->name, iter->prefix); -if (entry_prefix_state ==PREFIX_EXCLUDES_DIR ) +if (entry_prefix_state ==PREFIX_EXCLUDES_DIR || + (entry_prefix_state ==PREFIX_WITHIN_DIR && !(entry->flag &REF_DIR )))continue ; }else { entry_prefix_state = level->prefix_state;t/t1500-rev-parse.sh +23
-0@@ -264,4 +264,27 @@ test_expect_success 'rev-parse --since= unsqueezed ordering' ' test_cmp expect actual ' +test_expect_success 'rev-parse --bisect includes bad, excludes good' ' + test_commit_bulk 6 && + + git update-ref refs/bisect/bad-1 HEAD~1 && + git update-ref refs/bisect/b HEAD~2 && + git update-ref refs/bisect/bad-3 HEAD~3 && + git update-ref refs/bisect/good-3 HEAD~3 && + git update-ref refs/bisect/bad-4 HEAD~4 && + git update-ref refs/bisect/go HEAD~4 && + + # Note: refs/bisect/b and refs/bisect/go should be ignored because they + # do not match the refs/bisect/bad or refs/bisect/good prefixes. + cat >expect <<-EOF && + refs/bisect/bad-1 + refs/bisect/bad-3 + refs/bisect/bad-4 + ^refs/bisect/good-3 + EOF + + git rev-parse --symbolic-full-name --bisect >actual && + test_cmp expect actual +' + test_donet/t4205-log-pretty-formats.sh +9
-0@@ -956,6 +956,36 @@ test_expect_success '%S in git log --format works with other placeholders (part test_cmp expect actual ' +test_expect_success 'setup more commits for %S with --bisect' ' + test_commit four && + test_commit five && + + head1=$(git rev-parse --verify HEAD~0) && + head2=$(git rev-parse --verify HEAD~1) && + head3=$(git rev-parse --verify HEAD~2) && + head4=$(git rev-parse --verify HEAD~3) +'
t/t4205-log-pretty-formats.sh test_expect_success '%S in git log --format works with other placeholders (part · line 977
Quoted 10 lines
t/t4205-log-pretty-formats.sh +10
-0+ +test_expect_success '%S with --bisect labels commits with refs/bisect/bad ref' ' + git update-ref refs/bisect/bad-$head1 $head1 && + git update-ref refs/bisect/go $head1 && + git update-ref refs/bisect/bad-$head2 $head2 && + git update-ref refs/bisect/b $head3 && + git update-ref refs/bisect/bad-$head4 $head4 && + git update-ref refs/bisect/good-$head4 $head4 && + + # We expect to see the range of commits betwee refs/bisect/good-$head4
Nit: s/betwee/between. Probably not worth rerolling this series only because of this typo though.
Patrick
Quoted 17 lines
t/t4205-log-pretty-formats.sh +11
-0+ # and refs/bisect/bad-$head1. The "source" ref is the nearest bisect ref + # from which the commit is reachable. + cat >expect <<-EOF && + $head1 refs/bisect/bad-$head1 + $head2 refs/bisect/bad-$head2 + $head3 refs/bisect/bad-$head2 + EOF + git log --bisect --format="%H %S" >actual && + test_cmp expect actual +' + test_expect_success 'log --pretty=reference' ' git log --pretty="tformat:%h (%s, %as)" >expect && git log --pretty=reference >actual &&Signature · 1 line
gitgitgadget
PATCH v2 2/4 dir.[ch]: expose 'get_dtype'
In reply to Victoria Dye via GitGitGadgetFrom: Victoria Dye <[email protected]>
Move 'get_dtype()' from 'diagnose.c' to 'dir.c' and add its declaration to 'dir.h' so that it is accessible to callers in other files. The function and its documentation are moved verbatim except for a small addition to the description clarifying what the 'path' arg represents.
--- diagnose.c | 36 ------------------------------------ dir.c | 28 ++++++++++++++++++++++++++++ dir.h | 11 +++++++++++ 3 files changed, 39 insertions(+), 36 deletions(-)
diagnose.c +0 -36
@@ -71,42 +71,6 @@ static int dir_file_stats(struct object_directory *object_dir, void *data)return 0 ; } -/* -* Get the d_type of a dirent. If the d_type is unknown, derive it from -* stat.st_mode. -* -* Note that 'path' is assumed to have a trailing slash. It is also modified -* in-place during the execution of the function, but is then reverted to its -* original value before returning. -*/ -static unsigned char get_dtype (struct dirent *e,struct strbuf *path) -{ -struct stat st; -unsigned char dtype =DTYPE (e); -size_t base_path_len; - -if (dtype !=DT_UNKNOWN ) -return dtype; - -/* d_type unknown in dirent, try to fall back on lstat results */ - base_path_len = path->len; -strbuf_addstr (path, e->d_name); -if (lstat (path->buf, &st)) - goto cleanup; - -/* determine d_type from st_mode */ -if (S_ISREG (st.st_mode)) - dtype =DT_REG ; -else if (S_ISDIR (st.st_mode)) - dtype =DT_DIR ; -else if (S_ISLNK (st.st_mode)) - dtype =DT_LNK ; - -cleanup: -strbuf_setlen (path, base_path_len); -return dtype; -} -static int count_files (struct strbuf *path) {DIR *dir =opendir (path->buf);
dir.c +28 -0
@@ -2235,6 +2235,34 @@ static int get_index_dtype(struct index_state *istate,return DT_UNKNOWN ; } +unsigned char get_dtype (struct dirent *e,struct strbuf *path) +{ +struct stat st; +unsigned char dtype =DTYPE (e); +size_t base_path_len; + +if (dtype !=DT_UNKNOWN ) +return dtype; + +/* d_type unknown in dirent, try to fall back on lstat results */ + base_path_len = path->len; +strbuf_addstr (path, e->d_name); +if (lstat (path->buf, &st)) + goto cleanup; + +/* determine d_type from st_mode */ +if (S_ISREG (st.st_mode)) + dtype =DT_REG ; +else if (S_ISDIR (st.st_mode)) + dtype =DT_DIR ; +else if (S_ISLNK (st.st_mode)) + dtype =DT_LNK ; + +cleanup: +strbuf_setlen (path, base_path_len); +return dtype; +} +static int resolve_dtype (int dtype,struct index_state *istate,const char *path,int len) {
dir.h +11 -0
@@ -363,6 +363,17 @@ struct dir_struct {struct dirent *readdir_skip_dot_and_dotdot (DIR *dirp); +/* +* Get the d_type of a dirent. If the d_type is unknown, derive it from +* stat.st_mode using the path to the dirent's containing directory (path) and +* the name of the dirent itself. +* +* Note that 'path' is assumed to have a trailing slash. It is also modified +* in-place during the execution of the function, but is then reverted to its +* original value before returning. +*/ +unsigned char get_dtype (struct dirent *e,struct strbuf *path); +/*Count the number of slashes for string s*/ int count_slashes (const char *s);
Signature · 1 line
gitgitgadget
PATCH v2 3/4 dir.[ch]: add 'follow_symlink' arg to 'get_dtype'
In reply to Victoria Dye via GitGitGadgetFrom: Victoria Dye <[email protected]>
Add a 'follow_symlink' boolean option to 'get_type()'. If 'follow_symlink' is enabled, DT_LNK (in addition to DT_UNKNOWN) d_types triggers the stat-based d_type resolution, using 'stat' instead of 'lstat' to get the type of the followed symlink. Note that symlinks are not followed recursively, so a symlink pointing to another symlink will still resolve to DT_LNK.
Update callers in 'diagnose.c' to specify 'follow_symlink = 0' to preserve current behavior.
--- diagnose.c | 6 +++--- dir.c | 13 +++++++++---- dir.h | 7 ++++++- 3 files changed, 18 insertions(+), 8 deletions(-)
diagnose.c +3 -3
@@ -81,7 +81,7 @@ static int count_files(struct strbuf *path)return 0 ;while ((e =readdir_skip_dot_and_dotdot (dir)) !=NULL ) -if (get_dtype (e, path) ==DT_REG ) +if (get_dtype (e, path,0 ) ==DT_REG ) count++;closedir (dir);
@@ -110,7 +110,7 @@ static void loose_objs_stats(struct strbuf *buf, const char *path) base_path_len = count_path.len;while ((e =readdir_skip_dot_and_dotdot (dir)) !=NULL ) -if (get_dtype (e, &count_path) ==DT_DIR && +if (get_dtype (e, &count_path,0 ) ==DT_DIR &&strlen (e->d_name) ==2 && !hex_to_bytes (&c, e->d_name,1 )) {strbuf_setlen (&count_path, base_path_len);
@@ -155,7 +155,7 @@ static int add_directory_to_archiver(struct strvec *archiver_args,strbuf_add_absolute_path (&abspath, at_root ?"." : path);strbuf_addch (&abspath,'/' ); - dtype =get_dtype (e, &abspath); + dtype =get_dtype (e, &abspath,0 );strbuf_setlen (&buf, len);strbuf_addstr (&buf, e->d_name);
dir.c +9 -4
@@ -2235,19 +2235,24 @@ static int get_index_dtype(struct index_state *istate,return DT_UNKNOWN ; } -unsigned char get_dtype (struct dirent *e,struct strbuf *path) +unsigned char get_dtype (struct dirent *e,struct strbuf *path, +int follow_symlink) {struct stat st;unsigned char dtype =DTYPE (e);size_t base_path_len; -if (dtype !=DT_UNKNOWN ) +if (dtype !=DT_UNKNOWN && !(follow_symlink && dtype ==DT_LNK ))return dtype; -/* d_type unknown in dirent, try to fall back on lstat results */ +/* +* d_type unknown or unfollowed symlink, try to fall back on [l]stat +* results. If [l]stat fails, explicitly set DT_UNKNOWN. +*/ base_path_len = path->len;strbuf_addstr (path, e->d_name); -if (lstat (path->buf, &st)) +if ((follow_symlink &&stat (path->buf, &st)) || + (!follow_symlink &&lstat (path->buf, &st))) goto cleanup;/* determine d_type from st_mode */
dir.h +6 -1
@@ -368,11 +368,16 @@ struct dirent *readdir_skip_dot_and_dotdot(DIR *dirp);* stat.st_mode using the path to the dirent's containing directory (path) and * the name of the dirent itself. * +* If 'follow_symlink' is 1, this function will attempt to follow DT_LNK types +* using 'stat'. Links are *not* followed recursively, so a symlink pointing +* to another symlink will still resolve to 'DT_LNK'. +* * Note that 'path' is assumed to have a trailing slash. It is also modified * in-place during the execution of the function, but is then reverted to its * original value before returning. */ -unsigned char get_dtype (struct dirent *e,struct strbuf *path); +unsigned char get_dtype (struct dirent *e,struct strbuf *path, +int follow_symlink);/*Count the number of slashes for string s*/ int count_slashes (const char *s);
Signature · 1 line
gitgitgadget
PATCH v2 4/4 files-backend.c: avoid stat in 'loose_fill_ref_dir'
In reply to Victoria Dye via GitGitGadgetFrom: Victoria Dye <[email protected]>
Modify the 'readdir' loop in 'loose_fill_ref_dir' to, rather than 'stat' a file to determine whether it is a directory or not, use 'get_dtype'.
Currently, the loop uses 'stat' to determine whether each dirent is a directory itself or not in order to construct the appropriate ref cache entry. If 'stat' fails (returning a negative value), the dirent is silently skipped; otherwise, 'S_ISDIR(st.st_mode)' is used to check whether the entry is a directory.
On platforms that include an entry's d_type in in the 'dirent' struct, this extra 'stat' check is redundant. We can use the 'get_dtype' method to extract this information on platforms that support it (i.e. where NO_D_TYPE_IN_DIRENT is unset), and derive it with 'stat' on platforms that don't. Because 'stat' is an expensive call, this confers a modest-but-noticeable performance improvement when iterating over large numbers of refs (approximately 20% speedup in 'git for-each-ref' in a 30k ref repo).
Unlike other existing usage of 'get_dtype', the 'follow_symlinks' arg is set to 1 to replicate the existing handling of symlink dirents. This unfortunately requires calling 'stat' on the associated entry regardless of platform, but symlinks in the loose ref store are highly unlikely since they'd need to be created manually by a user.
Note that this patch also changes the condition for skipping creation of a ref entry from "when 'stat' fails" to "when the d_type is anything other than DT_REG or DT_DIR". If a dirent's d_type is DT_UNKNOWN (either because the platform doesn't support d_type in dirents or some other reason) or DT_LNK, 'get_dtype' will try to derive the underlying type with 'stat'. If the 'stat' fails, the d_type will remain 'DT_UNKNOWN' and dirent will be skipped. However, it will also be skipped if it is any other valid d_type (e.g. DT_FIFO for named pipes, DT_LNK for a nested symlink). Git does not handle these properly anyway, so we can safely constrain accepted types to directories and regular files.
--- refs/files-backend.c | 14 +++++--------- 1 file changed, 5 insertions(+), 9 deletions(-)
refs/files-backend.c +5 -9
@@ -246,10 +246,8 @@ static void loose_fill_ref_dir(struct ref_store *ref_store,int dirnamelen =strlen (dirname);struct strbuf refname;struct strbuf path =STRBUF_INIT ; -size_t path_baselen;files_ref_path (refs, &path, dirname); - path_baselen = path.len; d =opendir (path.buf);if (!d) {
@@ -262,23 +260,22 @@ static void loose_fill_ref_dir(struct ref_store *ref_store, while ((de = readdir(d)) != NULL) { struct object_id oid; - struct stat st; int flag; + unsigned char dtype; if (de->d_name[0] == '.') continue; if (ends_with(de->d_name, ".lock")) continue; strbuf_addstr(&refname, de->d_name); - strbuf_addstr(&path, de->d_name); - if (stat(path.buf, &st) < 0) { - ; /* silently ignore */ - } else if (S_ISDIR(st.st_mode)) { + + dtype = get_dtype(de, &path, 1); + if (dtype == DT_DIR) { strbuf_addch(&refname, '/'); add_entry_to_dir(dir, create_dir_entry(dir->cache, refname.buf, refname.len)); - } else { + } else if (dtype == DT_REG) { if (!refs_resolve_ref_unsafe(&refs->base, refname.buf, RESOLVE_REF_READING,
@@ -308,7 +305,6 @@ static void loose_fill_ref_dir(struct ref_store *ref_store, create_ref_entry(refname.buf, &oid, flag)); }strbuf_setlen (&refname, dirnamelen); -strbuf_setlen (&path, path_baselen); }strbuf_release (&refname);strbuf_release (&path);
Signature · 1 line
gitgitgadget