[m-rev.] diff: speed up modules.m a bit

[Zoltan Somogyi]

compiler/modules.m:
	When computing the dependency graph, avoid situations in which
	a module to be processed is in the list of modules to be processed
	multiple times, since this can lead to very deep recursion which
	requires lots of stack in debugging grades. Instead of using a list,
	use a set of modules to be processed.

	This also leads to a slight speedup in non-debugging grades; doing
	--generate-dependencies on the compiler six times in a row drops from
	a total time of 107.x seconds to 104.x seconds on my laptop.

Zoltan.

cvs diff: Diffing .
Index: modules.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/modules.m,v
retrieving revision 1.386
diff -u -b -r1.386 modules.m
--- modules.m	10 Apr 2006 06:57:26 -0000	1.386
+++ modules.m	10 Apr 2006 06:57:36 -0000
@@ -3947,7 +3947,8 @@
 
 generate_dependencies(Mode, Search, ModuleName, DepsMap0, !IO) :-
     % First, build up a map of the dependencies.
-    generate_deps_map([ModuleName], Search, DepsMap0, DepsMap, !IO),
+    generate_deps_map(set.make_singleton_set(ModuleName), Search,
+        DepsMap0, DepsMap, !IO),
 
     %
     % Check whether we could read the main `.m' file.
@@ -4265,18 +4266,19 @@
     % (Module1 deps_rel Module2) means Module1 is imported by Module2.
 :- type deps_rel == relation(module_name).
 
-:- pred generate_deps_map(list(module_name)::in, bool::in,
+:- pred generate_deps_map(set(module_name)::in, bool::in,
     deps_map::in, deps_map::out, io::di, io::uo) is det.
 
-generate_deps_map([], _, !DepsMap, !IO).
-generate_deps_map([Module | Modules], Search, !DepsMap, !IO) :-
+generate_deps_map(!.Modules, Search, !DepsMap, !IO) :-
+    ( set.remove_least(!.Modules, Module, !:Modules) ->
         % Look up the module's dependencies, and determine whether
         % it has been processed yet.
-    lookup_dependencies(Module, Search, Done, !DepsMap, ModuleImports, !IO),
-        % If the module hadn't been processed yet, then add its
-        % imports, parents, and public children to the list of
-        % dependencies we need to generate, and mark it as
-        % having been processed.
+        lookup_dependencies(Module, Search, Done, !DepsMap, ModuleImports,
+            !IO),
+
+        % If the module hadn't been processed yet, then add its imports,
+        % parents, and public children to the list of dependencies we need
+        % to generate, and mark it as having been processed.
     (
         Done = no,
         map.set(!.DepsMap, Module, deps(yes, ModuleImports), !:DepsMap),
@@ -4290,15 +4292,23 @@
             ModuleImports ^ int_deps,
             ModuleImports ^ impl_deps,
             ModuleImports ^ public_children, % a.k.a. incl_deps
-            ForeignImportedModules,
-            Modules],
-            Modules1)
+                ForeignImportedModules],
+                ModulesToAdd),
+            % We could keep a list of the modules we have already processed
+            % and subtract it from ModulesToAddSet here, but doing that
+            % actually leads to a small slowdown.
+            set.list_to_set(ModulesToAdd, ModulesToAddSet),
+            set.union(ModulesToAddSet, !Modules)
     ;
-        Done = yes,
-        Modules1 = Modules
+            Done = yes
     ),
-        % Recursively process the remaining modules
-    generate_deps_map(Modules1, Search, !DepsMap, !IO).
+        % Recursively process the remaining modules.
+        generate_deps_map(!.Modules, Search, !DepsMap, !IO)
+    ;
+        % If we can't remove the smallest, then the set of modules to be
+        % processed is empty.
+        true
+    ).
 
     % Construct a pair of dependency relations (the interface dependencies
     % and the implementation dependencies) for all the modules in the program.
cvs diff: Diffing notes
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------