{"thread":{"id":"42560","subject":"[PATCH] tree-diff: avoid alloca for large allocations","startedAt":"2016-06-07T22:53:00Z","lastAt":"2016-06-08T01:36:56Z","messageCount":3,"participants":["Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"288668","messageId":"20160607225300.GA2285@sigill.intra.peff.net","threadId":"42560","inReplyTo":null,"subject":"[PATCH] tree-diff: avoid alloca for large allocations","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-06-07T22:53:00Z","receivedAt":"2016-06-07T22:53:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Commit 72441af (tree-diff: rework diff_tree() to generate\ndiffs for multiparent cases as well, 2014-04-07) introduced\nthe use of alloca so that the common cases of commits with 1\nor 2 parents would not be adversely affected by going\nthrough the multi-parent code.\n\nHowever, our xalloca is not ideal when the number of parents\ngrows very large:\n\n  1. If the requested size is too large for our stack,\n     alloca() has no way to tell us, and we simply segfault\n     while trying to access the memory.\n\n  2. It does not use our usual memory_limit_check() logic.\n\nI measured, and alloca is indeed buying us a very small\nspeedup over xmalloc()/free(). So we'd want to keep\nsomething like it.\n\nThis patch simply puts a conditional in place at each\ncallsite: we use alloca for common known-small numbers of\nparents, and otherwise use the heap. We are technically\nstill vulnerable to (1), but no more so than if we simply\nput a few dozen bytes on the stack, which we must do all the\ntime anyway. And likewise, we technically miss a memory\nlimit check if it is tiny, but such a limit is pointless.\n\nAn alternative to this would be implement something like:\n\n  struct tree *tp, tp_fallback[2];\n  if (nparent <= ARRAY_SIZE(tp_fallback))\n          tp = tp_fallback;\n  else\n\t  ALLOC_ARRAY(tp, nparent);\n  ...\n  if (tp != tp_fallback)\n\t  free(tp);\n\nThat would let us drop our xalloca() portability code\nentirely. But in my measurements, this seemed to perform\nslightly worse than the xalloca solution.\n\nNote in the example above, and in the patch below, I've used\nALLOC_ARRAY() to replace the manual xmalloc(nr * sizeof(*x)).\nBesides being shorter, this has the bonus that one cannot\naccidentally overflow a size_t during that computation.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nAnd yes, I actually saw this in real life. The commit in question had a\nmillion parents, which is obviously silly. I never let it run to\ncompletion, as presumably there's some quadratic stuff in there. So we\ncould also have a general max-parent limit. I'm just not sure what it\nwould be; any limit we set would be arbitrary. Most of the rest of git\nis happy to chug along using whatever RAM and CPU you are comfortable to\ngive it, and if you want to wait 5 minutes for your answer, go right\nahead.\n\n tree-diff.c | 22 ++++++++++++++++------\n 1 file changed, 16 insertions(+), 6 deletions(-)\n\ndiff --git a/tree-diff.c b/tree-diff.c\nindex ff4e0d3..ebf40f4 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -14,6 +14,16 @@\n  */\n #define S_IFXMIN_NEQ\tS_DIFFTREE_IFXMIN_NEQ\n \n+#define FAST_ARRAY_ALLOC(x, nr) do { \\\n+\tif ((nr) <= 2) \\\n+\t\t(x) = xalloca((nr) * sizeof(*(x))); \\\n+\telse \\\n+\t\tALLOC_ARRAY((x), nr); \\\n+} while(0)\n+#define FAST_ARRAY_FREE(x, nr) do { \\\n+\tif ((nr) > 2) \\\n+\t\tfree((x)); \\\n+} while(0)\n \n static struct combine_diff_path *ll_diff_tree_paths(\n \tstruct combine_diff_path *p, const unsigned char *sha1,\n@@ -265,7 +275,7 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *p,\n \tif (recurse) {\n \t\tconst unsigned char **parents_sha1;\n \n-\t\tparents_sha1 = xalloca(nparent * sizeof(parents_sha1[0]));\n+\t\tFAST_ARRAY_ALLOC(parents_sha1, nparent);\n \t\tfor (i = 0; i < nparent; ++i) {\n \t\t\t/* same rule as in emitthis */\n \t\t\tint tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ);\n@@ -277,7 +287,7 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *p,\n \t\tstrbuf_add(base, path, pathlen);\n \t\tstrbuf_addch(base, '/');\n \t\tp = ll_diff_tree_paths(p, sha1, parents_sha1, nparent, base, opt);\n-\t\txalloca_free(parents_sha1);\n+\t\tFAST_ARRAY_FREE(parents_sha1, nparent);\n \t}\n \n \tstrbuf_setlen(base, old_baselen);\n@@ -402,8 +412,8 @@ static struct combine_diff_path *ll_diff_tree_paths(\n \tvoid *ttree, **tptree;\n \tint i;\n \n-\ttp     = xalloca(nparent * sizeof(tp[0]));\n-\ttptree = xalloca(nparent * sizeof(tptree[0]));\n+\tFAST_ARRAY_ALLOC(tp, nparent);\n+\tFAST_ARRAY_ALLOC(tptree, nparent);\n \n \t/*\n \t * load parents first, as they are probably already cached.\n@@ -531,8 +541,8 @@ static struct combine_diff_path *ll_diff_tree_paths(\n \tfree(ttree);\n \tfor (i = nparent-1; i >= 0; i--)\n \t\tfree(tptree[i]);\n-\txalloca_free(tptree);\n-\txalloca_free(tp);\n+\tFAST_ARRAY_FREE(tptree, nparent);\n+\tFAST_ARRAY_FREE(tp, nparent);\n \n \treturn p;\n }\n-- \n2.9.0.rc1.159.g81173282e\n"},{"id":"288672","messageId":"xmqq8tygo6s4.fsf@gitster.mtv.corp.google.com","threadId":"42560","inReplyTo":"20160607225300.GA2285@sigill.intra.peff.net","subject":"Re: [PATCH] tree-diff: avoid alloca for large allocations","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-06-08T00:36:59Z","receivedAt":"2016-06-08T00:36:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> An alternative to this would be implement something like:\n>\n>   struct tree *tp, tp_fallback[2];\n>   if (nparent <= ARRAY_SIZE(tp_fallback))\n>           tp = tp_fallback;\n>   else\n> \t  ALLOC_ARRAY(tp, nparent);\n>   ...\n>   if (tp != tp_fallback)\n> \t  free(tp);\n>\n> That would let us drop our xalloca() portability code\n> entirely. But in my measurements, this seemed to perform\n> slightly worse than the xalloca solution.\n\nIt indeed is curious why this \"obvious\" alternative performed\nworse.\n\n> +#define FAST_ARRAY_ALLOC(x, nr) do { \\\n> +\tif ((nr) <= 2) \\\n> +\t\t(x) = xalloca((nr) * sizeof(*(x))); \\\n> +\telse \\\n> +\t\tALLOC_ARRAY((x), nr); \\\n> +} while(0)\n> +#define FAST_ARRAY_FREE(x, nr) do { \\\n> +\tif ((nr) > 2) \\\n> +\t\tfree((x)); \\\n> +} while(0)\n\nAn obvious and clean implementation of the idea.\n\nThe only slight worry I have is that nr must stay constant until the\ntime the caller calls FREE(), but for the only three callsite pairs\nit is clear nparent will stay constant and this is local to the\nfile.\n\nThanks.\n\n>  static struct combine_diff_path *ll_diff_tree_paths(\n>  \tstruct combine_diff_path *p, const unsigned char *sha1,\n> @@ -265,7 +275,7 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *p,\n>  \tif (recurse) {\n>  \t\tconst unsigned char **parents_sha1;\n>  \n> -\t\tparents_sha1 = xalloca(nparent * sizeof(parents_sha1[0]));\n> +\t\tFAST_ARRAY_ALLOC(parents_sha1, nparent);\n>  \t\tfor (i = 0; i < nparent; ++i) {\n>  \t\t\t/* same rule as in emitthis */\n>  \t\t\tint tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ);\n> @@ -277,7 +287,7 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *p,\n>  \t\tstrbuf_add(base, path, pathlen);\n>  \t\tstrbuf_addch(base, '/');\n>  \t\tp = ll_diff_tree_paths(p, sha1, parents_sha1, nparent, base, opt);\n> -\t\txalloca_free(parents_sha1);\n> +\t\tFAST_ARRAY_FREE(parents_sha1, nparent);\n>  \t}\n>  \n>  \tstrbuf_setlen(base, old_baselen);\n> @@ -402,8 +412,8 @@ static struct combine_diff_path *ll_diff_tree_paths(\n>  \tvoid *ttree, **tptree;\n>  \tint i;\n>  \n> -\ttp     = xalloca(nparent * sizeof(tp[0]));\n> -\ttptree = xalloca(nparent * sizeof(tptree[0]));\n> +\tFAST_ARRAY_ALLOC(tp, nparent);\n> +\tFAST_ARRAY_ALLOC(tptree, nparent);\n>  \n>  \t/*\n>  \t * load parents first, as they are probably already cached.\n> @@ -531,8 +541,8 @@ static struct combine_diff_path *ll_diff_tree_paths(\n>  \tfree(ttree);\n>  \tfor (i = nparent-1; i >= 0; i--)\n>  \t\tfree(tptree[i]);\n> -\txalloca_free(tptree);\n> -\txalloca_free(tp);\n> +\tFAST_ARRAY_FREE(tptree, nparent);\n> +\tFAST_ARRAY_FREE(tp, nparent);\n>  \n>  \treturn p;\n>  }\n"},{"id":"288675","messageId":"20160608013656.GA7277@sigill.intra.peff.net","threadId":"42560","inReplyTo":"xmqq8tygo6s4.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] tree-diff: avoid alloca for large allocations","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-06-08T01:36:56Z","receivedAt":"2016-06-08T01:36:56Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jun 07, 2016 at 05:36:59PM -0700, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > An alternative to this would be implement something like:\n> >\n> >   struct tree *tp, tp_fallback[2];\n> >   if (nparent <= ARRAY_SIZE(tp_fallback))\n> >           tp = tp_fallback;\n> >   else\n> > \t  ALLOC_ARRAY(tp, nparent);\n> >   ...\n> >   if (tp != tp_fallback)\n> > \t  free(tp);\n> >\n> > That would let us drop our xalloca() portability code\n> > entirely. But in my measurements, this seemed to perform\n> > slightly worse than the xalloca solution.\n> \n> It indeed is curious why this \"obvious\" alternative performed\n> worse.\n\nYeah. I'd be happy if somebody wanted to prove me wrong here. It's\nentirely possible I just did something stupid. I had wrapped up the\nabove in the FAST_ARRAY_ALLOC macro. It would waste the stack space when\nwe _did_ have to call malloc, but that should almost never happen in my\nbenchmark. It also allocates an extra slot on the stack for non-merge\ncommits. So I guess the wasted 24 bytes or whatever could have in\nimpact. It's also possible that the extra variable simply tickles the\noptimizer in some way; I didn't look at the generated asm.\n\nFWIW, here are the timings I had come up with for running \"git log --raw\n--no-abbrev --no-renames\" on linux.git (the same benchmark from the\ncommit that originally added the alloca). The \"time\" output at the end\nis best-of-five, with the \"attempt\" lines showing the wall-clock time\nfor each:\n\n  [original, with xalloca]\n  Attempt 1: 30.669\n  Attempt 2: 30.782\n  Attempt 3: 31.807\n  Attempt 4: 31.152\n  Attempt 5: 30.243\n\n  real    0m30.243s\n  user    0m30.112s\n  sys     0m0.128s\n\n\n  [xmalloc/free instead of xalloca]\n  Attempt 1: 31.306\n  Attempt 2: 31.814\n  Attempt 3: 31.138\n  Attempt 4: 31.787\n  Attempt 5: 32.23\n\n  real    0m31.138s\n  user    0m30.976s\n  sys     0m0.160s\n\n\n  [local var with fallback to xmalloc]\n  Attempt 1: 30.926\n  Attempt 2: 31.466\n  Attempt 3: 31.865\n  Attempt 4: 31.345\n  Attempt 5: 33.159\n\n  real    0m30.926s\n  user    0m30.804s\n  sys     0m0.120s\n\n\nSo the improvement here over even a naive malloc/free is _really_ small.\nYou'll note that the best-of-five for xmalloc is actually smaller than\nthe worst-case with xalloca. But the mean is still 2% better. The mean\nfor the \"fallback\" case aren't really any better (which makes me wonder\nif I was somehow accidentally calling malloc each time).\n\nSo I dunno. For 2%, I was tempted to simply say \"screw it, let's just\nforget this micro-optimization and call xmalloc\". This patch is the\nconservative choice in that it has the same performance profile as the\noriginal. Or so I thought. I didn't record the old timings, but they\nlooked similar to the original. I just recreated them while writing this\nemail and got:\n\n  [xalloca with fallback to xmalloc]\n  Attempt 1: 31.356\n  Attempt 2: 31.725\n  Attempt 3: 31.454\n  Attempt 4: 30.898\n  Attempt 5: 31.937\n\n  real    0m30.898s\n  user    0m30.752s\n  sys     0m0.144s\n\nwhich really isn't much better than the local-var case. I wonder if just\nhaving the conditional stack/heap is what kills us (either itself, or\nbecause it affects the optimizer).\n\nI dunno.\n\n\n> > +#define FAST_ARRAY_ALLOC(x, nr) do { \\\n> > +\tif ((nr) <= 2) \\\n> > +\t\t(x) = xalloca((nr) * sizeof(*(x))); \\\n> > +\telse \\\n> > +\t\tALLOC_ARRAY((x), nr); \\\n> > +} while(0)\n> > +#define FAST_ARRAY_FREE(x, nr) do { \\\n> > +\tif ((nr) > 2) \\\n> > +\t\tfree((x)); \\\n> > +} while(0)\n> \n> An obvious and clean implementation of the idea.\n> \n> The only slight worry I have is that nr must stay constant until the\n> time the caller calls FREE(), but for the only three callsite pairs\n> it is clear nparent will stay constant and this is local to the\n> file.\n\nYep, I had the same worry. I think it's OK because the damage is limited\nto tree-diff.c. I'm not sure I would promote this macro for general use.\n\n-Peff\n"}]}