Message-ID: <3E71BD8C.654AA81B@yahoo.com>
Date: Fri, 14 Mar 2003 06:31:24 -0500
From: CBFalconer <cbfalconer AT yahoo DOT com>
Organization: Ched Research
X-Mailer: Mozilla 4.75 [en] (Win98; U)
X-Accept-Language: en
MIME-Version: 1.0
To: Martin Stromberg <Martin DOT Stromberg AT epl DOT ericsson DOT se>,
   djgpp-workers <djgpp-workers AT delorie DOT com>
Subject: Re: nmalloc revisited
References: <200303140800 DOT JAA26535 AT lws256 DOT lu DOT erisoft DOT se>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Reply-To: cbfalconer AT worldnet DOT att DOT net

Martin Stromberg wrote:
> 
> > BTW the nmalloc.c code has not been altered since June 2002, and
> > the overall package is unaltered since November 2002 (some
> > documentation changes and testing).  It remains available at:
> 
> So it remains incompatible with the debugging machinery already
> present in DJGPP?
> 
> I'll back out my local incorporation of it as it seems it never will
> be (and some DJGPP test case(s?) won't build).

What won't build?  I have never found any specification for the
debugging systems, but the debug interface remains in nmalloc,
which allows as detailed examination as wished of the internal
structures, without ANY dependance on magic numbers.  AFAICT the
system is completely standard compliant, and works.

The following header:

/* -------- sysquery.h ------------ */

#ifndef sysquery_h
#define sysquery_h
#ifdef __cplusplus
   extern "C" {
#endif

/* This allows a clean connection to debugging software      */
/* NOTE: ANY value equivalent to -1 means data not available */
/*       for the unsigned chars this means 0xffh.            */
struct _sysquery {
   unsigned char data, gdlo, sz, prvf, nxtf, nxt, prv, ohead;
   void *        nilp;
};

/* This can return the above values, hopefully in a register    */
/* NONE is used in nextfree, prevfree as the equivalent of NULL */
/* With the unclean knowledge that nil is actually a pointer to */
/* freehdrs[1], and that lastsbrk is actually freehdrs[0], the  */
/* entire malloc structure is open to debuggery.                */
struct _sysquery _sysmalloc(void);

#ifdef __cplusplus
   }
#endif

#endif
/* -------- sysquery.h ------------ */

which is part of the system already, gives complete access to the
internals.  There is already an example of its usage in
tnmalloc.c.  Since all the offsets from the users pointers are
small numbers, they are returned as char.  This is intended to
allow the complete structure to be returned in a register in some
machines.  At any rate the value return ensures that there is no
inadverdent fouling of the system by this call.

You can see the dramatic effects by trying evilalgo.c, or by
executing test 4 of the hashlib package for something like 40000
allocations.  nmalloc cuts the running time of that test by about
a factor of 60, all spent in the free routine.  

The following shows the results of evilalgo on my machine, with
evilalgn using nmalloc, and evilalgo using the original.  Note
that nmalloc has no problem with it.  Only the first of the
following runs uses the original.

[1] c:\c\malloc>timerun evilalgo 100000
Timer 3 on:  5:47:56
*************
count=52832
Timer 3 off:  5:48:23  Elapsed: 0:00:26.64

[1] c:\c\malloc>timerun evilalgn 100000
Timer 3 on:  5:48:33
*************************
count=100000
Timer 3 off:  5:48:38  Elapsed: 0:00:04.99

[1] c:\c\malloc>timerun evilalgn 200000
Timer 3 on:  6:05:28
*************************************************
count=200000
Timer 3 off:  6:05:42  Elapsed: 0:00:13.90

[1] c:\c\malloc>timerun evilalgn 300000
Timer 3 on:  6:07:46
**********************************************************************
count=285360
Timer 3 off:  6:08:11  Elapsed: 0:00:25.32

which indicates that nmalloc is doing a much better job of
handling existing memory, and doesn't fail, while malloc failed at
52832 calls versus 285360 for nmalloc.  These are fairly dramatic
improvements.  I don't know just where the realloc failure occurs
in the existing malloc, and don't really care.  I do know that I
spent considerable time ensuring that nmallocs realloc was as
efficient as I could make it, and that the result is close to 50%
of the nmalloc code.

evilalgo.c is in the nmalloc package, but I include it here
anyhow:

/* From djgpp mail list - an evil algorithm */
/* This shows up the difference between DJGPP2.03 malloc and
   nmalloc, both in speed and in efficiency of memory use.
   Snaffled/cleaned up for testing use by C.B. Falconer.

   To use the new malloc, simply link it with the object module.
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct {
   char af[10];
   char name[10];
} record;

record **dt, *d;

int main(int argc, char ** argv)
{
   unsigned long n = 1000;  /* was 200000L */
   unsigned int  count;
   void         *v;

   if (argc > 1) n = strtoul(argv[1], NULL, 10);

   dt = NULL;
   for (count = 0; count < n; count++) {
      if ((v = realloc(dt, (count + 1) * sizeof *dt))) dt = v;
      else break;
      if (!(d = dt[count] = calloc(10, sizeof *d))) break;
      if (!(count & 0xfff)) putc('*', stderr);
   }
   printf("\ncount=%d\n", count);
   return(0);
} /* evilalgo */

Incidentally, your messages are appearing here without the
reply-to field, which makes it awkward to reply on the list.

-- 
Chuck F (cbfalconer AT yahoo DOT com) (cbfalconer AT worldnet DOT att DOT net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!