Simon Peyton Jones pushed to branch wip/T26724 at Glasgow Haskell Compiler / GHC Commits: e4cb1494 by Simon Peyton Jones at 2026-01-06T20:56:11+00:00 Try harder to keep the substitution empty Avoid unnecessary cloning of varaibles in the Simplifier. Addresses #26724, See Note [Keeping the substitution empty] There are a few big wins -- see below Metrics: compile_time/bytes allocated ------------------------------------- Baseline Test Metric value New value Change ---------------------------------------------------------------------------- CoOpt_Singletons(normal) ghc/alloc 721,544,088 692,174,216 -4.1% GOOD LargeRecord(normal) ghc/alloc 1,268,031,157 1,265,168,448 -0.2% T14766(normal) ghc/alloc 918,218,533 688,432,296 -25.0% GOOD T15703(normal) ghc/alloc 318,103,629 306,638,016 -3.6% GOOD T17836(normal) ghc/alloc 419,174,584 418,400,824 -0.2% T18478(normal) ghc/alloc 471,042,976 470,261,376 -0.2% T20261(normal) ghc/alloc 573,387,162 563,663,336 -1.7% T24984(normal) ghc/alloc 87,832,666 87,636,168 -0.2% T25196(optasm) ghc/alloc 1,103,284,040 1,101,376,992 -0.2% hard_hole_fits(normal) ghc/alloc 224,981,413 224,608,208 -0.2% geo. mean -0.3% minimum -25.0% maximum +0.1% Metric Decrease: CoOpt_Singletons T14766 T15703 - - - - - 2 changed files: - compiler/GHC/Core/Subst.hs - compiler/GHC/Core/TyCo/Subst.hs Changes: ===================================== compiler/GHC/Core/Subst.hs ===================================== @@ -380,8 +380,10 @@ substIdBndr _doc rec_subst subst@(Subst in_scope env tvs cvs) old_id old_ty = idType old_id old_w = idMult old_id - no_type_change = (isEmptyVarEnv tvs && isEmptyVarEnv cvs) || + no_type_change = isEmptyTCvSubst subst || (noFreeVarsOfType old_ty && noFreeVarsOfType old_w) + -- isEmptyTCvSubst: see Note [Keeping the substitution empty] + -- in GHC.Core.TyCo.Subst -- new_id has the right IdInfo -- The lazy-set is because we're in a loop here, with ===================================== compiler/GHC/Core/TyCo/Subst.hs ===================================== @@ -960,7 +960,8 @@ substTyVarBndrUsing subst_fn subst@(Subst in_scope idenv tenv cenv) old_var -- Assertion check that we are not capturing something in the substitution old_ki = tyVarKind old_var - no_kind_change = noFreeVarsOfType old_ki -- verify that kind is closed + no_kind_change = isEmptyTCvSubst subst || noFreeVarsOfType old_ki + -- isEmptyTCvSubst: see Note [Keeping the substitution empty] no_change = no_kind_change && (new_var == old_var) -- no_change means that the new_var is identical in -- all respects to the old_var (same unique, same kind) @@ -988,7 +989,8 @@ substCoVarBndrUsing subst_fn subst@(Subst in_scope idenv tenv cenv) old_var (Subst (in_scope `extendInScopeSet` new_var) idenv tenv new_cenv, new_var) where new_co = mkCoVarCo new_var - no_kind_change = noFreeVarsOfTypes [t1, t2] + no_kind_change = isEmptyTCvSubst subst || noFreeVarsOfTypes [t1, t2] + -- isEmptyTCvSubst: see Note [Keeping the substitution empty] no_change = new_var == old_var && no_kind_change new_cenv | no_change = delVarEnv cenv old_var @@ -1034,3 +1036,22 @@ substTyCoBndr subst (Anon ty af) = (subst, Anon (substScaledTy subst ty substTyCoBndr subst (Named (Bndr tv vis)) = (subst', Named (Bndr tv' vis)) where (subst', tv') = substVarBndr subst tv + +{- Note [Keeping the substitution empty] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +A very common situation is where we run over a term doing no cloning, +no substitution, nothing. In that case the TCvSubst till be empty, and +it is /very/ valuable to /keep/ it empty: + +* It's wasted effort to build up an identity substitution mapping + [x:->x, y:->y]. + +* When we come to a binder, if the incoming substitution is empty, + we can avoid substituting its type; and that in turn may mean that + the binder itself does not change and we don't need to extend the + substitution. + +* In the Simplifier we substitute over both types and coercions. + If the substitution is empty, this is a no-op -- but only if it + is empty! +-} View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/e4cb149447bfdcab7d5cfaa0d8f80659... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/e4cb149447bfdcab7d5cfaa0d8f80659... You're receiving this email because of your account on gitlab.haskell.org.