summaryrefslogtreecommitdiff
path: root/tree-diff.c
diff options
context:
space:
mode:
authorJeff King <peff@peff.net>2016-06-07 22:53:00 (GMT)
committerJunio C Hamano <gitster@pobox.com>2016-06-08 00:47:34 (GMT)
commitb8ba412bf7c38ac86dbaebdf939b0039bacf434c (patch)
tree42aca02b2d38147aa5a76b8a2bf4e9077e6c67fb /tree-diff.c
parent765428699a5381f113d19974720bc91b5bfeaf1d (diff)
downloadgit-b8ba412bf7c38ac86dbaebdf939b0039bacf434c.zip
git-b8ba412bf7c38ac86dbaebdf939b0039bacf434c.tar.gz
git-b8ba412bf7c38ac86dbaebdf939b0039bacf434c.tar.bz2
tree-diff: avoid alloca for large allocations
Commit 72441af (tree-diff: rework diff_tree() to generate diffs for multiparent cases as well, 2014-04-07) introduced the use of alloca so that the common cases of commits with 1 or 2 parents would not be adversely affected by going through the multi-parent code. However, our xalloca is not ideal when the number of parents grows very large: 1. If the requested size is too large for our stack, alloca() has no way to tell us, and we simply segfault while trying to access the memory. 2. It does not use our usual memory_limit_check() logic. I measured, and alloca is indeed buying us a very small speedup over xmalloc()/free(). So we'd want to keep something like it. This patch simply puts a conditional in place at each callsite: we use alloca for common known-small numbers of parents, and otherwise use the heap. We are technically still vulnerable to (1), but no more so than if we simply put a few dozen bytes on the stack, which we must do all the time anyway. And likewise, we technically miss a memory limit check if it is tiny, but such a limit is pointless. An alternative to this would be implement something like: struct tree *tp, tp_fallback[2]; if (nparent <= ARRAY_SIZE(tp_fallback)) tp = tp_fallback; else ALLOC_ARRAY(tp, nparent); ... if (tp != tp_fallback) free(tp); That would let us drop our xalloca() portability code entirely. But in my measurements, this seemed to perform slightly worse than the xalloca solution. Note in the example above, and in the patch below, I've used ALLOC_ARRAY() to replace the manual xmalloc(nr * sizeof(*x)). Besides being shorter, this has the bonus that one cannot accidentally overflow a size_t during that computation. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'tree-diff.c')
-rw-r--r--tree-diff.c22
1 files changed, 16 insertions, 6 deletions
diff --git a/tree-diff.c b/tree-diff.c
index 4b32d40..286cab8 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -14,6 +14,16 @@
*/
#define S_IFXMIN_NEQ S_DIFFTREE_IFXMIN_NEQ
+#define FAST_ARRAY_ALLOC(x, nr) do { \
+ if ((nr) <= 2) \
+ (x) = xalloca((nr) * sizeof(*(x))); \
+ else \
+ ALLOC_ARRAY((x), nr); \
+} while(0)
+#define FAST_ARRAY_FREE(x, nr) do { \
+ if ((nr) > 2) \
+ free((x)); \
+} while(0)
static struct combine_diff_path *ll_diff_tree_paths(
struct combine_diff_path *p, const unsigned char *sha1,
@@ -265,7 +275,7 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *p,
if (recurse) {
const unsigned char **parents_sha1;
- parents_sha1 = xalloca(nparent * sizeof(parents_sha1[0]));
+ FAST_ARRAY_ALLOC(parents_sha1, nparent);
for (i = 0; i < nparent; ++i) {
/* same rule as in emitthis */
int tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ);
@@ -277,7 +287,7 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *p,
strbuf_add(base, path, pathlen);
strbuf_addch(base, '/');
p = ll_diff_tree_paths(p, sha1, parents_sha1, nparent, base, opt);
- xalloca_free(parents_sha1);
+ FAST_ARRAY_FREE(parents_sha1, nparent);
}
strbuf_setlen(base, old_baselen);
@@ -402,8 +412,8 @@ static struct combine_diff_path *ll_diff_tree_paths(
void *ttree, **tptree;
int i;
- tp = xalloca(nparent * sizeof(tp[0]));
- tptree = xalloca(nparent * sizeof(tptree[0]));
+ FAST_ARRAY_ALLOC(tp, nparent);
+ FAST_ARRAY_ALLOC(tptree, nparent);
/*
* load parents first, as they are probably already cached.
@@ -531,8 +541,8 @@ static struct combine_diff_path *ll_diff_tree_paths(
free(ttree);
for (i = nparent-1; i >= 0; i--)
free(tptree[i]);
- xalloca_free(tptree);
- xalloca_free(tp);
+ FAST_ARRAY_FREE(tptree, nparent);
+ FAST_ARRAY_FREE(tp, nparent);
return p;
}