[RFC Needed] Allow creation of `Map` using custom comparer

[mrange]

Map is suprisingly slow. I have experimented a bit and it seems to boil down to the generic comparer used by Map.

I have experimented with adding a method to Map that allows me to specify a custom comparer:

      let comparer = 
        { new IComparer<Key> with
          member x.Compare (l, r) = l.Value.CompareTo r.Value
        }
      Map.emptyWithComparer comparer

and ran some performance tests. These are the numbers for the generic comparer:

Running test case: Map     - Lookup......It took 8686 ms, CC=0, 0, 0
Running test case: Map     - Insert......It took 9838 ms, CC=458, 0, 0
Running test case: Map     - Remove......It took 7388 ms, CC=387, 0, 0

These are the numbers with comparer above.

Running test case: Map     - Lookup......It took 347 ms, CC=0, 0, 0
Running test case: Map     - Insert......It took 1897 ms, CC=458, 0, 0
Running test case: Map     - Remove......It took 1342 ms, CC=387, 0, 0

So it do seem the comparer affect performance and it could be beneficial for performance sensitive applications to be able to provide a customer comparer.

Now; is this something that would be worth creating a PR for or are there reasons why this is not desired?

Regards,

Mårten

[forki]

Map is used in many places in the compiler. If there is a way to make it
faster then this might be very beneficial.

Am 17.11.2016 21:57 schrieb "mrange" notifications@github.com:

Map is suprisingly slow. I have experimented a bit and it seems to boil
down to the generic comparer used by Map.

I have experimented with adding a method to Map that allows me to specify
a custom comparer:

  let comparer =
    { new IComparer<Key> with
      member x.Compare (l, r) = l.Value.CompareTo r.Value
    }
  Map.emptyWithComparer comparer

and ran some performance tests. These are the numbers for the generic
comparer:

Running test case: Map - Lookup......It took 8686 ms, CC=0, 0, 0
Running test case: Map - Insert......It took 9838 ms, CC=458, 0, 0
Running test case: Map - Remove......It took 7388 ms, CC=387, 0, 0

These are the numbers with comparer above.

Running test case: Map - Lookup......It took 347 ms, CC=0, 0, 0
Running test case: Map - Insert......It took 1897 ms, CC=458, 0, 0
Running test case: Map - Remove......It took 1342 ms, CC=387, 0, 0

So it do seem the comparer affect performance and it could be beneficial
for performance sensitive applications to be able to provide a customer
comparer.

Now; is this something that would be worth creating a PR for or are there
reasons why this is not desired?

Regards,

Mårten

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
#1770, or mute the
thread
https://github.com/notifications/unsubscribe-auth/AADgNGqaESFmi4_gs6pLxr0ABuCZBfqwks5q_L-tgaJpZM4K1zOx
.

[dsyme]

@mrange @forki The tradeoff is basically between coherence (the soundness you get from making sure there is one comparer even when combining sets/maps) and the extra performance from specializing the comparer.

@mrange Could you compare performance against a custom key type implementing IComparable please? That's effectively current recommended methodology if generic comparison is a performance problem.

I'm on record in the discussion on type classes as arguing that a potential lack of coherence isn't necessarily a problem. But for Set and Map I'm hesitated to open the floodgate.... :)

[mrange]

@dsyme Type Key above implements IComparable.

  type Key(v : int) =
    member x.Value = v

    interface IComparable with
      member x.CompareTo(o : obj) =
        match o with
        | :? Key as k -> v.CompareTo (k.Value)
        | _           -> -1

    interface IComparable<Key> with
      member x.CompareTo(o : Key) = v.CompareTo (o.Value)

    interface IEquatable<Key> with
      member x.Equals(o : Key)  = v = o.Value

    override x.Equals(o : obj)  =
      match o with
      | :? Key as k -> v = k.Value
      | _           -> false
    override x.GetHashCode()    = v.GetHashCode ()
    override x.ToString()       = sprintf "%d" v

Looking at GenericCompare it looks to me like there are ~12 type tests until it lands calls CompareTo which to me seem to explain why it's rather slow.

One could try to tackle the root problem and optimize GenericCompare since I have a map of Key we know that it has to land in a CompareTo so the only tests that should remain are the nullness test and then call CompareTo. However, @latkin pointed out to me that there were an attempt to optimize GenericCompare but it was abandoned because it's a rather delicate subject.

I understand the soundness problem as two Map instances with same content can look vastly different depending on the comparer.

Yet, this seems to me to be a rather important topic as Map lookup is rather slow and I hesistate to use Map because of that.

Regards,
Mårten

[dsyme]

@mrange Thanks. Please open a fslang suggestion on this? It's a design addition so should have an RFC. I'd like more discussion on it too

[davidglassborow]

@mrange did you ever create an fslang for this (following your detailed investigations in https://gist.github.com/mrange/d6e7415113ebfa52ccb660f4ce534dd4)

[dsyme]

This needs an RFC - @mrange do you want to create it?

[zpodlovics]

I am afraid the comparer will remain slow (at least for value types) until the value type boxing remains. However F# now has a new infrastructure the byref like types to attack this problem. Would it possible to have custom comparison / equality where the (struct) argument passed by readonly reference as inref<MyValueType> ?

#526

[abelbraaksma]

Looking at GenericCompare it looks to me like there are ~12 type tests until it lands calls CompareTo which to me seem to explain why it's rather slow

As a first fix, wouldn't it be worthwhile to have the first test be: if it implements IComparable, use that? Or is that a breaking change? Or can we otherwise optimize it, for instance with static overloads or internally caching the comparer for subsequent calls?

Changing the behavior as suggested may lead to incompatibilities, but from this thread it seems that there are some (obvious?) ways to improve performance.