Efficient membership for home modules
authorBartosz Nitka <niteria@gmail.com>
Wed, 10 May 2017 11:36:52 +0000 (04:36 -0700)
committerBartosz Nitka <niteria@gmail.com>
Wed, 10 May 2017 11:37:26 +0000 (04:37 -0700)
This changes the linear lookup in a list to an efficient
lookup in an IntMap. The linear lookup effectively made
the algorithm quadratic, which for a test case that I have
(5000 modules) introduced significant slowdown.

I ran 3 experiments to estimate the impact of this:

"No-op", profiled, just `:load`: P146, `186s`
"before", profiled, `:load` followed by 10x `:r`: P147, `315s`
"after", profiled, `:load` followed by 10x `:r`: P148, `250s`

Going by the math of `(250-186)/(315-186) = 50%` this is a 2x improvement
on `:r`.

Test Plan: ./validate

Reviewers: simonmar, austin, bgamari

Reviewed By: simonmar

Subscribers: rwbarton, thomie

Differential Revision: https://phabricator.haskell.org/D3562

compiler/main/GhcMake.hs

index 7cc5276..4d06b6e 100644 (file)
@@ -220,8 +220,9 @@ load' how_much mHscMessage mod_graph = do
     -- B.hs-boot in the module graph, but no B.hs
     -- The downsweep should have ensured this does not happen
     -- (see msDeps)
-    let all_home_mods = [ms_mod_name s
-                        | s <- mod_graph, not (isBootSummary s)]
+    let all_home_mods =
+          mkUniqSet [ ms_mod_name s
+                    | s <- mod_graph, not (isBootSummary s)]
     -- TODO: Figure out what the correct form of this assert is. It's violated
     -- when you have HsBootMerge nodes in the graph: then you'll have hs-boot
     -- files without corresponding hs files.
@@ -236,7 +237,7 @@ load' how_much mHscMessage mod_graph = do
         checkHowMuch _ = id
 
         checkMod m and_then
-            | m `elem` all_home_mods = and_then
+            | m `elementOfUniqSet` all_home_mods = and_then
             | otherwise = do
                     liftIO $ errorMsg dflags (text "no such module:" <+>
                                      quotes (ppr m))
@@ -656,7 +657,7 @@ unload hsc_env stable_linkables -- Unload everthing *except* 'stable_linkables'
 checkStability
         :: HomePackageTable   -- HPT from last compilation
         -> [SCC ModSummary]   -- current module graph (cyclic)
-        -> [ModuleName]       -- all home modules
+        -> UniqSet ModuleName -- all home modules
         -> ([ModuleName],     -- stableObject
             [ModuleName])     -- stableBCO
 
@@ -669,7 +670,8 @@ checkStability hpt sccs all_home_mods = foldl checkSCC ([],[]) sccs
      where
         scc = flattenSCC scc0
         scc_mods = map ms_mod_name scc
-        home_module m   = m `elem` all_home_mods && m `notElem` scc_mods
+        home_module m =
+          m `elementOfUniqSet` all_home_mods && m `notElem` scc_mods
 
         scc_allimps = nub (filter home_module (concatMap ms_home_allimps scc))
             -- all imports outside the current SCC, but in the home pkg