Performance regression in equality constraint using TypeFamilies in GHC 9.8.1+
## Summary
Starting with GHC 9.8.1 the following module requires 10s of seconds and multiple gigs of memory to compile. On GHC 9.6.7 it compiles in ~200ms.
This is a simplified example from a commercial Haskell project that compiles on 9.6.7, but we cannot upgrade due to compile time and memory usage in later versions.
```haskell
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeFamilies #-}
module Typechecker (
someTypes
) where
import Data.Kind (Type)
import GHC.TypeLits (Symbol)
type family Append (left :: [k]) (right :: [k]) :: [k] where
Append '[] right = right
Append (a : rest) right = a : Append rest right
type family TaggedTypes (tags :: [(Symbol, Type)]) :: [Type] where
TaggedTypes '[] = '[]
TaggedTypes ('(_, typ) : rest) = typ : TaggedTypes rest
data Types (types :: [(Symbol, Type)]) = Types
mkTypes :: forall sym val. val -> Types '[ '(sym, val) ]
mkTypes _ = Types
appendTypes ::
-- This constraint is the one that causes the issue. If the next line is commented
-- out, then this module compiles quickly
Append (TaggedTypes left) (TaggedTypes right) ~ TaggedTypes (Append left right) =>
Types left -> Types right -> Types (Append left right)
appendTypes _ _ = Types
someTypes ::
Types
[ '("01", Int)
, '("02", Int)
, '("03", Int)
, '("04", Int)
, '("05", Int)
, '("06", Int)
, '("07", Int)
, '("08", Int)
, '("09", Int)
, '("10", Int)
, '("11", Int)
, '("12", Int)
, '("13", Int)
, '("14", Int)
, '("15", Int)
, '("16", Int)
, '("17", Int)
, '("18", Int)
, '("19", Int)
]
someTypes =
mkTypes @"01" 1 `appendTypes`
mkTypes @"02" 2 `appendTypes`
mkTypes @"03" 3 `appendTypes`
mkTypes @"04" 4 `appendTypes`
mkTypes @"05" 5 `appendTypes`
mkTypes @"06" 6 `appendTypes`
mkTypes @"07" 7 `appendTypes`
mkTypes @"08" 8 `appendTypes`
mkTypes @"09" 9 `appendTypes`
mkTypes @"10" 10 `appendTypes`
mkTypes @"11" 11 `appendTypes`
mkTypes @"12" 12 `appendTypes`
mkTypes @"13" 13 `appendTypes`
mkTypes @"14" 14 `appendTypes`
mkTypes @"15" 15 `appendTypes`
mkTypes @"16" 16 `appendTypes`
mkTypes @"17" 17 `appendTypes`
mkTypes @"18" 18 `appendTypes`
mkTypes @"19" 19
```
## Steps to reproduce
`ghc TypeChecker.hs`
## Expected behavior
Speed and memory usage comparable to 9.6.7.
## Environment
* GHC versions showing slowness: 9.8.1, 9.8.4, 9.10.3, 9.12.2
(9.14.0.20250908 does not exhibit the problem)
[ghc-9.6.7-verbose.txt](/uploads/fa4b5a727dde6322f4f062a024a665d1/ghc-9.6.7-verbose.txt)
[ghc-9.10.3-verbose.txt](/uploads/2998c858a90432c6597bbe59804d69f7/ghc-9.10.3-verbose.txt)
issue