Mail Archives: djgpp-workers/2002/02/19/15:27:36
*** resent because of wrong maillist address ***
Eli Zaretskii wrote:
>
> > 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.
Then that is an unclean interface to me. The malloc module could
publish either the amount of block overhead (as an extern const
data item with an implementation space name) and/or the record
specification offsets, again as extern consts.
The following is my current definition; the guardxx can be
elided. How can it be made compatible? After all, that was the
purpose of sending the preliminary. I would not advise publishing
the entire definition.
typedef struct memblock {
struct memblock *prev;
struct memblock *next;
struct memblock *nextfree;
ulong sz; /* of this memblock */
ulong guardlo; /* may hold size requested */
/* here lies the actual assigned storage */
/* so the following must be addressed by adding offset */
/* storage must always be a multiple of 4 in size */
/* thus these items are fictional, i.e. for zero data */
ulong guardhi;
} memblock, *memblockp;
> > 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.
It has to search all the lists for adjacencies. O(n). And it has
to search for each item freed. O(n) again, resulting in O(n*n).
Maybe better characterized as O(n*m). I am cutting the Gordian
knot by preserving pointers to adjacent items in prev and next.
> > 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.
I did use my real address, in the reply-to field. Just as here.
The from field is not editable except by reconfiguring.
--
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)
- Raw text -