author | Jeff King <peff@peff.net> | |
Sun, 11 Mar 2007 02:39:17 +0000 (21:39 -0500) | ||
committer | Shawn O. Pearce <spearce@spearce.org> | |
Mon, 12 Mar 2007 19:01:44 +0000 (15:01 -0400) | ||
commit | f022f85f6d50b66ac5f4c49830a040627a0d8194 | |
tree | 2a2e5372c9c1e47c4c67e6baf9b0b20549446c47 | tree | snapshot |
parent | fc095242b16d57bad1bfe089f919b9d6e6deda1b | commit | diff |
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>
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>
fast-import.c | diff | blob | history |