Date: Mon, 10 May 93 10:37:02 EDT
From: DJ Delorie <dj AT ctron DOT com>
To: gpk AT physics DOT att DOT com
Cc: djgpp AT sun DOT soe DOT clarkson DOT edu
Subject: Re: malloc

> I wonder if a memory allocator that keeps the blocks sorted by size in
> a b-tree might be good.  You'd expect to get rapid access to a block
> of the approximately correct size ( ln(N) tests ), and since you could
> use a best-fit (rather than a first-fit) strategy, there would probably
> be less memory fragmentation than the classic list_sorted_by_address
> algorithm.  Since blocks could be split, and the remainders put back on
> the b-tree, you wouldn't have the BSD lack-of-recycling problem.

Most malloc's use a size-keyed hash table, which is faster than a
b-tree.  Studies have shown that first-fit yeilds less fragmentation
than best-fit since the fragments are larger and thus more likely to
be reused.