[Bug libc/4349] New: _int_malloc extremely slow with ordblks free chunks

["sun_mingzhou at emc dot com" <sourceware-bugzilla at sourceware dot org>]

I am experiencing perhaps a worst-case scenario of malloc when there are a very
large number (million) of free chunks (ordblks in mallinfo).

It's a long running C++ program that, over the course of a long task,
accumulates a large number of objects of various sorts, including STL container
elements and other customer class types. Eventually it uses close to 1G of
memory. When the task is done most but not all of these objects are free'ed,
resulting in a very large number of ordblks's. After that, the subsequent malloc
calls become extremely slow. oprofile shows that most of the time is spent
_int_malloc, and in two while loops in particular.

I wrote a simple test program (which will be attached) to simulate this
scenarios. After getting the test program to this state:
  int arena;    /* non-mmapped space allocated from system */ 1000378368
  int ordblks;  /* number of free chunks */    1000002
 int smblks;   /* number of fastbin blocks */ 0
  int hblks;    /* number of mmapped regions */ 0
 int hblkhd;   /* space in mmapped regions */  0
 int usmblks;  /* maximum total allocated space */ 0
 int fsmblks;  /* space available in freed fastbin blocks */  0
  int uordblks; /* total allocated space */  360360048
  int fordblks; /* total free space */  640018320
  int keepcost;  88624

The subsequent 300 malloc calls will take 20 seconds on a 2.66GHz Xeon Linux. 

oprofile with a debug build of glibc 2.4-11 indicates that the bulk (99%) of the
time is spent in the while loop in _int_malloc:
 sample  %
               :        /* maintain large bins in sorted order */
   132  0.0133 :        if (fwd != bck) {
               :          /* Or with inuse bit to speed comparisons */
     1 1.0e-04 :          size |= PREV_INUSE;
               :          /* if smaller than smallest, bypass loop below */
               :          assert((bck->bk->size & NON_MAIN_ARENA) == 0);
   546  0.0549 :          if ((unsigned long)(size) <= (unsigned
long)(bck->bk->size)) {
               :            fwd = bck;
               :            bck = bck->bk;
               :          }
               :          else {
               :            assert((fwd->size & NON_MAIN_ARENA) == 0);
984997 99.0818 :            while ((unsigned long)(size) < (unsigned
long)(fwd->size)) {
  2935  0.2952 :              fwd = fwd->fd;
               :              assert((fwd->size & NON_MAIN_ARENA) == 0);
               :            }
    29  0.0029 :            bck = fwd->bk;
               :          }
               :        }

I am using the x86_64 glibc-2.4-11 library from Fedora Core 5 update. 

If this is a known limitation, is there a good work around (other than providing
another layer of memory management between the application and malloc library?)
Searching on the web, this problem might be related to the issue Tomash Brechko
had a patch for in Dec 2004
(http://sourceware.org/ml/libc-alpha/2004-12/msg00041.html) His patch is
apparently not included in the glibc 2.4 tree.  Would this patch been eventually
considered?

-- 
           Summary: _int_malloc extremely slow with ordblks free chunks
           Product: glibc
           Version: 2.4
            Status: NEW
          Severity: normal
          Priority: P2
         Component: libc
        AssignedTo: drepper at redhat dot com
        ReportedBy: sun_mingzhou at emc dot com
                CC: glibc-bugs at sources dot redhat dot com


http://sourceware.org/bugzilla/show_bug.cgi?id=4349

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.