X-Authentication-Warning: delorie.com: mailnull set sender to djgpp-workers-bounces using -f
Message-ID: <3C72A4D5.4B2E490D@yahoo.com>
Date: Tue, 19 Feb 2002 14:17:41 -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: djgpp-workers AT delorie DOT com
Subject: [Fwd: Malloc/free DJGPP code]
Content-Type: multipart/mixed;
 boundary="------------42AF80E936A3ECBD14CC9724"
Reply-To: djgpp-workers AT delorie DOT com

This is a multi-part message in MIME format.
--------------42AF80E936A3ECBD14CC9724
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

Forwarded at Eli's request.

-- 
Chuck F (cbfalconer AT yahoo DOT com) (cbfalconer AT XXXXworldnet DOT att DOT net)
   Available for consulting/temporary embedded and systems.
   (Remove "XXXX" from reply address. yahoo works unmodified)
   mailto:uce AT ftc DOT gov  (for spambots to harvest)
--------------42AF80E936A3ECBD14CC9724
Content-Type: message/rfc822
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

Return-Path: <halo1 AT zahav DOT net DOT il>
Received: from frigg.inter.net.il ([192.114.186.16])
          by mtiwgwc23.worldnet.att.net
          (InterMail vM.4.01.03.27 201-229-121-127-20010626) with ESMTP
          id <20020219124139 DOT EQAJ14171 DOT mtiwgwc23 DOT worldnet DOT att DOT net AT frigg DOT inter DOT net DOT il>
          for <cbfalconer AT worldnet DOT att DOT net>;
          Tue, 19 Feb 2002 12:41:39 +0000
Received: from zaretsky (diup-221-167.inter.net.il [213.8.221.167])
	by frigg.inter.net.il (Mirapoint)
	with ESMTP id BFU14064;
	Tue, 19 Feb 2002 14:13:36 +0200 (IST)
Date: Tue, 19 Feb 2002 14:11:05 +0200
From: "Eli Zaretskii" <eliz AT is DOT elta DOT co DOT il>
Sender: halo1 AT zahav DOT net DOT il
To: cbfalconer AT worldnet DOT att DOT net
Message-Id: <8971-Tue19Feb2002141104+0200-eliz AT is DOT elta DOT co DOT il>
X-Mailer: emacs 21.2.50 (via feedmail 8 I) and Blat ver 1.8.9
CC: djgpp-workers AT delorie DOT com
In-reply-to: <3C723299 DOT 563B5B72 AT yahoo DOT com> (message from CBFalconer on Tue, 19
	Feb 2002 06:10:17 -0500)
Subject: Re: Malloc/free DJGPP code
Reply-to: Eli Zaretskii <eliz AT is DOT elta DOT co DOT il>
References: <Pine DOT SUN DOT 3 DOT 91 DOT 1020218084527 DOT 1856I AT is> <3C723299 DOT 563B5B72 AT yahoo DOT com>
X-Mozilla-Status2: 00000000

> Date: Tue, 19 Feb 2002 06:10:17 -0500
> From: CBFalconer <cbfalconer AT yahoo DOT com>
> 
> My earlier messages showed the profile results, and pinpointed the
> problem.  I even quoted the nested for loop that caused the
> O(N**2) performance.

Sorry, I don't see any nested for loops in `merge'.  Could you please
identify the loop with O(n^2) behavior?

> I also (earlier yet) supplied some timings
> that demonstrated that performance.  The profiling showed over 80%
> of a 5 second run spent in the merge at only about 20,000 items.

There's no doubt that `merge' is taking most of the time in that
specific case.  The question is how can we speed up `merge'; to
answer that, I think we need to understand _why_ it is so slow.

> I can see why you would be worried about altering *published*
> binary structures, but the internals of malloc are hidden in the
> original code, and I am adhering strictly to the published
> interface.  So the cause of worry escapes me.

That's because you don't see the whole picture.  In the CVS, there's
an additional malloc debugging module which knows about the BLOCK
structure.  In addition, packages such as YAMD and other malloc
debuggers have intimate knowledge about BLOCK.  We don't want to
break those and other software without a good reason.

> As long as merging requires an exhaustive search of a singly
> linked list for merge candidates, it is sooner or later going to
> require such an O(N**2) algorithm.

I don't understand why; please explain.  AFAICS, `merge' simply scans
the appropriate sublist linearly until it finds the block being freed.

> Aside: so far I am not receiving the workers maillist, because it
> is being sent to my spam-trap rather than the reply-to address.

Are you talking about messages sent by DJ's mailing list software, or
by people who reply to you?  The former should be fixable by
susbcribing to djgpp-workers with your real address; the latter is a
matter of people using broken mailers, so please complain to each
individual whose mailer does that.

--------------42AF80E936A3ECBD14CC9724--