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" 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: <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 Precedence: bulk > Date: Tue, 19 Feb 2002 06:10:17 -0500 > From: CBFalconer > > 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.