djgpp slow free()

i use this function to destroy my tree:

Code:

void DestroyTree(splay_t *root)
{
   splay_t *tmp;

   while(root)
   {
      while(root->left)
         RotateRight(&root);
      tmp  = root;
      root = root->right;
      free(tmp->rec);
      free(tmp);
   }
}

when i compile this with djgpp and fill my tree with 1000000 random numbers it takes forever to free everything. if i remove one of the calls to free or if the data is entered sorted, it frees everything up pretty quick. i don't get this slow down with msvc. can anyone here explain what causes this or give a possible solution? thanks.

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.

thanks for the info and the link to the alt malloc. ill have sit down with a cup of coffee and give it a look tomorrow... actually later today. it's 4 am here. i was thinking of allocing large blocks and freeing the blocks instead of traversing the tree. think that will speed things up a bit?