Perf - Lots of time being spent in HashCompare.GenericCompare due to LowerComputedListOrArrayExpr

[ChrisCanCompute]

Please provide a succinct description of the issue.

Repro steps

The project I'm seeing this in is the slowest of about 300 in our solution to compile. The project is contains sensitive information, so I'm unable to share it and I have been unable to reproduce this issue in a way that I can share here.
What I can provide is the subtree from a profile of the compiler as it compiles the project.

GenericCompare  •  1,628 ms  •  Microsoft.FSharp.Core.LanguagePrimitives+HashCompare.GenericCompare(GenericComparer, Object, Object)
  92.86%   CompareTo  •  1,512 ms of 1,628  •  System.Tuple`2.CompareTo(Object, IComparer)
    84.02%   tryGetValue  •  1,368 ms of 1,628  •  Microsoft.FSharp.Collections.MapTreeModule.tryGetValue(IComparer, TKey, ref TValue, MapTree)
      71.85%   TryForward  •  1,170 ms of 1,628  •  FSharp.Compiler.TypedTree+CcuThunk.TryForward(String[], String)
        71.85%   tryForwardPrefixPath@3238  •  FSharp.Compiler.TypedTree.tryForwardPrefixPath@3238(String[], CcuThunk, Int32)
          71.85%   TryDeref  •  FSharp.Compiler.TypedTree+NonLocalEntityRef.TryDeref(Boolean)
            71.85%   get_TryDeref  •  FSharp.Compiler.TypedTree+EntityRef.get_TryDeref
              42.74%   LowerComputedListOrArrayExpr  •  696 ms of 1,628  •  FSharp.Compiler.LowerCallsAndSeqs.LowerComputedListOrArrayExpr(FSharpFunc, TcGlobals, ImportMap, Expr)
              29.12%   get_TryDeref  •  474 ms of 1,628  •  FSharp.Compiler.TypedTree+ValRef.get_TryDeref
      12.16%   TryGetValue  •  198 ms of 1,628  •  Microsoft.FSharp.Collections.FSharpMap`2.TryGetValue(TKey, out TValue)
    8.84%   CompareTo  •  144 ms of 1,628  •  System.Tuple`2.CompareTo(Object, IComparer)
  6.16%   tryGetValue  •  100 ms of 1,628  •  Microsoft.FSharp.Collections.MapTreeModule.tryGetValue(IComparer, TKey, ref TValue, MapTree)
  0.98%   add  •  16 ms of 1,628  •  Microsoft.FSharp.Collections.MapTreeModule.add(IComparer, TKey, TValue, MapTree)

For reference, total profiled compile of the project took 29,938 ms, so we're spending ~5% of compile time doing these comparisons.

Expected behavior

Compiler should be quick to run

Actual behavior

Compiler is spending a lot of time in GenericCompare

Known workarounds

N/A

Related information

I'm running with

Microsoft (R) F# Compiler version 12.0.2.0 for F# 6.0

From past experience, swapping a Map for a Dictionary can improve performance in lookups, which would be a change to https://github.com/dotnet/fsharp/blob/main/src/fsharp/TypedTree.fs#L5383
I've not managed to build the compiler inside our company firewall, so I've not been able to try this out.

[dsyme]

The relevant code is a Map lookup on a string[] * string for the CcuTypeForwarderTable

Certainly this can be changed to either a Dictionary using a HashIdentity.Structural comparer, or to a bespoke data structure wrapping a Dictionary using a bespoke implementation of IEqualityComparer

[ChrisCanCompute]

I've managed to attach a debugger and see what's in the Map.
I've got ~2500 entries and they're either System.* or Microsoft.Win32.SafeHandles.*. I'm not sure if this is expected or not.

[nojaf]

Hello @ChrisCanCompute, would it be ok to close this issue?

[ChrisCanCompute]

Yep. Thanks Florian!