Date: Mon, 10 May 1993 09:21:06 -0700 (PDT)
From: Andrew Tucker <a_tucker AT paul DOT spu DOT edu>
Subject: Re: malloc
To: gpk AT physics DOT att DOT com
Cc: djgpp AT sun DOT soe DOT clarkson DOT edu


On Mon, 10 May 1993 gpk AT physics DOT att DOT com wrote:

> 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.
> 
> --Greg Kochanski


Sounds good, but a Btree would bring in a lot of overhead, or at least,
more than a simple sorted, linked-list scheme.  Depending on the
speed/fragmentation/efficiency differences it may be worth it.


/* Andrew */

"As far as the laws of mathematics refer to reality, they are not certain;
 and as far as they are certain, they do not refer to reality"
				Albert Einstein