[m-rev.] for review: proper mmc --make speedup

[Peter Wang]

On 2008-07-07, Julien Fischer <juliensf at csse.unimelb.edu.au> wrote:
>
> On Fri, 27 Jun 2008, Peter Wang wrote:
>
>> Estimated hours taken: 12
>> Branches: main
>>
>> Speed up dependency computation in `mmc --make'.  It was spending the majority
>> of its time taking unions of sets.  Therefore change to a set representation
>> which is fast for unions, sparse_bitset.  To make use of bitsets, maintain a
>> mapping between module_names and integers, and dependency_files and integers.
>> Use version_hash_tables and version_arrays to hold the forward and reverse
>> mappings.
>
>> (We don't really need version types.)
>
> Why are you using them then?  Presumably to avoid having to muck about
> with the insts on real hash tables and arrays?

Yes.

>> +:- pred union_deps_plain_set(
>> +    find_module_deps_plain_set(T)::in(find_module_deps_plain_set),
>> +    module_index::in, bool::out, set(T)::in, set(T)::out,
>> +    make_info::in, make_info::out, io::di, io::uo) is det.
>> +
>> +:- pred deps_set_foldl3_maybe_stop_at_error(bool::in,
>> +    foldl3_pred_with_status(T, Acc, Info, IO)::in(foldl3_pred_with_status),
>> +    deps_set(T)::in, bool::out, Acc::in, Acc::out, Info::in, Info::out,
>> +    IO::di, IO::uo) is det <= enum(T).
>
> Why are the last two arguments polymorphic there?

foldl3_maybe_stop_at_error was polymorphic.

>> +%-----------------------------------------------------------------------------%
>> +
>> +:- type deps_result(T) == pair(bool, deps_set(T)).
>
> I would make that into a proper d.u. type.
>
> 	:- type deps_result(T) ---> deps_result(bool, deps_set(T)).

Done.

>> +:- type module_deps_result == deps_result(module_index).
>> +
>> +union_deps(FindDeps, ModuleIndex, Success, Deps0, Deps, !Info, !IO) :-
>> +    FindDeps(ModuleIndex, Success, Deps1, !Info, !IO),
>> +    Deps = union(Deps0, Deps1).
>
> That looks okay otherwise.

I also added more caching.  Interdiff follows.

Peter


diff --git a/compiler/make.dependencies.m b/compiler/make.dependencies.m
index 7b0288d..d946ed6 100644
--- a/compiler/make.dependencies.m
+++ b/compiler/make.dependencies.m
@@ -160,6 +160,9 @@
 :- type cached_transitive_dependencies.
 :- func init_cached_transitive_dependencies = cached_transitive_dependencies.
 
+:- type cached_foreign_imports.
+:- func init_cached_foreign_imports = cached_foreign_imports.
+
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
@@ -297,7 +300,12 @@ dependency_files_to_index_set_2(DepFiles, Set0, Set, !Info) :-
 
 %-----------------------------------------------------------------------------%
 
-:- type deps_result(T) == pair(bool, deps_set(T)).
+:- type deps_result(T)
+    --->    deps_result(
+                dr_success  :: bool,
+                dr_set      :: deps_set(T)
+            ).
+
 :- type module_deps_result == deps_result(module_index).
 
 union_deps(FindDeps, ModuleIndex, Success, Deps0, Deps, !Info, !IO) :-
@@ -660,7 +668,7 @@ init_cached_direct_imports = map.init.
 
 direct_imports(ModuleIndex, Success, Modules, !Info, !IO) :-
     ( Result0 = !.Info ^ cached_direct_imports ^ elem(ModuleIndex) ->
-        Result0 = Success - Modules
+        Result0 = deps_result(Success, Modules)
     ;
         KeepGoing = !.Info ^ keep_going,
 
@@ -695,7 +703,7 @@ direct_imports(ModuleIndex, Success, Modules, !Info, !IO) :-
             )
         ),
         !:Info = !.Info ^ cached_direct_imports ^ elem(ModuleIndex)
-            := Success - Modules
+            := deps_result(Success, Modules)
     ).
 
     % Return the modules for which `.int' files are read in a compilation
@@ -710,12 +718,12 @@ non_intermod_direct_imports(ModuleIndex, Success, Modules, !Info, !IO) :-
         !.Info ^ cached_non_intermod_direct_imports ^ elem(ModuleIndex)
             = Result
     ->
-        Result = Success - Modules
+        Result = deps_result(Success, Modules)
     ;
         non_intermod_direct_imports_2(ModuleIndex, Success, Modules,
             !Info, !IO),
         !Info ^ cached_non_intermod_direct_imports ^ elem(ModuleIndex)
-            := Success - Modules
+            := deps_result(Success, Modules)
     ).
 
 :- pred non_intermod_direct_imports_2(module_index::in, bool::out,
@@ -840,6 +848,10 @@ intermod_imports(ModuleIndex, Success, Modules, !Info, !IO) :-
 
 %-----------------------------------------------------------------------------%
 
+:- type cached_foreign_imports == map(module_index, module_deps_result).
+
+init_cached_foreign_imports = map.init.
+
 :- pred foreign_imports(module_index::in, bool::out,
     deps_set(module_index)::out, make_info::in, make_info::out, io::di, io::uo)
     is det.
@@ -884,6 +896,22 @@ find_module_foreign_imports(Languages, ModuleIndex, Success, ForeignModules,
 
 find_module_foreign_imports_2(Languages, ModuleIndex,
         Success, ForeignModules, !Info, !IO) :-
+    % Languages should be constant for the duration of the process.
+    ( Result0 = !.Info ^ cached_foreign_imports ^ elem(ModuleIndex) ->
+        Result0 = deps_result(Success, ForeignModules)
+    ;
+        find_module_foreign_imports_3(Languages, ModuleIndex,
+            Success, ForeignModules, !Info, !IO),
+        !Info ^ cached_foreign_imports ^ elem(ModuleIndex)
+            := deps_result(Success, ForeignModules)
+    ).
+
+:- pred find_module_foreign_imports_3(set(foreign_language)::in,
+    module_index::in, bool::out, deps_set(module_index)::out,
+    make_info::in, make_info::out, io::di, io::uo) is det.
+
+find_module_foreign_imports_3(Languages, ModuleIndex,
+        Success, ForeignModules, !Info, !IO) :-
     module_index_to_name(!.Info, ModuleIndex, ModuleName),
     get_module_dependencies(ModuleName, MaybeImports, !Info, !IO),
     (
@@ -1028,8 +1056,6 @@ fact_table_files(ModuleIndex, Success, Files, !Info, !IO) :-
                 module_locn
             ).
 
-:- type transitive_deps_result == pair(bool, deps_set(module_index)).
-
 :- type transitive_dependencies_type
     --->    interface_imports
     ;       all_imports            % every import_module and use_module
@@ -1041,7 +1067,7 @@ fact_table_files(ModuleIndex, Success, Files, !Info, !IO) :-
     ;       any_module.
 
 :- type cached_transitive_dependencies ==
-    map(transitive_dependencies_root, transitive_deps_result).
+    map(transitive_dependencies_root, deps_result(module_index)).
 
 init_cached_transitive_dependencies = map.init.
 
@@ -1079,14 +1105,14 @@ find_transitive_module_dependencies(DependenciesType, ModuleLocn,
     DepsRoot = transitive_dependencies_root(ModuleIndex, DependenciesType,
         ModuleLocn),
     ( Result0 = !.Info ^ cached_transitive_dependencies ^ elem(DepsRoot) ->
-        Result0 = Success - Modules
+        Result0 = deps_result(Success, Modules)
     ;
         globals.io_lookup_bool_option(keep_going, KeepGoing, !IO),
         find_transitive_module_dependencies_2(KeepGoing,
             DependenciesType, ModuleLocn, ModuleIndex,
             Success, init, Modules, !Info, !IO),
         !:Info = !.Info ^ cached_transitive_dependencies ^ elem(DepsRoot)
-            := Success - Modules
+            := deps_result(Success, Modules)
     ).
 
 :- pred find_transitive_module_dependencies_2(bool::in,
@@ -1107,7 +1133,7 @@ find_transitive_module_dependencies_2(KeepGoing, DependenciesType,
             DependenciesType, ModuleLocn),
         Result0 = !.Info ^ cached_transitive_dependencies ^ elem(DepsRoot)
     ->
-        Result0 = Success - Modules1,
+        Result0 = deps_result(Success, Modules1),
         Modules = union(Modules0, Modules1)
     ;
         module_index_to_name(!.Info, ModuleIndex, ModuleName),
diff --git a/compiler/make.m b/compiler/make.m
index b40ceac..eda3b69 100644
--- a/compiler/make.m
+++ b/compiler/make.m
@@ -134,6 +134,8 @@
                 cached_transitive_dependencies
                                         :: cached_transitive_dependencies,
 
+                cached_foreign_imports  :: cached_foreign_imports,
+
                 % Should the `.module_dep' files be rebuilt.
                 % Set to `no' for `mmc --make clean'.
                 rebuild_module_deps     :: rebuild_module_deps,
@@ -354,6 +356,7 @@ make_process_args(Variables, OptionArgs, Targets0, !IO) :-
             init_cached_direct_imports,
             init_cached_direct_imports,
             init_cached_transitive_dependencies,
+            init_cached_foreign_imports,
             ShouldRebuildModuleDeps, KeepGoing,
             set.init, no, set.list_to_set(ClassifiedTargets),
             AnalysisRepeat),


--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------