Two algorithms that give me different timing results on two different machines

What could possibly be going on?

I ran algorithm 1 and 2 in Matlab on one machine a few thousand times. Algorithm 1 always dominates algorithm 2 in terms of speed.

I then run it again on another machine a few thousand times but only 40-50% of the times do Algorithm 1 dominates algorithm 2's speed.

I can't seem to explain it. The results are different. How do I really know which algorithm's speed is better?

[Walter Roberson]

Different numbers of cores? Different amounts of available memory? Different MATLAB versions? Different operating systems? 32 bit versus 64 bit?

[Jan]

Using the profiler to find the commands, which cause the differences, would be a useful strategy. Then post the relevant lines.

Answer 1

[Matt J]

For example ... if Algorithm 2 uses more/larger basic linear algebra operations than Algorithm 1, then Algorithm 2 might start to overtake Algorithm 1 on a machine with more cores. MATLAB tries to multi-thread matrix manipulation as optimally as it can, and the resulting acceleration of those operations is greater when more parallel computing resources are available.

How do I really know which algorithm's speed is better?

This is always a hardware-dependent question.

[John]

Now if I asked which algorithm has better complexity, that shouldn't be a hardware dependent question. It seems like the complexity for Algorithm 1 is better on one machine than it is on another machine, which shouldn't be the case.

[Walter Roberson]

There are algorithms for doing parallel sorts that are better complexity than the best non-parallel sort can do. But if you try to use that parallel sort algorithm on a system that does not have multiple processors, the result is going to be worse than the non-parallel sort.

[Matt J]

Now if I asked which algorithm has better complexity, that shouldn't be a hardware dependent question

If by complexity, you mean, number of operations in relation to the data size O(N), O(N^2), etc... then it's true that that is not a hardware dependent question. However, the number of operations does not always correlate with speed, especially when parallel computing is in play.

Even without parallel computing, memory access patterns can influence speed as much or more than number of operations performed. If memory is accessed in a highly sequential matter, for example, it will be faster than an algorithm that jumps randomly to different locations. Differences in caching can also affect memory access effort. The latter, I think, is the more likely thing to vary machine-to-machine.

Answer 2

[Jan]

When doubles are processed by the floating point unit of a Intel CPU, NaNs cause a significantly slower execution time. This does not happen for the SSE unit or the floating point unit of AMD processors. So depending on the hardware storing the information of bad values by NaNs or a dedicated logical mask can be more efficient.

Multi-threading can have strange effects for simple operations like the SUM already: For more than 89900 elements, multi-threading is applied. Then the limited precision will cause different results depending on the number of cores. And because summing is not numerically stable, the effects can be large. Now imagine, an iterative method depends on the result of a dot-product. Now rounding errors depend on the hardware and can influence the convergence systematically. To control such effects, a very exhaustive debugging is required.