This is the mail archive of the libc-alpha@sources.redhat.com mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Bad malloc performance in glibc 2.3?


Hi,

> > I have 2 reports of bad malloc performance in glibc 2.3. It appears
> > that malloc_consolidate () takes way too much CPU time under certain
> > conditions. malloc in 2.2 is ok. Has anyone seen it?

Ok, here is the promised patch (it's actually much smaller than it
looks), adapted from Doug Lea's malloc-2.7.1pre1 (unreleased as of
yet).  Could you verify whether it makes a difference in the cases you
cite?  If it does not, does it make a difference if you increase
FIRST_SORTED_BIN_SIZE?

I'd also like to here from anyone where this patch _hurts_ performance
in a particular case.

Regards,
Wolfram.

--- malloc/malloc.c	2002/03/29 14:27:23
+++ malloc/malloc.c	2002/05/12 21:16:52
@@ -26,7 +26,7 @@
 * Version ptmalloc2-20011215
   $Id: malloc.c,v 1.92 2002/04/02 22:37:28 drepper Exp $
   based on:
-  VERSION 2.7.0 Sun Mar 11 14:14:06 2001  Doug Lea  (dl at gee)
+  VERSION 2.7.1pre1 Sat May 12 07:41:21 2001  Doug Lea  (dl at gee)
 
    Note: There may be an updated version of this malloc obtainable at
            http://www.malloc.de/malloc/ptmalloc2.tar.gz
@@ -200,6 +200,7 @@
     REALLOC_ZERO_BYTES_FREES   1
     MALLOC_FAILURE_ACTION      errno = ENOMEM, if __STD_C defined, else no-op
     TRIM_FASTBINS              0
+    FIRST_SORTED_BIN_SIZE      512
 
     Options for customizing MORECORE:
 
@@ -1976,6 +1977,27 @@
 #define bin_index(sz) \
  ((in_smallbin_range(sz)) ? smallbin_index(sz) : largebin_index(sz))
 
+/*
+  FIRST_SORTED_BIN_SIZE is the chunk size corresponding to the
+  first bin that is maintained in sorted order. This must
+  be the smallest size corresponding to a given bin.
+
+  Normally, this should be MIN_LARGE_SIZE. But you can weaken
+  best fit guarantees to sometimes speed up malloc by increasing value.
+  Doing this means that malloc may choose a chunk that is 
+  non-best-fitting by up to the width of the bin.
+
+  Some useful cutoff values:
+      512 - all bins sorted
+     2560 - leaves bins <=     64 bytes wide unsorted  
+    12288 - leaves bins <=    512 bytes wide unsorted
+    65536 - leaves bins <=   4096 bytes wide unsorted
+   262144 - leaves bins <=  32768 bytes wide unsorted
+       -1 - no bins sorted (not recommended!)
+*/
+
+#define FIRST_SORTED_BIN_SIZE MIN_LARGE_SIZE 
+/* #define FIRST_SORTED_BIN_SIZE 65536 */
 
 /*
   Unsorted chunks
@@ -2569,8 +2591,11 @@
         idx = bin_index(size);
         assert(idx == i);
         /* lists are sorted */
-        assert(p->bk == b ||
-               (unsigned long)chunksize(p->bk) >= (unsigned long)chunksize(p));
+        if ((unsigned long) size >= (unsigned long)(FIRST_SORTED_BIN_SIZE)) {
+	  assert(p->bk == b ||
+		 (unsigned long)chunksize(p->bk) >=
+		 (unsigned long)chunksize(p));
+	}
       }
       /* chunk is followed by a legal chain of inuse chunks */
       for (q = next_chunk(p);
@@ -3828,17 +3853,18 @@
         bck = bin_at(av, victim_index);
         fwd = bck->fd;
 
-        /* maintain large bins in sorted order */
         if (fwd != bck) {
-	  /* Or with inuse bit to speed comparisons */
-          size |= PREV_INUSE;
-          /* if smaller than smallest, bypass loop below */
+          /* if smaller than smallest, place first */
 	  assert((bck->bk->size & NON_MAIN_ARENA) == 0);
-          if ((unsigned long)(size) <= (unsigned long)(bck->bk->size)) {
+          if ((unsigned long)(size) < (unsigned long)(bck->bk->size)) {
             fwd = bck;
             bck = bck->bk;
           }
-          else {
+          else if ((unsigned long)(size) >= 
+                   (unsigned long)(FIRST_SORTED_BIN_SIZE)) {
+
+            /* maintain large bins in sorted order */
+            size |= PREV_INUSE; /* Or with inuse bit to speed comparisons */
 	    assert((fwd->size & NON_MAIN_ARENA) == 0);
             while ((unsigned long)(size) < (unsigned long)(fwd->size)) {
               fwd = fwd->fd;
@@ -3866,37 +3892,34 @@
     if (!in_smallbin_range(nb)) {
       bin = bin_at(av, idx);
 
-      /* skip scan if empty or largest chunk is too small */
-      if ((victim = last(bin)) != bin &&
-          (unsigned long)(first(bin)->size) >= (unsigned long)(nb)) {
-
-        while (((unsigned long)(size = chunksize(victim)) <
-                (unsigned long)(nb)))
-          victim = victim->bk;
+      for (victim = last(bin); victim != bin; victim = victim->bk) {
+	size = chunksize(victim);
 
-        remainder_size = size - nb;
-        unlink(victim, bck, fwd);
-
-        /* Exhaust */
-        if (remainder_size < MINSIZE)  {
-          set_inuse_bit_at_offset(victim, size);
-	  if (av != &main_arena)
-	    victim->size |= NON_MAIN_ARENA;
-          check_malloced_chunk(av, victim, nb);
-          return chunk2mem(victim);
-        }
-        /* Split */
-        else {
-          remainder = chunk_at_offset(victim, nb);
-          unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
-          remainder->bk = remainder->fd = unsorted_chunks(av);
-          set_head(victim, nb | PREV_INUSE |
-		   (av != &main_arena ? NON_MAIN_ARENA : 0));
-          set_head(remainder, remainder_size | PREV_INUSE);
-          set_foot(remainder, remainder_size);
-          check_malloced_chunk(av, victim, nb);
-          return chunk2mem(victim);
-        }
+	if ((unsigned long)(size) >= (unsigned long)(nb)) {
+	  remainder_size = size - nb;
+	  unlink(victim, bck, fwd);
+
+	  /* Exhaust */
+	  if (remainder_size < MINSIZE)  {
+	    set_inuse_bit_at_offset(victim, size);
+	    if (av != &main_arena)
+	      victim->size |= NON_MAIN_ARENA;
+	    check_malloced_chunk(av, victim, nb);
+	    return chunk2mem(victim);
+	  }
+	  /* Split */
+	  else {
+	    remainder = chunk_at_offset(victim, nb);
+	    unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
+	    remainder->bk = remainder->fd = unsorted_chunks(av);
+	    set_head(victim, nb | PREV_INUSE |
+		     (av != &main_arena ? NON_MAIN_ARENA : 0));
+	    set_head(remainder, remainder_size | PREV_INUSE);
+	    set_foot(remainder, remainder_size);
+	    check_malloced_chunk(av, victim, nb);
+	    return chunk2mem(victim);
+	  }
+	}
       }
     }
 


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]