alloca wars

[Dave Brower]

In <1988Aug7.002334.6987 at utzoo.uucp> henry at utzoo.uucp (Henry Spencer) writes:
>In <697 at goofy.megatest.UUCP> djones at megatest.UUCP (Dave Jones) writes:
>>Speed.  The malloc() on in Sun3 OS, for example, is incredibly slow
>>after a few thousand blocks have been allocated...
>
>This just says that whoever wrote Sun's malloc was incompetent.  There is
>nothing inherently hard about writing a fast malloc, although it's not
>simple, especially for widely-diversified needs.

Don't you just love the way the electronic communication helps make
generally reasonable people offensive?  It's more than a bit out of line
to say the Sun programmer is incompetant.  It isn't simple making the
tradoffs inherent in an allocator.  I've never seen a one that would
satisfy all desirable criteria for all clients, because the requirements
are completely program specific.

There are at least four dimensions to the allocator problem:

	(1)	Time to get a block.
	(2)	Run size of the program (swap space).
	(3)	Fragmentation, and what is does to (1) and (2).
	(4)	Time to release a block, and what that does to (2) and (3).

No one algorithm is ever going to be optimal in all cases.  The stack
based alloca is nearly ideal for allocating large numbers of small
easily disposed objects.  Malloc and friends are better for smaller
numbers of probably larger objects.  Sbrk with +/- increments is more
for getting and releasing small numbers of large objects.  

There is no one correct answer.  "Incompetence" is a unfairly glib way
of saying that one perfectly valid implementation isn't the one that
would be best for a particular application.

-dB
"Ready when you are Raoul!"
{amdahl, cpsc6a, mtxinu, sun, hoptoad}!rtech!daveb daveb at rtech.com <- FINALLY!