{"thread":{"id":"38823","subject":"[PATCH] refs.c: get_ref_cache: use a bucket hash","startedAt":"2015-03-16T14:20:26Z","lastAt":"2015-11-16T16:31:30Z","messageCount":12,"participants":["Andreas Krey","Thomas Gummerer","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"257784","messageId":"20150316142026.GJ7847@inner.h.apk.li","threadId":"38823","inReplyTo":null,"subject":"[PATCH] refs.c: get_ref_cache: use a bucket hash","fromName":"Andreas Krey","fromEmail":"a.krey@gmx.de","sentAt":"2015-03-16T14:20:26Z","receivedAt":"2015-03-16T14:20:26Z","isPatch":true,"sender":{"key":"a.krey@gmx.de","avatar":"https://avatars.githubusercontent.com/u/37810?v=4"},"body":"get_ref_cache used a linear list, which obviously is O(n^2).\nUse a fixed bucket hash which just takes a factor of 100000\n(~ 317^2) out of the n^2 - which is enough.\n\nSigned-off-by: Andreas Krey <a.krey@gmx.de>\n---\n\nThis brings 'git clean -ndx' times down from 17 minutes\nto 11 seconds on one of our workspaces (which accumulated\na lot of ignored directories). Actuallly using adaptive\nhashing or other structures seems overkill.\n\n refs.c | 13 ++++++++-----\n 1 file changed, 8 insertions(+), 5 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex e23542b..8198d9e 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -982,6 +982,8 @@ struct packed_ref_cache {\n \tstruct stat_validity validity;\n };\n \n+#define REF_CACHE_HASH 317\n+\n /*\n  * Future: need to be in \"struct repository\"\n  * when doing a full libification.\n@@ -996,7 +998,7 @@ static struct ref_cache {\n \t * is initialized correctly.\n \t */\n \tchar name[1];\n-} ref_cache, *submodule_ref_caches;\n+} ref_cache, *submodule_ref_caches[REF_CACHE_HASH];\n \n /* Lock used for the main packed-refs file: */\n static struct lock_file packlock;\n@@ -1065,18 +1067,19 @@ static struct ref_cache *create_ref_cache(const char *submodule)\n  */\n static struct ref_cache *get_ref_cache(const char *submodule)\n {\n-\tstruct ref_cache *refs;\n+\tstruct ref_cache *refs, **bucketp;\n+\tbucketp = submodule_ref_caches + strhash(submodule) % REF_CACHE_HASH;\n \n \tif (!submodule || !*submodule)\n \t\treturn &ref_cache;\n \n-\tfor (refs = submodule_ref_caches; refs; refs = refs->next)\n+\tfor (refs = *bucketp; refs; refs = refs->next)\n \t\tif (!strcmp(submodule, refs->name))\n \t\t\treturn refs;\n \n \trefs = create_ref_cache(submodule);\n-\trefs->next = submodule_ref_caches;\n-\tsubmodule_ref_caches = refs;\n+\trefs->next = *bucketp;\n+\t*bucketp = refs;\n \treturn refs;\n }\n \n-- \n2.3.2.223.g7a9409c\n"},{"id":"257802","messageId":"20150316171909.GA8618@hank","threadId":"38823","inReplyTo":"20150316142026.GJ7847@inner.h.apk.li","subject":"Re: [PATCH] refs.c: get_ref_cache: use a bucket hash","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2015-03-16T17:19:10Z","receivedAt":"2015-03-16T17:19:10Z","isPatch":true,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"Hi,\n\nOn 03/16, Andreas Krey wrote:\n> get_ref_cache used a linear list, which obviously is O(n^2).\n> Use a fixed bucket hash which just takes a factor of 100000\n> (~ 317^2) out of the n^2 - which is enough.\n>\n> Signed-off-by: Andreas Krey <a.krey@gmx.de>\n> ---\n>\n> This brings 'git clean -ndx' times down from 17 minutes\n> to 11 seconds on one of our workspaces (which accumulated\n> a lot of ignored directories). Actuallly using adaptive\n> hashing or other structures seems overkill.\n>\n>  refs.c | 13 ++++++++-----\n>  1 file changed, 8 insertions(+), 5 deletions(-)\n>\n> diff --git a/refs.c b/refs.c\n> index e23542b..8198d9e 100644\n> --- a/refs.c\n> +++ b/refs.c\n> @@ -982,6 +982,8 @@ struct packed_ref_cache {\n>  \tstruct stat_validity validity;\n>  };\n>\n> +#define REF_CACHE_HASH 317\n> +\n>  /*\n>   * Future: need to be in \"struct repository\"\n>   * when doing a full libification.\n> @@ -996,7 +998,7 @@ static struct ref_cache {\n>  \t * is initialized correctly.\n>  \t */\n>  \tchar name[1];\n> -} ref_cache, *submodule_ref_caches;\n> +} ref_cache, *submodule_ref_caches[REF_CACHE_HASH];\n>\n>  /* Lock used for the main packed-refs file: */\n>  static struct lock_file packlock;\n> @@ -1065,18 +1067,19 @@ static struct ref_cache *create_ref_cache(const char *submodule)\n>   */\n>  static struct ref_cache *get_ref_cache(const char *submodule)\n>  {\n> -\tstruct ref_cache *refs;\n> +\tstruct ref_cache *refs, **bucketp;\n> +\tbucketp = submodule_ref_caches + strhash(submodule) % REF_CACHE_HASH;\n>\n\nThis breaks the test-suite for me, in the cases where submodule is\nNULL.  How about something like this on top?\n\ndiff --git a/refs.c b/refs.c\nindex 8198d9e..311faf2 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1068,7 +1068,9 @@ static struct ref_cache *create_ref_cache(const char *submodule)\n static struct ref_cache *get_ref_cache(const char *submodule)\n {\n        struct ref_cache *refs, **bucketp;\n-       bucketp = submodule_ref_caches + strhash(submodule) % REF_CACHE_HASH;\n+       bucketp = submodule_ref_caches;\n+       if (submodule)\n+               bucketp += strhash(submodule) % REF_CACHE_HASH;\n\n        if (!submodule || !*submodule)\n                return &ref_cache;\n\n>  \tif (!submodule || !*submodule)\n>  \t\treturn &ref_cache;\n>\n> -\tfor (refs = submodule_ref_caches; refs; refs = refs->next)\n> +\tfor (refs = *bucketp; refs; refs = refs->next)\n>  \t\tif (!strcmp(submodule, refs->name))\n>  \t\t\treturn refs;\n>\n>  \trefs = create_ref_cache(submodule);\n> -\trefs->next = submodule_ref_caches;\n> -\tsubmodule_ref_caches = refs;\n> +\trefs->next = *bucketp;\n> +\t*bucketp = refs;\n>  \treturn refs;\n>  }\n>\n> --\n> 2.3.2.223.g7a9409c\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at  http://vger.kernel.org/majordomo-info.html\n"},{"id":"257803","messageId":"xmqq1tkosvpi.fsf@gitster.dls.corp.google.com","threadId":"38823","inReplyTo":"20150316142026.GJ7847@inner.h.apk.li","subject":"Re: [PATCH] refs.c: get_ref_cache: use a bucket hash","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-03-16T17:23:05Z","receivedAt":"2015-03-16T17:23:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Andreas Krey <a.krey@gmx.de> writes:\n\n> get_ref_cache used a linear list, which obviously is O(n^2).\n> Use a fixed bucket hash which just takes a factor of 100000\n> (~ 317^2) out of the n^2 - which is enough.\n>\n> Signed-off-by: Andreas Krey <a.krey@gmx.de>\n> ---\n>\n> This brings 'git clean -ndx' times down from 17 minutes\n> to 11 seconds on one of our workspaces (which accumulated\n> a lot of ignored directories).\n\nNice.\n\nThese impressive numbers should go to the commit log message,\ntogether with a bit more numbers to characterise the shape of the\nrepository that exhibits the problem with the original code.  You\nsay \"a lot of ignored directories\", but do you mean directories in\nthe working tree (which I suppose do not have much to do with the\nsubmodule_ref_caches[])?  I am guessing that the repository has tons\nof submodules?  How many is \"tons\" to make the pain noticeable?\n\n> Actuallly using adaptive\n> hashing or other structures seems overkill.\n\nPerhaps _implementing_ these structures only for this codepath may\nbe overkill, but would it be an overkill to _use_ existing hashmap.c\nimplementation?  After all, those who wrote the original would have\nthought that anything more complex than a linear list would be\noverkill, and nobody disagreed until you found that your repository\ndisagreed with that assumption ;-)\n\n>  refs.c | 13 ++++++++-----\n>  1 file changed, 8 insertions(+), 5 deletions(-)\n>\n> diff --git a/refs.c b/refs.c\n> index e23542b..8198d9e 100644\n> --- a/refs.c\n> +++ b/refs.c\n> @@ -982,6 +982,8 @@ struct packed_ref_cache {\n>  \tstruct stat_validity validity;\n>  };\n>  \n> +#define REF_CACHE_HASH 317\n> +\n>  /*\n>   * Future: need to be in \"struct repository\"\n>   * when doing a full libification.\n> @@ -996,7 +998,7 @@ static struct ref_cache {\n>  \t * is initialized correctly.\n>  \t */\n>  \tchar name[1];\n> -} ref_cache, *submodule_ref_caches;\n> +} ref_cache, *submodule_ref_caches[REF_CACHE_HASH];\n>  \n>  /* Lock used for the main packed-refs file: */\n>  static struct lock_file packlock;\n> @@ -1065,18 +1067,19 @@ static struct ref_cache *create_ref_cache(const char *submodule)\n>   */\n>  static struct ref_cache *get_ref_cache(const char *submodule)\n>  {\n> -\tstruct ref_cache *refs;\n> +\tstruct ref_cache *refs, **bucketp;\n> +\tbucketp = submodule_ref_caches + strhash(submodule) % REF_CACHE_HASH;\n>  \n>  \tif (!submodule || !*submodule)\n>  \t\treturn &ref_cache;\n>  \n> -\tfor (refs = submodule_ref_caches; refs; refs = refs->next)\n> +\tfor (refs = *bucketp; refs; refs = refs->next)\n>  \t\tif (!strcmp(submodule, refs->name))\n>  \t\t\treturn refs;\n>  \n>  \trefs = create_ref_cache(submodule);\n> -\trefs->next = submodule_ref_caches;\n> -\tsubmodule_ref_caches = refs;\n> +\trefs->next = *bucketp;\n> +\t*bucketp = refs;\n>  \treturn refs;\n>  }\n"},{"id":"257809","messageId":"20150316184040.GA8902@inner.h.apk.li","threadId":"38823","inReplyTo":"xmqq1tkosvpi.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] refs.c: get_ref_cache: use a bucket hash","fromName":"Andreas Krey","fromEmail":"a.krey@gmx.de","sentAt":"2015-03-16T18:40:40Z","receivedAt":"2015-03-16T18:40:40Z","isPatch":true,"sender":{"key":"a.krey@gmx.de","avatar":"https://avatars.githubusercontent.com/u/37810?v=4"},"body":"On Mon, 16 Mar 2015 10:23:05 +0000, Junio C Hamano wrote:\n> Andreas Krey <a.krey@gmx.de> writes:\n> \n...\n> say \"a lot of ignored directories\", but do you mean directories in\n> the working tree (which I suppose do not have much to do with the\n> submodule_ref_caches[])?\n\nApparently, they do.\n\n>I am guessing that the repository has tons\n> of submodules?\n\nNot a single one. Thats's thie interesting thing that\nmakes me think I'm not actually solving the right problem.\n\nThis repo has about 100k subdirectories that are ignored\n(I don't know whether directly or within ignored dirs),\nand strace said that git looks for '.git/HEAD' and one\nother file in each of these. Apparently it trieds to\nfind out if any of these dirs happen to be a git repo\nwhich git clean treats specially, but it seems it also\ncalls get_ref_cache for each of these dires even though\nthe turn out not to be a sub-repo.\n\nIn other words: I suspect that get_ref_cache shouldn't\nbe called that often, or that the cache entries should\nbe removed once a directory is found not to be a sub repo.\nThen the linear list wouldn't really hurt.\n\nI'll look into that tomorrow, and also into the hashmap API.\n\nAndreas\n\n-- \n\"Totally trivial. Famous last words.\"\nFrom: Linus Torvalds <torvalds@*.org>\nDate: Fri, 22 Jan 2010 07:29:21 -0800\n"},{"id":"257827","messageId":"20150317024005.GA26313@peff.net","threadId":"38823","inReplyTo":"20150316184040.GA8902@inner.h.apk.li","subject":"Re: [PATCH] refs.c: get_ref_cache: use a bucket hash","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-03-17T02:40:05Z","receivedAt":"2015-03-17T02:40:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"[+cc Michael for get_ref_cache wisdom]\n\nOn Mon, Mar 16, 2015 at 07:40:40PM +0100, Andreas Krey wrote:\n\n> >I am guessing that the repository has tons\n> > of submodules?\n> \n> Not a single one. Thats's thie interesting thing that\n> makes me think I'm not actually solving the right problem.\n> \n> This repo has about 100k subdirectories that are ignored\n> (I don't know whether directly or within ignored dirs),\n> and strace said that git looks for '.git/HEAD' and one\n> other file in each of these. Apparently it trieds to\n> find out if any of these dirs happen to be a git repo\n> which git clean treats specially, but it seems it also\n> calls get_ref_cache for each of these dires even though\n> the turn out not to be a sub-repo.\n> \n> In other words: I suspect that get_ref_cache shouldn't\n> be called that often, or that the cache entries should\n> be removed once a directory is found not to be a sub repo.\n> Then the linear list wouldn't really hurt.\n\nYeah, I'd agree.\n\nThe get_ref_cache code was designed to scale to the actual number of\nsubmodules. I do not mind seeing it become a hash if people really do\nhave a large number of submodules, but that is not what is happening\nhere.\n\nBisecting, it looks like things got slow for your case starting in\nf538a91 (git-clean: Display more accurate delete messages, 2013-01-11).\nI reproduced with basically:\n\n  git init\n  for i in $(seq 30000); do mkdir $i; done\n  time git clean -nd >/dev/null\n\nIt jumps in that commit from ~50ms to ~3000ms.\n\nA backtrace from get_ref_cache shows:\n\n  #0  get_ref_cache (submodule=0xa6a4f0 \"1\") at refs.c:1070\n  #1  0x0000000000516469 in resolve_gitlink_ref (path=0xa6a4d0 \"1/\", refname=0x584822 \"HEAD\", \n      sha1=0x7fffffffde90 \"\\002\") at refs.c:1429\n  #2  0x0000000000423584 in remove_dirs (path=0x7fffffffe2f0, prefix=0x0, force_flag=2, dry_run=1, quiet=0, \n      dir_gone=0x7fffffffe314) at builtin/clean.c:164\n  #3  0x00000000004255a9 in cmd_clean (argc=0, argv=0x7fffffffe5e0, prefix=0x0) at builtin/clean.c:981\n  #4  0x0000000000405554 in run_builtin (p=0x7f7b18 <commands+408>, argc=2, argv=0x7fffffffe5e0) at git.c:348\n  #5  0x0000000000405761 in handle_builtin (argc=2, argv=0x7fffffffe5e0) at git.c:530\n  #6  0x000000000040587d in run_argv (argcp=0x7fffffffe4cc, argv=0x7fffffffe4d8) at git.c:576\n  #7  0x0000000000405a6e in main (argc=2, av=0x7fffffffe5d8) at git.c:685\n\nSo git-clean speculatively asks \"what is HEAD in this maybe-submodule?\". The\nright solution is probably one of:\n\n  1. In remove_dirs, find out if we have an actual submodule before calling\n     resolve_gitlink_ref.\n\n  2. Teach get_ref_cache a \"read-only\" mode that will not auto-vivify the cache\n     if it does not already exist.\n\nOf the two, I think (1) is probably cleaner (I think the way the ref\ncode is structured, we have to create the submodule ref_cache in order\nto start looking things up in it).\n\nIt looks like we don't even really care about the value of HEAD. We just\nwant to know \"is it a git directory?\". I think in other places (like\n\"git add\"), we just do an existence check for \"$dir/.git\". That would\nnot catch a bare repository, but I do not think the current check does\neither (it is looking for submodules, which always have a .git).\n\nMaybe something like (largely untested):\n\ndiff --git a/builtin/clean.c b/builtin/clean.c\nindex 98c103f..e2cc47b 100644\n--- a/builtin/clean.c\n+++ b/builtin/clean.c\n@@ -148,6 +148,32 @@ static int exclude_cb(const struct option *opt, const char *arg, int unset)\n \treturn 0;\n }\n \n+static int dir_is_repo(struct strbuf *path)\n+{\n+\tsize_t orig = path->len;\n+\tint ret;\n+\n+\tstrbuf_addstr(path, \"/.git\");\n+\tif (!access(path->buf, F_OK))\n+\t\tret = 1; /* definitely */\n+\telse if (errno == ENOENT)\n+\t\tret = 0; /* definitely not */\n+\telse {\n+\t\t/*\n+\t\t * We couldn't tell. It would probably be safer to err\n+\t\t * on the side of saying \"yes\" here, because we are\n+\t\t * deciding what to delete, and are more likely to keep\n+\t\t * a sub-repo. But it would probably also create annoying\n+\t\t * false positives, where a directory we do not have\n+\t\t * permission to read would say something misleading\n+\t\t * like \"not deleting sub-repo foo...\"\n+\t\t */\n+\t\tret = 0;\n+\t}\n+\tstrbuf_setlen(path, orig);\n+\treturn ret;\n+}\n+\n static int remove_dirs(struct strbuf *path, const char *prefix, int force_flag,\n \t\tint dry_run, int quiet, int *dir_gone)\n {\n@@ -155,13 +181,11 @@ static int remove_dirs(struct strbuf *path, const char *prefix, int force_flag,\n \tstruct strbuf quoted = STRBUF_INIT;\n \tstruct dirent *e;\n \tint res = 0, ret = 0, gone = 1, original_len = path->len, len;\n-\tunsigned char submodule_head[20];\n \tstruct string_list dels = STRING_LIST_INIT_DUP;\n \n \t*dir_gone = 1;\n \n-\tif ((force_flag & REMOVE_DIR_KEEP_NESTED_GIT) &&\n-\t\t\t!resolve_gitlink_ref(path->buf, \"HEAD\", submodule_head)) {\n+\tif ((force_flag & REMOVE_DIR_KEEP_NESTED_GIT) && dir_is_repo(path)) {\n \t\tif (!quiet) {\n \t\t\tquote_path_relative(path->buf, prefix, &quoted);\n \t\t\tprintf(dry_run ?  _(msg_would_skip_git_dir) : _(msg_skip_git_dir),\n"},{"id":"257832","messageId":"xmqqd248p4o9.fsf@gitster.dls.corp.google.com","threadId":"38823","inReplyTo":"20150317024005.GA26313@peff.net","subject":"Re: [PATCH] refs.c: get_ref_cache: use a bucket hash","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-03-17T05:35:18Z","receivedAt":"2015-03-17T05:35:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> The get_ref_cache code was designed to scale to the actual number of\n> submodules. I do not mind seeing it become a hash if people really do\n> have a large number of submodules, but that is not what is happening\n> here.\n> ...\n> So git-clean speculatively asks \"what is HEAD in this maybe-submodule?\". The\n> right solution is probably one of:\n>\n>   1. In remove_dirs, find out if we have an actual submodule before calling\n>      resolve_gitlink_ref.\n>\n>   2. Teach get_ref_cache a \"read-only\" mode that will not auto-vivify the cache\n>      if it does not already exist.\n>\n> Of the two, I think (1) is probably cleaner (I think the way the ref\n> code is structured, we have to create the submodule ref_cache in order\n> to start looking things up in it).\n\nThanks for a great analysis.  I too wondered if we should be growing\nthe per-submodule ref-cache when we are only probing.\n\n> It looks like we don't even really care about the value of HEAD. We just\n> want to know \"is it a git directory?\". I think in other places (like\n> \"git add\"), we just do an existence check for \"$dir/.git\". That would\n> not catch a bare repository, but I do not think the current check does\n> either (it is looking for submodules, which always have a .git).\n\nIf we wanted to be consistent, perhaps we should be reusing the \"is\nthis a git repository?\" check used by the auto-discovery codepath\n(setup.c:is_git_directory(), perhaps?), but the idea looks simple\nenough and sounds sensible.\n\n> Maybe something like (largely untested):\n>\n> diff --git a/builtin/clean.c b/builtin/clean.c\n> index 98c103f..e2cc47b 100644\n> --- a/builtin/clean.c\n> +++ b/builtin/clean.c\n> @@ -148,6 +148,32 @@ static int exclude_cb(const struct option *opt, const char *arg, int unset)\n>  \treturn 0;\n>  }\n>  \n> +static int dir_is_repo(struct strbuf *path)\n> +{\n> +\tsize_t orig = path->len;\n> +\tint ret;\n> +\n> +\tstrbuf_addstr(path, \"/.git\");\n> +\tif (!access(path->buf, F_OK))\n> +\t\tret = 1; /* definitely */\n> +\telse if (errno == ENOENT)\n> +\t\tret = 0; /* definitely not */\n> +\telse {\n> +\t\t/*\n> +\t\t * We couldn't tell. It would probably be safer to err\n> +\t\t * on the side of saying \"yes\" here, because we are\n> +\t\t * deciding what to delete, and are more likely to keep\n> +\t\t * a sub-repo. But it would probably also create annoying\n> +\t\t * false positives, where a directory we do not have\n> +\t\t * permission to read would say something misleading\n> +\t\t * like \"not deleting sub-repo foo...\"\n> +\t\t */\n> +\t\tret = 0;\n> +\t}\n> +\tstrbuf_setlen(path, orig);\n> +\treturn ret;\n> +}\n> +\n>  static int remove_dirs(struct strbuf *path, const char *prefix, int force_flag,\n>  \t\tint dry_run, int quiet, int *dir_gone)\n>  {\n> @@ -155,13 +181,11 @@ static int remove_dirs(struct strbuf *path, const char *prefix, int force_flag,\n>  \tstruct strbuf quoted = STRBUF_INIT;\n>  \tstruct dirent *e;\n>  \tint res = 0, ret = 0, gone = 1, original_len = path->len, len;\n> -\tunsigned char submodule_head[20];\n>  \tstruct string_list dels = STRING_LIST_INIT_DUP;\n>  \n>  \t*dir_gone = 1;\n>  \n> -\tif ((force_flag & REMOVE_DIR_KEEP_NESTED_GIT) &&\n> -\t\t\t!resolve_gitlink_ref(path->buf, \"HEAD\", submodule_head)) {\n> +\tif ((force_flag & REMOVE_DIR_KEEP_NESTED_GIT) && dir_is_repo(path)) {\n>  \t\tif (!quiet) {\n>  \t\t\tquote_path_relative(path->buf, prefix, &quoted);\n>  \t\t\tprintf(dry_run ?  _(msg_would_skip_git_dir) : _(msg_skip_git_dir),\n"},{"id":"257833","messageId":"20150317054759.GA16860@peff.net","threadId":"38823","inReplyTo":"xmqqd248p4o9.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH] refs.c: get_ref_cache: use a bucket hash","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-03-17T05:48:00Z","receivedAt":"2015-03-17T05:48:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Mar 16, 2015 at 10:35:18PM -0700, Junio C Hamano wrote:\n\n> > It looks like we don't even really care about the value of HEAD. We just\n> > want to know \"is it a git directory?\". I think in other places (like\n> > \"git add\"), we just do an existence check for \"$dir/.git\". That would\n> > not catch a bare repository, but I do not think the current check does\n> > either (it is looking for submodules, which always have a .git).\n> \n> If we wanted to be consistent, perhaps we should be reusing the \"is\n> this a git repository?\" check used by the auto-discovery codepath\n> (setup.c:is_git_directory(), perhaps?), but the idea looks simple\n> enough and sounds sensible.\n\nYeah, I almost suggested that, but I'm concerned that would make us\ninconsistent with how we report untracked files. I thought that dir.c\nused \".git\" as a magic token there.\n\nBut it seems I'm wrong. We do ignore \".git\" directly in treat_path(),\nbut treat_directory actually checks resolve_gitlink_ref. I think this\nwill suffer the same problem as Andreas's original issue (e.g., if you\nrun \"git ls-files -o\").\n\nLikewise, I think dir.c:remove_dir_recurse is in a similar boat.\nGrepping for resolve_gitlink_ref, it looks like there may be others,\ntoo.\n\nAll of these should be using the same test, I think. Doing that with\nis_git_directory() is probably OK. It is a little more expensive than we\nmight want for mass-use (it actually opens and parses the HEAD file in\neach directory), but it quits early when we _don't_ see a git directory,\nwhich would be the common case here.\n\n-Peff\n"},{"id":"273280","messageId":"20151113152915.GC16219@inner.h.apk.li","threadId":"38823","inReplyTo":"20150317054759.GA16860@peff.net","subject":"Re: [PATCH] refs.c: get_ref_cache: use a bucket hash","fromName":"Andreas Krey","fromEmail":"a.krey@gmx.de","sentAt":"2015-11-13T15:29:15Z","receivedAt":"2015-11-13T15:29:15Z","isPatch":true,"sender":{"key":"a.krey@gmx.de","avatar":"https://avatars.githubusercontent.com/u/37810?v=4"},"body":"On Tue, 17 Mar 2015 01:48:00 +0000, Jeff King wrote:\n> On Mon, Mar 16, 2015 at 10:35:18PM -0700, Junio C Hamano wrote:\n> \n> > > It looks like we don't even really care about the value of HEAD. We just\n> > > want to know \"is it a git directory?\". I think in other places (like\n> > > \"git add\"), we just do an existence check for \"$dir/.git\". That would\n> > > not catch a bare repository, but I do not think the current check does\n> > > either (it is looking for submodules, which always have a .git).\n> > \n> > If we wanted to be consistent, perhaps we should be reusing the \"is\n> > this a git repository?\" check used by the auto-discovery codepath\n> > (setup.c:is_git_directory(), perhaps?), but the idea looks simple\n> > enough and sounds sensible.\n> \n> Yeah, I almost suggested that, but I'm concerned that would make us\n> inconsistent with how we report untracked files. I thought that dir.c\n> used \".git\" as a magic token there.\n> \n> But it seems I'm wrong. We do ignore \".git\" directly in treat_path(),\n> but treat_directory actually checks resolve_gitlink_ref. I think this\n> will suffer the same problem as Andreas's original issue (e.g., if you\n> run \"git ls-files -o\").\n\nGuess what landed on my desk this week. Same repo, same\napplication test suite, same problem, now with 'git ls-files -o'.\n\n> Likewise, I think dir.c:remove_dir_recurse is in a similar boat.\n> Grepping for resolve_gitlink_ref, it looks like there may be others,\n> too.\n\nCan't we handle this in resolve_gitlink_ref itself? As I understand it,\nit should resolve a ref (here \"HEAD\") when path points to a submodule.\nWhen there isn't one it should return -1, so:\n\ndiff --git a/refs.c b/refs.c\nindex 132eff5..f8648c5 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1553,6 +1553,10 @@ int resolve_gitlink_ref(const char *path, const char *refname, unsigned char *sh\n \tif (!len)\n \t\treturn -1;\n \tsubmodule = xstrndup(path, len);\n+\tif (!is_git_directory(submodule)) {\n+\t\tfree(submodule);\n+\t\treturn -1;\n+\t}\n \trefs = get_ref_cache(submodule);\n \tfree(submodule);\n\nI'm way too little into the code to see what may this may get wrong.\n\nBut this, as well as the old hash-ref-cache patch speeds me\nup considerably, in this case a git ls-files -o from half a\nminute of mostly user CPU to a second.\n\n> All of these should be using the same test, I think. Doing that with\n> is_git_directory() is probably OK. It is a little more expensive than we\n> might want for mass-use (it actually opens and parses the HEAD file in\n> each directory),\n\nThis happens as well when we let resolve_gitlink_ref run its old course.\n(It (ls-files) even seems to try to open .git and then .git/HEAD, even\nif the former fails with ENOENT.)\n\nAndreas\n\n-- \n\"Totally trivial. Famous last words.\"\nFrom: Linus Torvalds <torvalds@*.org>\nDate: Fri, 22 Jan 2010 07:29:21 -0800\n"},{"id":"273304","messageId":"20151114000118.GB18260@sigill.intra.peff.net","threadId":"38823","inReplyTo":"20151113152915.GC16219@inner.h.apk.li","subject":"Re: [PATCH] refs.c: get_ref_cache: use a bucket hash","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-11-14T00:01:18Z","receivedAt":"2015-11-14T00:01:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 13, 2015 at 04:29:15PM +0100, Andreas Krey wrote:\n\n> > Likewise, I think dir.c:remove_dir_recurse is in a similar boat.\n> > Grepping for resolve_gitlink_ref, it looks like there may be others,\n> > too.\n> \n> Can't we handle this in resolve_gitlink_ref itself? As I understand it,\n> it should resolve a ref (here \"HEAD\") when path points to a submodule.\n> When there isn't one it should return -1, so:\n\nI'm not sure. I think part of the change to git-clean was that\nis_git_directory() is a _better_ check than \"can we resolve HEAD?\"\nbecause it covers empty repos, too.\n\n> diff --git a/refs.c b/refs.c\n> index 132eff5..f8648c5 100644\n> --- a/refs.c\n> +++ b/refs.c\n> @@ -1553,6 +1553,10 @@ int resolve_gitlink_ref(const char *path, const char *refname, unsigned char *sh\n>  \tif (!len)\n>  \t\treturn -1;\n>  \tsubmodule = xstrndup(path, len);\n> +\tif (!is_git_directory(submodule)) {\n> +\t\tfree(submodule);\n> +\t\treturn -1;\n> +\t}\n>  \trefs = get_ref_cache(submodule);\n>  \tfree(submodule);\n> \n> I'm way too little into the code to see what may this may get wrong.\n\nI don't think it produces wrong outcomes, but I think it's sub-optimal.\nIn cases where we already have a ref cache, we'll hit the filesystem for\neach lookup to re-confirm what we already know. That doesn't affect your\ncase, but it does when we actually _do_ have a submodule.\n\nSo if we were to follow this route, I think it would go better in\nget_ref_cache itself (right after we determine there is no existing\ncache, but before we call create_ref_cache()).\n\n> But this, as well as the old hash-ref-cache patch speeds me\n> up considerably, in this case a git ls-files -o from half a\n> minute of mostly user CPU to a second.\n\nRight, that makes sense to me.\n\n> > All of these should be using the same test, I think. Doing that with\n> > is_git_directory() is probably OK. It is a little more expensive than we\n> > might want for mass-use (it actually opens and parses the HEAD file in\n> > each directory),\n> \n> This happens as well when we let resolve_gitlink_ref run its old course.\n> (It (ls-files) even seems to try to open .git and then .git/HEAD, even\n> if the former fails with ENOENT.)\n\nYes, I think my earlier comment that you are quoting was just misguided.\nWe only do the extra work if the directory actually does look like a\ngitdir, and the many-directories case we are optimizing here is the\nopposite of that.\n\nSo summing up, I think:\n\n  1. We could get by with teaching get_ref_cache not to auto-create ref\n     caches for non-git-directories.\n\n  2. But for a little more work, pushing the is_git_directory() check\n     out to the call-sites gives us probably saner semantics overall.\n\n-Peff\n"},{"id":"273332","messageId":"20151114132209.GH16219@inner.h.apk.li","threadId":"38823","inReplyTo":"20151114000118.GB18260@sigill.intra.peff.net","subject":"Re: [PATCH] refs.c: get_ref_cache: use a bucket hash","fromName":"Andreas Krey","fromEmail":"a.krey@gmx.de","sentAt":"2015-11-14T13:22:09Z","receivedAt":"2015-11-14T13:22:09Z","isPatch":true,"sender":{"key":"a.krey@gmx.de","avatar":"https://avatars.githubusercontent.com/u/37810?v=4"},"body":"On Fri, 13 Nov 2015 19:01:18 +0000, Jeff King wrote:\n....\n> > Can't we handle this in resolve_gitlink_ref itself? As I understand it,\n> > it should resolve a ref (here \"HEAD\") when path points to a submodule.\n> > When there isn't one it should return -1, so:\n> \n> I'm not sure. I think part of the change to git-clean was that\n> is_git_directory() is a _better_ check than \"can we resolve HEAD?\"\n> because it covers empty repos, too.\n\nI could do\n\n  refs = find_ref_cache(submodule);\n  if (!refs && !is_git_directory(....\n\nin resolve_gitlink_ref().\n\n...\n> > @@ -1553,6 +1553,10 @@ int resolve_gitlink_ref(const char *path, const char *refname, unsigned char *sh\n> >  \tif (!len)\n> >  \t\treturn -1;\n> >  \tsubmodule = xstrndup(path, len);\n> > +\tif (!is_git_directory(submodule)) {\n> > +\t\tfree(submodule);\n> > +\t\treturn -1;\n> > +\t}\n> >  \trefs = get_ref_cache(submodule);\n> >  \tfree(submodule);\n> \n> I don't think it produces wrong outcomes, but I think it's sub-optimal.\n> In cases where we already have a ref cache, we'll hit the filesystem for\n> each lookup to re-confirm what we already know. That doesn't affect your\n> case, but it does when we actually _do_ have a submodule.\n\nI could do\n\n  refs = find_ref_cache(submodule);\n  if (!refs && !is_git_directory(....\n\nAlso, in my case the current code tries .git/HEAD and .git/packed-refs\nfor each directory.\n\n> So if we were to follow this route, I think it would go better in\n> get_ref_cache itself (right after we determine there is no existing\n> cache, but before we call create_ref_cache()).\n\nThe stupid part is that get_ref_cache itself only creates the\ncache entry and leaved the actual check for later - then it\nis too late to not create the cache entry.\n\nAlso, when we put it into get_ref_cache we need to return null\nfor our case and see what for_each_ref_submodule & co make out of that.\nThat's why I'd like it in resolve_gitlink_ref. :-) Or we put an\nno_create parameter into get_ref_cache(). Probably violating\nsome style guide:\n\ndiff --git a/refs.c b/refs.c\nindex 132eff5..005d0eb 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1160,7 +1160,7 @@ static struct ref_cache *create_ref_cache(const char *submodule)\n  * will be allocated and initialized but not necessarily populated; it\n  * should not be freed.\n  */\n-static struct ref_cache *get_ref_cache(const char *submodule)\n+static struct ref_cache *get_ref_cache(const char *submodule, int do_create)\n {\n \tstruct ref_cache *refs;\n \n@@ -1171,6 +1171,9 @@ static struct ref_cache *get_ref_cache(const char *submodule)\n \t\tif (!strcmp(submodule, refs->name))\n \t\t\treturn refs;\n \n+\tif (!do_create && !is_git_directory(submodule))\n+\t\treturn 0;\n+\n \trefs = create_ref_cache(submodule);\n \trefs->next = submodule_ref_caches;\n \tsubmodule_ref_caches = refs;\n@@ -1553,9 +1556,12 @@ int resolve_gitlink_ref(const char *path, const char *refname, unsigned char *sh\n \tif (!len)\n \t\treturn -1;\n \tsubmodule = xstrndup(path, len);\n-\trefs = get_ref_cache(submodule);\n+\trefs = get_ref_cache(submodule, 0);\n \tfree(submodule);\n \n+\tif (!refs)\n+\t\treturn -1;\n+\n \tretval = resolve_gitlink_ref_recursive(refs, refname, sha1, 0);\n \treturn retval;\n }\n@@ -2126,7 +2132,7 @@ int for_each_ref(each_ref_fn fn, void *cb_data)\n \n int for_each_ref_submodule(const char *submodule, each_ref_fn fn, void *cb_data)\n {\n-\treturn do_for_each_ref(get_ref_cache(submodule), \"\", fn, 0, 0, cb_data);\n+\treturn do_for_each_ref(get_ref_cache(submodule, 1), \"\", fn, 0, 0, cb_data);\n }\n \n int for_each_ref_in(const char *prefix, each_ref_fn fn, void *cb_data)\n@@ -2146,7 +2152,7 @@ int for_each_fullref_in(const char *prefix, each_ref_fn fn, void *cb_data, unsig\n int for_each_ref_in_submodule(const char *submodule, const char *prefix,\n \t\teach_ref_fn fn, void *cb_data)\n {\n-\treturn do_for_each_ref(get_ref_cache(submodule), prefix, fn, strlen(prefix), 0, cb_data);\n+\treturn do_for_each_ref(get_ref_cache(submodule, 1), prefix, fn, strlen(prefix), 0, cb_data);\n }\n \n int for_each_tag_ref(each_ref_fn fn, void *cb_data)\n\n(might be nicer to split into find_ref_cache() and get_ref_cache()\ninstead of adding the parameter).\n\n...\n>   2. But for a little more work, pushing the is_git_directory() check\n>      out to the call-sites gives us probably saner semantics overall.\n\nActually, I don't quite think that. The code we push out would be\nthe same in each place ('is_git_directory() && ...'), wouldn't it?\n\nAndreas\n\n-- \n\"Totally trivial. Famous last words.\"\nFrom: Linus Torvalds <torvalds@*.org>\nDate: Fri, 22 Jan 2010 07:29:21 -0800\n"},{"id":"273333","messageId":"20151114133501.GI16219@inner.h.apk.li","threadId":"38823","inReplyTo":"20151114000118.GB18260@sigill.intra.peff.net","subject":"Re: [PATCH] refs.c: get_ref_cache: use a bucket hash","fromName":"Andreas Krey","fromEmail":"a.krey@gmx.de","sentAt":"2015-11-14T13:35:01Z","receivedAt":"2015-11-14T13:35:01Z","isPatch":true,"sender":{"key":"a.krey@gmx.de","avatar":"https://avatars.githubusercontent.com/u/37810?v=4"},"body":"On Fri, 13 Nov 2015 19:01:18 +0000, Jeff King wrote:\n...\n>   2. But for a little more work, pushing the is_git_directory() check\n>      out to the call-sites gives us probably saner semantics overall.\n\nOops, now I get it[1]: You mean replacing resolve_gitlink_ref usages\nwith is_git_directory, like:\n\ndiff --git a/dir.c b/dir.c\nindex d2a8f06..7765dc6 100644\n--- a/dir.c\n+++ b/dir.c\n@@ -1375,8 +1375,7 @@ static enum path_treatment treat_directory(struct dir_struct *dir,\n \t\tif (dir->flags & DIR_SHOW_OTHER_DIRECTORIES)\n \t\t\tbreak;\n \t\tif (!(dir->flags & DIR_NO_GITLINKS)) {\n-\t\t\tunsigned char sha1[20];\n-\t\t\tif (resolve_gitlink_ref(dirname, \"HEAD\", sha1) == 0)\n+\t\t\tif (is_git_directory(dirname))\n \t\t\t\treturn path_untracked;\n \t\t}\n \t\treturn path_recurse;\n\nThat, I like. If it is correct.\n\nAndreas\n\n[1] After reading the introduction of is_git_directory, 0179ca7a62.\n\n-- \n\"Totally trivial. Famous last words.\"\nFrom: Linus Torvalds <torvalds@*.org>\nDate: Fri, 22 Jan 2010 07:29:21 -0800\n"},{"id":"273372","messageId":"20151116163130.GA15046@sigill.intra.peff.net","threadId":"38823","inReplyTo":"20151114133501.GI16219@inner.h.apk.li","subject":"Re: [PATCH] refs.c: get_ref_cache: use a bucket hash","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-11-16T16:31:30Z","receivedAt":"2015-11-16T16:31:30Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Nov 14, 2015 at 02:35:01PM +0100, Andreas Krey wrote:\n\n> On Fri, 13 Nov 2015 19:01:18 +0000, Jeff King wrote:\n> ...\n> >   2. But for a little more work, pushing the is_git_directory() check\n> >      out to the call-sites gives us probably saner semantics overall.\n> \n> Oops, now I get it[1]: You mean replacing resolve_gitlink_ref usages\n> with is_git_directory, like:\n\nYes. I mistakenly said is_git_directory, when I really meant\nis_git_repository, the new function added in 0179ca7a62. You seem to\nhave figured out what I meant, but the critical thing is that we check\n\"$dir/.git\", not just \"$dir\" (and check it both as a git dir and as a\ngitfile, as is_git_repository() does).\n\nI'm not sure if we can simply make that function public or not. It's\nmostly straightforward, but it does err on the side of \"yes, this is a\ngit repo\" if we see a \".git\" file we can't read. I think that's probably\nreasonable in most sites, but I didn't look closely.\n\n> diff --git a/dir.c b/dir.c\n> index d2a8f06..7765dc6 100644\n> --- a/dir.c\n> +++ b/dir.c\n> @@ -1375,8 +1375,7 @@ static enum path_treatment treat_directory(struct dir_struct *dir,\n>  \t\tif (dir->flags & DIR_SHOW_OTHER_DIRECTORIES)\n>  \t\t\tbreak;\n>  \t\tif (!(dir->flags & DIR_NO_GITLINKS)) {\n> -\t\t\tunsigned char sha1[20];\n> -\t\t\tif (resolve_gitlink_ref(dirname, \"HEAD\", sha1) == 0)\n> +\t\t\tif (is_git_directory(dirname))\n>  \t\t\t\treturn path_untracked;\n>  \t\t}\n>  \t\treturn path_recurse;\n> \n> That, I like. If it is correct.\n\nYes, that's what I had in mind, modulo the directory/repository thing\nabove (the is_git_repository function also takes a strbuf, so we'd need\nto handle that extra allocation somewhere).\n\n-Peff\n"}]}