{"thread":{"id":"31838","subject":"[PATCH] Cache stat_tracking_info() for faster status and branch -v","startedAt":"2012-10-16T17:36:07Z","lastAt":"2012-10-20T09:02:30Z","messageCount":3,"participants":["Nguyễn Thái Ngọc Duy","Junio C Hamano","Nguyen Thai Ngoc Duy"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"201373","messageId":"1350408967-13919-1-git-send-email-pclouds@gmail.com","threadId":"31838","inReplyTo":null,"subject":"[PATCH] Cache stat_tracking_info() for faster status and branch -v","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-10-16T17:36:07Z","receivedAt":"2012-10-16T17:36:07Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"stat_tracking_info() is used to calculated how many commits ahead or\nbehind for a branch. Rev walking can be slow especially when the\nbranch is way behind its remote end. By caching the results, we won't\nhave to rev walk every time we need these information.\nstat_tracking_info() cost can be greatly reduced this way.\n\nThis makes sure \"git status\" instant no matter how far behind HEAD\nis, except the first time after HEAD changes. This also makes\n\"branch -v\" usable (for me) as it's now also instant versus 3.5\nseconds in non-cache case on my machine.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n I wanted guaranteed-fast status for another reason, but it turns out\n \"branch -v\" benefits even more. Recent commit walking is not\n efficiently optimized even with Shawn's pack bitmaps. This may be\n useful some people, I guess.\n\n remote.c | 42 ++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 42 insertions(+)\n\ndiff --git a/remote.c b/remote.c\nindex 04fd9ea..db825b8 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -1549,6 +1549,7 @@ int stat_tracking_info(struct branch *branch, int *num_ours, int *num_theirs)\n \tstruct rev_info revs;\n \tconst char *rev_argv[10], *base;\n \tint rev_argc;\n+\tint fd;\n \n \t/*\n \t * Nothing to report unless we are marked to build on top of\n@@ -1579,6 +1580,33 @@ int stat_tracking_info(struct branch *branch, int *num_ours, int *num_theirs)\n \tif (theirs == ours)\n \t\treturn 0;\n \n+\tif (!access(git_path(\"stat_tracking_cache/%s\",\n+\t\t\t     branch->refname), R_OK)) {\n+\t\tstruct strbuf sb = STRBUF_INIT;\n+\t\tunsigned char sha1_ours[20], sha1_theirs[20];\n+\t\tint n1, n2;\n+\t\tif ((fd = open(git_path(\"stat_tracking_cache/%s\",\n+\t\t\t\t\tbranch->refname),\n+\t\t\t       O_RDONLY)) != -1 &&\n+\t\t    strbuf_read(&sb, fd, 0) != -1 &&\n+\t\t    sb.len > (40 + 1) * 2 &&\n+\t\t    !get_sha1_hex(sb.buf, sha1_ours) &&\n+\t\t    sb.buf[40] == '\\n' &&\n+\t\t    !get_sha1_hex(sb.buf + 41, sha1_theirs) &&\n+\t\t    sb.buf[81] == '\\n' &&\n+\t\t    !hashcmp(sha1_ours, ours->object.sha1) &&\n+\t\t    !hashcmp(sha1_theirs, theirs->object.sha1) &&\n+\t\t    sscanf(sb.buf + 82, \"%d\\n%d\\n\", &n1, &n2) == 2) {\n+\t\t\t*num_ours = n1;\n+\t\t\t*num_theirs = n2;\n+\t\t\tclose(fd);\n+\t\t\tstrbuf_release(&sb);\n+\t\t\treturn 1;\n+\t\t}\n+\t\tclose(fd);\n+\t\tstrbuf_release(&sb);\n+\t}\n+\n \t/* Run \"rev-list --left-right ours...theirs\" internally... */\n \trev_argc = 0;\n \trev_argv[rev_argc++] = NULL;\n@@ -1608,6 +1636,20 @@ int stat_tracking_info(struct branch *branch, int *num_ours, int *num_theirs)\n \t\t\t(*num_theirs)++;\n \t}\n \n+\tif (!safe_create_leading_directories(git_path(\"stat_tracking_cache/%s\",\n+\t\t\t\t\t\t      branch->refname)) &&\n+\t    (fd = open(git_path(\"stat_tracking_cache/%s\",\n+\t\t\t\tbranch->refname),\n+\t\t       O_CREAT | O_TRUNC | O_RDWR, 0644)) != -1) {\n+\t\tstruct strbuf sb = STRBUF_INIT;\n+\t\tstrbuf_addf(&sb, \"%s\\n\", sha1_to_hex(ours->object.sha1));\n+\t\tstrbuf_addf(&sb, \"%s\\n\", sha1_to_hex(theirs->object.sha1));\n+\t\tstrbuf_addf(&sb, \"%d\\n%d\\n\", *num_ours, *num_theirs);\n+\t\twrite(fd, sb.buf, sb.len);\n+\t\tstrbuf_release(&sb);\n+\t\tclose(fd);\n+\t}\n+\n \t/* clear object flags smudged by the above traversal */\n \tclear_commit_marks(ours, ALL_REV_FLAGS);\n \tclear_commit_marks(theirs, ALL_REV_FLAGS);\n-- \n1.8.0.rc2.21.g0695653\n"},{"id":"201562","messageId":"7v7gqmjl6n.fsf@alter.siamese.dyndns.org","threadId":"31838","inReplyTo":"1350408967-13919-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH] Cache stat_tracking_info() for faster status and branch -v","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-10-19T19:50:24Z","receivedAt":"2012-10-19T19:50:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:\n\n> stat_tracking_info() is used to calculated how many commits ahead or\n> behind for a branch. Rev walking can be slow especially when the\n> branch is way behind its remote end. By caching the results, we won't\n> have to rev walk every time we need these information.\n> stat_tracking_info() cost can be greatly reduced this way.\n>\n> This makes sure \"git status\" instant no matter how far behind HEAD\n> is, except the first time after HEAD changes. This also makes\n> \"branch -v\" usable (for me) as it's now also instant versus 3.5\n> seconds in non-cache case on my machine.\n>\n> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n> ---\n>  I wanted guaranteed-fast status for another reason, but it turns out\n>  \"branch -v\" benefits even more. Recent commit walking is not\n>  efficiently optimized even with Shawn's pack bitmaps. This may be\n>  useful some people, I guess.\n\nNot particularly interested in the cause, but not so strongly\nagainst it to veto it.\n\nThe design looks questionable.\n\nYou can fork one or more branches off of a single branch.  You may\nfork your 'frotz' branch off of remotes/origin/master but also\nanother 'xyzzy' branch may be forked from the same.\n\nI understand that you are trying to optimize, given two commit\nobject names X and Y, the cost to learn the symmetric distances\nbetween them.\n\nDoesn't it make more sense to use a notes-cache that is keyed off of\nthe commit object name X of the remote?  You will have a single note\nthat stores a blob for the commit object remotes/origin/master, and\nthe blob tells you how far the commit at the tip of 'frotz' is from\nit, and the same for 'xyzzy'.\n\nYou would obviouly need to run \"gc\" on such a notes-cache tree from\ntime to time, removing notes for commits that are not tip of any\nbranch that could be a fork point, and from the remaining notes\nblobs, entries that describe commits that are not tip of any branch,\nif you go that route.\n\n>\n>  remote.c | 42 ++++++++++++++++++++++++++++++++++++++++++\n>  1 file changed, 42 insertions(+)\n>\n> diff --git a/remote.c b/remote.c\n> index 04fd9ea..db825b8 100644\n> --- a/remote.c\n> +++ b/remote.c\n> @@ -1549,6 +1549,7 @@ int stat_tracking_info(struct branch *branch, int *num_ours, int *num_theirs)\n>  \tstruct rev_info revs;\n>  \tconst char *rev_argv[10], *base;\n>  \tint rev_argc;\n> +\tint fd;\n>  \n>  \t/*\n>  \t * Nothing to report unless we are marked to build on top of\n> @@ -1579,6 +1580,33 @@ int stat_tracking_info(struct branch *branch, int *num_ours, int *num_theirs)\n>  \tif (theirs == ours)\n>  \t\treturn 0;\n>  \n> +\tif (!access(git_path(\"stat_tracking_cache/%s\",\n> +\t\t\t     branch->refname), R_OK)) {\n> +\t\tstruct strbuf sb = STRBUF_INIT;\n> +\t\tunsigned char sha1_ours[20], sha1_theirs[20];\n> +\t\tint n1, n2;\n> +\t\tif ((fd = open(git_path(\"stat_tracking_cache/%s\",\n> +\t\t\t\t\tbranch->refname),\n> +\t\t\t       O_RDONLY)) != -1 &&\n> +\t\t    strbuf_read(&sb, fd, 0) != -1 &&\n> +\t\t    sb.len > (40 + 1) * 2 &&\n> +\t\t    !get_sha1_hex(sb.buf, sha1_ours) &&\n> +\t\t    sb.buf[40] == '\\n' &&\n> +\t\t    !get_sha1_hex(sb.buf + 41, sha1_theirs) &&\n> +\t\t    sb.buf[81] == '\\n' &&\n> +\t\t    !hashcmp(sha1_ours, ours->object.sha1) &&\n> +\t\t    !hashcmp(sha1_theirs, theirs->object.sha1) &&\n> +\t\t    sscanf(sb.buf + 82, \"%d\\n%d\\n\", &n1, &n2) == 2) {\n> +\t\t\t*num_ours = n1;\n> +\t\t\t*num_theirs = n2;\n> +\t\t\tclose(fd);\n> +\t\t\tstrbuf_release(&sb);\n> +\t\t\treturn 1;\n> +\t\t}\n> +\t\tclose(fd);\n> +\t\tstrbuf_release(&sb);\n> +\t}\n> +\n>  \t/* Run \"rev-list --left-right ours...theirs\" internally... */\n>  \trev_argc = 0;\n>  \trev_argv[rev_argc++] = NULL;\n> @@ -1608,6 +1636,20 @@ int stat_tracking_info(struct branch *branch, int *num_ours, int *num_theirs)\n>  \t\t\t(*num_theirs)++;\n>  \t}\n>  \n> +\tif (!safe_create_leading_directories(git_path(\"stat_tracking_cache/%s\",\n> +\t\t\t\t\t\t      branch->refname)) &&\n> +\t    (fd = open(git_path(\"stat_tracking_cache/%s\",\n> +\t\t\t\tbranch->refname),\n> +\t\t       O_CREAT | O_TRUNC | O_RDWR, 0644)) != -1) {\n> +\t\tstruct strbuf sb = STRBUF_INIT;\n> +\t\tstrbuf_addf(&sb, \"%s\\n\", sha1_to_hex(ours->object.sha1));\n> +\t\tstrbuf_addf(&sb, \"%s\\n\", sha1_to_hex(theirs->object.sha1));\n> +\t\tstrbuf_addf(&sb, \"%d\\n%d\\n\", *num_ours, *num_theirs);\n> +\t\twrite(fd, sb.buf, sb.len);\n> +\t\tstrbuf_release(&sb);\n> +\t\tclose(fd);\n> +\t}\n> +\n>  \t/* clear object flags smudged by the above traversal */\n>  \tclear_commit_marks(ours, ALL_REV_FLAGS);\n>  \tclear_commit_marks(theirs, ALL_REV_FLAGS);\n"},{"id":"201589","messageId":"CACsJy8A2ub2y64qAbP2OTPNsVi-KmxAMFdwBBLXYReF5ASZLKg@mail.gmail.com","threadId":"31838","inReplyTo":"7v7gqmjl6n.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] Cache stat_tracking_info() for faster status and branch -v","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-10-20T09:02:30Z","receivedAt":"2012-10-20T09:02:30Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Oct 20, 2012 at 2:50 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Not particularly interested in the cause, but not so strongly\n> against it to veto it.\n\nI wonder how many people keep old branches like I do, which are\nusually far from remotes.\n\n> Doesn't it make more sense to use a notes-cache that is keyed off of\n> the commit object name X of the remote?  You will have a single note\n> that stores a blob for the commit object remotes/origin/master, and\n> the blob tells you how far the commit at the tip of 'frotz' is from\n> it, and the same for 'xyzzy'.\n>\n> You would obviouly need to run \"gc\" on such a notes-cache tree from\n> time to time, removing notes for commits that are not tip of any\n> branch that could be a fork point, and from the remaining notes\n> blobs, entries that describe commits that are not tip of any branch,\n> if you go that route.\n\nThe notes-cache route looks much nicer. Thanks. We can also use Jeff's\npersistent hash table from his rename-cache series.\n-- \nDuy\n"}]}