This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Unreviewed patches


> >  >
> >
> > Again this patch foundered due to the impasse between the original
> > author and yourself and the lack of a maintainer to moderate.  More
> > supporting evidence would have helped.
> This one i have more of a problem with.
> I really doubt that everyone else who uses a fibheap is wrong.
> It *should* be faster, and if it *really* matters, i can do it.
> I just don't see it as that big a deal when nothing currently really uses
> the stuff.

the webizer does, as well as my new induction variable detection on rtl
level; this is why I am concerned about the speed of df functions.

Considering the fibheap stuff -- IMHO in general the more complicated
structures have larger multiplicative constants than the equivalent simpler
structures (the O(1) insert for fibheaps does not really matter, as you
pull everything from the queue anyway).  The fibheaps lose mostly due
to being forced to manipulate a complicated structure consisting from
multiple levels of double-linked lists, while the simple heaps have
no such overhead. This of course does not say that our implementation
cannot be faster, just that I doubt it can beat the simple heaps.

For why then fibheaps are so often used -- they are pretty flexible and
support wide range of operations that the normal heaps do not or
require to add similar overhead to support them. In many applications
this is much more important than their speed (as it usually should be
majorized by processing times for elements anyway).


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]