[PATCH] malloc.c: size skip list to bound best-fit search time

[Tomash Brechko <tomash at tvcom dot ru>]

Hi!

Summary: below is a patch to prevent malloc() extreme performance
degradation in some not-so-unusual cases.

Observation: since all bins in `struct malloc_state' that hold ordered
lists of free large chunks have bounded range of chunk sizes they
contain, and given range have number of different sizes that is far
less than the number of chunks corresponding bin may hold at one time)
there are necessarily (sometimes extremely long) runs of chunks with
the same size (and the narrower the range the longer runs are).

This makes _int_malloc() in some not-so-unusual cases extremely slow
(having time complexity of O(M*N), where M is the number of chunks of
size >=S1 already in bin, and N is the number of chunks of size S2<S1
in `unsorted_chunks'---every insertion of S2 in bin results in
skipping over all M chunks of >=S1 (provided that bin also has chunk
of size S3<S2, so S2-chunks are not pushed from back)).

Below is a patch that implements skip lists for bins holding ordered
lists of large chunks, where elements of skip list are *strictly*
ordered, thus providing upper bound on number of steps needed to
insert chunk in bin or to find best fit.  This bound is equal to the
number of *different sizes* of chunks currently in bin, and does not
depend on the total number of chunks the bin holds.

In my case in some malloc-intensive application, 4x-12x speedup was
achieved for parts that run after parts that slice memory in small
unconsolidatable pieces.

The main drawback is that `malloc_struct' now slightly exceed 2K in
size (for 32-bit platform, it was ~1K).

I also sent patch to malloc.de against current ptmalloc2.


Tomash


2004-12-12  Tomash Brechko <tomash@tvcom.ru>
 
        * malloc/malloc.c: Add size skip lists for bins of large
          chunks to bound search time.


--- malloc.c-orig	2004-12-12 15:56:19.192955000 +0300
+++ malloc.c	2004-12-12 16:08:29.079995920 +0300
@@ -1696,6 +1696,32 @@
   struct malloc_chunk* bk;
 };
 
+/*
+  Free large chunks (with size >= MIN_LARGE_SIZE) are stored in bins
+  in non-increasing size order as described below.  To speed up
+  insertion and best fit search, we maintain doubly linked "skip
+  list" to skip over runs of chunks of the same size.  This
+  effectively makes search time proportional to the number of
+  different chunk sizes in bin, thus bounded for every bin but the
+  last.
+
+  Implementors: we maintain invariant that of the run of equal-sized
+  chunks the last (one that precedes smaller chunk, or eol) is linked
+  into the skip list.  Thus multiple insertions of same-sized chunks
+  in _int_malloc() won't require skip list updates.
+
+  While allocating bins below we assume there won't be a hole between
+  `base' and `larger' fields of struct malloc_large_chunk.
+*/
+
+struct malloc_large_chunk {
+
+  struct malloc_chunk base;
+
+  struct malloc_large_chunk* smaller;
+  struct malloc_large_chunk* larger;
+};
+
 
 /*
    malloc_chunk details:
@@ -1747,6 +1773,10 @@
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |             Back pointer to previous chunk in list            |
             +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+            |  Pointer to next smaller chunk in list (for large chunk only) |
+            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+            |  Pointer to prev larger chunk in list  (for large chunk only) |
+            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
             |             Unused space (may be 0 bytes long)                .
             .                                                               .
             .                                                               |
@@ -1927,31 +1957,36 @@
      MAP_ANONYMOUS, a dummy file descriptor for mmap.
 
    Beware of lots of tricks that minimize the total bookkeeping space
-   requirements. The result is a little over 1K bytes (for 4byte
+   requirements. The result is a little over 2K bytes (for 4byte
    pointers and size_t.)
 */
 
 /*
   Bins
 
-    An array of bin headers for free chunks. Each bin is doubly
-    linked.  The bins are approximately proportionally (log) spaced.
-    There are a lot of these bins (128). This may look excessive, but
-    works very well in practice.  Most bins hold sizes that are
-    unusual as malloc request sizes, but are more usual for fragments
-    and consolidated sets of chunks, which is what these bins hold, so
-    they can be found quickly.  All procedures maintain the invariant
-    that no consolidated chunk physically borders another one, so each
-    chunk in a list is known to be preceeded and followed by either
-    inuse chunks or the ends of memory.
+    An array of bin headers for free chunks. Each bin is doubly linked
+    and also has skip list.  The bins are approximately proportionally
+    (log) spaced.  There are a lot of these bins (128). This may look
+    excessive, but works very well in practice.  Most bins hold sizes
+    that are unusual as malloc request sizes, but are more usual for
+    fragments and consolidated sets of chunks, which is what these
+    bins hold, so they can be found quickly.  All procedures maintain
+    the invariant that no consolidated chunk physically borders
+    another one, so each chunk in a list is known to be preceeded and
+    followed by either inuse chunks or the ends of memory.
 
     Chunks in bins are kept in size order, with ties going to the
-    approximately least recently used chunk. Ordering isn't needed
-    for the small bins, which all contain the same-sized chunks, but
-    facilitates best-fit allocation for larger chunks. These lists
-    are just sequential. Keeping them in order almost never requires
-    enough traversal to warrant using fancier ordered data
-    structures.
+    approximately least recently used chunk. Ordering isn't needed for
+    the small bins, which all contain the same-sized chunks, but
+    facilitates best-fit allocation for larger chunks. These lists are
+    just sequential.  To bound traversal time there is additional skip
+    list of chunks in strictly decreasing size order.  This makes
+    finding chunk of the right size very quick, because for most bins
+    number of different sizes it can hold is small compared to the
+    number of chunks of these sizes (it is in reverse proportion to
+    the number of chunks the bin can possibly hold), besides
+    applications tend to have many equal-sized allocations (and hence
+    frees).
 
     Chunks of the same size are linked with the most
     recently freed at the front, and allocations are taken from the
@@ -1960,37 +1995,31 @@
     adjacent freed chunks, resulting in larger free chunks and less
     fragmentation.
 
-    To simplify use in double-linked lists, each bin header acts
-    as a malloc_chunk. This avoids special-casing for headers.
-    But to conserve space and improve locality, we allocate
-    only the fd/bk pointers of bins, and then use repositioning tricks
-    to treat these as the fields of a malloc_chunk*.
+    To simplify use in double-linked lists, each bin header acts as a
+    malloc_chunk (and can be safely used as malloc_large_chunk). This
+    avoids special-casing for headers.  But to conserve space and
+    improve locality, we allocate only the fd/bk and larger/smaller
+    pointers of bins, and then use repositioning tricks to treat these
+    as the fields of a malloc_chunk* (or malloc_large_chunk*).
 */
 
 typedef struct malloc_chunk* mbinptr;
+typedef struct malloc_large_chunk* mlargechunkptr;
 
 /* addressing -- note that bin_at(0) does not exist */
-#define bin_at(m, i) ((mbinptr)((char*)&((m)->bins[(i)<<1]) - (SIZE_SZ<<1)))
+#define bin_at(m, i) ((mbinptr)((char*)&((m)->bins[(i)<<2]) - (SIZE_SZ<<1)))
+
+/* Convertions between chunk types.  */
+#define largechunk(p) ((mlargechunkptr)(p))
+#define normalchunk(p) ((mchunkptr)(p))
 
 /* analog of ++bin */
-#define next_bin(b)  ((mbinptr)((char*)(b) + (sizeof(mchunkptr)<<1)))
+#define next_bin(b)  ((mbinptr)((char*)(b) + (sizeof(mchunkptr)<<2)))
 
 /* Reminders about list directionality within bins */
 #define first(b)     ((b)->fd)
 #define last(b)      ((b)->bk)
 
-/* Take a chunk off a bin list */
-#define unlink(P, BK, FD) {                                            \
-  FD = P->fd;                                                          \
-  BK = P->bk;                                                          \
-  if (__builtin_expect (FD->bk != P || BK->fd != P, 0))                \
-    malloc_printerr (check_action, "corrupted double-linked list", P); \
-  else {                                                               \
-    FD->bk = BK;                                                       \
-    BK->fd = FD;                                                       \
-  }                                                                    \
-}
-
 /*
   Indexing
 
@@ -2033,6 +2062,45 @@
 #define bin_index(sz) \
  ((in_smallbin_range(sz)) ? smallbin_index(sz) : largebin_index(sz))
 
+/* Skip list traversal.  */
+#define get_smaller(P) normalchunk(largechunk(P)->smaller)
+
+#define get_larger(P) normalchunk(largechunk(P)->larger)
+
+/* Reset skip list pointers.  */
+#define set_no_skip_list(P, SIZE) {                                    \
+  if (!in_smallbin_range(SIZE))                                        \
+    largechunk(P)->larger = largechunk(P)->smaller = NULL;             \
+}
+
+/* Determine whether this chunk is linked in skip list.  */
+#define in_skip_list(P)                                                \
+  (!in_smallbin_range(P->size) && largechunk(P)->larger != NULL) 
+
+/* Take a chunk off a bin list */
+#define unlink(P, BK, FD) {                                            \
+  FD = P->fd;                                                          \
+  BK = P->bk;                                                          \
+  if (__builtin_expect (FD->bk != P || BK->fd != P, 0))                \
+    malloc_printerr (check_action, "corrupted double-linked list", P); \
+  else {                                                               \
+    FD->bk = BK;                                                       \
+    BK->fd = FD;                                                       \
+  }                                                                    \
+  if (in_skip_list(P)) {                                               \
+    if (get_larger(P) != BK) {                                         \
+      largechunk(BK)->larger = largechunk(P)->larger;                  \
+      largechunk(BK)->smaller = largechunk(P)->smaller;                \
+      largechunk(BK)->larger->smaller = largechunk(BK);                \
+      largechunk(BK)->smaller->larger = largechunk(BK);                \
+    }                                                                  \
+    else {                                                             \
+      largechunk(P)->larger->smaller = largechunk(P)->smaller;         \
+      largechunk(P)->smaller->larger = largechunk(P)->larger;          \
+    }                                                                  \
+  }                                                                    \
+}
+
 
 /*
   Unsorted chunks
@@ -2046,11 +2114,15 @@
 
     The NON_MAIN_ARENA flag is never set for unsorted chunks, so it
     does not have to be taken into account in size comparisons.
+
+    Unsorted chunks, even if large, are never in skip list and have
+    their larger/smaller pointers set to NULL.
 */
 
 /* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
 #define unsorted_chunks(M)          (bin_at(M, 1))
 
+
 /*
   Top
 
@@ -2211,8 +2283,8 @@
   /* The remainder from the most recent split of a small request */
   mchunkptr        last_remainder;
 
-  /* Normal bins packed as described above */
-  mchunkptr        bins[NBINS * 2];
+  /* Normal bins packed as described above (four pointers each) */
+  mchunkptr        bins[NBINS * 4];
 
   /* Bitmap of bins */
   unsigned int     binmap[BINMAPSIZE];
@@ -2280,11 +2352,15 @@
 {
   int     i;
   mbinptr bin;
+  mlargechunkptr large_chunk;
 
   /* Establish circular links for normal bins */
   for (i = 1; i < NBINS; ++i) {
     bin = bin_at(av,i);
     bin->fd = bin->bk = bin;
+
+    large_chunk = largechunk(bin);
+    large_chunk->larger = large_chunk->smaller = large_chunk;
   }
 
 #if MORECORE_CONTIGUOUS
@@ -2676,7 +2752,30 @@
         /* lists are sorted */
         assert(p->bk == b ||
                (unsigned long)chunksize(p->bk) >= (unsigned long)chunksize(p));
+
+        if (in_skip_list(p)) {
+          mchunkptr larger;
+          mchunkptr smaller;
+
+          larger = get_larger(p);
+          smaller = get_smaller(p);
+
+          /* skip lists are strictly ordered... */
+          assert(larger == b ||
+                 (unsigned long)chunksize(larger) > (unsigned long)size);
+          assert(smaller == b ||
+                 (unsigned long)chunksize(smaller) < (unsigned long)size);
+
+          /* ... and include every differen size */
+          assert((unsigned long)chunksize(larger->fd) == (unsigned long)size);
+        }
+      }
+      else if (!in_smallbin_range(chunksize(p))) {
+        /* unsorted chunk is not in skip list */
+        assert(get_larger(p) == NULL);
+        assert(get_smaller(p) == NULL);
       }
+
       /* chunk is followed by a legal chain of inuse chunks */
       for (q = next_chunk(p);
            (q != av->top && inuse(q) &&
@@ -3951,6 +4050,7 @@
         unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
         av->last_remainder = remainder;
         remainder->bk = remainder->fd = unsorted_chunks(av);
+        set_no_skip_list(remainder, remainder_size);
 
         set_head(victim, nb | PREV_INUSE |
 		 (av != &main_arena ? NON_MAIN_ARENA : 0));
@@ -3983,29 +4083,60 @@
         fwd = bck->fd;
       }
       else {
+        int has_unique_size;    /* Whether we should add chunk to skip list */
+
         victim_index = largebin_index(size);
         bck = bin_at(av, victim_index);
-        fwd = bck->fd;
+        fwd = get_smaller(bck); /* The largest one, actually.  */
 
         /* maintain large bins in sorted order */
-        if (fwd != bck) {
-	  /* Or with inuse bit to speed comparisons */
+        has_unique_size = (fwd == bck);
+        if (!has_unique_size) {
+	  /* Set inuse bit to get correct comparison results, since
+             other chunks have it set.  */
           size |= PREV_INUSE;
-          /* if smaller than smallest, bypass loop below */
+          /* if strictly smaller than smallest, bypass loop below */
 	  assert((bck->bk->size & NON_MAIN_ARENA) == 0);
-          if ((unsigned long)(size) <= (unsigned long)(bck->bk->size)) {
+          assert((bck->bk->size & PREV_INUSE) != 0);
+          if ((unsigned long)(size) < (unsigned long)(bck->bk->size)) {
             fwd = bck;
             bck = bck->bk;
+            has_unique_size = 1;
           }
           else {
 	    assert((fwd->size & NON_MAIN_ARENA) == 0);
+            assert((fwd->size & PREV_INUSE) != 0);
             while ((unsigned long)(size) < (unsigned long)(fwd->size)) {
-              fwd = fwd->fd;
+              fwd = get_smaller(fwd);
+              assert(fwd != bck);
 	      assert((fwd->size & NON_MAIN_ARENA) == 0);
+              assert((fwd->size & PREV_INUSE) != 0);
 	    }
-            bck = fwd->bk;
+
+            has_unique_size =
+              ((unsigned long)(size) > (unsigned long)(fwd->size));
+
+            /* We'll insert chunk just after the larger one.  */
+            bck = get_larger(fwd);
+            fwd = bck->fd;
           }
         }
+
+        assert(!in_skip_list(victim));
+
+        if (has_unique_size) {
+          mlargechunkptr lvictim;
+
+          assert(bck == bin_at(av, victim_index)
+                 || (unsigned long)(bck->size) > (unsigned long)(size));
+
+          lvictim = largechunk(victim);
+
+          lvictim->larger = largechunk(bck);
+          lvictim->smaller = largechunk(bck)->smaller;
+          lvictim->larger->smaller = lvictim;
+          lvictim->smaller->larger = lvictim;
+        }
       }
 
       mark_bin(av, victim_index);
@@ -4017,9 +4148,8 @@
 
     /*
       If a large request, scan through the chunks of current bin in
-      sorted order to find smallest that fits.  This is the only step
-      where an unbounded number of chunks might be scanned without doing
-      anything useful with them. However the lists tend to be short.
+      sorted order to find smallest that fits.  Use skip list for
+      that.
     */
 
     if (!in_smallbin_range(nb)) {
@@ -4029,13 +4159,13 @@
       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;
+        while ((unsigned long)(size = chunksize(victim)) < (unsigned long)(nb))
+          victim = get_larger(victim);
 
-        remainder_size = size - nb;
         unlink(victim, bck, fwd);
 
+        remainder_size = size - nb;
+
         /* Exhaust */
         if (remainder_size < MINSIZE)  {
           set_inuse_bit_at_offset(victim, size);
@@ -4049,6 +4179,8 @@
           remainder = chunk_at_offset(victim, nb);
           unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
           remainder->bk = remainder->fd = unsorted_chunks(av);
+          set_no_skip_list(remainder, remainder_size);
+
           set_head(victim, nb | PREV_INUSE |
 		   (av != &main_arena ? NON_MAIN_ARENA : 0));
           set_head(remainder, remainder_size | PREV_INUSE);
@@ -4112,12 +4244,13 @@
         /*  We know the first chunk in this bin is big enough to use. */
         assert((unsigned long)(size) >= (unsigned long)(nb));
 
-        remainder_size = size - nb;
+        /* Last chunk is always in skip list.  */
+        assert(in_smallbin_range(size)
+               || largechunk(bin)->larger == largechunk(victim));
 
-        /* unlink */
-        bck = victim->bk;
-        bin->bk = bck;
-        bck->fd = bin;
+        unlink(victim, bck, fwd);
+
+        remainder_size = size - nb;
 
         /* Exhaust */
         if (remainder_size < MINSIZE) {
@@ -4134,6 +4267,8 @@
 
           unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
           remainder->bk = remainder->fd = unsorted_chunks(av);
+          set_no_skip_list(remainder, remainder_size);
+
           /* advertise as last remainder */
           if (in_smallbin_range(nb))
             av->last_remainder = remainder;
@@ -4341,6 +4476,7 @@
       p->fd = fwd;
       bck->fd = p;
       fwd->bk = p;
+      set_no_skip_list(p, size);
 
       set_head(p, size | PREV_INUSE);
       set_foot(p, size);
@@ -4501,6 +4637,8 @@
             set_head(p, size | PREV_INUSE);
             p->bk = unsorted_bin;
             p->fd = first_unsorted;
+            set_no_skip_list(p, size);
+
             set_foot(p, size);
           }