[PATCH] Speed up hybrid_search_bitmap

[Zdenek Dvorak]

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

your argumentation is wrong; you always remove exactly what you insert,
so it does not really matter if you count O(1) + O(log n) or O(log n) +
O(log n). The thing that matters is that Fibonacci heaps are a
relatively complicated structure with much higher multiplicative
constants than ordinary heaps.

> >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?

Before replacement:
[122]    0.9    0.12    1.84     990         iterative_dataflow_bitmap [122]
                0.03    0.85  384460/405950      fibheap_extract_min [224]
                0.18    0.63    3220/3220        hybrid_search_bitmap [251]
                0.02    0.08  384460/405950      fibheap_insert [732]
                0.03    0.01   90360/1594390     bitmap_copy [297]
                0.01    0.00    6440/6440        sbitmap_first_set_bit [1541]
                0.01    0.00  387680/408960      fibheap_empty [1482]
                0.00    0.00    4210/1409750     sbitmap_zero [589]
                0.00    0.00     990/4140        fibheap_new [1967]
                0.00    0.00    1980/34620       sbitmap_alloc [1860]
                0.00    0.00     990/2795940     xmalloc [776]
                0.00    0.00     990/4140        fibheap_delete [2513]

after replacement:

[209]    0.5    0.09    0.95     990         iterative_dataflow_bitmap [209]
                0.19    0.67    3220/3220        hybrid_search_bitmap [239]
                0.03    0.00  384460/384460      heap_extract_min [1141]
                0.02    0.01   90360/1594390     bitmap_copy [341]
                0.02    0.00  384460/384460      heap_insert [1286]
                0.01    0.00  387680/387680      heap_size [1495]
                0.00    0.00    1980/34620       sbitmap_alloc [1426]
                0.00    0.00    4210/1409750     sbitmap_zero [571]
                0.00    0.00     990/2796930     xmalloc [683]
                0.00    0.00     990/990         heap_alloc [2174]
                0.00    0.00    6440/6440        sbitmap_first_set_bit [2487]

> I've never seen it in profiles.
> I'd really like to see if we can't optimize it before we go replacing 
> it.

maybe, but you will never make it as fast as simple ordinary heaps (the
reason to use Fibonacci heaps would be if you used decrease key operation,
as here really matters that you can do it in constant time). I think it
would be a waste of time, as df.c is the only place where significant time is
spent in fibheap_extract_min.

Zdenek