Re: perl malloc slow?

Poul-Henning Kamp compares two different ways of resizing a
buffer (edited slightly):

> 	for (;;) {
  		if (buffer too small)
> 			p = realloc(p, l += 80);
> 		[...]
> 	}

versus

> 	for (;;) {
  		if (buffer too small)
> 			p = realloc(p, l *= 16);
> 		[...]
> 	}
> 	p = realloc(p, strlen(p) + 1);

It's also worth pointing out that the second
algorithm here is A LOT FASTER (for any value of
16; in practice, 16 is often equal to 2).

This is something that a lot of people miss;
bumping the size by a constant results in quadratic
amortized allocation time (because of the copying),
where the second algorithm gives linear amortized
allocation time.

If you don't know what that means, don't worry, just
remember one thing: DO NOT use the first one.
It's a bad idea, it doesn't scale, it should
be fixed wherever you see it.

Tim