From f022f85f6d50b66ac5f4c49830a040627a0d8194 Mon Sep 17 00:00:00 2001 From: Jeff King Date: Sat, 10 Mar 2007 21:39:17 -0500 Subject: fast-import: grow tree storage more aggressively 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 Signed-off-by: Shawn O. Pearce --- fast-import.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/fast-import.c b/fast-import.c index d9492b9884..ac3714596a 100644 --- a/fast-import.c +++ b/fast-import.c @@ -1062,7 +1062,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; @@ -1229,7 +1229,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; -- cgit v1.2.3