Malloc (was an atrocious pun)

[Richard Harter]

In article <5253 at sdcrdcf.UUCP> markb at sdcrdcf.UUCP (Mark Biggar) writes:

>Actually malloc is a case where rolling your own can provide emormous
>speed up in your program.  Do you realize just how much overhead is added
>to malloc just so you can free things.  I wrote a large (20000 lines)
>program that used malloc everywhere.  The longer it ran the slower it got.
>On profiling it I discovered that the program was spending 47% of its time
>in malloc!  The program never freed anything, so I replaced malloc with a
>much simpler one that just gave me some memory and didn't do any of the
>screwy thing that the regular malloc does (like chase down a link list of
>every block ever allocated to see if you might just have freed a block big
>enough to honor the the current request).  This gave me a 40%+ speedup in
>the program and the program stopped getting slower.  By putting the simple
>replacement malloc in its own file, I made the program just as protable as
>befor because you didn't have to use my malloc. (Altough mine would work
>correctly on both bsd and SV type unix systems.)

As someone else notes, the right thing to do is to make your own routine
with its own name.

The question I have, is malloc usually implemented as badly as described.
We did our own allocator for sundry reasons, mostly beause what we had
heard of malloc implementations was a little disturbing.  Some of the
things that we did were 

(a)	Remove allocation control data from the allocated space so that
an overwrite would not crash the allocator.

(b)	Use a table of linked lists for blocks of small and medium lengths
so that allocation usually involves no search for a block of the right
size.

(c)	Keep the allocated addresses in a hash table so that it is possible
to check whether a deallocation is legitimate.

(d)	Associate a time and origin stamp with each allocated block [added
for storage allocation leak analysis]

	The point of all this is that it is not all that hard to implement
an allocator that is fast, efficient, and reasonably secure against abuse.
How good are typical implementations of malloc?
-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.