Unreviewed patches

[Zdenek Dvorak]

Hello,

> >>>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.
> Where can i find this stuff?  When I can access it, i'm happy to 
> profile and speed up.

on rtlopt-branch.

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

Zdenek