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 <email@example.com> Signed-off-by: Shawn O. Pearce <firstname.lastname@example.org>