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