From Bugzilla Helper:
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.4b) Gecko/20030507

Description of problem:

See test program in the "steps to reproduce" entry.

If you malloc lots of varying length strings, free-ing
them can be very slow, as much as 1000 times slower
than when using fixed-length strings.

Version-Release number of selected component (if applicable):
glibc-2.2.4-31

How reproducible:
Always

Steps to Reproduce:
Run this program, observe the timing.

#include <time.h>
#include <stdlib.h>
#include <malloc.h>

#define NUMSTRINGS 100000
char **strings;
double start;

#define START start = clock();
#define END (clock() - start) / CLOCKS_PER_SEC;

void allocate(int len)
{
    int i;
    for (i = 0; i < NUMSTRINGS; i++) {
        strings[i] = (char *) malloc(len + (i % 10) - 5);
    }
}

void deallocate()
{
    int i;
    for (i = 0; i < NUMSTRINGS; i++) {
        free(strings[i]);
    }
}

void randomize()
{
    int i, j;
    char * foo;
    for (i = 0; i < NUMSTRINGS; i++) {
        j = rand() % NUMSTRINGS;
        foo = strings[i];
        strings[i] = strings[j];
        strings[j] = foo;
    }
}

int
main(int argc, char **argv)
{
    int i;
    double t1,t2,t3;

    strings = (char **) malloc(sizeof(char*) * NUMSTRINGS);
    printf("String Length, Alloc (sec), Dealloc(sec), Random Dealloc(sec)\n");
    for (i = 10; i < 2000; i+=100) {
        START
        allocate(i);
        t1 = END
        START
        deallocate();
        t2 = END
        START
        allocate(i);
        t1 += END
        randomize();
        START
        deallocate();
        t3 = END
        t1 = t1 * 0.5;
        printf("%d, %g, %g, %g\n", i, t1, t2, t3);
    }
    return 0;
} 

Actual Results:  Here it is. The key thing is this line:

strings[i] = (char *) malloc(len + (i % 10) - 5);

if it were changed to:

strings[i] = (char *) malloc(len);

even random deallocs are faster.

String Length, Alloc (sec), Dealloc(sec), Random Dealloc(sec)
10, 0.005, 0.01, 0.04
110, 0.035, 0.01, 0.16
210, 0.05, 0.02, 0.79
310, 0.06, 0.03, 0.86
410, 0.09, 0.01, 2.08
510, 0.095, 0.03, 17.38
610, 0.11, 0.03, 6.75
710, 0.125, 0.03, 18.58
810, 0.14, 0.04, 7.58
910, 0.165, 0.03, 18.04
1010, 0.17, 0.05, 1.87
1110, 0.195, 0.04, 15.32


Expected Results:  
freeing should be linear in time, and not dependant on the
lenght, or randomness of the lengths, of the allocated strings.


Additional info: