Date: Wed, 07 Jan 2004 14:11:32 -0800 From: Tim Kientzle <kientzle@acm.org> To: Poul-Henning Kamp <phk@phk.freebsd.dk> Cc: Peter Jeremy <peterjeremy@optushome.com.au> Subject: Re: perl malloc slow? Message-ID: <3FFC8414.9040008@acm.org> In-Reply-To: <31178.1073481069@critter.freebsd.dk> References: <31178.1073481069@critter.freebsd.dk>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?3FFC8414.9040008>