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.