{"thread":{"id":"35303","subject":"[PATCH] checkout: most of the time we have good leading directories","startedAt":"2013-11-08T00:30:14Z","lastAt":"2013-11-09T20:09:05Z","messageCount":3,"participants":["Junio C Hamano","Thomas Rast"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"230228","messageId":"xmqqy54zohux.fsf@gitster.dls.corp.google.com","threadId":"35303","inReplyTo":null,"subject":"[PATCH] checkout: most of the time we have good leading directories","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-11-08T00:30:14Z","receivedAt":"2013-11-08T00:30:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"When \"git checkout\" wants to create a path, e.g. a/b/c/d/e, after\nseeing if the entire thing already exists (in which case we check if\nthat is up-to-date and do not bother to check it out, or we unlink\nand recreate it), we validate that the leading directory path is\nwithout funny symlinks by seeing a/, a/b/, a/b/c/ and then a/b/c/d/\nare all without funny symlinks, by calling has_dirs_only_path() in\nthis order.\n\nWhen we are checking out many files (imagine: initial checkout),\nhowever, it is likely that an earlier checkout would have already\nmade sure that the leading directory a/b/c/d/ is in good order; by\nfirst checking the whole path a/b/c/d/ first, we can often bypass\ncalls to has_dirs_only_path() for leading part.\n\nThis cuts down the number of calls to has_dirs_only_path() for\nchecking out Linux kernel sources afresh from 190k down to 98k.\n\nSigned-off-by: Junio C Hamano \n---\n\n * Just a random experimental change I was playing with today,\n looking for low hanging fruits before having to thread the entire\n checkout codepath.\n\n entry.c | 12 ++++++++++--\n 1 file changed, 10 insertions(+), 2 deletions(-)\n\ndiff --git a/entry.c b/entry.c\nindex 7b7aa81..e2c0ac6 100644\n--- a/entry.c\n+++ b/entry.c\n@@ -6,9 +6,17 @@\n static void create_directories(const char *path, int path_len,\n \t\t\t const struct checkout *state)\n {\n-\tchar *buf = xmalloc(path_len + 1);\n-\tint len = 0;\n+\tchar *buf;\n+\tint len;\n+\n+\tfor (len = path_len - 1; 0 <= len; len--)\n+\t\tif (path[len] == '/')\n+\t\t\tbreak;\n+\tif (has_dirs_only_path(path, len, state->base_dir_len))\n+\t\treturn; /* ok, we have the whole leading directory */\n \n+\tbuf = xmalloc(path_len + 1);\n+\tlen = 0;\n \twhile (len < path_len) {\n \t\tdo {\n \t\t\tbuf[len] = path[len];\n"},{"id":"230358","messageId":"87iow1ps9t.fsf@linux-k42r.v.cablecom.net","threadId":"35303","inReplyTo":"xmqqy54zohux.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] checkout: most of the time we have good leading directories","fromName":"Thomas Rast","fromEmail":"tr@thomasrast.ch","sentAt":"2013-11-09T14:24:30Z","receivedAt":"2013-11-09T14:24:30Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> When \"git checkout\" wants to create a path, e.g. a/b/c/d/e, after\n> seeing if the entire thing already exists (in which case we check if\n> that is up-to-date and do not bother to check it out, or we unlink\n> and recreate it), we validate that the leading directory path is\n> without funny symlinks by seeing a/, a/b/, a/b/c/ and then a/b/c/d/\n> are all without funny symlinks, by calling has_dirs_only_path() in\n> this order.\n>\n> When we are checking out many files (imagine: initial checkout),\n> however, it is likely that an earlier checkout would have already\n> made sure that the leading directory a/b/c/d/ is in good order; by\n> first checking the whole path a/b/c/d/ first, we can often bypass\n> calls to has_dirs_only_path() for leading part.\n\nNaively one would think that this is just as much work -- to correctly\nverify that the path consist only of actual directories (not symlinks)\nwe have to lstat() every component regardless. It seems the reason this\nis an optimization is that has_dirs_only_path() caches its results, so\nthat we can get 'a/b/c/d/ is okay in every component' from the cache.\n\nIs this analysis correct? If so, can you spell that out in the commit\nmessage?\n\n-- \nThomas Rast\ntr@thomasrast.ch\n"},{"id":"230362","messageId":"xmqqsiv5mj6m.fsf@gitster.dls.corp.google.com","threadId":"35303","inReplyTo":"87iow1ps9t.fsf@linux-k42r.v.cablecom.net","subject":"Re: [PATCH] checkout: most of the time we have good leading directories","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-11-09T20:09:05Z","receivedAt":"2013-11-09T20:09:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> Junio C Hamano writes:\n>\n>> When \"git checkout\" wants to create a path, e.g. a/b/c/d/e, after\n>> seeing if the entire thing already exists (in which case we check if\n>> that is up-to-date and do not bother to check it out, or we unlink\n>> and recreate it), we validate that the leading directory path is\n>> without funny symlinks by seeing a/, a/b/, a/b/c/ and then a/b/c/d/\n>> are all without funny symlinks, by calling has_dirs_only_path() in\n>> this order.\n>>\n>> When we are checking out many files (imagine: initial checkout),\n>> however, it is likely that an earlier checkout would have already\n>> made sure that the leading directory a/b/c/d/ is in good order; by\n>> first checking the whole path a/b/c/d/ first, we can often bypass\n>> calls to has_dirs_only_path() for leading part.\n>\n> Naively one would think that this is just as much work -- to correctly\n> verify that the path consist only of actual directories (not symlinks)\n> we have to lstat() every component regardless. It seems the reason this\n> is an optimization is that has_dirs_only_path() caches its results, so\n> that we can get 'a/b/c/d/ is okay in every component' from the cache.\n>\n> Is this analysis correct? If so, can you spell that out in the commit\n> message?\n\nIt was done without analysis ;-) but I think you are correct.\n\nIf you are checking out a/b/c/d/{m,a,n,y}, after you checked out\na/b/c/d/m, the has_dirs_only_path cache knows a/b/c/d/ is in good\norder so when you check out a/b/c/d/{a,n,y}, we can just ask for\na/b/c/d/ and get an OK immediately. There is no point asking from\na/, a/b/, a/b/c/ and then a/b/c/d/, in the original pessimistic\norder. A change done _right_ to properly optimize this might even\nwant to change the main loop that the patch bypassed.\n\nI do not think the patch (or the \"change done right\" for that\nmatter) will make much difference on a platform with good filesystem\nmetadata caching. It may be very interesting to see if that simple\npatch makes any difference on Windows, though. If it does, then we\nmay want to look into cleaning up the code further.\n\nThanks for a comment.\n"}]}