Float out can take quadratic time
Summary
I've written a simple Template Haskell program that produces nested expressions. If these programs get large then it can take very long to compile them.
Steps to reproduce
{-# LANGUAGE TemplateHaskell #-}
module Common where
data List_ a f = Nil_ | Cons_ a f deriving Functor
between alg a b
| a == b = [|| $$alg Nil_ ||]
| otherwise = [|| $$alg (Cons_ a $$(between alg (a + 1) b)) ||]
{-# LANGUAGE TemplateHaskell #-}
module Foo where
import Common
foo :: (List_ Int a -> a) -> a
foo alg = $$(between [|| alg ||] 0 1000)
If we compile this with ghc -O Foo.hs -ddump-timings
we will see the float out timings. If I change the third argument of between from 1000 we can see how it scales:
size | 2nd float-out time (ms) |
---|---|
1000 | 601 |
2000 | 2595 |
3000 | 5862 |
4000 | 10944 |
5000 | 18825 |
6000 | 25289 |
7000 | 34933 |
8000 | 49785 |
9000 | 61680 |
10000 | 76162 |
So it seems float-out takes quadratic time in this case.
In particular, I'm looking at the second float out pass, which looks like this in the dump:
*** Float out(FOS {Lam = Just 0,
Consts = True,
OverSatApps = True}) [Foo]:
Float out(FOS {Lam = Just 0, Consts = True, OverSatApps = True}) [Foo]: alloc=205141562384 time=76162.434
Also the remaining timings do seem to scale linearly. With code generation taking the most time besides that second float out pass.
Expected behavior
Compile faster.
Environment
- GHC version used: 9.8.1