[PATCH 1/3] fast-import: grow tree storage more aggressively

[Jeff King <peff@peff.net>]

When building up a tree for a commit, fast-import
dynamically allocates memory for the tree entries. When more
space is needed, the allocated memory is increased by a
constant amount. For very large trees, this means
re-allocating and memcpy()ing the memory O(n) times.

To compound this problem, releasing the previous tree
resource does not free the memory; it is kept in a pool
for future trees. This means that each of the O(n)
allocations will consume increasing amounts of memory,
giving O(n^2) memory consumption.

Signed-off-by: Jeff King <peff@peff.net>
---
 fast-import.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/fast-import.c b/fast-import.c
index fda5018..81bc6ea 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -1058,7 +1058,7 @@ static void load_tree(struct tree_entry *root)
 		struct tree_entry *e = new_tree_entry();
 
 		if (t->entry_count == t->entry_capacity)
-			root->tree = t = grow_tree_content(t, 8);
+			root->tree = t = grow_tree_content(t, t->entry_count);
 		t->entries[t->entry_count++] = e;
 
 		e->tree = NULL;
@@ -1225,7 +1225,7 @@ static int tree_content_set(
 	}
 
 	if (t->entry_count == t->entry_capacity)
-		root->tree = t = grow_tree_content(t, 8);
+		root->tree = t = grow_tree_content(t, t->entry_count);
 	e = new_tree_entry();
 	e->name = to_atom(p, (unsigned short)n);
 	e->versions[0].mode = 0;
-- 
1.5.0.3.931.g55c05