braner@batcomputer.tn.cornell.edu (braner) (08/08/88)
[] 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.