Thread: djgpp slow free()

  1. #1
    Registered User
    Join Date
    Feb 2002
    Posts
    31

    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.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Feb 2002
    Posts
    31
    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?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. free() doesn't seem to work...
    By AlienJedi in forum C Programming
    Replies: 10
    Last Post: 01-29-2008, 05:27 PM
  2. Free Store of memory
    By George2 in forum C++ Programming
    Replies: 6
    Last Post: 11-12-2007, 02:27 PM
  3. How to free memory in this program
    By Coconut in forum C Programming
    Replies: 1
    Last Post: 10-26-2002, 10:57 PM