From: Vik Heyndrickx <Vik DOT Heyndrickx AT rug DOT ac DOT be>
Newsgroups: comp.os.msdos.djgpp
Subject: Re: question to malloc and free
Date: Wed, 02 Sep 1998 15:37:42 +0200
Organization: University of Ghent, Belgium
Lines: 44
Message-ID: <35ED4A26.1AD0@rug.ac.be>
References: <199808271918 DOT PAA16748 AT delorie DOT com> <35E5EDF2 DOT 3DDE5F7D AT unb DOT ca>
NNTP-Posting-Host: eduserv1.rug.ac.be
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

Endlisnis wrote:
> 
> DJ Delorie wrote:
> 
>     I've read that the size of the block allocated by malloc/new is always
> a power of 2, and rounded up to one if it isn't (after adding it's few
> words).  Why does it do this?  This seems (to me) like it would waste about
> 1/2 the RAM allocated.

The most important reasons are:
- It was imperically proven that this method avoids severe memory
fragmentation (which I'm not convinced of for the new (DJ-)malloc BTW).
- It uses a very fast look-up method for as well allocating as
deallocating, and it eases coallescing adjacent memory blocks, resulting
in relatively easy and short algorithms (read: bug free).

What concerns the memory wastage:
Theoretically this method wastes AT MOST 1/2 of all memory. For DJGPP
this means that at most 1/2 of all virtual memory is wasted. However,
most memory managers (part of the DPMI host) apply lazy allocation,
which means that only memory (and swap space) is allocated when the page
(of 4Kb) is effectively used (read or written to). According to Charles
Sandmann that also is true for CWSDPMI. 

An example:
The user requests exactly 64K (65536 bytes) from malloc.
The malloc implementation adds a few bytes, say N (typically 16 or 32
bytes in many implementations), needed for its administrativa.
Then the size 64K+N is round up to the next power of 2, which is 128K
(131072 bytes).
All bytes in the range [N+64K;128K] are never used, and hence due to the
lazy allocation scheme they are never physically allocated (and thus no
wasted RAM, but still wasted virtual memory since that is often limited
up to 16Mb, 64Mb or 2Gb depending on the used OS).
The physical RAM that is wasted is the RAM in the last page that is
never used and would be in this example case 4Kb-N. In an average case
(4Kb / 2).

If I am wrong, please feel free to correct me.

-- 
 \ Vik /-_-_-_-_-_-_/
  \___/ Heyndrickx /
   \ /-_-_-_-_-_-_/  Knight in the Order of the Unsigned Types