Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ukma!uflorida!novavax!twwells!bill
From: bill@twwells.uucp (T. William Wells)
Newsgroups: comp.lang.c
Subject: Re: Memory Allocation (was Re: binary data files)
Message-ID: <903@twwells.uucp>
Date: 6 May 89 16:28:46 GMT
References: <10946@bloom-beacon.MIT.EDU> <12546@ut-emx.UUCP> <8758@csli.Stanford.EDU> <11021@bloom-beacon.MIT.EDU> <29978@apple.Apple.COM>
Reply-To: bill@twwells.UUCP (T. William Wells)
Organization: None, Ft. Lauderdale
Lines: 35
Summary:
Expires:
Sender:
Followup-To:
Distribution:
Keywords:

In article <29978@apple.Apple.COM> desnoyer@Apple.COM (Peter Desnoyers) writes:
: No, No. This algorithm takes O(n^^2) copies in the worst case. If you
: change your code to:
:
:       while data
:         if not room
:           current_size *= 2
:           ptr = realloc( ptr, curr_size)

For text input that is supposed to come from a user, I often use the
following:

	size += size < 480 ? size + 32 : 100;

It generates these numbers:

	0 32 96 224 400 580 680 ...

The theory is that many inputs are written in very short lines, most
are written in 80+, the vast bulk are written significantly under
256, and once you have lines longer than that, you have bigger
problems than the time wasted in this allocation.

Of course, it isn't a lot different from:

	0 32 64 128 256 512 ...

But it frequently does one less allocation, e.g., when reading filled
text.

If one wanted the benefits of the power of two growth, one could
write it without the conditional.

---
Bill                            { uunet | novavax } !twwells!bill