{"thread":{"id":"26934","subject":"[PATCH 2/5] tree-walk: drop unused parameter from match_dir_prefix","startedAt":"2011-03-31T01:37:57Z","lastAt":"2011-09-09T02:02:46Z","messageCount":30,"participants":["Dan McGee","Nguyen Thai Ngoc Duy","Junio C Hamano","Erik Faye-Lund","Andreas Ericsson","Nguyễn Thái Ngọc Duy","Antriksh Pany"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"164744","messageId":"1301535481-1085-1-git-send-email-dpmcgee@gmail.com","threadId":"26934","inReplyTo":null,"subject":"[PATCH 1/5] diff_tree_sha1: skip diff_tree if old == new","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-03-31T01:37:57Z","receivedAt":"2011-03-31T01:37:57Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"This was seen to happen in some invocations of git-log with a filtered\npath. Only do it if we are not recursively descending, as otherwise we\nmess with copy and rename detection in full tree moves.\n\nWe need to exclude times when FIND_COPIES_HARDER is enabled as the diff\nmachinery requires traversal of all files in this case to find copies\nfrom files that did not change at all in the given revision.\n\nSigned-off-by: Dan McGee \n---\n\nThese next few patches are all derived from trying to make operations on this\nrepository a bit faster:\n http://projects.archlinux.org/svntogit/packages.git/\n\nAs far as a different shape of repository, this one qualifies. Some stats from\nafter running `git gc --prune` and looking at things from count-objects among\nothers:\n\n arch-packages linux-2.6\nin-pack: 496718 1979274\nsize-pack: 112582 513977\nls | wc -l: 2401 34\nls-tree -r | wc -l 14039 36706\nls-tree -r -t | grep ' tree ' | wc -l\n 11211 2256\ntime git log -- zzzzz_not_exist >/dev/null\n 35.558s 0.976s\n\nI didn't find some golden switch to turn that made things instantly fast, but\nthese patches did at least give some speedups. Suggestions/feedback/etc.\nwelcome. Most profiling was done with `valgrind --tool=callgrind` and then\nusing kcachegrind to chase down slow spots.\n\n tree-diff.c | 3 +++\n 1 files changed, 3 insertions(+), 0 deletions(-)\n\ndiff --git a/tree-diff.c b/tree-diff.c\nindex 76f83fc..ab90f1a 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -286,6 +286,9 @@ int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const cha\n \tunsigned long size1, size2;\n \tint retval;\n \n+\tif (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(old, new))\n+\t\treturn 0;\n+\n \ttree1 = read_object_with_reference(old, tree_type, &size1, NULL);\n \tif (!tree1)\n \t\tdie(\"unable to read source tree (%s)\", sha1_to_hex(old));\n-- \n1.7.4.2\n"},{"id":"164743","messageId":"1301535481-1085-2-git-send-email-dpmcgee@gmail.com","threadId":"26934","inReplyTo":"1301535481-1085-1-git-send-email-dpmcgee@gmail.com","subject":"[PATCH 2/5] tree-walk: drop unused parameter from match_dir_prefix","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-03-31T01:37:58Z","receivedAt":"2011-03-31T01:37:58Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"Signed-off-by: Dan McGee \n---\n tree-walk.c | 4 ++--\n 1 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 322becc..9be8007 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -522,7 +522,7 @@ static int match_entry(const struct name_entry *entry, int pathlen,\n \treturn 0;\n }\n \n-static int match_dir_prefix(const char *base, int baselen,\n+static int match_dir_prefix(const char *base,\n \t\t\t const char *match, int matchlen)\n {\n \tif (strncmp(base, match, matchlen))\n@@ -579,7 +579,7 @@ int tree_entry_interesting(const struct name_entry *entry,\n \n \t\tif (baselen >= matchlen) {\n \t\t\t/* If it doesn't match, move along... */\n-\t\t\tif (!match_dir_prefix(base_str, baselen, match, matchlen))\n+\t\t\tif (!match_dir_prefix(base_str, match, matchlen))\n \t\t\t\tgoto match_wildcards;\n \n \t\t\tif (!ps->recursive || ps->max_depth == -1)\n-- \n1.7.4.2\n"},{"id":"164748","messageId":"1301535481-1085-3-git-send-email-dpmcgee@gmail.com","threadId":"26934","inReplyTo":"1301535481-1085-1-git-send-email-dpmcgee@gmail.com","subject":"[PATCH 3/5] tree-walk: micro-optimization in tree_entry_interesting","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-03-31T01:37:59Z","receivedAt":"2011-03-31T01:37:59Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"In the case of a wide breadth top-level tree (~2400 entries, all trees\nin this case), we can see a noticeable cost in the profiler calling\nstrncmp() here. Most of the time we are at the base level of the\nrepository, so base is \"\" and baselen == 0, which means we will always\ntest true. Break out this one tiny case so we can short circuit the\nstrncmp() call.\n\nThis resulted in an ~11% improvement (43 to 38 secs) for a reasonable\nlog operation on the Arch Linux Packages SVN clone repository, which\ncontained 117220 commits and the aforementioned 2400 top-level objects:\n git log -- autogen/trunk pacman/trunk/ wget/trunk/\n\nNegligible slowdown was noted with other repositories (e.g. linux-2.6).\n\nSigned-off-by: Dan McGee \n---\n tree-walk.c | 4 ++--\n 1 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 9be8007..f386151 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -591,8 +591,8 @@ int tree_entry_interesting(const struct name_entry *entry,\n \t\t\t\t\t ps->max_depth);\n \t\t}\n \n-\t\t/* Does the base match? */\n-\t\tif (!strncmp(base_str, match, baselen)) {\n+\t\t/* Either there must be no base, or the base must match. */\n+\t\tif (baselen == 0 || !strncmp(base_str, match, baselen)) {\n \t\t\tif (match_entry(entry, pathlen,\n \t\t\t\t\tmatch + baselen, matchlen - baselen,\n \t\t\t\t\t&never_interesting))\n-- \n1.7.4.2\n"},{"id":"164746","messageId":"1301535481-1085-4-git-send-email-dpmcgee@gmail.com","threadId":"26934","inReplyTo":"1301535481-1085-1-git-send-email-dpmcgee@gmail.com","subject":"[PATCH 4/5] tree-walk: unroll get_mode since loop boundaries are well-known","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-03-31T01:38:00Z","receivedAt":"2011-03-31T01:38:00Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"We know our mode entry in our tree objects should be 5 or 6 characters\nlong. This change both enforces this fact and also unrolls the parsing\nof the information giving the compiler more room for optimization of the\noperations.\n\nSigned-off-by: Dan McGee \n---\n tree-walk.c | 41 ++++++++++++++++++++++++++++++++++-------\n 1 files changed, 34 insertions(+), 7 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex f386151..41383b0 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -9,16 +9,43 @@ static const char *get_mode(const char *str, unsigned int *modep)\n \tunsigned char c;\n \tunsigned int mode = 0;\n \n-\tif (*str == ' ')\n-\t\treturn NULL;\n-\n-\twhile ((c = *str++) != ' ') {\n-\t\tif (c < '0' || c > '7')\n-\t\t\treturn NULL;\n+\t/*\n+\t * Unroll what looks like a loop since the bounds are\n+\t * well-known. There should be at least 5 and at most 6\n+\t * characters available in any valid mode, as '40000' is the\n+\t * shortest while '160000' (S_IFGITLINK) is the longest.\n+\t */\n+\t/* char 1 */\n+\tc = *str++;\n+\tif (c < '0' || c > '7') return NULL;\n+\tmode = (mode << 3) + (c - '0');\n+\t/* char 2 */\n+\tc = *str++;\n+\tif (c < '0' || c > '7') return NULL;\n+\tmode = (mode << 3) + (c - '0');\n+\t/* char 3 */\n+\tc = *str++;\n+\tif (c < '0' || c > '7') return NULL;\n+\tmode = (mode << 3) + (c - '0');\n+\t/* char 4 */\n+\tc = *str++;\n+\tif (c < '0' || c > '7') return NULL;\n+\tmode = (mode << 3) + (c - '0');\n+\t/* char 5 */\n+\tc = *str++;\n+\tif (c < '0' || c > '7') return NULL;\n+\tmode = (mode << 3) + (c - '0');\n+\t/* char 6, optional */\n+\tif (*str != ' ') {\n+\t\tc = *str++;\n+\t\tif (c < '0' || c > '7') return NULL;\n \t\tmode = (mode << 3) + (c - '0');\n \t}\n+\n+\tif (*str != ' ') return NULL;\n+\n \t*modep = mode;\n-\treturn str;\n+\treturn str + 1;\n }\n \n static void decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned long size)\n-- \n1.7.4.2\n"},{"id":"164747","messageId":"1301535481-1085-5-git-send-email-dpmcgee@gmail.com","threadId":"26934","inReplyTo":"1301535481-1085-1-git-send-email-dpmcgee@gmail.com","subject":"[PATCH 5/5] tree-walk: match_entry microoptimization","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-03-31T01:38:01Z","receivedAt":"2011-03-31T01:38:01Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"Before calling strncmp(), see if we can get away with checking only the\nfirst character of the passed path components instead.\n\nSigned-off-by: Dan McGee \n---\n tree-walk.c | 26 ++++++++++++++++++--------\n 1 files changed, 18 insertions(+), 8 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 41383b0..083b951 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -488,9 +488,10 @@ static int match_entry(const struct name_entry *entry, int pathlen,\n \t\t const char *match, int matchlen,\n \t\t int *never_interesting)\n {\n-\tint m = -1; /* signals that we haven't called strncmp() */\n+\tint m = -1; /* signals that we haven't compared strings */\n \n \tif (*never_interesting) {\n+\t\tconst int maxlen = (matchlen < pathlen) ? matchlen : pathlen;\n \t\t/*\n \t\t * We have not seen any match that sorts later\n \t\t * than the current path.\n@@ -500,10 +501,13 @@ static int match_entry(const struct name_entry *entry, int pathlen,\n \t\t * Does match sort strictly earlier than path\n \t\t * with their common parts?\n \t\t */\n-\t\tm = strncmp(match, entry->path,\n-\t\t\t (matchlen < pathlen) ? matchlen : pathlen);\n-\t\tif (m < 0)\n-\t\t\treturn 0;\n+\t\tif (maxlen && match[0] > entry->path[0]) {\n+\t\t\t/* no good for the shortcut here, match must be <= */\n+\t\t} else {\n+\t\t\tm = strncmp(match, entry->path, maxlen);\n+\t\t\tif(m < 0)\n+\t\t\t\treturn 0;\n+\t\t}\n \n \t\t/*\n \t\t * If we come here even once, that means there is at\n@@ -531,12 +535,17 @@ static int match_entry(const struct name_entry *entry, int pathlen,\n \t\t\treturn 0;\n \t}\n \n-\tif (m == -1)\n+\tif (m == -1) {\n \t\t/*\n-\t\t * we cheated and did not do strncmp(), so we do\n+\t\t * we cheated and did compare strings, so we do\n \t\t * that here.\n \t\t */\n-\t\tm = strncmp(match, entry->path, pathlen);\n+\t\tif (pathlen && match[0] == entry->path[0])\n+\t\t\t/* invariant: matchlen == pathlen */\n+\t\t\tm = strncmp(match, entry->path, pathlen);\n+\t\telse\n+\t\t\tm = 1;\n+\t}\n \n \t/*\n \t * If common part matched earlier then it is a hit,\n@@ -552,6 +561,7 @@ static int match_entry(const struct name_entry *entry, int pathlen,\n static int match_dir_prefix(const char *base,\n \t\t\t const char *match, int matchlen)\n {\n+\t/* invariant: baselen >= matchlen */\n \tif (strncmp(base, match, matchlen))\n \t\treturn 0;\n \n-- \n1.7.4.2\n"},{"id":"164788","messageId":"AANLkTinwovtXfm-OvVivwyjs2RT8+D6Mj=OXkQCNH8uy@mail.gmail.com","threadId":"26934","inReplyTo":"1301535481-1085-1-git-send-email-dpmcgee@gmail.com","subject":"Re: [PATCH 1/5] diff_tree_sha1: skip diff_tree if old == new","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-03-31T12:58:20Z","receivedAt":"2011-03-31T12:58:20Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Mar 31, 2011 at 8:37 AM, Dan McGee wrote:\n> These next few patches are all derived from trying to make operations on this\n> repository a bit faster:\n>    http://projects.archlinux.org/svntogit/packages.git/\n>\n> ...\n>\n> time git log -- zzzzz_not_exist >/dev/null\n>                          35.558s      0.976s\n\nDo you have numbers before and after applying this series? It'd be\ninteresting to see how much we gain from the series.\n-- \nDuy\n"},{"id":"164793","messageId":"AANLkTi=sShiwiRMF+cgiWimO80FBRKNmskwTb4JYZeSG@mail.gmail.com","threadId":"26934","inReplyTo":"AANLkTinwovtXfm-OvVivwyjs2RT8+D6Mj=OXkQCNH8uy@mail.gmail.com","subject":"Re: [PATCH 1/5] diff_tree_sha1: skip diff_tree if old == new","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-03-31T13:56:11Z","receivedAt":"2011-03-31T13:56:11Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"On Thu, Mar 31, 2011 at 7:58 AM, Nguyen Thai Ngoc Duy wrote:\n> On Thu, Mar 31, 2011 at 8:37 AM, Dan McGee wrote:\n>> These next few patches are all derived from trying to make operations on this\n>> repository a bit faster:\n>>    http://projects.archlinux.org/svntogit/packages.git/\n>>\n>> ...\n>>\n>> time git log -- zzzzz_not_exist >/dev/null\n>>                          35.558s      0.976s\n>\n> Do you have numbers before and after applying this series? It'd be\n> interesting to see how much we gain from the series.\n\nWhipped some up for you:\n\nRepo Operation master after delta\narch-packages ../git/git-log 2.26 2.27 -0.01\narch-packages ../git/git-log -- zzzzz_not_exist 34.69 26.75 7.93\narch-packages ../git/git-log -- aaaaa_first 6.02 5.76 0.26\nlinux-2.6 ../git/git-log 5.51 5.50 0.02\nlinux-2.6 ../git/git-log -- zzzzz_not_exist 0.95 0.92 0.03\nlinux-2.6 ../git/git-log -- aaaaa_first 0.89 0.86 0.03\n\nThese are all the \"real\" value from time with the full set of patches\napplied. As you can see, one either gains or isn't really affected by\nthese; anything under 0.05s delta is noise.\n\nBigger gains than this don't seem too plausible unless we move away\nfrom linear parsing and traversal of tree objects.\n\n-Dan\n"},{"id":"164933","messageId":"7vfwq1ehcq.fsf@alter.siamese.dyndns.org","threadId":"26934","inReplyTo":"1301535481-1085-1-git-send-email-dpmcgee@gmail.com","subject":"Re: [PATCH 1/5] diff_tree_sha1: skip diff_tree if old == new","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-04-01T22:28:53Z","receivedAt":"2011-04-01T22:28:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Dan McGee writes:\n\n> This was seen to happen in some invocations of git-log with a filtered\n> path. Only do it if we are not recursively descending, as otherwise we\n> mess with copy and rename detection in full tree moves.\n\nThere is no code that corresponds to your \"Only do it...\" description in\nyour patch, though. The existing code already takes care of that part\nwith or without your patch, no?\n\n> diff --git a/tree-diff.c b/tree-diff.c\n> index 76f83fc..ab90f1a 100644\n> --- a/tree-diff.c\n> +++ b/tree-diff.c\n> @@ -286,6 +286,9 @@ int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const cha\n> \tunsigned long size1, size2;\n> \tint retval;\n> \n> +\tif (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(old, new))\n> +\t\treturn 0;\n> +\n\nI am very curious why this patch makes a difference; doesn't an existing\ntest in compare_tree_entry() oalready cull extra recursion? There is:\n\n\tif (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(sha1, sha2) &&\n\t\tmode1 == mode2)\n\t\treturn 0;\n\nbefore a recursive call to diff_tree_sha1() to dig deeper.\n"},{"id":"164947","messageId":"BANLkTikZ=eH-Jdd-kdvw4JKPbqCr7kviZg@mail.gmail.com","threadId":"26934","inReplyTo":"1301535481-1085-5-git-send-email-dpmcgee@gmail.com","subject":"Re: [PATCH 5/5] tree-walk: match_entry microoptimization","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-04-02T09:06:56Z","receivedAt":"2011-04-02T09:06:56Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Mar 31, 2011 at 8:38 AM, Dan McGee wrote:\n> Before calling strncmp(), see if we can get away with checking only the\n> first character of the passed path components instead.\n>\n> Signed-off-by: Dan McGee \n\nI wonder if inlining strcmp() would be better (at least cleaner code).\nIt seems like you try to avoid the function call cost here.\n-- \nDuy\n"},{"id":"164948","messageId":"BANLkTi=QK0_P3=rGFLXzZzk7c7JSNxuBmA@mail.gmail.com","threadId":"26934","inReplyTo":"1301535481-1085-4-git-send-email-dpmcgee@gmail.com","subject":"Re: [PATCH 4/5] tree-walk: unroll get_mode since loop boundaries are well-known","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-04-02T09:28:55Z","receivedAt":"2011-04-02T09:28:55Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Mar 31, 2011 at 8:38 AM, Dan McGee wrote:\n> We know our mode entry in our tree objects should be 5 or 6 characters\n> long. This change both enforces this fact and also unrolls the parsing\n> of the information giving the compiler more room for optimization of the\n> operations.\n\nI'm skeptical. Did you measure signficant gain after this patch? I\nlooked at asm output with -O3 and failed to see the compiler doing\nanything fancy. Perhaps it's because I'm on x86 with quite small\nregister set.\n-- \nDuy\n"},{"id":"164955","messageId":"BANLkTi=MupnQ9Ovy=A0nD+wDaK7wkVDryw@mail.gmail.com","threadId":"26934","inReplyTo":"BANLkTi=QK0_P3=rGFLXzZzk7c7JSNxuBmA@mail.gmail.com","subject":"Re: [PATCH 4/5] tree-walk: unroll get_mode since loop boundaries are well-known","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-04-02T17:28:24Z","receivedAt":"2011-04-02T17:28:24Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"On Sat, Apr 2, 2011 at 4:28 AM, Nguyen Thai Ngoc Duy wrote:\n> On Thu, Mar 31, 2011 at 8:38 AM, Dan McGee wrote:\n>> We know our mode entry in our tree objects should be 5 or 6 characters\n>> long. This change both enforces this fact and also unrolls the parsing\n>> of the information giving the compiler more room for optimization of the\n>> operations.\n>\n> I'm skeptical. Did you measure signficant gain after this patch? I\n> looked at asm output with -O3 and failed to see the compiler doing\n> anything fancy. Perhaps it's because I'm on x86 with quite small\n> register set.\n\nI'm on x86_64 and was just using -O2; -O3 produces the same output\nactually. You can see it below. I had taken a look at this before I\nsubmitted, and noticed a few things:\n1. We do use multiple registers now since we aren't constrained to a loop.\n2. movzbl (for the string parts) and cmb instructions tend to get\nclustered first.\n3. mozbl (for the mode shifting) and leal instructions tend to get\nclustered later.\n4. The normal case now involves no conditional jumps until the ' '\n(space) comparison.\n\nCall these \"trivial\", but on my worst case operation times went from\n(shown below) 27.41 secs to 26.49 secs. Considering this operation is\ncalled 530,588,868 times (that is not a typo) during this operation,\nevery saved instruction or non-missed branch prediction does seem to\nmake a difference.\n\n-Dan\n\nRepo:\nhttp://projects.archlinux.org/svntogit/packages.git/\n\nOld:\n$ time ../git/git-log -- zzzzz_not_exist > /dev/null\n\nreal\t0m27.409s\nuser\t0m27.172s\nsys\t0m0.230s\n\n.LVL3:\n.LBB58:\n.LBB59:\n\t.loc 1 12 0 is_stmt 1\n\tmovzbl\t(%rsi), %eax\n\tcmpb\t$32, %al\n\tje\t.L5\n.LVL4:\n\t.loc 1 16 0\n\tleal\t-48(%rax), %edx\n.LVL5:\n\t.loc 1 15 0\n\tleaq\t1(%rsi), %rdi\n.LVL6:\n\t.loc 1 16 0\n\tcmpb\t$7, %dl\n\tja\t.L5\n\txorl\t%edx, %edx\n\tjmp\t.L6\n.LVL7:\n\t.p2align 4,,10\n\t.p2align 3\n.L7:\n\tleal\t-48(%rax), %ecx\n\tcmpb\t$7, %cl\n\tja\t.L5\n.LVL8:\n.L6:\n\t.loc 1 18 0\n\tmovzbl\t%al, %eax\n\tleal\t-48(%rax,%rdx,8), %edx\n.LVL9:\n\t.loc 1 15 0\n\tmovzbl\t(%rdi), %eax\n.LVL10:\n\taddq\t$1, %rdi\n.LVL11:\n\tcmpb\t$32, %al\n\tjne\t.L7\n\n\nNew:\n$ time ../git/git-log -- zzzzz_not_exist > /dev/null\n\nreal\t0m26.490s\nuser\t0m26.282s\nsys\t0m0.200s\n\n.LVL3:\n.LBB58:\n.LBB59:\n\t.loc 1 19 0 is_stmt 1\n\tmovzbl\t(%rsi), %eax\n.LVL4:\n\t.loc 1 20 0\n\tleal\t-48(%rax), %edx\n.LVL5:\n\tcmpb\t$7, %dl\n\tja\t.L5\n.LVL6:\n\t.loc 1 23 0\n\tmovzbl\t1(%rsi), %edx\n.LVL7:\n\t.loc 1 24 0\n\tleal\t-48(%rdx), %ecx\n\tcmpb\t$7, %cl\n\tja\t.L5\n.LVL8:\n\t.loc 1 27 0\n\tmovzbl\t2(%rsi), %ecx\n.LVL9:\n\t.loc 1 28 0\n\tleal\t-48(%rcx), %edi\n\tcmpb\t$7, %dil\n\tja\t.L5\n.LVL10:\n\t.loc 1 31 0\n\tmovzbl\t3(%rsi), %edi\n.LVL11:\n\t.loc 1 32 0\n\tleal\t-48(%rdi), %r8d\n\tcmpb\t$7, %r8b\n\tja\t.L5\n.LVL12:\n\t.loc 1 35 0\n\tmovzbl\t4(%rsi), %r8d\n.LVL13:\n\t.loc 1 36 0\n\tleal\t-48(%r8), %r9d\n\tcmpb\t$7, %r9b\n\tja\t.L5\n\t.loc 1 21 0\n\tmovzbl\t%al, %eax\n\t.loc 1 25 0\n\tmovzbl\t%dl, %edx\n\t.loc 1 29 0\n\tmovzbl\t%cl, %ecx\n\t.loc 1 25 0\n\tleal\t-432(%rdx,%rax,8), %edx\n\t.loc 1 33 0\n\tmovzbl\t%dil, %edi\n\t.loc 1 37 0\n\tmovzbl\t%r8b, %r8d\n\t.loc 1 35 0\n\tleaq\t5(%rsi), %rax\n\t.loc 1 29 0\n\tleal\t-48(%rcx,%rdx,8), %edx\n\t.loc 1 39 0\n\tmovzbl\t5(%rsi), %ecx\n\t.loc 1 33 0\n\tleal\t-48(%rdi,%rdx,8), %edx\n\t.loc 1 39 0\n\tcmpb\t$32, %cl\n\t.loc 1 37 0\n\tleal\t-48(%r8,%rdx,8), %edx\n.LVL14:\n\t.loc 1 39 0\n\tje\t.L7\n.LVL15:\n\t.loc 1 41 0\n\tleal\t-48(%rcx), %eax\n\tcmpb\t$7, %al\n\tja\t.L5\n\t.loc 1 45 0\n\tcmpb\t$32, 6(%rsi)\n\t.loc 1 42 0\n\tmovzbl\t%cl, %ecx\n\t.loc 1 40 0\n\tleaq\t6(%rsi), %rax\n\t.loc 1 42 0\n\tleal\t-48(%rcx,%rdx,8), %edx\n.LVL16:\n\t.loc 1 45 0\n\tjne\t.L5\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 63901f8..dd7bd45 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -4,11 +4,22 @@\n #include \"dir.h\"\n #include \"tree.h\"\n\n+static unsigned long hit_ctr = 0;\n+\n+static void print_hit_ctr(void)\n+{\n+ fprintf(stderr, \"hit_ctr: %lu\\n\", hit_ctr);\n+}\n+\n static const char *get_mode(const char *str, unsigned int *modep)\n {\n unsigned char c;\n unsigned int mode = 0;\n\n+ if(hit_ctr == 0) {\n+ atexit(print_hit_ctr);\n+ }\n+ hit_ctr++;\n /*\n * Unroll what looks like a loop since the bounds are\n * well-known. There should be at least 5 and at most 6\n"},{"id":"164956","messageId":"BANLkTinMoSBhG2d=JDhR5homsgn=_HB87w@mail.gmail.com","threadId":"26934","inReplyTo":"BANLkTikZ=eH-Jdd-kdvw4JKPbqCr7kviZg@mail.gmail.com","subject":"Re: [PATCH 5/5] tree-walk: match_entry microoptimization","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-04-02T17:54:39Z","receivedAt":"2011-04-02T17:54:39Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"On Sat, Apr 2, 2011 at 4:06 AM, Nguyen Thai Ngoc Duy wrote:\n> On Thu, Mar 31, 2011 at 8:38 AM, Dan McGee wrote:\n>> Before calling strncmp(), see if we can get away with checking only the\n>> first character of the passed path components instead.\n>>\n>> Signed-off-by: Dan McGee \n>\n> I wonder if inlining strcmp() would be better (at least cleaner code).\n> It seems like you try to avoid the function call cost here.\n\n100% agree with you, but I have no idea how to do that. Realize also\nyou can use memcmp() here; I tried that and got no noticeable gain\n(likely due to how short these strings are). However, it is what we\nuse in most other functions in this file. I assume the compiler would\ninline versions with a static length, but if you have suggestions as\nto how to inline a non-trivial version here I'm all ears.\n\n-Dan\n"},{"id":"164958","messageId":"BANLkTi=hJm4ax__5DDCvK9VdLcNxVO2bVA@mail.gmail.com","threadId":"26934","inReplyTo":"AANLkTinPSqDPdGi5nA3sH1D2wMSW1SQc+5gRqdLy++y0@mail.gmail.com","subject":"Fwd: [PATCH 1/5] diff_tree_sha1: skip diff_tree if old == new","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-04-02T18:38:21Z","receivedAt":"2011-04-02T18:38:21Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"Forgot to forward this to the list as well, I apologize.\n\nOn Fri, Apr 1, 2011 at 5:28 PM, Junio C Hamano wrote:\n> Dan McGee writes:\n>\n>> This was seen to happen in some invocations of git-log with a filtered\n>> path. Only do it if we are not recursively descending, as otherwise we\n>> mess with copy and rename detection in full tree moves.\n>\n> There is no code that corresponds to your \"Only do it...\" description in\n> your patch, though.  The existing code already takes care of that part\n> with or without your patch, no?\n\nDamn, I forgot to update the message- see below.\n\n>> diff --git a/tree-diff.c b/tree-diff.c\n>> index 76f83fc..ab90f1a 100644\n>> --- a/tree-diff.c\n>> +++ b/tree-diff.c\n>> @@ -286,6 +286,9 @@ int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const cha\n>>       unsigned long size1, size2;\n>>       int retval;\n>>\n>> +     if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(old, new))\n>> +             return 0;\n>> +\n>\n> I am very curious why this patch makes a difference; doesn't an existing\n> test in compare_tree_entry() oalready cull extra recursion?  There is:\n\nThis was originally testing RECURSIVE; however I discovered that was\nnot the culprit to my failed tests.\n\nt9300-fastimport.sh was failing on \"copy then modify subdirectory\" due\nto the full info not being loaded for the before sha1 in that test-\ninstead of showing the fcf778cda ... C100 part (this is just the first\nline of expected, all were the same), it was 000000 ... A. once I\nadded the above fallthrough to not shortcut if this option was\nenabled, things worked fine and all tests passed.\n\n>        if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(sha1, sha2) &&\n>                mode1 == mode2)\n>                return 0;\n>\n> before a recursive call to diff_tree_sha1() to dig deeper.\n>\n\nI'm not totally sure why this check wasn't working, but without the\nabove exception my patch definitely broke tests.\n\n-Dan\n"},{"id":"164975","messageId":"20110403040119.GA18104@do","threadId":"26934","inReplyTo":"1301535481-1085-3-git-send-email-dpmcgee@gmail.com","subject":"Re: [PATCH 3/5] tree-walk: micro-optimization in tree_entry_interesting","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-04-03T04:01:19Z","receivedAt":"2011-04-03T04:01:19Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Mar 30, 2011 at 08:37:59PM -0500, Dan McGee wrote:\n> In the case of a wide breadth top-level tree (~2400 entries, all trees\n> in this case), we can see a noticeable cost in the profiler calling\n> strncmp() here. Most of the time we are at the base level of the\n> repository, so base is \"\" and baselen == 0, which means we will always\n> test true. Break out this one tiny case so we can short circuit the\n> strncmp() call.\n> \n> This resulted in an ~11% improvement (43 to 38 secs) for a reasonable\n> log operation on the Arch Linux Packages SVN clone repository, which\n> contained 117220 commits and the aforementioned 2400 top-level objects:\n> git log -- autogen/trunk pacman/trunk/ wget/trunk/\n> \n> Negligible slowdown was noted with other repositories (e.g. linux-2.6).\n> \n> Signed-off-by: Dan McGee \n\nAck.\n\nOn my (slower) laptop, the same command with vanilla git -O3 takes\n95 secs. Your patch cuts it down to 82 secs.\n\nI tried inlining strncmp with a version from glibc. Without your patch\nit takes 88 secs. With your patch, it takes 86 secs (still worse than\nyour patch alone). A better strncmp version must be used on my system,\nI suspect.\n\n--8<--\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 322becc..0859b5c 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -457,6 +457,55 @@ int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned ch\n \treturn retval;\n }\n \n+static inline int inline_strncmp(const char *s1, const char *s2, size_t n)\n+{\n+\tunsigned char c1 = '\\0';\n+\tunsigned char c2 = '\\0';\n+\n+\tif (n == 0)\n+\t\treturn 0;\n+\n+\tif (n >= 4) {\n+\t\tsize_t n4 = n >> 2;\n+\t\tdo {\n+\t\t\tc1 = (unsigned char) *s1++;\n+\t\t\tc2 = (unsigned char) *s2++;\n+\t\t\tif (c1 == '\\0' || c1 != c2)\n+\t\t\t\treturn c1 - c2;\n+\t\t\tc1 = (unsigned char) *s1++;\n+\t\t\tc2 = (unsigned char) *s2++;\n+\t\t\tif (c1 == '\\0' || c1 != c2)\n+\t\t\t\treturn c1 - c2;\n+\t\t\tc1 = (unsigned char) *s1++;\n+\t\t\tc2 = (unsigned char) *s2++;\n+\t\t\tif (c1 == '\\0' || c1 != c2)\n+\t\t\t\treturn c1 - c2;\n+\t\t\tc1 = (unsigned char) *s1++;\n+\t\t\tc2 = (unsigned char) *s2++;\n+\t\t\tif (c1 == '\\0' || c1 != c2)\n+\t\t\t\treturn c1 - c2;\n+\t\t} while (--n4 > 0);\n+\t\tn &= 3;\n+\t}\n+\n+\twhile (n > 0) {\n+\t\tc1 = (unsigned char) *s1++;\n+\t\tc2 = (unsigned char) *s2++;\n+\t\tif (c1 == '\\0' || c1 != c2)\n+\t\t\treturn c1 - c2;\n+\t\tn--;\n+\t}\n+\n+\treturn c1 - c2;\n+}\n+\n+#if 1\n+#ifdef strncmp\n+#undef strncmp\n+#endif\n+#define strncmp inline_strncmp\n+#endif\n+\n static int match_entry(const struct name_entry *entry, int pathlen,\n \t\t const char *match, int matchlen,\n \t\t int *never_interesting)\n--8<--\n-- \nDuy\n"},{"id":"164976","messageId":"BANLkTind3zWEZYxgTXx=spOnAo_xnRx5eQ@mail.gmail.com","threadId":"26934","inReplyTo":"BANLkTi=MupnQ9Ovy=A0nD+wDaK7wkVDryw@mail.gmail.com","subject":"Re: [PATCH 4/5] tree-walk: unroll get_mode since loop boundaries are well-known","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-04-03T04:07:18Z","receivedAt":"2011-04-03T04:07:18Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Apr 3, 2011 at 12:28 AM, Dan McGee wrote:\n> On Sat, Apr 2, 2011 at 4:28 AM, Nguyen Thai Ngoc Duy wrote:\n>> On Thu, Mar 31, 2011 at 8:38 AM, Dan McGee wrote:\n>>> We know our mode entry in our tree objects should be 5 or 6 characters\n>>> long. This change both enforces this fact and also unrolls the parsing\n>>> of the information giving the compiler more room for optimization of the\n>>> operations.\n>>\n>> I'm skeptical. Did you measure signficant gain after this patch? I\n>> looked at asm output with -O3 and failed to see the compiler doing\n>> anything fancy. Perhaps it's because I'm on x86 with quite small\n>> register set.\n>\n> I'm on x86_64 and was just using -O2; -O3 produces the same output\n> actually. You can see it below. I had taken a look at this before I\n> submitted, and noticed a few things:\n> 1. We do use multiple registers now since we aren't constrained to a loop.\n> 2. movzbl (for the string parts) and cmb instructions tend to get\n> clustered first.\n> 3. mozbl (for the mode shifting) and leal instructions tend to get\n> clustered later.\n> 4. The normal case now involves no conditional jumps until the ' '\n> (space) comparison.\n>\n> Call these \"trivial\", but on my worst case operation times went from\n> (shown below) 27.41 secs to 26.49 secs. Considering this operation is\n> called 530,588,868 times (that is not a typo) during this operation,\n> every saved instruction or non-missed branch prediction does seem to\n> make a difference.\n\nIf it makes it better for you, I'm good.\n-- \nDuy\n"},{"id":"165069","messageId":"7vaag7dv0z.fsf@alter.siamese.dyndns.org","threadId":"26934","inReplyTo":"1301535481-1085-3-git-send-email-dpmcgee@gmail.com","subject":"Re: [PATCH 3/5] tree-walk: micro-optimization in tree_entry_interesting","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-04-03T18:55:40Z","receivedAt":"2011-04-03T18:55:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Dan McGee writes:\n\n> In the case of a wide breadth top-level tree (~2400 entries, all trees\n> in this case), we can see a noticeable cost in the profiler calling\n> strncmp() here. Most of the time we are at the base level of the\n> repository, so base is \"\" and baselen == 0, which means we will always\n> test true. Break out this one tiny case so we can short circuit the\n> strncmp() call.\n\nThis sounds as if the patch helps only when you have a superfat tree at\nthe \"top-level\" of the project, but wouldn't this benefit any superfat\ntree at _any_ level while we recursively descend into it?\n\n> This resulted in an ~11% improvement (43 to 38 secs) for a reasonable\n> log operation on the Arch Linux Packages SVN clone repository, which\n> contained 117220 commits and the aforementioned 2400 top-level objects:\n> git log -- autogen/trunk pacman/trunk/ wget/trunk/\n>\n> Negligible slowdown was noted with other repositories (e.g. linux-2.6).\n\nIt would have been easier to swallow if the last sentence were \"This could\nlead to a slowdown in repositories without directories that are too wide,\nbut in practice it was not even measurable.\" \"Negligible\" sounds as if it\nhad still measurable downside, and as if you decided that the slowdown can\nbe ignored---but obviously you are not an unbiased judge.\n\nThere is nothing wrong in the patch per-se, but I really wish we didn't\nhave to do this; it feels like the compiler should be helping us in this\ncase.\n\n> Signed-off-by: Dan McGee \n> ---\n> tree-walk.c | 4 ++--\n> 1 files changed, 2 insertions(+), 2 deletions(-)\n>\n> diff --git a/tree-walk.c b/tree-walk.c\n> index 9be8007..f386151 100644\n> --- a/tree-walk.c\n> +++ b/tree-walk.c\n> @@ -591,8 +591,8 @@ int tree_entry_interesting(const struct name_entry *entry,\n> \t\t\t\t\t ps->max_depth);\n> \t\t}\n> \n> -\t\t/* Does the base match? */\n> -\t\tif (!strncmp(base_str, match, baselen)) {\n> +\t\t/* Either there must be no base, or the base must match. */\n> +\t\tif (baselen == 0 || !strncmp(base_str, match, baselen)) {\n> \t\t\tif (match_entry(entry, pathlen,\n> \t\t\t\t\tmatch + baselen, matchlen - baselen,\n> \t\t\t\t\t&never_interesting))\n"},{"id":"165101","messageId":"BANLkTi=dF7p9K5c8SYFJjZ7uognwizuuaQ@mail.gmail.com","threadId":"26934","inReplyTo":"1301535481-1085-4-git-send-email-dpmcgee@gmail.com","subject":"Re: [PATCH 4/5] tree-walk: unroll get_mode since loop boundaries are well-known","fromName":"Erik Faye-Lund","fromEmail":"kusmabite@gmail.com","sentAt":"2011-04-04T10:29:29Z","receivedAt":"2011-04-04T10:29:29Z","isPatch":true,"sender":{"key":"kusmabite@gmail.com","avatar":"https://avatars.githubusercontent.com/u/47073?v=4"},"body":"On Thu, Mar 31, 2011 at 3:38 AM, Dan McGee wrote:\n> We know our mode entry in our tree objects should be 5 or 6 characters\n> long. This change both enforces this fact and also unrolls the parsing\n> of the information giving the compiler more room for optimization of the\n> operations.\n>\n> Signed-off-by: Dan McGee \n> ---\n>  tree-walk.c |   41 ++++++++++++++++++++++++++++++++++-------\n>  1 files changed, 34 insertions(+), 7 deletions(-)\n>\n> diff --git a/tree-walk.c b/tree-walk.c\n> index f386151..41383b0 100644\n> --- a/tree-walk.c\n> +++ b/tree-walk.c\n> @@ -9,16 +9,43 @@ static const char *get_mode(const char *str, unsigned int *modep)\n>        unsigned char c;\n>        unsigned int mode = 0;\n>\n> -       if (*str == ' ')\n> -               return NULL;\n> -\n> -       while ((c = *str++) != ' ') {\n> -               if (c < '0' || c > '7')\n> -                       return NULL;\n> +       /*\n> +        * Unroll what looks like a loop since the bounds are\n> +        * well-known. There should be at least 5 and at most 6\n> +        * characters available in any valid mode, as '40000' is the\n> +        * shortest while '160000' (S_IFGITLINK) is the longest.\n> +        */\n> +       /* char 1 */\n> +       c = *str++;\n> +       if (c < '0' || c > '7') return NULL;\n\nWe perfer this style:\n\nif (c < '0' || c > '7')\n\treturn NULL;\n\ni.e a line-break and a tab between the if-statement and the conditional code.\n\n> +       mode = (mode << 3) + (c - '0');\n> +       /* char 2 */\n> +       c = *str++;\n> +       if (c < '0' || c > '7') return NULL;\n> +       mode = (mode << 3) + (c - '0');\n> +       /* char 3 */\n> +       c = *str++;\n> +       if (c < '0' || c > '7') return NULL;\n> +       mode = (mode << 3) + (c - '0');\n> +       /* char 4 */\n> +       c = *str++;\n> +       if (c < '0' || c > '7') return NULL;\n> +       mode = (mode << 3) + (c - '0');\n> +       /* char 5 */\n> +       c = *str++;\n> +       if (c < '0' || c > '7') return NULL;\n> +       mode = (mode << 3) + (c - '0');\n\nWouldn't this part be cleaner as a constant-length loop? Any\noptimizing compiler should end up unrolling this, and we don't get as\nmuch code-duplication...\n\nOddly enough, this change gave me a drastic (> 20%) performance\nincrease in my test (isolating get_mode in a separate compilation\nunit, and calling it in a loop):\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex b8d504b..114ad63 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -7,42 +7,30 @@\n static const char *get_mode(const char *str, unsigned int *modep)\n {\n \tunsigned char c;\n-\tunsigned int mode = 0;\n+\tunsigned int mode = 0, i;\n\n \t/*\n-\t * Unroll what looks like a loop since the bounds are\n+\t * Allow the compiler to unroll the loop since the bounds are\n \t * well-known. There should be at least 5 and at most 6\n \t * characters available in any valid mode, as '40000' is the\n \t * shortest while '160000' (S_IFGITLINK) is the longest.\n \t */\n-\t/* char 1 */\n-\tc = *str++;\n-\tif (c < '0' || c > '7') return NULL;\n-\tmode = (mode << 3) + (c - '0');\n-\t/* char 2 */\n-\tc = *str++;\n-\tif (c < '0' || c > '7') return NULL;\n-\tmode = (mode << 3) + (c - '0');\n-\t/* char 3 */\n-\tc = *str++;\n-\tif (c < '0' || c > '7') return NULL;\n-\tmode = (mode << 3) + (c - '0');\n-\t/* char 4 */\n-\tc = *str++;\n-\tif (c < '0' || c > '7') return NULL;\n-\tmode = (mode << 3) + (c - '0');\n-\t/* char 5 */\n-\tc = *str++;\n-\tif (c < '0' || c > '7') return NULL;\n-\tmode = (mode << 3) + (c - '0');\n+\tfor (i = 0; i < 5; ++i) {\n+\t\tc = *str++;\n+\t\tif (c < '0' || c > '7')\n+\t\t\treturn NULL;\n+\t\tmode = (mode << 3) + (c - '0');\n+\t}\n \t/* char 6, optional */\n \tif (*str != ' ') {\n \t\tc = *str++;\n-\t\tif (c < '0' || c > '7') return NULL;\n+\t\tif (c < '0' || c > '7')\n+\t\t\treturn NULL;\n \t\tmode = (mode << 3) + (c - '0');\n \t}\n\n-\tif (*str != ' ') return NULL;\n+\tif (*str != ' ')\n+\t\treturn NULL;\n\n \t*modep = mode;\n \treturn str + 1;\n"},{"id":"165107","messageId":"4D99B9D9.1020101@op5.se","threadId":"26934","inReplyTo":"BANLkTi=dF7p9K5c8SYFJjZ7uognwizuuaQ@mail.gmail.com","subject":"Re: [PATCH 4/5] tree-walk: unroll get_mode since loop boundaries are well-known","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2011-04-04T12:30:17Z","receivedAt":"2011-04-04T12:30:17Z","isPatch":true,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"On 04/04/2011 12:29 PM, Erik Faye-Lund wrote:\n> \n> Wouldn't this part be cleaner as a constant-length loop? Any\n> optimizing compiler should end up unrolling this, and we don't get as\n> much code-duplication...\n> \n\nIt would.\n\n> Oddly enough, this change gave me a drastic (> 20%) performance\n> increase in my test (isolating get_mode in a separate compilation\n> unit, and calling it in a loop):\n> \n> diff --git a/tree-walk.c b/tree-walk.c\n> index b8d504b..114ad63 100644\n> --- a/tree-walk.c\n> +++ b/tree-walk.c\n> @@ -7,42 +7,30 @@\n> static const char *get_mode(const char *str, unsigned int *modep)\n> {\n> \tunsigned char c;\n> -\tunsigned int mode = 0;\n> +\tunsigned int mode = 0, i;\n> \n> \t/*\n> -\t * Unroll what looks like a loop since the bounds are\n> +\t * Allow the compiler to unroll the loop since the bounds are\n> \t * well-known. There should be at least 5 and at most 6\n> \t * characters available in any valid mode, as '40000' is the\n> \t * shortest while '160000' (S_IFGITLINK) is the longest.\n> \t */\n> -\t/* char 1 */\n> -\tc = *str++;\n> -\tif (c< '0' || c> '7') return NULL;\n> -\tmode = (mode<< 3) + (c - '0');\n> -\t/* char 2 */\n> -\tc = *str++;\n> -\tif (c< '0' || c> '7') return NULL;\n> -\tmode = (mode<< 3) + (c - '0');\n> -\t/* char 3 */\n> -\tc = *str++;\n> -\tif (c< '0' || c> '7') return NULL;\n> -\tmode = (mode<< 3) + (c - '0');\n> -\t/* char 4 */\n> -\tc = *str++;\n> -\tif (c< '0' || c> '7') return NULL;\n> -\tmode = (mode<< 3) + (c - '0');\n> -\t/* char 5 */\n> -\tc = *str++;\n> -\tif (c< '0' || c> '7') return NULL;\n> -\tmode = (mode<< 3) + (c - '0');\n> +\tfor (i = 0; i< 5; ++i) {\n\ns/i< 5/i < 5/ (nitpicking, yes)\n\n> +\t\tc = *str++;\n> +\t\tif (c< '0' || c> '7')\n> +\t\t\treturn NULL;\n> +\t\tmode = (mode<< 3) + (c - '0');\n\nThis could be (micro-)optimized further as:\n\n--%<--%<--\nfor (i = 0; i < 5; i++) {\n\tint c = *str++ - '0';\n\tif (c & ~7) {\n\t\t/* 5 chars is ok, so long as *str is now a space */\n\t\tif (i == 5 && c == ' ') {\n\t\t\t*modep = mode;\n\t\t\treturn str;\n\t\t}\n\t\treturn NULL;\n\t}\n\tmode = (mode << 3) + c;\n}\n\n/* this should be a space, or we've got a malformed entry */\nif (*str != ' ')\n\treturn NULL;\n\nreturn str + 1;\n--%<--%<--\n\nThis should be slightly faster since there's now only one comparison\ninside the loop and since one branch contains a second branch fork-point\nand an inevitable early return the branch prediction machinery in gcc\nwill favor the most common case properly, but pre-computations on 'mode'\nhave to be undone in one case of hitting the early return, it might be\nfaster to play pickup after a loop to 5 is done.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n\nConsidering the successes of the wars on alcohol, poverty, drugs and\nterror, I think we should give some serious thought to declaring war\non peace.\n"},{"id":"165113","messageId":"1301928386-25038-1-git-send-email-pclouds@gmail.com","threadId":"26934","inReplyTo":"1301535481-1085-3-git-send-email-dpmcgee@gmail.com","subject":"[PATCH] tree_entry_interesting: inline strncmp()","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-04-04T14:46:26Z","receivedAt":"2011-04-04T14:46:26Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"strncmp() is the function that takes most of the time inside\ntree_entry_interesting(). Inline it so we can shave some seconds out\nof function call time.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n Turns out simplicity is the best. My straight copy of strncmp from\n glibc performed worse.\n\n With this I get a slightly better performance than Dan's 3/5:\n 81.07-82.27 secs versus 82.02-82.92 (no other patches are applied).\n But I'm happy even if it gives the same or slightly worse\n performance because this applies to more cases than flat top tree\n case.\n\n Dan, match_dir_prefix() can also use some reordering to avoid\n strncmp(). But I suppose it won't give much gain on packages.git\n\n tree-walk.c | 28 ++++++++++++++++++++++++----\n 1 files changed, 24 insertions(+), 4 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 322becc..80bfc3a 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -457,6 +457,26 @@ int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned ch\n \treturn retval;\n }\n \n+/* Static version of strncmp to reduce function call cost */\n+static inline int strncmp_1(const char *s1, const char *s2, size_t n)\n+{\n+\tunsigned char c1 = '\\0';\n+\tunsigned char c2 = '\\0';\n+\n+\tif (!n)\n+\t\treturn 0;\n+\n+\twhile (n > 0) {\n+\t\tc1 = (unsigned char) *s1++;\n+\t\tc2 = (unsigned char) *s2++;\n+\t\tif (c1 == '\\0' || c1 != c2)\n+\t\t\treturn c1 - c2;\n+\t\tn--;\n+\t}\n+\n+\treturn c1 - c2;\n+}\n+\n static int match_entry(const struct name_entry *entry, int pathlen,\n \t\t const char *match, int matchlen,\n \t\t int *never_interesting)\n@@ -473,7 +493,7 @@ static int match_entry(const struct name_entry *entry, int pathlen,\n \t\t * Does match sort strictly earlier than path\n \t\t * with their common parts?\n \t\t */\n-\t\tm = strncmp(match, entry->path,\n+\t\tm = strncmp_1(match, entry->path,\n \t\t\t (matchlen < pathlen) ? matchlen : pathlen);\n \t\tif (m < 0)\n \t\t\treturn 0;\n@@ -509,7 +529,7 @@ static int match_entry(const struct name_entry *entry, int pathlen,\n \t\t * we cheated and did not do strncmp(), so we do\n \t\t * that here.\n \t\t */\n-\t\tm = strncmp(match, entry->path, pathlen);\n+\t\tm = strncmp_1(match, entry->path, pathlen);\n \n \t/*\n \t * If common part matched earlier then it is a hit,\n@@ -525,7 +545,7 @@ static int match_entry(const struct name_entry *entry, int pathlen,\n static int match_dir_prefix(const char *base, int baselen,\n \t\t\t const char *match, int matchlen)\n {\n-\tif (strncmp(base, match, matchlen))\n+\tif (strncmp_1(base, match, matchlen))\n \t\treturn 0;\n \n \t/*\n@@ -592,7 +612,7 @@ int tree_entry_interesting(const struct name_entry *entry,\n \t\t}\n \n \t\t/* Does the base match? */\n-\t\tif (!strncmp(base_str, match, baselen)) {\n+\t\tif (!strncmp_1(base_str, match, baselen)) {\n \t\t\tif (match_entry(entry, pathlen,\n \t\t\t\t\tmatch + baselen, matchlen - baselen,\n \t\t\t\t\t&never_interesting))\n-- \n1.7.4.74.g639db\n"},{"id":"165125","messageId":"7v7hba9csn.fsf@alter.siamese.dyndns.org","threadId":"26934","inReplyTo":"1301535481-1085-4-git-send-email-dpmcgee@gmail.com","subject":"Re: [PATCH 4/5] tree-walk: unroll get_mode since loop boundaries are well-known","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-04-04T16:55:20Z","receivedAt":"2011-04-04T16:55:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Dan McGee writes:\n\n> We know our mode entry in our tree objects should be 5 or 6 characters\n> long. This change both enforces this fact...\n\nI find the implementation later shown in the thread is cleaner, but I'd\ncomment on the word \"enforces\" here.\n\nIt is more like \"versions of git we know how to read from writes mode bits\nwith 5 or 6 characters---if we see something else, either the tree object\nis corrupt, or we are too old to read the new type of entry in the tree\nobject\".\n\nSo returning NULL is fine and it tells the caller that we do not\nunderstand the tree object. The caller says \"corrupt tree file\" when we\ndo so here, but this change needs to rephrase it. If we stopped because\nwe saw something other than ' ' after the run of octal digits, then we\nknow the tree is corrupt. If we saw a three octal digits 644 in the mode\nfield, terminated with ' ', maybe we are seeing a new kind of tree entry\ngenerated from later versions of git.\n\nIdeally, I'd rather see error checking done even higher layer than\ndecode_tree_entry() for the \"we are too old\" case, though. We should\nreturn mode 0644 in such a case, and let the caller suggest that the\nversion of git we are running might be too old, or the tree may have been\nwritten by a broken system that tried to mimic git in its error message.\n"},{"id":"165148","messageId":"BANLkTi=yVrS9MsBF1YR9D-QWej-n1uDQyQ@mail.gmail.com","threadId":"26934","inReplyTo":"7vaag7dv0z.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 3/5] tree-walk: micro-optimization in tree_entry_interesting","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-04-05T00:22:39Z","receivedAt":"2011-04-05T00:22:39Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"On Sun, Apr 3, 2011 at 1:55 PM, Junio C Hamano wrote:\n> Dan McGee writes:\n>\n>> In the case of a wide breadth top-level tree (~2400 entries, all trees\n>> in this case), we can see a noticeable cost in the profiler calling\n>> strncmp() here. Most of the time we are at the base level of the\n>> repository, so base is \"\" and baselen == 0, which means we will always\n>> test true. Break out this one tiny case so we can short circuit the\n>> strncmp() call.\n>\n> This sounds as if the patch helps only when you have a superfat tree at\n> the \"top-level\" of the project, but wouldn't this benefit any superfat\n> tree at _any_ level while we recursively descend into it?\n\nCorrect. I looked at the fact that more often than not, we wouldn't\nhave to descend into subtrees unless searching for a path underneath\nit, so that is why I phrased it that way. So the \"in the case of\" was\nquite literally the case I was testing, but didn't mean to exclude\nother potential test cases.\n\n>> This resulted in an ~11% improvement (43 to 38 secs) for a reasonable\n>> log operation on the Arch Linux Packages SVN clone repository, which\n>> contained 117220 commits and the aforementioned 2400 top-level objects:\n>>     git log -- autogen/trunk pacman/trunk/ wget/trunk/\n>>\n>> Negligible slowdown was noted with other repositories (e.g. linux-2.6).\n>\n> It would have been easier to swallow if the last sentence were \"This could\n> lead to a slowdown in repositories without directories that are too wide,\n> but in practice it was not even measurable.\"  \"Negligible\" sounds as if it\n> had still measurable downside, and as if you decided that the slowdown can\n> be ignored---but obviously you are not an unbiased judge.\n\nPerhaps I was too cautious with my words- but I was also trying to not\nbe biased. Considering this same operation takes < 1 second in\nlinux-2.6, I only wanted to mention it could have a slight effect. In\nreality I saw nothing more than an extra 0.01s or so, and definitely\nnothing significant. Let me know if you see otherwise.\n\ndmcgee@galway ~/projects/linux-2.6 (master)\n$ time ../git/git-log -- zzzzz_not_exist > /dev/null\n\nreal\t0m0.945s\nuser\t0m0.857s\nsys\t0m0.083s\n\n> There is nothing wrong in the patch per-se, but I really wish we didn't\n> have to do this; it feels like the compiler should be helping us in this\n> case.\n>\n>> Signed-off-by: Dan McGee \n>> ---\n>>  tree-walk.c |    4 ++--\n>>  1 files changed, 2 insertions(+), 2 deletions(-)\n>>\n>> diff --git a/tree-walk.c b/tree-walk.c\n>> index 9be8007..f386151 100644\n>> --- a/tree-walk.c\n>> +++ b/tree-walk.c\n>> @@ -591,8 +591,8 @@ int tree_entry_interesting(const struct name_entry *entry,\n>>                                             ps->max_depth);\n>>               }\n>>\n>> -             /* Does the base match? */\n>> -             if (!strncmp(base_str, match, baselen)) {\n>> +             /* Either there must be no base, or the base must match. */\n>> +             if (baselen == 0 || !strncmp(base_str, match, baselen)) {\n>>                       if (match_entry(entry, pathlen,\n>>                                       match + baselen, matchlen - baselen,\n>>                                       &never_interesting))\n>\n"},{"id":"165164","messageId":"BANLkTi==M=N+Z3qcsYk+tHap8A1Y41QfLw@mail.gmail.com","threadId":"26934","inReplyTo":"7v7hba9csn.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 4/5] tree-walk: unroll get_mode since loop boundaries are well-known","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-04-05T05:33:37Z","receivedAt":"2011-04-05T05:33:37Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"On Mon, Apr 4, 2011 at 5:29 AM, Erik Faye-Lund wrote:\n>\n> We perfer this style:\n>\n> if (c < '0' || c > '7')\n> return NULL;\n>\n> i.e a line-break and a tab between the if-statement and the conditional code.\nI am well aware, I just wanted to make the code a bit less lengthy due\nto the repetition.\n\nOn Mon, Apr 4, 2011 at 11:55 AM, Junio C Hamano wrote:\n> Dan McGee writes:\n>\n>> We know our mode entry in our tree objects should be 5 or 6 characters\n>> long. This change both enforces this fact...\n>\n> I find the implementation later shown in the thread is cleaner,\nTotally agree; I should have tried to do it this way in the first\nplace. However, compiling the fixed-length 0 to 5 loop does not\nproduce fully-unrolled assembly for me with CFLAGS=\"-march=native\n-mtune=native -O2 -pipe -g\" on x86_64. I see two copies of the loop\nonly, and even worse is the (lack of) performance (each is the mode of\n3 runs). Compilers are stupid apparently.\n\nHand-unrolled:\n$ time ../git/git-log -- zzzzz_not_exist > /dev/null\nreal\t0m28.616s\nuser\t0m28.428s\nsys\t0m0.177s\n\nStatic counter loop:\n$ time ../git/git-log -- zzzzz_not_exist > /dev/null\nreal\t0m26.393s\nuser\t0m26.185s\nsys\t0m0.203s\n\nDiff between the two down at the bottom.\n\n> but I'd\n> comment on the word \"enforces\" here.\n>\n> It is more like \"versions of git we know how to read from writes mode bits\n> with 5 or 6 characters---if we see something else, either the tree object\n> is corrupt, or we are too old to read the new type of entry in the tree\n> object\".\nOK, sounds like we have opposite thinking on this, interesting.\n\nget_mode() is not get_permissions()- it is the same as the stat()\nst_mode field, which means it has to (as of now) include at least one\nof the S_IFREG, S_IFDIR, or S_IFGITLINK flags in its value.\n\nAll of S_ISREG, S_ISDIR, and S_ISGITLINK are used fsck_walk_tree(). So\nI'm not seeing a change in the tree storage format happening anytime\nsoon as there is little way to preserve both forward and backward\ncompatibility.\n\nCurrently git will happily parse both a \"1\" in the tree stream, or a\n\"165324132132464677321513252351\"- it doesn't care. The problem is in\nthe former case, a mode of 01 doesn't have any significance later on.\nIn the latter case, we will be left-shifting our mode to hell and it\nbecomes worthless.\n\nDo we disagree on clamping the lower limit at 5, the upper limit at 6, or both?\n\n> So returning NULL is fine and it tells the caller that we do not\n> understand the tree object.  The caller says \"corrupt tree file\" when we\n> do so here, but this change needs to rephrase it.  If we stopped because\n> we saw something other than ' ' after the run of octal digits, then we\n> know the tree is corrupt.  If we saw a three octal digits 644 in the mode\n> field, terminated with ' ', maybe we are seeing a new kind of tree entry\n> generated from later versions of git.\n>\n> Ideally, I'd rather see error checking done even higher layer than\n> decode_tree_entry() for the \"we are too old\" case, though.  We should\n> return mode 0644 in such a case, and let the caller suggest that the\n> version of git we are running might be too old, or the tree may have been\n> written by a broken system that tried to mimic git in its error message.\n>\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 63901f8..63ec130 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -7,34 +7,21 @@\n static const char *get_mode(const char *str, unsigned int *modep)\n {\n unsigned char c;\n- unsigned int mode = 0;\n+ unsigned int mode = 0, i;\n\n /*\n- * Unroll what looks like a loop since the bounds are\n+ * Allow the compiler to unroll the loop since the bounds are\n * well-known. There should be at least 5 and at most 6\n * characters available in any valid mode, as '40000' is the\n * shortest while '160000' (S_IFGITLINK) is the longest.\n */\n- /* char 1 */\n- c = *str++;\n- if (c < '0' || c > '7') return NULL;\n- mode = (mode << 3) + (c - '0');\n- /* char 2 */\n- c = *str++;\n- if (c < '0' || c > '7') return NULL;\n- mode = (mode << 3) + (c - '0');\n- /* char 3 */\n- c = *str++;\n- if (c < '0' || c > '7') return NULL;\n- mode = (mode << 3) + (c - '0');\n- /* char 4 */\n- c = *str++;\n- if (c < '0' || c > '7') return NULL;\n- mode = (mode << 3) + (c - '0');\n- /* char 5 */\n- c = *str++;\n- if (c < '0' || c > '7') return NULL;\n- mode = (mode << 3) + (c - '0');\n+ /* chars 1-5, optional */\n+ for (i = 0; i < 5; i++) {\n+ c = *str++;\n+ if (c < '0' || c > '7')\n+ return NULL;\n+ mode = (mode << 3) + (c - '0');\n+ }\n /* char 6, optional */\n if (*str != ' ') {\n c = *str++;\n"},{"id":"165240","messageId":"BANLkTin9P-OdTQhPTwcvgvpDoBg7E+va5Q@mail.gmail.com","threadId":"26934","inReplyTo":"BANLkTi==M=N+Z3qcsYk+tHap8A1Y41QfLw@mail.gmail.com","subject":"Re: [PATCH 4/5] tree-walk: unroll get_mode since loop boundaries are well-known","fromName":"Antriksh Pany","fromEmail":"antriksh.pany@gmail.com","sentAt":"2011-04-05T23:55:24Z","receivedAt":"2011-04-05T23:55:24Z","isPatch":true,"sender":{"key":"antriksh.pany@gmail.com","avatar":null},"body":"On Mon, Apr 4, 2011 at 10:33 PM, Dan McGee wrote:\n> ....\n> Totally agree; I should have tried to do it this way in the first\n> place. However, compiling the fixed-length 0 to 5 loop does not\n> produce fully-unrolled assembly for me with CFLAGS=\"-march=native\n> -mtune=native -O2 -pipe -g\" on x86_64. I see two copies of the loop\n> only, and even worse is the (lack of) performance (each is the mode of\n> 3 runs). Compilers are stupid apparently.\n> ....\n\nCan you try -O3? Or an explicit '-funroll-loops'?\ngcc I think does not do aggressive speed optimizations at the cost of\nspace when at O2.\n\nCheers\nAntriksh\n"},{"id":"165311","messageId":"BANLkTikNv+xGKZv-5bxQJWASym1ZDuAuYw@mail.gmail.com","threadId":"26934","inReplyTo":"BANLkTin9P-OdTQhPTwcvgvpDoBg7E+va5Q@mail.gmail.com","subject":"Re: [PATCH 4/5] tree-walk: unroll get_mode since loop boundaries are well-known","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-04-06T20:45:59Z","receivedAt":"2011-04-06T20:45:59Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"On Tue, Apr 5, 2011 at 6:55 PM, Antriksh Pany wrote:\n> On Mon, Apr 4, 2011 at 10:33 PM, Dan McGee wrote:\n>> ....\n>> Totally agree; I should have tried to do it this way in the first\n>> place. However, compiling the fixed-length 0 to 5 loop does not\n>> produce fully-unrolled assembly for me with CFLAGS=\"-march=native\n>> -mtune=native -O2 -pipe -g\" on x86_64. I see two copies of the loop\n>> only, and even worse is the (lack of) performance (each is the mode of\n>> 3 runs). Compilers are stupid apparently.\n>> ....\n>\n> Can you try -O3? Or an explicit '-funroll-loops'?\n> gcc I think does not do aggressive speed optimizations at the cost of\n> space when at O2.\n\nSure- both of these options show the loop being unrolled for all 5\niterations. However, that doesn't help me and the other 95% of people\nusing distro packages, git-scm.com binaries, or anyone compiling with\nthe default CFLAGS optimization level which is unfortunate.\n\n-Dan\n"},{"id":"166925","messageId":"BANLkTikMhUuog23TJhUT7Km7hPO7On4Apg@mail.gmail.com","threadId":"26934","inReplyTo":"1301535481-1085-1-git-send-email-dpmcgee@gmail.com","subject":"Re: [PATCH 1/5] diff_tree_sha1: skip diff_tree if old == new","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-05-03T07:34:12Z","receivedAt":"2011-05-03T07:34:12Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Mar 31, 2011 at 8:37 AM, Dan McGee wrote:\n> These next few patches are all derived from trying to make operations on this\n> repository a bit faster:\n>    http://projects.archlinux.org/svntogit/packages.git/\n>\n> As far as a different shape of repository, this one qualifies. Some stats from\n> after running `git gc --prune` and looking at things from count-objects among\n> others:\n\nDoes this series need any work to get (at least part of) it in?\n-- \nDuy\n"},{"id":"174575","messageId":"CAEik5nOSd+r0orJK63v4TEL-eKyE9eHuVgpH-9n+UjpeMv3nxA@mail.gmail.com","threadId":"26934","inReplyTo":"1301535481-1085-2-git-send-email-dpmcgee@gmail.com","subject":"Re: [PATCH 2/5] tree-walk: drop unused parameter from match_dir_prefix","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-08-30T18:55:42Z","receivedAt":"2011-08-30T18:55:42Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"On Wed, Mar 30, 2011 at 8:37 PM, Dan McGee wrote:\n> Signed-off-by: Dan McGee \n> ---\n\nThis still seems to apply to the current code, ping?\n\n>  tree-walk.c |    4 ++--\n>  1 files changed, 2 insertions(+), 2 deletions(-)\n>\n> diff --git a/tree-walk.c b/tree-walk.c\n> index 322becc..9be8007 100644\n> --- a/tree-walk.c\n> +++ b/tree-walk.c\n> @@ -522,7 +522,7 @@ static int match_entry(const struct name_entry *entry, int pathlen,\n>        return 0;\n>  }\n>\n> -static int match_dir_prefix(const char *base, int baselen,\n> +static int match_dir_prefix(const char *base,\n>                            const char *match, int matchlen)\n>  {\n>        if (strncmp(base, match, matchlen))\n> @@ -579,7 +579,7 @@ int tree_entry_interesting(const struct name_entry *entry,\n>\n>                if (baselen >= matchlen) {\n>                        /* If it doesn't match, move along... */\n> -                       if (!match_dir_prefix(base_str, baselen, match, matchlen))\n> +                       if (!match_dir_prefix(base_str, match, matchlen))\n>                                goto match_wildcards;\n>\n>                        if (!ps->recursive || ps->max_depth == -1)\n> --\n> 1.7.4.2\n"},{"id":"174579","messageId":"CAEik5nNaDkAa2+63g1z3c1JUB8sLuTLfYP3jLKZJg2=yKqyzDg@mail.gmail.com","threadId":"26934","inReplyTo":"CAEik5nOKrpFycZYVnSu4_5LYWxn0JS_hVXyiQH-80Bu-C4k8VQ@mail.gmail.com","subject":"Re: [PATCH 3/5] tree-walk: micro-optimization in tree_entry_interesting","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-08-30T19:51:32Z","receivedAt":"2011-08-30T19:51:32Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"On Mon, Apr 4, 2011 at 7:22 PM, Dan McGee wrote:\n> On Sun, Apr 3, 2011 at 1:55 PM, Junio C Hamano wrote:\n>> Dan McGee writes:\n>>\n>>> In the case of a wide breadth top-level tree (~2400 entries, all trees\n>>> in this case), we can see a noticeable cost in the profiler calling\n>>> strncmp() here. Most of the time we are at the base level of the\n>>> repository, so base is \"\" and baselen == 0, which means we will always\n>>> test true. Break out this one tiny case so we can short circuit the\n>>> strncmp() call.\n>>\n>> This sounds as if the patch helps only when you have a superfat tree at\n>> the \"top-level\" of the project, but wouldn't this benefit any superfat\n>> tree at _any_ level while we recursively descend into it?\n>\n> Correct. I looked at the fact that more often than not, we wouldn't\n> have to descend into subtrees unless searching for a path underneath\n> it, so that is why I phrased it that way. So the \"in the case of\" was\n> quite literally the case I was testing, but didn't mean to exclude\n> other potential test cases.\n>\n>>> This resulted in an ~11% improvement (43 to 38 secs) for a reasonable\n>>> log operation on the Arch Linux Packages SVN clone repository, which\n>>> contained 117220 commits and the aforementioned 2400 top-level objects:\n>>>     git log -- autogen/trunk pacman/trunk/ wget/trunk/\n>>>\n>>> Negligible slowdown was noted with other repositories (e.g. linux-2.6).\n>>\n>> It would have been easier to swallow if the last sentence were \"This could\n>> lead to a slowdown in repositories without directories that are too wide,\n>> but in practice it was not even measurable.\"  \"Negligible\" sounds as if it\n>> had still measurable downside, and as if you decided that the slowdown can\n>> be ignored---but obviously you are not an unbiased judge.\n>\n> Perhaps I was too cautious with my words- but I was also trying to not\n> be biased. Considering this same operation takes < 1 second in\n> linux-2.6, I only wanted to mention it could have a slight effect. In\n> reality I saw nothing more than an extra 0.01s or so, and definitely\n> nothing significant. Let me know if you see otherwise.\n>\n> dmcgee@galway ~/projects/linux-2.6 (master)\n> $ time ../git/git-log -- zzzzz_not_exist > /dev/null\n>\n> real    0m0.945s\n> user    0m0.857s\n> sys     0m0.083s\n>\n>> There is nothing wrong in the patch per-se, but I really wish we didn't\n>> have to do this; it feels like the compiler should be helping us in this\n>> case.\n\nIf I resurrect this with an updated commit message reflecting concerns\nraised, can it be merged? Given that it is a noticeable performance\nboost on real-life repositories and I can show it has little (<1%) to\nno impact on most repos, it is a definite win.\n\n>>> Signed-off-by: Dan McGee \n>>> ---\n>>>  tree-walk.c |    4 ++--\n>>>  1 files changed, 2 insertions(+), 2 deletions(-)\n>>>\n>>> diff --git a/tree-walk.c b/tree-walk.c\n>>> index 9be8007..f386151 100644\n>>> --- a/tree-walk.c\n>>> +++ b/tree-walk.c\n>>> @@ -591,8 +591,8 @@ int tree_entry_interesting(const struct name_entry *entry,\n>>>                                             ps->max_depth);\n>>>               }\n>>>\n>>> -             /* Does the base match? */\n>>> -             if (!strncmp(base_str, match, baselen)) {\n>>> +             /* Either there must be no base, or the base must match. */\n>>> +             if (baselen == 0 || !strncmp(base_str, match, baselen)) {\n>>>                       if (match_entry(entry, pathlen,\n>>>                                       match + baselen, matchlen - baselen,\n>>>                                       &never_interesting))\n>>\n>\n"},{"id":"174583","messageId":"7v62le1vlx.fsf@alter.siamese.dyndns.org","threadId":"26934","inReplyTo":"CAEik5nNaDkAa2+63g1z3c1JUB8sLuTLfYP3jLKZJg2=yKqyzDg@mail.gmail.com","subject":"Re: [PATCH 3/5] tree-walk: micro-optimization in tree_entry_interesting","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-08-30T20:40:26Z","receivedAt":"2011-08-30T20:40:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Dan McGee writes:\n\n>> dmcgee@galway ~/projects/linux-2.6 (master)\n>> $ time ../git/git-log -- zzzzz_not_exist > /dev/null\n>>\n>> real 0m0.945s\n>> user 0m0.857s\n>> sys 0m0.083s\n>>\n>>> There is nothing wrong in the patch per-se, but I really wish we didn't\n>>> have to do this; it feels like the compiler should be helping us in this\n>>> case.\n>\n> If I resurrect this with an updated commit message reflecting concerns\n> raised, can it be merged? Given that it is a noticeable performance\n> boost on real-life repositories and I can show it has little (<1%) to\n> no impact on most repos, it is a definite win.\n\nI do not see anything wrong in this particular patch per-se, but I really\nwish we didn't have to do this.\n\nPlease include a few lines of benchmarking result in the updated commit\nlog message as well if you are rerolling this patch, perhaps like I did\nin:\n\n http://thread.gmane.org/gmane.comp.version-control.git/179926/focus=180361\n\ni.e., before and after comparison.\n\nThanks.\n"},{"id":"175143","messageId":"1315533766-25901-1-git-send-email-dpmcgee@gmail.com","threadId":"26934","inReplyTo":"7v62le1vlx.fsf@alter.siamese.dyndns.org","subject":"[PATCH 1/2] tree-walk: drop unused parameter from match_dir_prefix","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-09-09T02:02:45Z","receivedAt":"2011-09-09T02:02:45Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"Signed-off-by: Dan McGee \n---\n tree-walk.c | 4 ++--\n 1 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 33f749e..dbcd94a 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -522,7 +522,7 @@ static int match_entry(const struct name_entry *entry, int pathlen,\n \treturn 0;\n }\n \n-static int match_dir_prefix(const char *base, int baselen,\n+static int match_dir_prefix(const char *base,\n \t\t\t const char *match, int matchlen)\n {\n \tif (strncmp(base, match, matchlen))\n@@ -579,7 +579,7 @@ int tree_entry_interesting(const struct name_entry *entry,\n \n \t\tif (baselen >= matchlen) {\n \t\t\t/* If it doesn't match, move along... */\n-\t\t\tif (!match_dir_prefix(base_str, baselen, match, matchlen))\n+\t\t\tif (!match_dir_prefix(base_str, match, matchlen))\n \t\t\t\tgoto match_wildcards;\n \n \t\t\tif (!ps->recursive || ps->max_depth == -1)\n-- \n1.7.6.1\n"},{"id":"175144","messageId":"1315533766-25901-2-git-send-email-dpmcgee@gmail.com","threadId":"26934","inReplyTo":"1315533766-25901-1-git-send-email-dpmcgee@gmail.com","subject":"[PATCH 2/2] tree-walk: micro-optimization in tree_entry_interesting","fromName":"Dan McGee","fromEmail":"dpmcgee@gmail.com","sentAt":"2011-09-09T02:02:46Z","receivedAt":"2011-09-09T02:02:46Z","isPatch":true,"sender":{"key":"dpmcgee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/265817?v=4"},"body":"In the case of a wide breadth top-level tree (~2400 entries, all trees\nin this case), we can see a noticeable cost in the profiler calling\nstrncmp() here. Most of the time we are at the base level of the\nrepository, so base is \"\" and baselen == 0, which means we will always\ntest true. Break out this one tiny case so we can short circuit the\nstrncmp() call.\n\nTest cases are as follows. packages.git is the Arch Linux git-svn clone\nof the packages repository which has the characteristics above.\n\nCommands:\n[1] packages.git, /usr/bin/time git log >/dev/null\n[2] packages.git, /usr/bin/time git log -- autogen/trunk pacman/trunk wget/trunk >/dev/null\n[3] linux.git, /usr/bin/time git log >/dev/null\n[4] linux.git, /usr/bin/time git log -- drivers/ata drivers/uio tools >/dev/null\n\nResults:\n before after %faster\n[1] 2.56 2.55 0.4%\n[2] 51.82 48.66 6.5%\n[3] 5.58 5.61 -0.5%\n[4] 1.55 1.51 0.2%\n\nThe takeaway here is this doesn't matter in many operations, but it does\nfor a certain style of repository and operation where it nets a 6.5%\nmeasured improvement. The other changes are likely not significant by\nreasonable statistics methods.\n\nNote: the measured improvement when originally submitted was ~11% (43 to\n38 secs) for operation [2]. At the time, the repository had 117220\ncommits; it now has 137537 commits.\n\nSigned-off-by: Dan McGee \n---\n tree-walk.c | 4 ++--\n 1 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex dbcd94a..e401f07 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -591,8 +591,8 @@ int tree_entry_interesting(const struct name_entry *entry,\n \t\t\t\t\t ps->max_depth);\n \t\t}\n \n-\t\t/* Does the base match? */\n-\t\tif (!strncmp(base_str, match, baselen)) {\n+\t\t/* Either there must be no base, or the base must match. */\n+\t\tif (baselen == 0 || !strncmp(base_str, match, baselen)) {\n \t\t\tif (match_entry(entry, pathlen,\n \t\t\t\t\tmatch + baselen, matchlen - baselen,\n \t\t\t\t\t&never_interesting))\n-- \n1.7.6.1\n"}]}