Message-Id: <199710272358.KAA01274@mona.lexicon.net.au>
Comments: Authenticated sender is <sjmachin AT mail DOT lexicon DOT net DOT au>
From: "John Machin" <sjmachin AT lexicon DOT net DOT au>
To: djgpp AT delorie DOT com
Date: Tue, 28 Oct 1997 10:57:16 +1000
MIME-Version: 1.0
Content-type: text/plain; charset=US-ASCII
Content-transfer-encoding: 7BIT
Subject: malloc()
Precedence: bulk


As mentioned in some discussions in this list, and in the
comments in malloc.c, the algorithm that is used allocates (or is
supposed to allocate) blocks of size 2^n. Of this, 4 bytes are
overhead. So a malloc(2044) -> 2048-byte block, malloc(2045) ->
4096-byte block, etc. This means (approximately) an overhead of 0%
to 100% on the requested size, or a waste of 0% to 50% of the memory
grabbed.

HOWEVER, experimental results, confirmed by reading the source, show
that the simplistic algorithm has been twiddled for request sizes
over 2044 bytes so that it skews the world by 4096 bytes. The
results are:

Requested size		Block		Max percent
			allocated	wasted

2045-8188		8192		75% (!!!!!!!)
8199-12284		12288		33%
12285-20476		20480		40%
-> infinity				-> 50%

This could be fixed, but I am puzzled why DJ hasn't snarfed a better
malloc from somewhere -- I understand his comments about GNU GPL
that he made in a posting, but what about public-domain stuff???

Pardon me if this has been considered and rejected it for 
reasons that I can't guess, but I'd suggest that "Doug Lea's malloc" 
would be a good substitute. I got it off the web, whacked in a few 
#defines, compiled it, and happiness prevailed; see below which is 
the first few lines of the source file with my changes and his 
"advertisement" and URLs.

Regards,

John Machin

/* === 22 Oct 97 : changes to make this work with DJGPP v2.01 === */
/* === by SJM (John Machin <sjmachin AT lexicon DOT net DOT au>) =========== */
#ifdef DJGPP
   #define HAVE_MMAP 0
   #define HAVE_MREMAP 0
   #define MORECORE_CLEARS 0
   /* DJGPP 2.01 sbrk() doesn't clear (w/o using crt_... flags) */
#endif
/* ==== end of SJM changes ====================================== */

/* ---------- To make a malloc.h, start cutting here ------------ */

/* 
  A version of malloc/free/realloc written by Doug Lea and released 
to the 
  public domain.  Send questions/comments/complaints/performance data
  to dl AT cs DOT oswego DOT edu

* VERSION 2.6.4  Thu Nov 28 07:54:55 1996  Doug Lea  (dl at gee)
  
   Note: There may be an updated version of this malloc obtainable at
           ftp://g.oswego.edu/pub/misc/malloc.c
         Check before installing!

* Why use this malloc?

  This is not the fastest, most space-conserving, most portable, or
  most tunable malloc ever written. However it is among the fastest
  while also being among the most space-conserving, portable and 
tunable.
  Consistent balance across these factors results in a good 
general-purpose 
  allocator. For a high-level description, see 
     http://g.oswego.edu/dl/html/malloc.html