X-Authentication-Warning:	delorie.com: mailnull set sender to djgpp-workers-bounces using -f
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@is.elta.co.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.563B5B72@yahoo.com> (message from CBFalconer on Tue, 19
	Feb 2002 06:10:17 -0500)
Subject:	Re: Malloc/free DJGPP code
References:	<Pine DOT SUN DOT 3 DOT 91 DOT 1020218084527 DOT 1856I AT is> <3C723299 DOT 563B5B72 AT yahoo DOT com>
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

> 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.

- Raw text -