-
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?