threads / patch / 35303

patchcheckout: most of the time we have good leading directories

Subject: [PATCH] checkout: most of the time we have good leading directories

## tl;dr

3 messages between Nov 8, 2013 and Nov 9, 2013. Diffs are folded; open one to read it.

replies: 2people: 2as markdown or json

Junio C Hamano· Nov 8, 2013, 00:30 UTC · lore

When "git checkout" wants to create a path, e.g. a/b/c/d/e, after seeing if the entire thing already exists (in which case we check if that is up-to-date and do not bother to check it out, or we unlink and recreate it), we validate that the leading directory path is without funny symlinks by seeing a/, a/b/, a/b/c/ and then a/b/c/d/ are all without funny symlinks, by calling has_dirs_only_path() in this order.

When we are checking out many files (imagine: initial checkout), however, it is likely that an earlier checkout would have already made sure that the leading directory a/b/c/d/ is in good order; by first checking the whole path a/b/c/d/ first, we can often bypass calls to has_dirs_only_path() for leading part.

This cuts down the number of calls to has_dirs_only_path() for checking out Linux kernel sources afresh from 190k down to 98k.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 * Just a random experimental change I was playing with today,
   looking for low hanging fruits before having to thread the entire
   checkout codepath.
 entry.c | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)
Show changes to entry.c +10 −2
diff --git a/entry.c b/entry.c
index 7b7aa81..e2c0ac6 100644
--- a/entry.c
+++ b/entry.c
@@ -6,9 +6,17 @@
 static void create_directories(const char *path, int path_len,
 			       const struct checkout *state)
 {
-	char *buf = xmalloc(path_len + 1);
-	int len = 0;
+	char *buf;
+	int len;
+
+	for (len = path_len - 1; 0 <= len; len--)
+		if (path[len] == '/')
+			break;
+	if (has_dirs_only_path(path, len, state->base_dir_len))
+		return; /* ok, we have the whole leading directory */
 
+	buf = xmalloc(path_len + 1);
+	len = 0;
 	while (len < path_len) {
 		do {
 			buf[len] = path[len];
Thomas Rast· Nov 9, 2013, 14:24 UTC · re: Junio C Hamano · lore

Re: [PATCH] checkout: most of the time we have good leading directories

Junio C Hamano <gitster@pobox.com> writes:
Show 13 quoted lines
> When "git checkout" wants to create a path, e.g. a/b/c/d/e, after
> seeing if the entire thing already exists (in which case we check if
> that is up-to-date and do not bother to check it out, or we unlink
> and recreate it), we validate that the leading directory path is
> without funny symlinks by seeing a/, a/b/, a/b/c/ and then a/b/c/d/
> are all without funny symlinks, by calling has_dirs_only_path() in
> this order.
>
> When we are checking out many files (imagine: initial checkout),
> however, it is likely that an earlier checkout would have already
> made sure that the leading directory a/b/c/d/ is in good order; by
> first checking the whole path a/b/c/d/ first, we can often bypass
> calls to has_dirs_only_path() for leading part.

Naively one would think that this is just as much work -- to correctly verify that the path consist only of actual directories (not symlinks) we have to lstat() every component regardless. It seems the reason this is an optimization is that has_dirs_only_path() caches its results, so that we can get 'a/b/c/d/ is okay in every component' from the cache.

Is this analysis correct? If so, can you spell that out in the commit message?

-- 
Thomas Rast
tr@thomasrast.ch
Junio C Hamano· Nov 9, 2013, 20:09 UTC · re: Thomas Rast · lore

Re: [PATCH] checkout: most of the time we have good leading directories

Thomas Rast <tr@thomasrast.ch> writes:
Show 24 quoted lines
> Junio C Hamano <gitster@pobox.com> writes:
>
>> When "git checkout" wants to create a path, e.g. a/b/c/d/e, after
>> seeing if the entire thing already exists (in which case we check if
>> that is up-to-date and do not bother to check it out, or we unlink
>> and recreate it), we validate that the leading directory path is
>> without funny symlinks by seeing a/, a/b/, a/b/c/ and then a/b/c/d/
>> are all without funny symlinks, by calling has_dirs_only_path() in
>> this order.
>>
>> When we are checking out many files (imagine: initial checkout),
>> however, it is likely that an earlier checkout would have already
>> made sure that the leading directory a/b/c/d/ is in good order; by
>> first checking the whole path a/b/c/d/ first, we can often bypass
>> calls to has_dirs_only_path() for leading part.
>
> Naively one would think that this is just as much work -- to correctly
> verify that the path consist only of actual directories (not symlinks)
> we have to lstat() every component regardless.  It seems the reason this
> is an optimization is that has_dirs_only_path() caches its results, so
> that we can get 'a/b/c/d/ is okay in every component' from the cache.
>
> Is this analysis correct?  If so, can you spell that out in the commit
> message?
It was done without analysis ;-) but I think you are correct.

If you are checking out a/b/c/d/{m,a,n,y}, after you checked out a/b/c/d/m, the has_dirs_only_path cache knows a/b/c/d/ is in good order so when you check out a/b/c/d/{a,n,y}, we can just ask for a/b/c/d/ and get an OK immediately. There is no point asking from a/, a/b/, a/b/c/ and then a/b/c/d/, in the original pessimistic order. A change done _right_ to properly optimize this might even want to change the main loop that the patch bypassed.

I do not think the patch (or the "change done right" for that matter) will make much difference on a platform with good filesystem metadata caching. It may be very interesting to see if that simple patch makes any difference on Windows, though. If it does, then we may want to look into cleaning up the code further.

Thanks for a comment.

← back to recent threads