speed of malloc()

[braner]

[]

In several implementations I have seen, and one that I have written
myself, there are two malloc()s.  A slow "system-malloc" that is designed
for allocating space for programs about to be run, etc, and a fast
"library-malloc" that is actually called when you say "malloc()" in
your program.  The system malloc may be slow because it is built to
be bomb-proof.  (Still can be not very slow.)  The library malloc
calls the system malloc (actually called SBRK or whatever) only when
necessary, and then allocates a rather large chunk (say 8K minimum).
Then the library function (which is internal to the process, since it
was linked to the program from a library archive!) doles out little pieces
of it for each malloc() call.  Upon free(), the little (or big) piece
is returned to the locally-managed pool but NOT to the system.  Upon
exit() everything is (or should be) returned to the system.  Since the
library malloc does not need to keep tables of who owns which block,
and can keep control info in the blocks, it can be rather fast.  One
I wrote (adapted from the example in K&R, with various sanity checks
added and only 6 bytes average overhead per block) takes about 150 microsecs.
(That's on a 15 MHz T414 transputer, roughly equivalent to a 68020.)
(And it's written in C :-)

- Moshe Braner

PS: the only fair way to benchmark a function is to time the complete
"y = f(x)" operation, so it includes the assignment and the function
calling overhead.