Mail Archives: djgpp/1996/10/23/21:47:08
In article <845921032 DOT 28340 DOT 0 AT abwillms DOT demon DOT co DOT uk>, alaric AT abwillms DOT demon DOT co DOT uk (Alaric B. Williams) writes:
|>Eli Zaretskii <eliz AT is DOT elta DOT co DOT il> wrote:
[Mistaken attributbion snipped - Eli was responding to a message
by Jon Slaughter]
|>
|>>Check out the method your program uses to allocate memory. If it
|>>allocates all the 18 MB at once, the DJGPP library allocation functions
|>>round that up to the next power of 2, which means you ask for 32 MB.
|>
|>How serious is that power-of-two waste - in that is it then free for
|>the next allocation to be taken from (ie if I then request 32-18 =
|>14Mb will it not 'allocate' any more), or is it really that bad?
|>
It really wastes it - virtually at least, although not physically,
although this may depend whether you use the zeroing malloc or
or plain malloc, and possibly also on your DPMI provider. If memory
is not truly allocated until it is referenced, you just end up with
holes in your address space - no big deal usually.
|>If so, what's the point? Surely it's no slower to allocate to the
|>nearest word?
|>
The idea of the algorithm (which comes from the BSD implementation of
libc) is not to be faster on initial allocation, but to be fast
for programs which make many calls to malloc/free for differing sized
blocks. Instead of a single linked list of all free chunks of memory,
which can grow very large and take a long time to search, a set of
lists of blocks of size 16,32,64, etc is kept and when you request
n bytes, a search is made of the list of blocks of size 2^K where 2^K >= n.
This also helps to reduce memory fragmentation in programs which make
many thousands or millions of calls to malloc/free.
The algorithm works well for cases where the average size of chunks
allocated is orders of magnitude less than the total address space or
real memory available. It breaks down when single allocations are
comparable in magnitude to the size of all memory available - i.e.
are within a factor of 10 or so of it.
There are alternative mallocs which use naive algorithms (allocate to the
nearest doubleword - you don't want to go smaller than that or your blocks
will be badly aligned for memory and cache fetches). They are slower in some
cases and more prone to memory fragmentation. Another approach, which we
have used on our larger Unix systems, is to use the power-of-2 algorithm
for blocks up to a specific size (we used 1 Mbyte, I think) and
an alternative , exact-fit algorithm for blocks above that. This
helped on our 4 Gbyte system, with a 2-Gbyte-per-process address space,
when programs making requests for 1.1 Gbyte of memory in one go fell over
because malloc tried to give them 2 Gbyte :-(
malloc is just straight user-type code, and anyone can replace
it without knowing djgpp or c internals.
----------------------------------------------------------------------------
Kevin Ashley K DOT Ashley AT Ulcc DOT ac DOT uk
Development Manager http://www.ulcc.ac.uk/staff/Kevin+Ashley
University of London Computer Centre. ...ukc!ncdlab!K.Ashley
This is not a signature
- Raw text -