{"thread":{"id":"45989","subject":"Performance regression in `git branch` due to ref-filter usage","startedAt":"2017-05-17T11:14:52Z","lastAt":"2017-05-19T06:12:21Z","messageCount":3,"participants":["Michael Haggerty","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"320033","messageId":"dfc3a334-8047-26b0-1142-81c703010507@alum.mit.edu","threadId":"45989","inReplyTo":null,"subject":"Performance regression in `git branch` due to ref-filter usage","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-05-17T11:14:34Z","receivedAt":"2017-05-17T11:14:52Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"While working on reference code, I was running `git branch` under\n`strace`, when I noticed that `$GIT_DIR/HEAD` was being `lstat()`ed and\n`read()` 121 times. This is in a repository with 114 branches, so\nprobably it is being run once per branch. The extra work makes a\nmeasurable difference to the (admittedly, short) runtime.\n\nAs recently as 2.12.3 the file was only read 4 times when running the\nsame command [1].\n\nThe regression bisects to\n\n    949af0684c (branch: use ref-filter printing APIs, 2017-01-10)\n\nIt would be nice if these extra syscalls could be avoided.\n\nI haven't checked whether other commands have similar regressions.\n\nMichael\n\n[1] One wonders why the file has to be read more than once, but that's a\ndifferent story and probably harder to fix.\n"},{"id":"320077","messageId":"20170517140417.kwzznw4su36k6pxv@sigill.intra.peff.net","threadId":"45989","inReplyTo":"dfc3a334-8047-26b0-1142-81c703010507@alum.mit.edu","subject":"Re: Performance regression in `git branch` due to ref-filter usage","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-05-17T14:04:18Z","receivedAt":"2017-05-17T14:04:35Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, May 17, 2017 at 01:14:34PM +0200, Michael Haggerty wrote:\n\n> While working on reference code, I was running `git branch` under\n> `strace`, when I noticed that `$GIT_DIR/HEAD` was being `lstat()`ed and\n> `read()` 121 times. This is in a repository with 114 branches, so\n> probably it is being run once per branch. The extra work makes a\n> measurable difference to the (admittedly, short) runtime.\n> \n> As recently as 2.12.3 the file was only read 4 times when running the\n> same command [1].\n> \n> The regression bisects to\n> \n>     949af0684c (branch: use ref-filter printing APIs, 2017-01-10)\n> \n> It would be nice if these extra syscalls could be avoided.\n> \n> I haven't checked whether other commands have similar regressions.\n\nIt looks like it's part of populate_value(). Each ref checks %(HEAD),\nand resolve HEAD individually to see if we're it. So it probably doesn't\naffect other commands by default (though you could specify %(HEAD)\nmanually via for-each-ref).\n\nThe solution is to cache the value we read and use it to compare against\neach ref. I'm not sure if we can do something more elegant than the\npatch below, which just caches it for the length of the program.\n\n> [1] One wonders why the file has to be read more than once, but that's a\n> different story and probably harder to fix.\n\nThe other ones seem to come from wt_status code, as part of\nget_head_description().\n\n---\ndiff --git a/ref-filter.c b/ref-filter.c\nindex 1fc5e9970..947919fc4 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -1284,6 +1284,20 @@ static const char *get_refname(struct used_atom *atom, struct ref_array_item *re\n \treturn show_ref(&atom->u.refname, ref->refname);\n }\n \n+static int head_matches(const char *refname)\n+{\n+\tstatic int initialized;\n+\tstatic char *head;\n+\n+\tif (!initialized) {\n+\t\tunsigned char sha1[20];\n+\t\thead = resolve_refdup(\"HEAD\", RESOLVE_REF_READING, sha1, NULL);\n+\t\tinitialized = 1;\n+\t}\n+\n+\treturn head && !strcmp(refname, head);\n+}\n+\n /*\n  * Parse the object referred by ref, and grab needed value.\n  */\n@@ -1369,12 +1383,7 @@ static void populate_value(struct ref_array_item *ref)\n \t\t} else if (!deref && grab_objectname(name, ref->objectname, v, atom)) {\n \t\t\tcontinue;\n \t\t} else if (!strcmp(name, \"HEAD\")) {\n-\t\t\tconst char *head;\n-\t\t\tunsigned char sha1[20];\n-\n-\t\t\thead = resolve_ref_unsafe(\"HEAD\", RESOLVE_REF_READING,\n-\t\t\t\t\t\t  sha1, NULL);\n-\t\t\tif (head && !strcmp(ref->refname, head))\n+\t\t\tif (head_matches(ref->refname))\n \t\t\t\tv->s = \"*\";\n \t\t\telse\n \t\t\t\tv->s = \" \";\n"},{"id":"320249","messageId":"20170519061212.5xrkqydzl32l24ck@sigill.intra.peff.net","threadId":"45989","inReplyTo":"20170517140417.kwzznw4su36k6pxv@sigill.intra.peff.net","subject":"[PATCH] ref-filter: resolve HEAD when parsing %(HEAD) atom","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-05-19T06:12:12Z","receivedAt":"2017-05-19T06:12:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"If the user asks to display (or sort by) the %(HEAD) atom,\nref-filter has to compare each refname to the value of HEAD.\nWe do so by resolving HEAD fresh when calling populate_value()\non each ref. If there are a large number of refs, this can\nhave a measurable impact on runtime.\n\nInstead, let's resolve HEAD once when we realize we need the\n%(HEAD) atom, allowing us to do a simple string comparison\nfor each ref. On a repository with 3000 branches (high, but\nan actual example found in the wild) this drops the\nbest-of-five time to run \"git branch >/dev/null\" from 59ms\nto 48ms (~20% savings).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nThe \"something like this\" patch I sent earlier just cached the value of\nHEAD in a global for the length of the program. This is a bit nicer, in\nthat it ties the cache to the atom we are filling in. But since that's\nalso stored in a program global, the end effect is the same. :) I think\nit's still worth doing it this way, though, as we might one day push the\nused_atom stuff into some kind of ref_filter_context struct, and then\nthis would Just Work.\n\nI did take a look at de-globalifying used_atom and friends, but it gets\npretty nasty pushing it all through the callstack. Since there's no\nimmediate benefit, I don't think it's really worth pursuing for now.\n\n ref-filter.c | 16 +++++++++-------\n 1 file changed, 9 insertions(+), 7 deletions(-)\n\ndiff --git a/ref-filter.c b/ref-filter.c\nindex 1fc5e9970..82ca411d0 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -93,6 +93,7 @@ static struct used_atom {\n \t\t\tunsigned int length;\n \t\t} objectname;\n \t\tstruct refname_atom refname;\n+\t\tchar *head;\n \t} u;\n } *used_atom;\n static int used_atom_cnt, need_tagged, need_symref;\n@@ -287,6 +288,12 @@ static void if_atom_parser(struct used_atom *atom, const char *arg)\n \t}\n }\n \n+static void head_atom_parser(struct used_atom *atom, const char *arg)\n+{\n+\tunsigned char unused[GIT_SHA1_RAWSZ];\n+\n+\tatom->u.head = resolve_refdup(\"HEAD\", RESOLVE_REF_READING, unused, NULL);\n+}\n \n static struct {\n \tconst char *name;\n@@ -325,7 +332,7 @@ static struct {\n \t{ \"push\", FIELD_STR, remote_ref_atom_parser },\n \t{ \"symref\", FIELD_STR, refname_atom_parser },\n \t{ \"flag\" },\n-\t{ \"HEAD\" },\n+\t{ \"HEAD\", FIELD_STR, head_atom_parser },\n \t{ \"color\", FIELD_STR, color_atom_parser },\n \t{ \"align\", FIELD_STR, align_atom_parser },\n \t{ \"end\" },\n@@ -1369,12 +1376,7 @@ static void populate_value(struct ref_array_item *ref)\n \t\t} else if (!deref && grab_objectname(name, ref->objectname, v, atom)) {\n \t\t\tcontinue;\n \t\t} else if (!strcmp(name, \"HEAD\")) {\n-\t\t\tconst char *head;\n-\t\t\tunsigned char sha1[20];\n-\n-\t\t\thead = resolve_ref_unsafe(\"HEAD\", RESOLVE_REF_READING,\n-\t\t\t\t\t\t  sha1, NULL);\n-\t\t\tif (head && !strcmp(ref->refname, head))\n+\t\t\tif (atom->u.head && !strcmp(ref->refname, atom->u.head))\n \t\t\t\tv->s = \"*\";\n \t\t\telse\n \t\t\t\tv->s = \" \";\n-- \n2.13.0.219.g63f6bc368\n\n"}]}