Unreviewed patches

[Daniel Berlin]

On Tuesday, June 3, 2003, at 03:49  AM, Zdenek Dvorak wrote:

> Hello,
>
>>>> http://gcc.gnu.org/ml/gcc-patches/2003-04/msg01569.html
>>>
>>> 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.

>
> 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.
I find it much more likely to be an implementation problem on my part.

>
> Zdenek
>