CODEWITHSUNDEEP
.netf#
matlabdbuser
matlabdbuser

Reputation: 838

F# simple type and structural comparison

in this question Why is this F# code so slow?, it is discussed that structrual comparison makes the function let min3(a, b, c) = min a (min b c) slow; shouldn't the structrual comparision on simple type be as fast as the native one? I am confused because people talked about always using HashIdentity.Structural for dictionary in F# in FSharp runs my algorithm slower than Python. If I have a dictionary with simple type(int or string) as the key, do I get performance penalty for using HashIdentity.Structural?

Upvotes: 3

Views: 929

Answers (1)

kvb
kvb

Reputation: 55184

Generally speaking, I wouldn't worry about the performance of comparisons, because for typical code comparisons are very unlikely to be a performance bottleneck. If you have determined that you have a performance problem and profiling reveals that comparisons are the cause, then you can think about how best to address it.

If you do need to consider the performance of comparisons, then you may need to understand how the compiler works. In the first example you've cited, the min3 function has type 'a * 'a * 'a -> 'a when 'a : comparison. This function will be compiled to a .NET method taking 3 arguments of a generic type which would look something like this in C#:

using LP = Microsoft.FSharp.Core.LanguagePrimitives;

T min3<T>(T a, T b, T c) {
    T d = LP.HashCompare.GenericLessThanIntrinsic(b,c) ? b : c;
    return LP.HashCompare.GenericLessThanIntrinsic(d,a) ? d : a;
}

The GenericLessThanIntrinsic method is also generic, and within it there must be logic to perform the comparison based on the actual type being compared. This may require a few type tests and virtual method calls. These are not hugely expensive operations, but they are dramatically slower than performing a direct comparison of two integer values. Therefore, if comparisons make up a large part of your workload, using the generic comparison routines could have a big impact on your overall performance, and specializing the min3 function to work only on integers rather than on any generic values could be a big performance win.

Likewise, if you are just storing integers as dictionary keys, then using the built in GetHashCode() and Equals() implementations on the keys (which is what the dictionary will do by default) will be faster than using structural comparison. However, whether this will be an important difference for you will depend on the actual code you are writing - as I said before, it is somewhat unusual for key comparisons to take up a significant fraction of an algorithm's running time.

Upvotes: 3

Related Questions