So, there are several ways in which the `new' malloc(3) is quite slow:

* realloc(3) ~always copies; it doesn't know how to extend or shrink a
  region (except in very special cases, like going from NBPG+1 to
  NBPG*2).

  This should be trivially solvable by just freeing the tail end or
  checking whether the pages after the object are available.

* realloc(3) and free(3) do a bunch of gratuitous O(n) (where `n' is
  the number of pages in the object) operations when dealing with
  multi-page chunks, just to figure out how large the chunk is!

  To solve this (but not add extra overhead), I suggest replacing
  MALLOC_FIRST/MALLOC_FOLLOW with MALLOC_ONE/MALLOC_MANY:

  + If the chunk is one page, the table entry will contain MALLOC_ONE.

  + If the chunk is more than one page, the table entry for the first
    page will contain MALLOC_MANY, the next entry will contain the
    actual number of pages, and the remaining entries will be left as
    MALLOC_FREE so that they do not need to be touched later.

  This will interfere slightly with some types of error detection, but
  this seems like a small price to pay for better performance.

* free(3) does a linear search down the free chunk list to add the
  page(s) being freed.

  This can be solved by making the free list be one of several types
  of tree structure.

Does anyone want to work on this?  I don't really have time, but I
think it's important to fix some of these problems.