X-Authentication-Warning: delorie.com: mailnull set sender to djgpp-workers-bounces using -f
From: sandmann AT clio DOT rice DOT edu (Charles Sandmann)
Message-Id: <10202192346.AA14305@clio.rice.edu>
Subject: Re: Malloc/free DJGPP code
To: djgpp-workers AT delorie DOT com
Date: Tue, 19 Feb 2002 17:46:39 -0600 (CST)
Cc: eliz AT is DOT elta DOT co DOT il (Eli Zaretskii), cbfalconer AT yahoo DOT com
In-Reply-To: <3C72DA25.F1AE5FF0@yahoo.com> from "CBFalconer" at Feb 19, 2002 06:05:09 PM
X-Mailer: ELM [version 2.5 PL2]
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Reply-To: djgpp-workers AT delorie DOT com
Errors-To: nobody AT delorie DOT com
X-Mailing-List: djgpp-workers AT delorie DOT com
X-Unsubscribes-To: listserv AT delorie DOT com
Precedence: bulk

> The outer loop isn't in malloc, it is in the application, which
> has the array or linked list or whatever of allocated memory to
> free.
> 
> >       for (bp=freelist[bu]; bp; bpp=&(bp->next), bp=bp->next)
> 
> This is the only thing that matters.  It makes each merge O(n),
> and must be executed O(n) times, thus O(n*n).

I agree this code should be improved.  We should not search a 
list - especially in a linear search.  If we can't find a a quick
way to merge blocks, we shouldn't merge blocks.

> At most dividing into sublists changes the constant factor.  The
> O(n*n) will always dominate.  The search has to go on until either
> an adjacency is found or the whole list has been searched and none
> has been found.  Sublists don't change this.

If there was some way to do a binary search in a sorted list we could
make that a log(n) type behavior which would IMO be acceptable, but
O(n) is bad.

> I can easily make a portion of the revised memblock compatible
> with the original, in that the size and freelist pointer will be
> at the same (-ve) offsets from the user pointer.  That would
> forbid the safety improvement I am making to guard against
> off-by-one indexed operations.  Publishing the offsets of those
> two items in implementation space would allow gradual conversion
> of unclean software that uses them, so that eventually the module
> would be truly independant  If the other software uses only the
> size that is better.  I envision a globally available variable:
> 
>    const int __msize_offset = offsetof(memblock, data)
>                             - offsetof(memblock, size);
> 
> and the header contains:
> 
>    extern const int __msize_offset;
> 
> which is initially constrained (and documented) to be the same as
> the present.

Be aware that alignment is also a very important issue here that we
just discussed about a week ago - I don't think we've decided which
of the 2 ways we should pick yet to fix our occasional alignment
offset issue.  I'm pretty uncomfortable making any major changes to
malloc() for many reasons if it can be avoided.