clone performance of experimental new http client library.

Antoine Pitrou solipsis at
Wed Oct 19 11:52:42 CDT 2011

On Wed, 19 Oct 2011 11:48:46 -0500
Matt Mackall <mpm at> wrote:
> <kernel VM expert hat on>
> On basically all systems, realloc() only works efficiently when there
> aren't existing neighboring allocations in the virtual address space.
> And that's entirely workload-dependent. If your app is regularly
> allocating new chunks of memory (because it's written in a dynamic
> language like Python, for instance), they're quite likely to interfere
> with attempts to realloc older blocks and you'll end up with repeated
> O(N^2) copying.

<naïve kernel-related question>
If the memory block (assuming it's a large one) was allocated using
mmap(), can't mremap() grow it efficiently?

> ..which is one of the reasons I dislike using cStringIO in Mercurial:
> it's based on realloc.

It's based on realloc, but it uses overallocation so that the amortized
cost is still O(n). Conversely, concatenating immutable strings will
allocate exactly the necessary memory size, which makes repeated
concatenation O(n**2).



More information about the Mercurial-devel mailing list