This is the mail archive of the
mailing list for the GCC project.
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
> >>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.
> Where can i find this stuff? When I can access it, i'm happy to
> profile and speed up.
> >Considering the fibheap stuff -- IMHO in general the more complicated
> >structures have larger multiplicative constants than the equivalent
> >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.
> Which is where i believe you are dead wrong.
> >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.
> They are often used as priority queues where there is no need to
> decrement a key quickly.
> They are widely regarded as *faster* as a priority queue structure than
> normal heaps.
> I have a hard time believing you are correct, and every piece of
> published material i can find (including my textbook from design and
> analysis of efficient algorithms, for that matter) is wrong.
can you send me a reference please? I was searching a web just now and
found nothing except the following citation (from a not really reliable
source) claiming that
"Fibonacci heaps are asymptotically the best priority queues known: They
perform all heap operations in O(log n) time, some even in amortized
constant time. However, in practise they are "known" (by the
theoreticians) to be inferior eg. to d-heaps because their internal
maintenance is relatively involved. Performance tests (with random data)
indicated that they are indeed a bit slower but not too much (at least
for many elements)."