compiler: Introduce and use RoughMap for instance environmentswip/roughmap-mp

Here we introduce a new data structure, RoughMap, inspired by the
previous `RoughTc` matching mechanism for checking instance matches.
This allows [Fam]InstEnv to be implemented as a trie indexed by these
RoughTc signatures, reducing the complexity of instance lookup and
FamInstEnv merging (done during the family instance conflict test)
from O(n) to O(log n).

The critical performance improvement currently realised by this patch is
in instance matching. In particular the RoughMap mechanism allows us to
discount many potential instances which will never match for constraints
involving type variables (see Note [Matching a RoughMap]). In realistic
code bases matchInstEnv was accounting for 50% of typechecker time due
to redundant work checking instances when simplifying instance contexts
when deriving instances. With this patch the cost is significantly
reduced.

The larger constants in InstEnv creation do mean that a few small
tests regress in allocations slightly. However, the runtime of T19703 is
reduced by a factor of 4. Moreover, the compilation time of the Cabal
library is slightly improved.

A couple of test cases are included which demonstrate significant
improvements in compile time with this patch.

This unfortunately does not fix the testcase provided in #19703 but does
fix #20933

-------------------------
Metric Decrease:
    T12425
Metric Increase:
    T13719
    T9872a
    T9872d
    hard_hole_fits
-------------------------

Co-authored-by: Matthew Pickering <matthewtpickering@gmail.com>

4 files changed, 88 insertions, 1 deletions

diff --git a/testsuite/tests/perf/compiler/InstanceMatching.stderr b/testsuite/tests/perf/compiler/InstanceMatching.stderr
new file mode 100644
index 0000000000..f4e978cf2e
--- /dev/null
+++ b/testsuite/tests/perf/compiler/InstanceMatching.stderr
@@ -0,0 +1,5 @@
+
+Match.hs:1006:1: error:
+    • No instance for (Show (F001 a)) arising from a use of ‘showsPrec’
+    • In the first argument of ‘(.)’, namely ‘(showsPrec 11 b1)’
+      In the second argument of ‘(.)’, namely
diff --git a/testsuite/tests/perf/compiler/Makefile b/testsuite/tests/perf/compiler/Makefile
index 0011c70710..33d2878db7 100644
--- a/testsuite/tests/perf/compiler/Makefile
+++ b/testsuite/tests/perf/compiler/Makefile
@@ -28,3 +28,8 @@ MultiLayerModulesTH_Make_Prep:
 MultiLayerModulesTH_OneShot_Prep: MultiLayerModulesTH_Make_Prep
 	$(CP) MultiLayerModules.hs MultiLayerModulesTH_OneShot.hs
 
+# Type family skolems
+InstanceMatching:
+	./genMatchingTest 0
+	'$(TEST_HC)' $(TEST_HC_OPTS) -fno-code -fwrite-interface Defs.hs
+
diff --git a/testsuite/tests/perf/compiler/all.T b/testsuite/tests/perf/compiler/all.T
index 4136572419..532db501e6 100644
--- a/testsuite/tests/perf/compiler/all.T
+++ b/testsuite/tests/perf/compiler/all.T
@@ -282,6 +282,7 @@ test('MultiLayerModules',
      multimod_compile,
      ['MultiLayerModules', '-v0'])
 
+
 # MultiLayerModules flip flops by 2.5%, depending on the
 # number of modules within GHC (#19293). Just widen the
 # acceptance window until we figured out how to fix it.
@@ -334,6 +335,30 @@ test('MultiLayerModulesDefsGhci',
      ghci_script,
      ['MultiLayerModulesDefsGhci.script'])
 
+test('InstanceMatching',
+     [ collect_compiler_stats('bytes allocated',3),
+       pre_cmd('$MAKE -s --no-print-directory InstanceMatching'),
+       extra_files(['genMatchingTest']),
+       compile_timeout_multiplier(5),
+       grep_errmsg('F001')],
+     multimod_compile_fail,
+     ['Match', '-fno-code -fwrite-interface -v0'])
+
+# This module stresses the KnownTC and NoKnownTC (skolem variable) cases
+test('InstanceMatching1',
+     [ collect_compiler_stats('bytes allocated',3),
+       pre_cmd('./genMatchingTest 1'),
+       extra_files(['genMatchingTest']),
+       compile_timeout_multiplier(5)
+       # this is _a lot_
+       # but this test has been failing every now and then,
+       # especially on i386. Let's just give it some room
+       # to complete successfully reliably everywhere.
+     ],
+     multimod_compile,
+     ['Defs', '-fno-code -fwrite-interface -v0'])
+
+
 test('MultiLayerModulesNoCode',
      [ collect_compiler_residency(15),
        pre_cmd('./genMultiLayerModulesNoCode'),
@@ -558,7 +583,7 @@ test('hard_hole_fits', # Testing multiple hole-fits with lots in scope for #1687
 test('T16875',  # Testing one hole-fit with a lot in scope for #16875
      collect_compiler_stats('bytes allocated', 2),
      compile, ['-fdefer-type-errors -fno-max-valid-hole-fits -package ghc'])
-test ('T20261', 
+test ('T20261',
       [collect_compiler_stats('all')],
       compile,
       [''])
diff --git a/testsuite/tests/perf/compiler/genMatchingTest b/testsuite/tests/perf/compiler/genMatchingTest
new file mode 100755
index 0000000000..9356d9028a
--- /dev/null
+++ b/testsuite/tests/perf/compiler/genMatchingTest
@@ -0,0 +1,52 @@
+#!/usr/bin/env bash
+# Generate a module with N data types and instances
+DEFS=10000
+MATCHES=500
+MODE=$1
+echo "module Defs where" > Defs.hs;
+for i in $(seq -w 1 $DEFS); do
+  echo "data T$i a = T$i a deriving Show" >> Defs.hs;
+done
+
+echo "{-# LANGUAGE TypeFamilies #-}" > Match.hs
+echo "{-# LANGUAGE StandaloneDeriving #-}" >> Match.hs
+echo "{-# LANGUAGE EmptyDataDecls #-}" >> Match.hs
+echo "module Match where" >> Match.hs
+echo "import Defs" >> Match.hs
+
+if [ $MODE -eq 0 ]; then
+  for i in $(seq -w 1 $MATCHES); do
+    echo "type family F$i a where" >> Match.hs;
+  done
+  echo "data T a = T" >> Match.hs
+  for i in $(seq -w 1 $MATCHES); do
+    echo "       (F$i a)" >> Match.hs;
+  done
+  echo "deriving instance Show (T a)" >> Match.hs;
+fi
+#elif [ $MODE -eq 1 ]; then
+#  echo "data T " >> Match.hs
+#    for i in $(seq -w 1 $MATCHES); do
+#      echo "       a$i" >> Match.hs;
+#    done
+#    echo "       = T " >> Match.hs
+#    for i in $(seq -w 1 $MATCHES); do
+#      echo "       a$i" >> Match.hs;
+#    done
+#    echo "deriving instance Show (T" >> Match.hs
+#    for i in $(seq -w 1 $MATCHES); do
+#      echo "       a$i" >> Match.hs;
+#    done
+#    echo "    )" >> Match.hs;
+#else
+#  for i in $(seq -w 1 $MATCHES); do
+#    echo "data F$i a" >> Match.hs;
+#  done
+#  echo "data T a = T" >> Match.hs
+#  for i in $(seq -w 1 $MATCHES); do
+#    echo "       (F$i a)" >> Match.hs;
+#  done
+#  echo "deriving instance Show (T a)" >> Match.hs;
+#
+#fi
+