diff options
| author | Jeff King <peff@peff.net> | 2007-03-10 21:39:17 -0500 |
|---|---|---|
| committer | Shawn O. Pearce <spearce@spearce.org> | 2007-03-12 15:01:44 -0400 |
| commit | f022f85f6d50b66ac5f4c49830a040627a0d8194 (patch) | |
| tree | 2a2e5372c9c1e47c4c67e6baf9b0b20549446c47 | |
| parent | fc095242b16d57bad1bfe089f919b9d6e6deda1b (diff) | |
| download | git-f022f85f6d50b66ac5f4c49830a040627a0d8194.tar.gz git-f022f85f6d50b66ac5f4c49830a040627a0d8194.tar.xz | |
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 <peff@peff.net>
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
| -rw-r--r-- | fast-import.c | 4 |
1 files changed, 2 insertions, 2 deletions
diff --git a/fast-import.c b/fast-import.c index d9492b988..ac3714596 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; |