It's a bug (feature) of the current malloc implementation. I wrote this test some time ago because I ran into the same problem
Code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* allocates a large number of blocks of memory */
/* then free's them again, timing how long it takes */
#define NUM_BLOCKS 40000
#define BLOCK_SIZE 20
void *ptrs[NUM_BLOCKS];
void forward_order_free ( void ) {
int i;
for ( i = 0 ; i < NUM_BLOCKS ; i++ ) {
free(ptrs[i]);
}
}
void reverse_order_free ( void ) {
int i;
for ( i = NUM_BLOCKS-1 ; i >= 0 ; i-- ) {
free(ptrs[i]);
}
}
/* fragmented free's result in allocated blocks between adjacent */
/* free'd blocks, which must be joined when the allocated block */
/* is finally free'd */
void forward_fragmented_free ( void ) {
int i;
for ( i = 0 ; i < NUM_BLOCKS ; i += 2 ) {
free(ptrs[i]);
}
for ( i = 1 ; i < NUM_BLOCKS ; i += 2 ) {
free(ptrs[i]);
}
}
void reverse_fragmented_free ( void ) {
int i;
for ( i = 0 ; i < NUM_BLOCKS ; i += 2 ) {
free(ptrs[i]);
}
for ( i = NUM_BLOCKS-1 ; i >=0 ; i -= 2 ) {
free(ptrs[i]);
}
}
int main ( int argc, char **argv ) {
int i;
int choice;
if ( argc > 1 ) {
choice = atoi( argv[1] );
} else {
printf("param = 1,2,3,4\n" );
exit( 1 );
}
printf("Start Time=%d\n",clock());
for ( i = 0 ; i < NUM_BLOCKS ; i++ ) {
ptrs[i] = malloc( BLOCK_SIZE );
}
printf("Malloc Time=%d\n",clock());
if ( choice == 1 ) forward_order_free();
if ( choice == 2 ) reverse_order_free();
if ( choice == 3 ) forward_fragmented_free();
if ( choice == 4 ) reverse_fragmented_free();
printf("Free Time=%d\n",clock());
return EXIT_SUCCESS;
}
Results:
>a.exe 1
Start Time=0
Malloc Time=5
Free Time=10
>a.exe 2
Start Time=0
Malloc Time=5
Free Time=10
>a.exe 3
Start Time=0
Malloc Time=5
Free Time=2945
>a.exe 4
Start Time=0
Malloc Time=10
Free Time=15
Perhaps this will help
http://www.delorie.com/djgpp/malloc/
It's supposed to be an alternative, but I don't know what its current state is.