[PATCH 1/3] fast-import: grow tree storage more aggressively
- From
Jeff King <peff@peff.net>
- Date
- Mar 10, 2007, 19:16 UTC
- Message-ID
- <20070310191648.GA3596@coredump.intra.peff.net>
- In-Reply-To
- <20070310191515.GA3416@coredump.intra.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