GitLab

Simon Jakobi pushed to branch wip/sjakobi/tweak-mk_mod_usage_info at Glasgow Haskell Compiler / GHC

Commits:

f595622f

by Simon Jakobi at 2026-04-22T02:52:00+02:00

Tweak mk_mod_usage_info

* Use O(log n) `elemModuleEnv` instead of O(n) `elem` to filter the
  direct imports.
* Use `nonDetModuleEnvKeys` to avoid sorting the ent_map keys twice.
* Prepend the presumably shorter list when creating all_mods with
  `(++)`. Actually this eliminates the `(++)` entirely, as it seems to
  fuse with the `filter` expression.
* As the above changes change the demand on ent_map, we force it
  to ensure it's only computed once.

As a result there is a tiny speed-up when generating the .hi-files for
modules with many imports.

None of the changes affect compilation determinism as the module list
is explicitly sorted to ensure a canonical order.

2 changed files:

compiler/GHC/HsToCore/Usage.hs
compiler/GHC/Unit/Module/Env.hs

Changes:

compiler/GHC/HsToCore/Usage.hs

@@ -219,15 +219,20 @@ mk_mod_usage_info :: UsageConfig
                -> NameSet
                -> IfG [Usage]
  mk_mod_usage_info uc home_unit home_unit_ids this_mod direct_imports imp_decls used_names
 -  = mapMaybeM mkUsageM usage_mods
 +  = ent_map `seq` mapMaybeM mkUsageM usage_mods
 +      -- ent_map is required _lazily_ for several sub-computations, so we force
 +      -- it here to ensure it's built only once.
    where
      safe_implicit_imps_req = uc_safe_implicit_imps_req uc
 -    used_mods    = moduleEnvKeys ent_map
 -    dir_imp_mods = Map.keys direct_imports
 -    all_mods     = used_mods ++ filter (`notElem` used_mods) dir_imp_mods
 -    usage_mods   = sortBy stableModuleCmp all_mods
 -                        -- canonical order is imported, to avoid interface-file
 +    used_mods     = nonDetModuleEnvKeys ent_map
 +                      -- nonDetModuleEnvKeys is OK here, because the
 +                      -- resulting usage_mods are sorted explicitly.
 +    is_used_mod m = m `elemModuleEnv` ent_map
 +    dir_imp_mods  = Map.keys direct_imports
 +    all_mods      = filter (not . is_used_mod) dir_imp_mods ++ used_mods
 +    usage_mods    = sortBy stableModuleCmp all_mods
 +                        -- canonical order is important, to avoid interface-file
                          -- wobblage.
      -- ent_map groups together all the things imported and used

compiler/GHC/Unit/Module/Env.hs

@@ -8,7 +8,7 @@ module GHC.Unit.Module.Env
     , lookupWithDefaultModuleEnv, mapModuleEnv, mkModuleEnv, emptyModuleEnv
     , alterModuleEnv
     , partitionModuleEnv
 -   , moduleEnvKeys, moduleEnvElts, moduleEnvToList
 +   , moduleEnvKeys, nonDetModuleEnvKeys, moduleEnvElts, moduleEnvToList
     , unitModuleEnv, isEmptyModuleEnv
     , extendModuleEnvWith, filterModuleEnv, mapMaybeModuleEnv
@@ -157,8 +157,15 @@ mkModuleEnv xs = ModuleEnv (Map.fromList [(NDModule k, v) | (k,v) <- xs])
  emptyModuleEnv :: ModuleEnv a
  emptyModuleEnv = ModuleEnv Map.empty
 +-- | See Note [ModuleEnv performance and determinism].
 +--
 +-- If you use this, please provide a justification why it doesn't introduce
 +-- nondeterminism.
 +nonDetModuleEnvKeys :: ModuleEnv a -> [Module]
 +nonDetModuleEnvKeys (ModuleEnv e) = map unNDModule $ Map.keys e
++
  moduleEnvKeys :: ModuleEnv a -> [Module]
 -moduleEnvKeys (ModuleEnv e) = sort $ map unNDModule $ Map.keys e
 +moduleEnvKeys = sort . nonDetModuleEnvKeys
    -- See Note [ModuleEnv performance and determinism]
  moduleEnvElts :: ModuleEnv a -> [a]