{"thread":{"id":"6157","subject":"Re: [PATCH] git-fetch: Avoid reading packed refs over and over again","startedAt":"2006-12-17T19:52:34Z","lastAt":"2006-12-30T20:02:30Z","messageCount":6,"participants":["Han-Wen Nienhuys","Johannes Schindelin","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"295665","messageId":"Pine.LNX.4.63.0612172048331.3635@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"6157","inReplyTo":null,"subject":"[PATCH] git-fetch: Avoid reading packed refs over and over again","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-12-17T19:52:34Z","receivedAt":"2006-12-17T19:52:34Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nWhen checking which tags to fetch, the old code used to call\ngit-show-ref --verify for _each_ remote tag. Since reading even\npacked refs is not a cheap operation when there are a lot of\nlocal refs, the code became quite slow.\n\nThis fixes it by teaching git-show-ref to filter out valid\n(i.e. locally stored) refs from stdin, when passing the parameter\n--filter-invalid to git-show-ref, and feeding it lines in the\nform 'sha1 refname'.\n\nSigned-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\n---\n\tSince this option is purely for use in git-fetch, I did not even\n\tbother documenting it.\n\n\tThis patch would have been so much cleaner if git-fetch was written\n\tin C... But since it accumulated so many functions by now, I see\n\tnot much chance for that (at least in the near future).\n\n\tIn very unscientific tests, a single read_packed_refs() in the \n\tlilypond repo took 0.1 seconds. Yep, that's 1/10th second. So, the \n\twhile loop in git-fetch took more than 10 seconds for 107 tags.\n\n builtin-show-ref.c |   28 +++++++++++++++++++++++++++-\n git-fetch.sh       |    2 +-\n 2 files changed, 28 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin-show-ref.c b/builtin-show-ref.c\nindex f6929d9..c0b55c1 100644\n--- a/builtin-show-ref.c\n+++ b/builtin-show-ref.c\n@@ -2,8 +2,9 @@\n #include \"refs.h\"\n #include \"object.h\"\n #include \"tag.h\"\n+#include \"path-list.h\"\n \n-static const char show_ref_usage[] = \"git show-ref [-q|--quiet] [--verify] [-h|--head] [-d|--dereference] [-s|--hash[=<length>]] [--abbrev[=<length>]] [--tags] [--heads] [--] [pattern*]\";\n+static const char show_ref_usage[] = \"git show-ref [-q|--quiet] [--verify] [-h|--head] [-d|--dereference] [-s|--hash[=<length>]] [--abbrev[=<length>]] [--tags] [--heads] [--] [pattern*] | --filter-invalid < ref-list\";\n \n static int deref_tags = 0, show_head = 0, tags_only = 0, heads_only = 0,\n \tfound_match = 0, verify = 0, quiet = 0, hash_only = 0, abbrev = 0;\n@@ -86,6 +87,29 @@ match:\n \treturn 0;\n }\n \n+static int add_valid(const char *refname, const unsigned char *sha1, int flag, void *cbdata)\n+{\n+\tstruct path_list *list = (struct path_list *)cbdata;\n+\tpath_list_insert(refname, list);\n+\treturn 0;\n+}\n+\n+static int filter_invalid()\n+{\n+\tstatic struct path_list valid_refs = { NULL, 0, 0, 0 };\n+\tchar buf[1024];\n+\n+\tfor_each_ref(add_valid, &valid_refs);\n+\twhile (fgets(buf, sizeof(buf), stdin)) {\n+\t\tint len = strlen(buf);\n+\t\tif (len > 0 && buf[len - 1] == '\\n')\n+\t\t\tbuf[--len] = '\\0';\n+\t\tif (len < 41 || !path_list_has_path(&valid_refs, buf + 41))\n+\t\t\tprintf(\"%s\\n\", buf);\n+\t}\n+\treturn 0;\n+}\n+\n int cmd_show_ref(int argc, const char **argv, const char *prefix)\n {\n \tint i;\n@@ -153,6 +177,8 @@ int cmd_show_ref(int argc, const char **argv, const char *prefix)\n \t\t\theads_only = 1;\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strcmp(arg, \"--filter-invalid\"))\n+\t\t\treturn filter_invalid();\n \t\tusage(show_ref_usage);\n \t}\n \tif (verify) {\ndiff --git a/git-fetch.sh b/git-fetch.sh\nindex 3feba32..d1c00db 100755\n--- a/git-fetch.sh\n+++ b/git-fetch.sh\n@@ -474,9 +474,9 @@ case \"$no_tags$tags\" in\n \t\techo \"$ls_remote_result\" |\n \t\tsed -n\t-e 's|^\\('\"$_x40\"'\\)\t\\(refs/tags/.*\\)^{}$|\\1 \\2|p' \\\n \t\t\t-e 's|^\\('\"$_x40\"'\\)\t\\(refs/tags/.*\\)$|\\1 \\2|p' |\n+\t\tgit-show-ref --filter-invalid |\n \t\twhile read sha1 name\n \t\tdo\n-\t\t\tgit-show-ref --verify --quiet -- \"$name\" && continue\n \t\t\tgit-check-ref-format \"$name\" || {\n \t\t\t\techo >&2 \"warning: tag ${name} ignored\"\n \t\t\t\tcontinue\n-- \n1.4.4.1.g3c2a-dirty\n"},{"id":"298372","messageId":"7vslfe3r4d.fsf@assigned-by-dhcp.cox.net","threadId":"6157","inReplyTo":"Pine.LNX.4.63.0612172048331.3635@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] git-fetch: Avoid reading packed refs over and over again","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-12-18T01:54:58Z","receivedAt":"2006-12-18T01:54:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> \tSince this option is purely for use in git-fetch, I did not even\n> \tbother documenting it.\n\nI think the name --filter-blah makes it unclear if it is a\nfilter that picks up items that match the criteria \"blah\" out of\nits input, or if it filters out the ones that do not match the\ncriteria.\n\nIn either case, you are not filtering \"invalid vs valid\" but\n\"existing vs missing\".\n\nIf you are making a git-fetch specific extension, it would make\nsense to include what the upstream sed does as well.  That is,\nthe user would become:\n\n\techo \"$ls_remote_result\" |\n-       sed -n\t-e 's|^\\('\"$_x40\"'\\)\t\\(refs/tags/.*\\)^{}$|\\1 \\2|p' \\\n-               -e 's|^\\('\"$_x40\"'\\)\t\\(refs/tags/.*\\)$|\\1 \\2|p' |\n+\tgit show-ref --exclude-existing=refs/tags/ |\n        while read sha1 name\n        do\n-\t\tgit-show-ref --verify --quiet -- \"$name\" && continue\n-\t\tgit-check-ref-format \"$name\" || {\n-\t\t\techo >&2 \"warning: tag ${name} ignored\"\n-\t\t\tcontinue\n\nThe 'exclude-existing' flag would filter out the ones that do not\nhead-match the specified hierarchy, the ones that we have, and\nthe ones that do not conform to a valid refname pattern (which\nwould filter out ^{} entries).\n\nHow about this as a replacement?\n\n---\n\n builtin-show-ref.c |   60 +++++++++++++++++++++++++++++++++++++++++++++++++++-\n git-fetch.sh       |   12 ++-------\n 2 files changed, 62 insertions(+), 10 deletions(-)\n\ndiff --git a/builtin-show-ref.c b/builtin-show-ref.c\nindex 0739798..b36f15e 100644\n--- a/builtin-show-ref.c\n+++ b/builtin-show-ref.c\n@@ -2,8 +2,9 @@\n #include \"refs.h\"\n #include \"object.h\"\n #include \"tag.h\"\n+#include \"path-list.h\"\n \n-static const char show_ref_usage[] = \"git show-ref [-q|--quiet] [--verify] [-h|--head] [-d|--dereference] [-s|--hash[=<length>]] [--abbrev[=<length>]] [--tags] [--heads] [--] [pattern*]\";\n+static const char show_ref_usage[] = \"git show-ref [-q|--quiet] [--verify] [-h|--head] [-d|--dereference] [-s|--hash[=<length>]] [--abbrev[=<length>]] [--tags] [--heads] [--] [pattern*] | --filter-invalid < ref-list\";\n \n static int deref_tags = 0, show_head = 0, tags_only = 0, heads_only = 0,\n \tfound_match = 0, verify = 0, quiet = 0, hash_only = 0, abbrev = 0;\n@@ -86,6 +87,59 @@ match:\n \treturn 0;\n }\n \n+static int add_existing(const char *refname, const unsigned char *sha1, int flag, void *cbdata)\n+{\n+\tstruct path_list *list = (struct path_list *)cbdata;\n+\tpath_list_insert(refname, list);\n+\treturn 0;\n+}\n+\n+/*\n+ * read \"^(?:<anything>\\s)?<refname>(?:\\^\\{\\})?$\" from the standard input,\n+ * and\n+ * (1) strip \"^{}\" at the end of line if any;\n+ * (2) ignore if match is provided and does not head-match refname;\n+ * (3) warn if refname is not a well-formed refname and skip;\n+ * (4) ignore if refname is a ref that exists in the local repository;\n+ * (5) otherwise output the line.\n+ */\n+static int exclude_existing(const char *match)\n+{\n+\tstatic struct path_list existing_refs = { NULL, 0, 0, 0 };\n+\tchar buf[1024];\n+\tint matchlen = match ? strlen(match) : 0;\n+\n+\tfor_each_ref(add_existing, &existing_refs);\n+\twhile (fgets(buf, sizeof(buf), stdin)) {\n+\t\tint len = strlen(buf);\n+\t\tchar *ref;\n+\t\tif (len > 0 && buf[len - 1] == '\\n')\n+\t\t\tbuf[--len] = '\\0';\n+\t\tif (!strcmp(buf + len - 3, \"^{}\")) {\n+\t\t\tlen -= 3;\n+\t\t\tbuf[len] = '\\0';\n+\t\t}\n+\t\tfor (ref = buf + len; buf < ref; ref--)\n+\t\t\tif (isspace(ref[-1]))\n+\t\t\t\tbreak;\n+\t\tif (match) {\n+\t\t\tint reflen = buf + len - ref;\n+\t\t\tif (reflen < matchlen)\n+\t\t\t\tcontinue;\n+\t\t\tif (strncmp(ref, match, matchlen))\n+\t\t\t\tcontinue;\n+\t\t}\n+\t\tif (check_ref_format(ref)) {\n+\t\t\tfprintf(stderr, \"warning: ref '%s' ignored\\n\", ref);\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!path_list_has_path(&existing_refs, ref)) {\n+\t\t\tprintf(\"%s\\n\", buf);\n+\t\t}\n+\t}\n+\treturn 0;\n+}\n+\n int cmd_show_ref(int argc, const char **argv, const char *prefix)\n {\n \tint i;\n@@ -153,6 +207,10 @@ int cmd_show_ref(int argc, const char **argv, const char *prefix)\n \t\t\theads_only = 1;\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strcmp(arg, \"--exclude-existing\"))\n+\t\t\treturn exclude_existing(NULL);\n+\t\tif (!strncmp(arg, \"--exclude-existing=\", 19))\n+\t\t\treturn exclude_existing(arg + 19);\n \t\tusage(show_ref_usage);\n \t}\n \tif (show_head)\ndiff --git a/git-fetch.sh b/git-fetch.sh\nindex fb35815..38101a6 100755\n--- a/git-fetch.sh\n+++ b/git-fetch.sh\n@@ -242,7 +242,7 @@ esac\n reflist=$(get_remote_refs_for_fetch \"$@\")\n if test \"$tags\"\n then\n-\ttaglist=`IFS=\"\t\" &&\n+\ttaglist=`IFS='\t' &&\n \t\t  echo \"$ls_remote_result\" |\n \t          while read sha1 name\n \t\t  do\n@@ -438,17 +438,11 @@ case \"$no_tags$tags\" in\n \t*:refs/*)\n \t\t# effective only when we are following remote branch\n \t\t# using local tracking branch.\n-\t\ttaglist=$(IFS=\" \" &&\n+\t\ttaglist=$(IFS='\t' &&\n \t\techo \"$ls_remote_result\" |\n-\t\tsed -n\t-e 's|^\\('\"$_x40\"'\\)\t\\(refs/tags/.*\\)^{}$|\\1 \\2|p' \\\n-\t\t\t-e 's|^\\('\"$_x40\"'\\)\t\\(refs/tags/.*\\)$|\\1 \\2|p' |\n+\t\tgit-show-ref --exclude-existing=refs/tags/ |\n \t\twhile read sha1 name\n \t\tdo\n-\t\t\tgit-show-ref --verify --quiet -- \"$name\" && continue\n-\t\t\tgit-check-ref-format \"$name\" || {\n-\t\t\t\techo >&2 \"warning: tag ${name} ignored\"\n-\t\t\t\tcontinue\n-\t\t\t}\n \t\t\tgit-cat-file -t \"$sha1\" >/dev/null 2>&1 || continue\n \t\t\techo >&2 \"Auto-following $name\"\n \t\t\techo \".${name}:${name}\"\n"},{"id":"296330","messageId":"Pine.LNX.4.63.0612181329480.3635@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"6157","inReplyTo":"7vslfe3r4d.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] git-fetch: Avoid reading packed refs over and over again","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-12-18T12:33:28Z","receivedAt":"2006-12-18T12:33:28Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 17 Dec 2006, Junio C Hamano wrote:\n\n> How about this as a replacement?\n\nMakes sense, except for:\n\n> --- a/builtin-show-ref.c\n> +++ b/builtin-show-ref.c\n> @@ -2,8 +2,9 @@\n>  #include \"refs.h\"\n>  #include \"object.h\"\n>  #include \"tag.h\"\n> +#include \"path-list.h\"\n>  \n> -static const char show_ref_usage[] = \"git show-ref [-q|--quiet] [--verify] [-h|--head] [-d|--dereference] [-s|--hash[=<length>]] [--abbrev[=<length>]] [--tags] [--heads] [--] [pattern*]\";\n> +static const char show_ref_usage[] = \"git show-ref [-q|--quiet] [--verify] [-h|--head] [-d|--dereference] [-s|--hash[=<length>]] [--abbrev[=<length>]] [--tags] [--heads] [--] [pattern*] | --filter-invalid < ref-list\";\n\nHere, you want to either not mention it at all, or add \n\"--exclude-existing[=<pattern>]\" instead of \"--filter-invalid\".\n\n> +\t\tif (!strcmp(buf + len - 3, \"^{}\")) {\n\nHere you have to check first, if len > 3. Strictly speaking, there should \nnot be any line coming in which is shorter than 42 bytes. But I was \nrecentely bitten by such an assuption...\n\nOverall, I like it. I even have the impression that this could actually \nopen a way to build in fetch instead of relying on a POSIX conformant and \nfast shell for such a central part of git.\n\nCiao,\nDscho\n"},{"id":"30508","messageId":"4596B837.8030108@xs4all.nl","threadId":"6157","inReplyTo":"Pine.LNX.4.63.0612181329480.3635@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] git-fetch: Avoid reading packed refs over and over again","fromName":"Han-Wen Nienhuys","fromEmail":"hanwen@xs4all.nl","sentAt":"2006-12-30T19:04:23Z","receivedAt":"2006-12-30T19:04:23Z","isPatch":true,"sender":{"key":"hanwen@google.com","avatar":"https://avatars.githubusercontent.com/u/31547?v=4"},"body":"Johannes Schindelin escreveu:\n> \n> Here you have to check first, if len > 3. Strictly speaking, there should \n> not be any line coming in which is shorter than 42 bytes. But I was \n> recentely bitten by such an assuption...\n> \n> Overall, I like it. I even have the impression that this could actually \n> open a way to build in fetch instead of relying on a POSIX conformant and \n> fast shell for such a central part of git.\n\nis there any chance of this going in GIT 1.5.0 ? It's not in the rc0 release.\n\n\n-- \n Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen\n"},{"id":"30509","messageId":"Pine.LNX.4.63.0612302020060.19693@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"6157","inReplyTo":"4596B837.8030108@xs4all.nl","subject":"Re: [PATCH] git-fetch: Avoid reading packed refs over and over again","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-12-30T19:24:01Z","receivedAt":"2006-12-30T19:24:01Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sat, 30 Dec 2006, Han-Wen Nienhuys wrote:\n\n> Johannes Schindelin escreveu:\n> > \n> > Here you have to check first, if len > 3. Strictly speaking, there should \n> > not be any line coming in which is shorter than 42 bytes. But I was \n> > recentely bitten by such an assuption...\n> > \n> > Overall, I like it. I even have the impression that this could actually \n> > open a way to build in fetch instead of relying on a POSIX conformant and \n> > fast shell for such a central part of git.\n> \n> is there any chance of this going in GIT 1.5.0 ? It's not in the rc0 \n> release.\n\nUm.\n\n$ git grep -e exclude-existing v1.5.0-rc0\nv1.5.0-rc0:builtin-show-ref.c:          if (!strcmp(arg, \"--exclude-existing\"))\nv1.5.0-rc0:builtin-show-ref.c:          if (!strncmp(arg, \"--exclude-existing=\", 19))\nv1.5.0-rc0:git-fetch.sh:                git-show-ref --exclude-existing=refs/tags/ |\n\nThe last line means that it _is_ in v1.5.0-rc0. (BTW it is the commit \ntags/v1.5.0-rc0~84, which I found by \"git log v1.5.0-rc0 git-fetch.sh | \ngit name-rev --tags --stdin | less\".)\n\nCiao,\nDscho\n"},{"id":"30513","messageId":"4596C5D6.701@xs4all.nl","threadId":"6157","inReplyTo":"Pine.LNX.4.63.0612302020060.19693@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH] git-fetch: Avoid reading packed refs over and over again","fromName":"Han-Wen Nienhuys","fromEmail":"hanwen@xs4all.nl","sentAt":"2006-12-30T20:02:30Z","receivedAt":"2006-12-30T20:02:30Z","isPatch":true,"sender":{"key":"hanwen@google.com","avatar":"https://avatars.githubusercontent.com/u/31547?v=4"},"body":"Johannes Schindelin escreveu:\n\n> $ git grep -e exclude-existing v1.5.0-rc0\n> v1.5.0-rc0:builtin-show-ref.c:          if (!strcmp(arg, \"--exclude-existing\"))\n> v1.5.0-rc0:builtin-show-ref.c:          if (!strncmp(arg, \"--exclude-existing=\", 19))\n> v1.5.0-rc0:git-fetch.sh:                git-show-ref --exclude-existing=refs/tags/ |\n> \n> The last line means that it _is_ in v1.5.0-rc0. (BTW it is the commit \n> tags/v1.5.0-rc0~84, which I found by \"git log v1.5.0-rc0 git-fetch.sh | \n> git name-rev --tags --stdin | less\".)\n\noh, oops. I was looking for the commit  message of the patch you originally \nsent me. Cool.\n\n-- \n Han-Wen Nienhuys - hanwen@xs4all.nl - http://www.xs4all.nl/~hanwen\n"}]}