memory allocation/deallocation (malloc experts needed)
Till Plewe
till at score.is.tsukuba.ac.jp
Fri May 21 01:03:15 PDT 2004
On Thu, May 20, 2004 at 05:36:31PM +0900, Charlie Root wrote:
> On Thu, May 20, 2004 at 01:42:00AM -0500, Dan Nelson wrote:
> > In the last episode (May 20), Till Plewe said:
> > > My problem is essentially that freeing large numbers of small chunks
> > > of memory can be very slow. I have run into this problem twice so
> > > far.
> >
> > Do you have a testcase? The attached program mallocs 1 million
> > 128-byte blocks, then frees them. With MALLOC_OPTIONS set to jz (i.e.
> > no filling of freed memory), it takes .184 seconds to free them all.
> > With it set to J, it takes 1 second.
> >
> > CPU: Intel Pentium III (909.96-MHz 686-class CPU)
> >
>
> ...
I changed your program a little bit to allow freeing the memory in
random order which is closer to what happens when hash tables are
deleted. The test program now allocates NUM pointers to SIZE byte
memory chunks and then frees them. RANDOM 0 means the order in which
the items are freed is the same as the order of allocation, while
RANDOM 1 means that the memory is freed in (somewhat) random order
The data below shows that freeing the memory is the bottleneck.
(MALLOC_OPTIONS JZ, using jz gives essentially the same results perhaps
about 25% faster)
My current guess is that the part copied below of the function
free_bytes in /usr/src/lib/libc/stdlib/malloc.c is to blame
where linked lists are traversed to move/delete pages whose
status has changed. At least that would explain the quadratic
behaviour in the output of the test program below.
============================================
lines 1010-1028 of /usr/src/lib/libc/stdlib/malloc.c
if (info->free == 1) {
/* Page became non-full */
mp = page_dir + info->shift;
/* Insert in address order */
while (*mp && (*mp)->next && (*mp)->next->page < info->page)
mp = &(*mp)->next;
info->next = *mp;
*mp = info;
return;
}
if (info->free != info->total)
return;
/* Find & remove this page in the queue */
while (*mp != info) {
mp = &((*mp)->next);
==============================================
========================
FreeBSD 5.2-CURRENT Sun May 2 08:40:29 JST 2004
CPU: Intel(R) Xeon(TM) CPU 2.40GHz (2392.05-MHz 686-class CPU)
test -n 20
NUM 1<<20 RANDOM 0 SIZE 16 malloc: 0.140976 free: 0.113800
NUM 1<<20 RANDOM 1 SIZE 16 malloc: 0.153176 free: 1.671878
test -n 21
NUM 1<<21 RANDOM 0 SIZE 16 malloc: 0.277667 free: 0.228911
NUM 1<<21 RANDOM 1 SIZE 16 malloc: 0.320030 free: 5.991513
test -n 22
NUM 1<<22 RANDOM 0 SIZE 16 malloc: 0.492440 free: 0.466889
NUM 1<<22 RANDOM 1 SIZE 16 malloc: 0.591442 free: 22.437910
test -n 23
NUM 1<<23 RANDOM 0 SIZE 16 malloc: 1.106733 free: 0.929016
NUM 1<<23 RANDOM 1 SIZE 16 malloc: 1.180094 free: 86.868541
test -n 24
NUM 1<<24 RANDOM 0 SIZE 16 malloc: 2.040155 free: 1.866336
NUM 1<<24 RANDOM 1 SIZE 16 malloc: 2.250588 free: 356.746455
test -n 25
NUM 1<<25 RANDOM 0 SIZE 16 malloc: 4.280042 free: 3.716874
NUM 1<<25 RANDOM 1 SIZE 16 malloc: 4.567206 free: 1497.213212
test -n 26
NUM 1<<26 RANDOM 0 SIZE 16 malloc: 8.543537 free: 7.612657
NUM 1<<26 RANDOM 1 SIZE 16 malloc: 9.055712 free: 6187.992730
==========================================
FreeBSD 5.2-CURRENT Wed May 19 10:59:08 JST 2004
CPU: AMD Opteron(tm) Processor 248 (2205.01-MHz K8-class CPU)
test -n 20
NUM 1<<20 RANDOM 0 SIZE 16 malloc:0.124275 free:0.067746
NUM 1<<20 RANDOM 0 SIZE 16 malloc:0.098449 free:0.066730
NUM 1<<20 RANDOM 1 SIZE 16 malloc:0.119348 free:1.435530
NUM 1<<20 RANDOM 1 SIZE 16 malloc:0.099841 free:1.428259
test -n 21
NUM 1<<21 RANDOM 0 SIZE 16 malloc:0.213471 free:0.134132
NUM 1<<21 RANDOM 0 SIZE 16 malloc:0.199287 free:0.132293
NUM 1<<21 RANDOM 1 SIZE 16 malloc:0.184251 free:4.998957
NUM 1<<21 RANDOM 1 SIZE 16 malloc:0.186739 free:4.849894
test -n 22
NUM 1<<22 RANDOM 0 SIZE 16 malloc:0.464616 free:0.255515
NUM 1<<22 RANDOM 0 SIZE 16 malloc:0.425375 free:0.254138
NUM 1<<22 RANDOM 1 SIZE 16 malloc:0.404901 free:17.264623
NUM 1<<22 RANDOM 1 SIZE 16 malloc:0.394420 free:18.328755
test -n 23
NUM 1<<23 RANDOM 0 SIZE 16 malloc:0.819199 free:0.514065
NUM 1<<23 RANDOM 0 SIZE 16 malloc:0.858903 free:0.520739
NUM 1<<23 RANDOM 1 SIZE 16 malloc:0.830438 free:67.556339
NUM 1<<23 RANDOM 1 SIZE 16 malloc:0.821419 free:67.287440
test -n 24
NUM 1<<24 RANDOM 0 SIZE 16 malloc:1.726636 free:1.032238
NUM 1<<24 RANDOM 0 SIZE 16 malloc:1.709127 free:1.028701
NUM 1<<24 RANDOM 1 SIZE 16 malloc:1.615758 free:290.153962
NUM 1<<24 RANDOM 1 SIZE 16 malloc:1.645739 free:279.887830
test -n 25
NUM 1<<25 RANDOM 0 SIZE 16 malloc:3.429280 free:2.044097
NUM 1<<25 RANDOM 0 SIZE 16 malloc:3.486703 free:2.026912
NUM 1<<25 RANDOM 1 SIZE 16 malloc:3.536784 free:1172.642691
NUM 1<<25 RANDOM 1 SIZE 16 malloc:3.481226 free:1176.604815
======================
test program
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <sys/resource.h>
#include <unistd.h>
#include <limits.h>
struct timeval elap;
struct rusage r_s, r_e;
int main(int argc,char *argv[])
{
int ch;
int n=0,r=0;
while((ch = getopt(argc,(void *)argv, "n:r")) != -1)
switch (ch)
{
case 'n':
n=(int)strtol(optarg,NULL,10);
if (n>27 || n<20) n=20;
break;
case 'r':
r=1;
break;
default:
errx(1,"huh?\n");
}
int NUM=1<<n;
int SIZE=16;
int MASK=NUM-1;
int i;
void *mypointers[NUM];
int redirect[NUM];
for (i = 0; i < NUM; i++)
redirect[i]=i;
if (r)
for (i = 0; i < NUM*10; i++)
{
int a=random()&MASK,b=random()&MASK,tmp;
tmp=redirect[a],redirect[a]=redirect[b],redirect[b]=tmp;
}
printf("NUM 1<<%d RANDOM %d SIZE %d malloc: ",n,r,SIZE);
fflush(stdout);
getrusage(RUSAGE_SELF, &r_s);
for (i = 0; i < NUM; i++)
{
mypointers[i] = malloc(SIZE);
}
getrusage(RUSAGE_SELF, &r_e);
timersub(&r_e.ru_utime, &r_s.ru_utime, &elap);
printf("%ld.%06ld free: ",elap.tv_sec, elap.tv_usec);
fflush(stdout);
getrusage(RUSAGE_SELF, &r_s);
for (i = 0; i < NUM; i++)
{
free(mypointers[redirect[i]]);
}
getrusage(RUSAGE_SELF, &r_e);
timersub(&r_e.ru_utime, &r_s.ru_utime, &elap);
printf("%ld.%06ld\n",elap.tv_sec, elap.tv_usec);
return 0;
}
More information about the freebsd-questions
mailing list