Subject: -current malloc(3) is slow
To: None <firstname.lastname@example.org>
From: Charles M. Hannum <email@example.com>
Date: 09/11/1999 15:24:46
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
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.