Re: [PATCH] Speed up hybrid_search_bitmap

[Daniel Berlin <dberlin at dberlin dot org>]

On Monday, April 21, 2003, at 04:43  AM, Zdenek Dvorak wrote:

> Hello,
>
> there is no reason to use Fibonacci heaps for worklist in
> iterative_dataflow_bitmap;

Actually, there was.

We perform a large number of inserts and extractmins.
On fibonacci heaps, insert is O(1), not logarithmic.
Extractmin should be a bit slower the first time (O(n) absolute worst 
case actual), but as fast or faster for the rest (log n in both cases).

You are replacing something that should be O(1) and O(log n) with 
something that is O(log n) and O(log n).


> this patch replaces them with ordinary
> heaps, thus speeding up df_analyse by 20%.

If it's really that much faster, then the fibheap probably needs a bit 
of optimization.
What operations are going slow, exactly?
I've never seen it in profiles.
I'd really like to see if we can't optimize it before we go replacing 
it.
--Dan