Measurements

We measured the heap size of the following nine mallocs when used with the same Hummingbird and Emacs dynamic memory access traces, which were described in Sections 2 and 3 above. We picked mostly open source malloc packages which are common on Linux and FreeBSD. We also included two Solaris mallocs, since the Solaris 3X malloc caused the heap overflow that prompted us to investigate the fragmentation problem in the first place.

The following description of the mallocs is sorted by increasing heap fragmentation at the end of the Hummingbird trace run. This is also the the order of entries in Table 3. The fragmentation percentage is computed by $100 \times (\frac{heap size}{live\ memory}-1)$.

• PhK/BSD malloc version 42
  Written by Poul-Henning Kamp [3] and distributed with FreeBSD, NetBSD and OpenBSD. Available from ftp://ftp.FreeBSD.org/pub/FreeBSD/src/lib/libc/stdlib/malloc.c .

• Solaris default
  This is the default malloc distributed on SunOS 5.6.

• GNU malloc last modified in 1995
  Written by Mike Heartel and distributed with the GNU libraries. Available from ftp://www.leo.org/pub/comp/os/unix/gnu .

  The latest version of GNU malloc is available from ftp://ftp.leo.org/pub/comp/os/unix/gnu/malloc.tar.gz .

• Modified binary buddy
  A modified binary buddy algorithm, which coalesces any two neighboring free blocks of the same size, even if the resulting block is not aligned on the new block size boundary. This algorithm uses a hash table to determine quickly if a neighboring block of the same size is completely free. This routine was written by the second author of this paper and will be available from https://www.bell-labs.com/~eran/malloc .

• Doug Lea's malloc version 2.6.6
  This malloc is optimized both for speed and fragmentation and is the basis for the GNU g++ malloc. Written by Doug Lea and available from https://gee.cs.oswego.edu/pub/misc/malloc.c .

• Quick Fit malloc
  An implementation of Weinstock and Wulf's fast segregated-storage algorithm based on an array of free lists. available from ftp://ftp.cs.colorado.edu/pub/cs/misc/qf.c .

• CSRI malloc version 1.18
  Written by Mark Moraes from the University of Toronto. Available from ftp://ftp.cs.toronto.edu/pub/moraes/malloc.tar.gz .

• Vmalloc written on 1/16/1994
  Kiem Phong-Vo's malloc with the ``default'' setting, which is optimized for ``typical'' workloads. The results of the ``best'' setting were very similar to the ``default'' setting for both Hummingbird and Emacs traces, so we reported only the results of the ``default'' setting. Available from https://portal.research.bell-labs.com/orgs/ssr/book/reuse/license/packages/95/vmalloc.html.

• Solaris 3X
  This is a ``space efficient'' malloc distributed with SunOS 5.8. It is available through linking with -lmalloc. Its manual page is man 3x malloc.

We ran all tests a dual processor Intel Pentium III with 700 MHz clock speed running SunOS 5.8 (Solaris 8 distribution). Note that the driver program is single threaded, so it did not use the 2nd processor.