{"thread":{"id":"45631","subject":"[PATCH v2] unpack-trees: avoid duplicate ODB lookups during checkout","startedAt":"2017-04-07T15:53:41Z","lastAt":"2017-04-11T20:42:53Z","messageCount":8,"participants":["git@jeffhostetler.com","René Scharfe","Jeff King","Jeff Hostetler"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"316360","messageId":"20170407155306.42375-2-git@jeffhostetler.com","threadId":"45631","inReplyTo":"20170407155306.42375-1-git@jeffhostetler.com","subject":"[PATCH v2] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-07T15:53:06Z","receivedAt":"2017-04-07T15:53:41Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nTeach traverse_trees_recursive() to not do redundant ODB\nlookups when both directories refer to the same OID.\n\nIn operations such as read-tree, checkout, and merge when\nthe differences between the commits are relatively small,\nthere will likely be many directories that have the same\nSHA-1.  In these cases we can avoid hitting the ODB multiple\ntimes for the same SHA-1.\n\nThis patch handles n=2 and n=3 cases and simply copies the\ndata rather than repeating the fill_tree_descriptor().\n\n================\nOn the Windows repo (500K trees, 3.1M files, 450MB index),\nthis reduced the overall time by 0.75 seconds when cycling\nbetween 2 commits with a single file difference.\n\n(avg) before: 22.699\n(avg) after:  21.955\n===============\n\n================\nUsing the p0004-read-tree test (posted earlier this week)\nwith 1M files on Linux:\n\nbefore:\n$ ./p0004-read-tree.sh\n0004.5: switch work1 work2 (1003037)       11.99(8.12+3.32)\n0004.6: switch commit aliases (1003037)    11.95(8.20+3.14)\n\nafter:\n$ ./p0004-read-tree.sh\n0004.5: switch work1 work2 (1003037)       11.02(7.71+2.78)\n0004.6: switch commit aliases (1003037)    10.95(7.57+2.82)\n================\n\nSigned-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n---\n unpack-trees.c | 23 +++++++++++++++++++----\n 1 file changed, 19 insertions(+), 4 deletions(-)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 3a8ee19..143c5d9 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -531,6 +531,11 @@ static int switch_cache_bottom(struct traverse_info *info)\n \treturn ret;\n }\n \n+static inline int are_same_oid(struct name_entry *name_j, struct name_entry *name_k)\n+{\n+\treturn name_j->oid && name_k->oid && !oidcmp(name_j->oid, name_k->oid);\n+}\n+\n static int traverse_trees_recursive(int n, unsigned long dirmask,\n \t\t\t\t    unsigned long df_conflicts,\n \t\t\t\t    struct name_entry *names,\n@@ -554,10 +559,20 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,\n \tnewinfo.df_conflicts |= df_conflicts;\n \n \tfor (i = 0; i < n; i++, dirmask >>= 1) {\n-\t\tconst unsigned char *sha1 = NULL;\n-\t\tif (dirmask & 1)\n-\t\t\tsha1 = names[i].oid->hash;\n-\t\tbuf[i] = fill_tree_descriptor(t+i, sha1);\n+\t\tif (i > 0 && are_same_oid(&names[i], &names[i-1])) {\n+\t\t\t/* implicitly borrow buf[i-1] inside tree_desc[i] */\n+\t\t\tmemcpy(&t[i], &t[i-1], sizeof(struct tree_desc));\n+\t\t\tbuf[i] = NULL;\n+\t\t} else if (i > 1 && are_same_oid(&names[i], &names[i-2])) {\n+\t\t\t/* implicitly borrow buf[i-2] inside tree_desc[i] */\n+\t\t\tmemcpy(&t[i], &t[i-2], sizeof(struct tree_desc));\n+\t\t\tbuf[i] = NULL;\n+\t\t} else {\n+\t\t\tconst unsigned char *sha1 = NULL;\n+\t\t\tif (dirmask & 1)\n+\t\t\t\tsha1 = names[i].oid->hash;\n+\t\t\tbuf[i] = fill_tree_descriptor(t+i, sha1);\n+\t\t}\n \t}\n \n \tbottom = switch_cache_bottom(&newinfo);\n-- \n2.9.3\n\n"},{"id":"316361","messageId":"20170407155306.42375-1-git@jeffhostetler.com","threadId":"45631","inReplyTo":null,"subject":"[PATCH v2] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-07T15:53:05Z","receivedAt":"2017-04-07T15:53:42Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler <jeffhost@microsoft.com>\n\nVersion 2 simplifies this and just copies the tree_descriptor\ndata and borrows the underlying buffer without mallocing.  It\nalso handles the n=3 cases, so merges shold be helped too.\n\nI've updated the p0004 perf times in the commit message.\nThe V2 changes took ~0.15 off the V1 times.  The total\nreduction is ~1 second.\n\n================\nAvoid duplicate ODB lookups for trees during traverse_tree_recursive().\n\nJeff Hostetler (1):\n  unpack-trees: avoid duplicate ODB lookups during checkout\n\n unpack-trees.c | 23 +++++++++++++++++++----\n 1 file changed, 19 insertions(+), 4 deletions(-)\n\n-- \n2.9.3\n\n"},{"id":"316411","messageId":"23662d7b-84a9-4b71-1aa5-5d3d111f5c3d@web.de","threadId":"45631","inReplyTo":"20170407155306.42375-2-git@jeffhostetler.com","subject":"Re: [PATCH v2] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-04-08T14:06:41Z","receivedAt":"2017-04-08T14:07:07Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 07.04.2017 um 17:53 schrieb git@jeffhostetler.com:\n> From: Jeff Hostetler <jeffhost@microsoft.com>\n> \n> Teach traverse_trees_recursive() to not do redundant ODB\n> lookups when both directories refer to the same OID.\n> \n> In operations such as read-tree, checkout, and merge when\n> the differences between the commits are relatively small,\n> there will likely be many directories that have the same\n> SHA-1.  In these cases we can avoid hitting the ODB multiple\n> times for the same SHA-1.\n> \n> This patch handles n=2 and n=3 cases and simply copies the\n> data rather than repeating the fill_tree_descriptor().\n> \n> ================\n> On the Windows repo (500K trees, 3.1M files, 450MB index),\n> this reduced the overall time by 0.75 seconds when cycling\n> between 2 commits with a single file difference.\n> \n> (avg) before: 22.699\n> (avg) after:  21.955\n> ===============\n> \n> ================\n> Using the p0004-read-tree test (posted earlier this week)\n> with 1M files on Linux:\n> \n> before:\n> $ ./p0004-read-tree.sh\n> 0004.5: switch work1 work2 (1003037)       11.99(8.12+3.32)\n> 0004.6: switch commit aliases (1003037)    11.95(8.20+3.14)\n> \n> after:\n> $ ./p0004-read-tree.sh\n> 0004.5: switch work1 work2 (1003037)       11.02(7.71+2.78)\n> 0004.6: switch commit aliases (1003037)    10.95(7.57+2.82)\n> ================\n> \n> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n> ---\n>   unpack-trees.c | 23 +++++++++++++++++++----\n>   1 file changed, 19 insertions(+), 4 deletions(-)\n> \n> diff --git a/unpack-trees.c b/unpack-trees.c\n> index 3a8ee19..143c5d9 100644\n> --- a/unpack-trees.c\n> +++ b/unpack-trees.c\n> @@ -531,6 +531,11 @@ static int switch_cache_bottom(struct traverse_info *info)\n>   \treturn ret;\n>   }\n>   \n> +static inline int are_same_oid(struct name_entry *name_j, struct name_entry *name_k)\n> +{\n> +\treturn name_j->oid && name_k->oid && !oidcmp(name_j->oid, name_k->oid);\n> +}\n> +\n>   static int traverse_trees_recursive(int n, unsigned long dirmask,\n>   \t\t\t\t    unsigned long df_conflicts,\n>   \t\t\t\t    struct name_entry *names,\n> @@ -554,10 +559,20 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,\n>   \tnewinfo.df_conflicts |= df_conflicts;\n>   \n>   \tfor (i = 0; i < n; i++, dirmask >>= 1) {\n> -\t\tconst unsigned char *sha1 = NULL;\n> -\t\tif (dirmask & 1)\n> -\t\t\tsha1 = names[i].oid->hash;\n> -\t\tbuf[i] = fill_tree_descriptor(t+i, sha1);\n> +\t\tif (i > 0 && are_same_oid(&names[i], &names[i-1])) {\n> +\t\t\t/* implicitly borrow buf[i-1] inside tree_desc[i] */\n> +\t\t\tmemcpy(&t[i], &t[i-1], sizeof(struct tree_desc));\n\nAn assignment would be simpler:\n\n\t\t\tt[i] = t[i - 1];\n\n> +\t\t\tbuf[i] = NULL;\n> +\t\t} else if (i > 1 && are_same_oid(&names[i], &names[i-2])) {\n> +\t\t\t/* implicitly borrow buf[i-2] inside tree_desc[i] */\n> +\t\t\tmemcpy(&t[i], &t[i-2], sizeof(struct tree_desc));\n\nSimilar case.\n\n> +\t\t\tbuf[i] = NULL;\n\nWhat makes the previous two entries special, or differently put: Why not \njust check *all* previous entries?  MAX_UNPACK_TREES is 8; the number of \ncomparisons would just about double in the worst case and stay the same \nfor three trees or less.  The order of four trees or more wouldn't \nmatter anymore.\n\n> +\t\t} else {\n> +\t\t\tconst unsigned char *sha1 = NULL;\n> +\t\t\tif (dirmask & 1)\n> +\t\t\t\tsha1 = names[i].oid->hash;\n> +\t\t\tbuf[i] = fill_tree_descriptor(t+i, sha1);\n> +\t\t}\n>   \t}\n>   \n>   \tbottom = switch_cache_bottom(&newinfo);\n> \n"},{"id":"316517","messageId":"20170410205540.wvlb7ch7bodiytmh@sigill.intra.peff.net","threadId":"45631","inReplyTo":"23662d7b-84a9-4b71-1aa5-5d3d111f5c3d@web.de","subject":"Re: [PATCH v2] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-04-10T20:55:40Z","receivedAt":"2017-04-10T20:55:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Apr 08, 2017 at 04:06:41PM +0200, René Scharfe wrote:\n\n> > +\t\t} else if (i > 1 && are_same_oid(&names[i], &names[i-2])) {\n> > +\t\t\t/* implicitly borrow buf[i-2] inside tree_desc[i] */\n> > +\t\t\tmemcpy(&t[i], &t[i-2], sizeof(struct tree_desc));\n> \n> Similar case.\n> \n> > +\t\t\tbuf[i] = NULL;\n> \n> What makes the previous two entries special, or differently put: Why not\n> just check *all* previous entries?  MAX_UNPACK_TREES is 8; the number of\n> comparisons would just about double in the worst case and stay the same for\n> three trees or less.  The order of four trees or more wouldn't matter\n> anymore.\n\nIf I understand correctly, we've got N (up to 8) trees, and we want to\nfind sets of duplicates. Adjacency doesn't matter. Aren't our options\nbasically:\n\n  - look through all previous entries naively, O(N^2)\n\n  - sort the list, O(N log N); but we need the original order, so we'd\n    have to unsort at the end, too\n\n  - use a hash table, O(N) but with O(N) extra storage\n\nI know N=8 isn't very big algorithmically speaking, but it would feel\nugly to introduce something quadratic. Especially the limit of 8 seems\nrather arbitrary. In normal cases we see at most a 3-way merge. Beyond\nthat we're in octopus territory, and 8 is way too low there (I think the\noctopus strategy just unpacks one at a time and barfs if there are any\nconflicts).\n\nI assume the rationale behind \"check the last 2\" is just \"this\noptimization will kick in reliably for all sane cases\", weird octopus\nunpack-trees be damned (though reading ca885a4fe, it sounds like 4-trees\ncan actually happen, but I'm not clear on how).\n\n-Peff\n"},{"id":"316525","messageId":"ea0aa4ea-1c28-c1dd-db92-d4758b9dca88@jeffhostetler.com","threadId":"45631","inReplyTo":"23662d7b-84a9-4b71-1aa5-5d3d111f5c3d@web.de","subject":"Re: [PATCH v2] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-10T21:26:05Z","receivedAt":"2017-04-10T21:26:11Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/8/2017 10:06 AM, René Scharfe wrote:\n> Am 07.04.2017 um 17:53 schrieb git@jeffhostetler.com:\n>> From: Jeff Hostetler <jeffhost@microsoft.com>\n>>\n>> Teach traverse_trees_recursive() to not do redundant ODB\n>> lookups when both directories refer to the same OID.\n>>\n>> In operations such as read-tree, checkout, and merge when\n>> the differences between the commits are relatively small,\n>> there will likely be many directories that have the same\n>> SHA-1.  In these cases we can avoid hitting the ODB multiple\n>> times for the same SHA-1.\n>>\n>> This patch handles n=2 and n=3 cases and simply copies the\n>> data rather than repeating the fill_tree_descriptor().\n>>\n>> ================\n>> On the Windows repo (500K trees, 3.1M files, 450MB index),\n>> this reduced the overall time by 0.75 seconds when cycling\n>> between 2 commits with a single file difference.\n>>\n>> (avg) before: 22.699\n>> (avg) after:  21.955\n>> ===============\n>>\n>> ================\n>> Using the p0004-read-tree test (posted earlier this week)\n>> with 1M files on Linux:\n>>\n>> before:\n>> $ ./p0004-read-tree.sh\n>> 0004.5: switch work1 work2 (1003037)       11.99(8.12+3.32)\n>> 0004.6: switch commit aliases (1003037)    11.95(8.20+3.14)\n>>\n>> after:\n>> $ ./p0004-read-tree.sh\n>> 0004.5: switch work1 work2 (1003037)       11.02(7.71+2.78)\n>> 0004.6: switch commit aliases (1003037)    10.95(7.57+2.82)\n>> ================\n>>\n>> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>\n>> ---\n>>   unpack-trees.c | 23 +++++++++++++++++++----\n>>   1 file changed, 19 insertions(+), 4 deletions(-)\n>>\n>> diff --git a/unpack-trees.c b/unpack-trees.c\n>> index 3a8ee19..143c5d9 100644\n>> --- a/unpack-trees.c\n>> +++ b/unpack-trees.c\n>> @@ -531,6 +531,11 @@ static int switch_cache_bottom(struct\n>> traverse_info *info)\n>>       return ret;\n>>   }\n>>   +static inline int are_same_oid(struct name_entry *name_j, struct\n>> name_entry *name_k)\n>> +{\n>> +    return name_j->oid && name_k->oid && !oidcmp(name_j->oid,\n>> name_k->oid);\n>> +}\n>> +\n>>   static int traverse_trees_recursive(int n, unsigned long dirmask,\n>>                       unsigned long df_conflicts,\n>>                       struct name_entry *names,\n>> @@ -554,10 +559,20 @@ static int traverse_trees_recursive(int n,\n>> unsigned long dirmask,\n>>       newinfo.df_conflicts |= df_conflicts;\n>>         for (i = 0; i < n; i++, dirmask >>= 1) {\n>> -        const unsigned char *sha1 = NULL;\n>> -        if (dirmask & 1)\n>> -            sha1 = names[i].oid->hash;\n>> -        buf[i] = fill_tree_descriptor(t+i, sha1);\n>> +        if (i > 0 && are_same_oid(&names[i], &names[i-1])) {\n>> +            /* implicitly borrow buf[i-1] inside tree_desc[i] */\n>> +            memcpy(&t[i], &t[i-1], sizeof(struct tree_desc));\n>\n> An assignment would be simpler:\n>\n>             t[i] = t[i - 1];\n\nTrue, but this might be a coin toss.  Maybe we should\nsee what the generated assembly looks like for each ??\n\n>\n>> +            buf[i] = NULL;\n>> +        } else if (i > 1 && are_same_oid(&names[i], &names[i-2])) {\n>> +            /* implicitly borrow buf[i-2] inside tree_desc[i] */\n>> +            memcpy(&t[i], &t[i-2], sizeof(struct tree_desc));\n>\n> Similar case.\n>\n>> +            buf[i] = NULL;\n>\n> What makes the previous two entries special, or differently put: Why not\n> just check *all* previous entries?  MAX_UNPACK_TREES is 8; the number of\n> comparisons would just about double in the worst case and stay the same\n> for three trees or less.  The order of four trees or more wouldn't\n> matter anymore.\n\nI tried to hit the common cases.  This loop runs a lot\nand I didn't want to put an O(n^2) thing in there to\nlook for any matching peer.  Most of the time we are\nin a simple 2 or 3 way effort.  I didn't want to pay\nfor the looping/branching overhead for the obscure [4..8]\nefforts.\n\n>\n>> +        } else {\n>> +            const unsigned char *sha1 = NULL;\n>> +            if (dirmask & 1)\n>> +                sha1 = names[i].oid->hash;\n>> +            buf[i] = fill_tree_descriptor(t+i, sha1);\n>> +        }\n>>       }\n>>         bottom = switch_cache_bottom(&newinfo);\n>>\n"},{"id":"316526","messageId":"ed64f8fc-9cec-4c46-b9e6-9e9e4983f95a@jeffhostetler.com","threadId":"45631","inReplyTo":"20170410205540.wvlb7ch7bodiytmh@sigill.intra.peff.net","subject":"Re: [PATCH v2] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-10T21:28:13Z","receivedAt":"2017-04-10T21:28:19Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/10/2017 4:55 PM, Jeff King wrote:\n> On Sat, Apr 08, 2017 at 04:06:41PM +0200, René Scharfe wrote:\n>\n>>> +\t\t} else if (i > 1 && are_same_oid(&names[i], &names[i-2])) {\n>>> +\t\t\t/* implicitly borrow buf[i-2] inside tree_desc[i] */\n>>> +\t\t\tmemcpy(&t[i], &t[i-2], sizeof(struct tree_desc));\n>>\n>> Similar case.\n>>\n>>> +\t\t\tbuf[i] = NULL;\n>>\n>> What makes the previous two entries special, or differently put: Why not\n>> just check *all* previous entries?  MAX_UNPACK_TREES is 8; the number of\n>> comparisons would just about double in the worst case and stay the same for\n>> three trees or less.  The order of four trees or more wouldn't matter\n>> anymore.\n>\n> If I understand correctly, we've got N (up to 8) trees, and we want to\n> find sets of duplicates. Adjacency doesn't matter. Aren't our options\n> basically:\n>\n>   - look through all previous entries naively, O(N^2)\n>\n>   - sort the list, O(N log N); but we need the original order, so we'd\n>     have to unsort at the end, too\n>\n>   - use a hash table, O(N) but with O(N) extra storage\n>\n> I know N=8 isn't very big algorithmically speaking, but it would feel\n> ugly to introduce something quadratic. Especially the limit of 8 seems\n> rather arbitrary. In normal cases we see at most a 3-way merge. Beyond\n> that we're in octopus territory, and 8 is way too low there (I think the\n> octopus strategy just unpacks one at a time and barfs if there are any\n> conflicts).\n>\n> I assume the rationale behind \"check the last 2\" is just \"this\n> optimization will kick in reliably for all sane cases\", weird octopus\n> unpack-trees be damned (though reading ca885a4fe, it sounds like 4-trees\n> can actually happen, but I'm not clear on how).\n\nyeah, i didn't want to pay for the obscure (n >= 4) cases with any\nof the above.  doing 2 or 3 gets us checkout and merge.  these are\nthe common usages.\n\nJeff\n\n"},{"id":"316532","messageId":"001f55c6-a694-7dde-b14b-9d1dcc9c9a09@web.de","threadId":"45631","inReplyTo":"ea0aa4ea-1c28-c1dd-db92-d4758b9dca88@jeffhostetler.com","subject":"Re: [PATCH v2] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-04-10T23:09:57Z","receivedAt":"2017-04-10T23:10:27Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 10.04.2017 um 23:26 schrieb Jeff Hostetler:\n > On 4/8/2017 10:06 AM, René Scharfe wrote:\n >> Am 07.04.2017 um 17:53 schrieb git@jeffhostetler.com:\n >>> +            /* implicitly borrow buf[i-1] inside tree_desc[i] */\n >>> +            memcpy(&t[i], &t[i-1], sizeof(struct tree_desc));\n >>\n >> An assignment would be simpler:\n >>\n >>             t[i] = t[i - 1];\n >\n > True, but this might be a coin toss.  Maybe we should\n > see what the generated assembly looks like for each ??\n\nClang, GCC and ICC inline that memcpy call; the assembly output is the\nsame for both variants: https://godbolt.org/g/1q0YwK.  I guess you worry\nabout compilers that are just bad at struct assignments (i.e. worse than\ncalling memcpy)?  Do you have examples (just curious)?\n\nAssignments are easier on the eye of human readers in any case, and\nthere is no way to silently get the size wrong.\n\n > I tried to hit the common cases.  This loop runs a lot\n > and I didn't want to put an O(n^2) thing in there to\n > look for any matching peer.  Most of the time we are\n > in a simple 2 or 3 way effort.  I didn't want to pay\n > for the looping/branching overhead for the obscure [4..8]\n > efforts.\n\nMakes sense, and it's a nice heuristic.  Perhaps it would be a good idea\nto document these choices in a comment?\n\nRené\n"},{"id":"316644","messageId":"ad2b5a8c-f9d0-82cb-25b8-76c1922af7f5@jeffhostetler.com","threadId":"45631","inReplyTo":"001f55c6-a694-7dde-b14b-9d1dcc9c9a09@web.de","subject":"Re: [PATCH v2] unpack-trees: avoid duplicate ODB lookups during checkout","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2017-04-11T20:42:33Z","receivedAt":"2017-04-11T20:42:53Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 4/10/2017 7:09 PM, René Scharfe wrote:\n> Am 10.04.2017 um 23:26 schrieb Jeff Hostetler:\n>> On 4/8/2017 10:06 AM, René Scharfe wrote:\n>>> Am 07.04.2017 um 17:53 schrieb git@jeffhostetler.com:\n>>>> +            /* implicitly borrow buf[i-1] inside tree_desc[i] */\n>>>> +            memcpy(&t[i], &t[i-1], sizeof(struct tree_desc));\n>>>\n>>> An assignment would be simpler:\n>>>\n>>>             t[i] = t[i - 1];\n>>\n>> True, but this might be a coin toss.  Maybe we should\n>> see what the generated assembly looks like for each ??\n>\n> Clang, GCC and ICC inline that memcpy call; the assembly output is the\n> same for both variants: https://godbolt.org/g/1q0YwK.  I guess you worry\n> about compilers that are just bad at struct assignments (i.e. worse than\n> calling memcpy)?  Do you have examples (just curious)?\n\nNice website!  Really!\n\nYes, my concern was that structure copies would do it\nfield by field rather than just a block copy.  No, I\ndon't have any examples -- maybe just some very old\nbrain cells.... :-)\n\nAnd I just checked VS2015 and the structure copy is a\nfew instructions shorter, but roughly the same.\n\n>\n> Assignments are easier on the eye of human readers in any case, and\n> there is no way to silently get the size wrong.\n\nagreed. thanks.\n\n>\n>> I tried to hit the common cases.  This loop runs a lot\n>> and I didn't want to put an O(n^2) thing in there to\n>> look for any matching peer.  Most of the time we are\n>> in a simple 2 or 3 way effort.  I didn't want to pay\n>> for the looping/branching overhead for the obscure [4..8]\n>> efforts.\n>\n> Makes sense, and it's a nice heuristic.  Perhaps it would be a good idea\n> to document these choices in a comment?\n\nGood point. Thanks.\n\n\n"}]}