Bug 97500 - Freeing random-lenght strings allocated by malloc is very slow
Freeing random-lenght strings allocated by malloc is very slow
Status: CLOSED CURRENTRELEASE
Product: Red Hat Linux
Classification: Retired
Component: glibc (Show other bugs)
7.2
i686 Linux
medium Severity medium
: ---
: ---
Assigned To: Jakub Jelinek
Brian Brock
:
Depends On:
Blocks:
  Show dependency treegraph
 
Reported: 2003-06-16 15:16 EDT by Scott Miller
Modified: 2016-11-24 10:11 EST (History)
1 user (show)

See Also:
Fixed In Version: 2.3.2
Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of:
Environment:
Last Closed: 2003-10-03 06:26:41 EDT
Type: ---
Regression: ---
Mount Type: ---
Documentation: ---
CRM:
Verified Versions:
Category: ---
oVirt Team: ---
RHEL 7.3 requirements from Atomic Host:
Cloudforms Team: ---


Attachments (Terms of Use)

  None (edit)
Description Scott Miller 2003-06-16 15:16:08 EDT
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:
Comment 1 Jakub Jelinek 2003-06-17 11:38:44 EDT
Please try glibc-2.3.x (e.g. as in RHL9). malloc has been completely rewritten
there.
Comment 2 Jakub Jelinek 2003-06-17 11:48:32 EDT
This is what I get with glibc-2.3.2:
String Length, Alloc (sec), Dealloc(sec), Random Dealloc(sec)
10, 0.03, 0.02, 0.03
110, 0.11, 0.04, 0.09
210, 0.145, 0.04, 0.09
310, 0.19, 0.06, 0.09
410, 0.24, 0.07, 0.11
510, 0.29, 0.06, 0.11
610, 0.335, 0.06, 0.11
710, 0.39, 0.06, 0.12
810, 0.44, 0.07, 0.12
910, 0.49, 0.08, 0.14
1010, 0.535, 0.08, 0.14
1110, 0.595, 0.09, 0.15
1210, 0.635, 0.09, 0.15
1310, 0.69, 0.09, 0.15
1410, 0.74, 0.1, 0.16
1510, 0.8, 0.1, 0.17
1610, 0.85, 0.11, 0.17
1710, 0.89, 0.13, 0.18
1810, 0.945, 0.2, 0.18
1910, 1.015, 0.27, 0.19
Comment 3 Jakub Jelinek 2003-10-03 06:26:41 EDT
Backporting malloc is not an option for the older distros, as it is too fundamental
change. You're free to use RHEL3/RHL9/Fedora Core 1 or at least glibc from it
if it works for you.

Note You need to log in before you can comment on or make changes to this bug.