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;                                                            
}
                                                          
_______________________________________________
[EMAIL PROTECTED] mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-questions
To unsubscribe, send any mail to "[EMAIL PROTECTED]"

Reply via email to