Fibonacci Vs. Binary Boost heap performance in the Fast Marching Method

Question

I now this is a question asked many times. However, I cannot find a solution for my specific problem.

I have implemented the Fast Marching Method (really similar to Dijkstra) in C++11 and two different variants: with Fibonacci heap and Binary Heap. For this, I have used the Boost 1.55 heap implementations (Fibonacci and D_ary, D=2).

It is expected the binary heap to be faster in small grids and the Fibonacci's to be faster in huge grids. However, the binary heap is always faster (and there is a "huge" difference). For example:

200x200 grid: 
 Binary: 16 ms
 Fibonacci: 24 ms

300x300 grid: 
 Binary: 38 ms
 Fibonacci: 50 ms

500x500 grid: 
 Binary: 113 ms
 Fibonacci: 148 ms

1000x1000 grid: 
 Binary: 504 ms
 Fibonacci: 642 ms

I am using -Ofast -fno-finite-math-only flags in G++ 4.8.

The main point is that I can assure that a few weeks ago exactly the same implementation returned expected results.

Can anybody give me some light on this please?

Thank you!

Answer 1

Actually I found the answer and no code was needed:

There are two different problems: - 1: It depends on the CPU. Same Ubuntu distro, same compiler, same code provide different results in the same computer. - 2: the grid size was not big enough. I had to go up to 4000x4000 in order to get a larger time for the Dary version than for the Fibonacci version. In other computed I tested (both 64 bits) it was enough with a 2000x2000 grid in order to get the expected results.

Also, it depends on the origin in which the distance map is being computed, and other small points that depend on the theory of the heaps and the Fast Marching Method.