From owner-freebsd-current@FreeBSD.ORG  Wed Jan  7 14:11:50 2004
Return-Path: <owner-freebsd-current@FreeBSD.ORG>
Delivered-To: freebsd-current@freebsd.org
Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125])
	by hub.freebsd.org (Postfix) with ESMTP
	id 3353316A4CE; Wed,  7 Jan 2004 14:11:50 -0800 (PST)
Received: from kientzle.com (h-66-166-149-50.SNVACAID.covad.net
	[66.166.149.50])	by mx1.FreeBSD.org (Postfix) with ESMTP
	id 8BF5D43D41; Wed,  7 Jan 2004 14:11:34 -0800 (PST)
	(envelope-from kientzle@acm.org)
Received: from acm.org ([66.166.149.54])
	by kientzle.com (8.12.9/8.12.9) with ESMTP id i07MBWkX045329;
	Wed, 7 Jan 2004 14:11:33 -0800 (PST)
	(envelope-from kientzle@acm.org)
Message-ID: <3FFC8414.9040008@acm.org>
Date: Wed, 07 Jan 2004 14:11:32 -0800
From: Tim Kientzle <kientzle@acm.org>
User-Agent: Mozilla/5.0 (X11; U; FreeBSD i386; en-US; rv:1.4) Gecko/20031006
X-Accept-Language: en-us, en
MIME-Version: 1.0
To: Poul-Henning Kamp <phk@phk.freebsd.dk>
References: <31178.1073481069@critter.freebsd.dk>
In-Reply-To: <31178.1073481069@critter.freebsd.dk>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
cc: Alexander Leidinger <Alexander@Leidinger.net>
cc: stable@freebsd.org
cc: current@freebsd.org
cc: Peter Jeremy <peterjeremy@optushome.com.au>
Subject: Re: perl malloc slow?
X-BeenThere: freebsd-current@freebsd.org
X-Mailman-Version: 2.1.1
Precedence: list
Reply-To: kientzle@acm.org
List-Id: Discussions about the use of FreeBSD-current
	<freebsd-current.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-current>,
	<mailto:freebsd-current-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-current>
List-Post: <mailto:freebsd-current@freebsd.org>
List-Help: <mailto:freebsd-current-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-current>,
	<mailto:freebsd-current-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Wed, 07 Jan 2004 22:11:50 -0000

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