clone performance of experimental new http client library.

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


On Wed, 19 Oct 2011 11:48:46 -0500
Matt Mackall <mpm at selenic.com> 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).

Regards

Antoine.


More information about the Mercurial-devel mailing list