X-Authentication-Warning: delorie.com: mailnull set sender to djgpp-bounces using -f
Date: Mon, 11 Feb 2002 22:03:50 +0200
From: "Eli Zaretskii" <eliz AT is DOT elta DOT co DOT il>
Sender: halo1 AT zahav DOT net DOT il
To: djgpp AT delorie DOT com
Message-Id: <3028-Mon11Feb2002220350+0200-eliz@is.elta.co.il>
X-Mailer: emacs 21.2.50 (via feedmail 8 I) and Blat ver 1.8.9
In-reply-to: <3C67DE6D.DEE8305C@yahoo.com> (message from CBFalconer on Mon, 11
	Feb 2002 15:10:03 GMT)
Subject: Re: Alignment problem
References: <Pine DOT SUN DOT 3 DOT 91 DOT 1020211133619 DOT 25095H-100000 AT is> <3C67DE6D DOT DEE8305C AT yahoo DOT com>
Reply-To: djgpp AT delorie DOT com
Errors-To: nobody AT delorie DOT com
X-Mailing-List: djgpp AT delorie DOT com
X-Unsubscribes-To: listserv AT delorie DOT com
Precedence: bulk

> From: CBFalconer <cbfalconer AT yahoo DOT com>
> Newsgroups: comp.os.msdos.djgpp
> Date: Mon, 11 Feb 2002 15:10:03 GMT
> 
> Flat profile:
> 
> Each sample counts as 0.0555556 seconds.
>   %   cumulative   self              self     total
>  time   seconds   seconds    calls  ns/call  ns/call  name
>  82.04      9.39     9.39    30001 312952.53 314921.80  merge
[...]
> which puts the problem (going by name) precisely where it was
> expected.

Yep, pretty much so.  It had to be merge.

> I still don't know how you are organizing the free list,

In a nutshell, they are kept in linked lists arranged in buckets by
block sizes, each sublist for a size that is a different power of 2.

Try stepping through malloc and free for several allocations and
deallocations of vastly different sizes, and I think you will see the
pattern clearly.

> If something identifies such blocks as being free or not, independant
> of the free list, this could be made linear.

You will see in the code that the LSB of the size/next pointer header
is used as the allocated/free marker.

> This implies that
> all blocks contain fields for next, size, and one bit for flags. 

Yes, there's a header and a trailer, each one 4-byte long.  See teh
definition of struct BLOCK.