[m-rev.] diff: 3% speedup on tools/speedtest

Zoltan Somogyi zs at csse.unimelb.edu.au
Wed Aug 19 17:31:07 AEST 2009
Previous message: [m-rev.] for review: improve typeclass constraints error messages
Next message: [m-rev.] diff: 3% speedup on tools/speedtest
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
compiler/dead_proc_elim.m:
	Use set_tree234s instead of plain sets. Since this module does
	a lot of manipulation of big sets, the faster operations allowed
	by the tree234 structure lead to a 3% speedup.

library/set_tree234.m:
	Set the language for syntax colouring to Mercury.

Zoltan.

cvs diff: Diffing .
cvs diff: Diffing analysis
cvs diff: Diffing bindist
cvs diff: Diffing boehm_gc
cvs diff: Diffing boehm_gc/Mac_files
cvs diff: Diffing boehm_gc/cord
cvs diff: Diffing boehm_gc/cord/private
cvs diff: Diffing boehm_gc/doc
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing boehm_gc/libatomic_ops-1.2
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/doc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/gcc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/hpc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/ibmc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/icc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/msftc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/sunc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/tests
cvs diff: Diffing boehm_gc/tests
cvs diff: Diffing boehm_gc/windows-untested
cvs diff: Diffing boehm_gc/windows-untested/vc60
cvs diff: Diffing boehm_gc/windows-untested/vc70
cvs diff: Diffing boehm_gc/windows-untested/vc71
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/dead_proc_elim.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/dead_proc_elim.m,v
retrieving revision 1.132
diff -u -b -r1.132 dead_proc_elim.m
--- compiler/dead_proc_elim.m	11 Jun 2009 07:00:07 -0000	1.132
+++ compiler/dead_proc_elim.m	18 Aug 2009 12:07:29 -0000
@@ -96,11 +96,11 @@
 :- import_module maybe.
 :- import_module pair.
 :- import_module queue.
+:- import_module set_tree234.
 :- import_module set.
 :- import_module string.
 :- import_module svmap.
 :- import_module svqueue.
-:- import_module svset.
 
 %-----------------------------------------------------------------------------%
 
@@ -127,7 +127,7 @@
 % or type_ctor_info structure whose id is not in the needed map.
 
 :- type entity_queue    ==  queue(entity).
-:- type examined_set    ==  set(entity).
+:- type examined_set    ==  set_tree234(entity).
 
 dead_proc_elim(ElimOptImported, !ModuleInfo, Specs) :-
     dead_proc_analyze(!ModuleInfo, Needed),
@@ -136,7 +136,7 @@
 %-----------------------------------------------------------------------------%
 
 dead_proc_analyze(!ModuleInfo, !:Needed) :-
-    set.init(Examined0),
+    Examined0 = set_tree234.init,
     dead_proc_initialize(!ModuleInfo, Queue0, !:Needed),
     dead_proc_examine(Queue0, Examined0, !.ModuleInfo, !Needed).
 
@@ -318,10 +318,10 @@
     % See if the queue is empty.
     ( svqueue.get(Entity, !Queue) ->
         % See if the next element has been examined before.
-        ( set.member(Entity, !.Examined) ->
+        ( set_tree234.member(!.Examined, Entity) ->
             dead_proc_examine(!.Queue, !.Examined, ModuleInfo, !Needed)
         ;
-            svset.insert(Entity, !Examined),
+            set_tree234.insert(Entity, !Examined),
             (
                 Entity = entity_proc(PredId, ProcId),
                 PredProcId = proc(PredId, ProcId),
@@ -875,9 +875,15 @@
     --->    pred_elim_info(
                 pred_elim_module_info   :: module_info,
                 pred_elim_queue         :: queue(pred_id), % preds to examine.
-                pred_elim_examined      :: set(pred_id),   % preds examined.
-                pred_elim_needed_ids    :: set(pred_id),   % needed pred_ids.
-                pred_elim_needed_named  :: set(sym_name)   % pred names needed.
+
+                % preds examined.
+                pred_elim_examined      :: set_tree234(pred_id),
+
+                % needed pred_ids.
+                pred_elim_needed_ids    :: set_tree234(pred_id),
+
+                % pred names needed.
+                pred_elim_needed_named  :: set_tree234(sym_name)
             ).
 
 dead_pred_elim(!ModuleInfo) :-
@@ -896,14 +902,14 @@
         Needed1, Needed),
     map.keys(Needed, Entities),
     queue.init(Queue1),
-    set.init(NeededPreds0),
+    NeededPreds0 = set_tree234.init,
     list.foldl2(dead_pred_elim_add_entity, Entities, Queue1, Queue,
         NeededPreds0, NeededPreds1),
 
     module_info_predids(PredIds, !ModuleInfo),
 
-    set.init(Preds0),
-    set.init(Names0),
+    Preds0 = set_tree234.init,
+    Names0 = set_tree234.init,
     DeadInfo0 = pred_elim_info(!.ModuleInfo, Queue, Preds0, NeededPreds1,
         Names0),
     list.foldl(dead_pred_elim_initialize, PredIds, DeadInfo0, DeadInfo1),
@@ -914,38 +920,44 @@
     % to force type specialization are also not needed. Here we add in those
     % which are needed.
 
-    module_info_get_type_spec_info(!.ModuleInfo,
-        type_spec_info(TypeSpecProcs0, TypeSpecForcePreds0,
-            SpecMap0, PragmaMap0)),
-    set.to_sorted_list(NeededPreds2, NeededPredList2),
+    module_info_get_type_spec_info(!.ModuleInfo, TypeSpecInfo0),
+    TypeSpecInfo0 = type_spec_info(TypeSpecProcs0, TypeSpecForcePreds0,
+        SpecMap0, PragmaMap0),
+    set_tree234.to_sorted_list(NeededPreds2) = NeededPredList2,
     list.foldl((pred(NeededPred::in, AllPreds0::in, AllPreds::out) is det :-
         ( map.search(SpecMap0, NeededPred, NewNeededPreds) ->
-            set.insert_list(AllPreds0, NewNeededPreds, AllPreds)
+            set_tree234.insert_list(NewNeededPreds, AllPreds0, AllPreds)
         ;
             AllPreds = AllPreds0
         )
     ), NeededPredList2, NeededPreds2, NeededPreds),
-    set.intersect(TypeSpecForcePreds0, NeededPreds, TypeSpecForcePreds),
+    % We expect TypeSpecForcePreds0 to have very few elements, and NeededPreds
+    % to have many. Therefore doing an individual O(log N) lookup in
+    % NeededPreds for each element of TypeSpecForcePreds0 is a better approach
+    % than an intersection operation that would have to traverse all of
+    % NeededPreds.
+    TypeSpecForcePreds =
+        set.filter(set_tree234.contains(NeededPreds), TypeSpecForcePreds0),
 
-    module_info_set_type_spec_info(
-        type_spec_info(TypeSpecProcs0, TypeSpecForcePreds,
+    TypeSpecInfo = type_spec_info(TypeSpecProcs0, TypeSpecForcePreds,
             SpecMap0, PragmaMap0),
-        !ModuleInfo),
+    module_info_set_type_spec_info(TypeSpecInfo, !ModuleInfo),
 
     module_info_get_predicate_table(!.ModuleInfo, PredTable0),
     module_info_get_partial_qualifier_info(!.ModuleInfo, PartialQualInfo),
     predicate_table_restrict(PartialQualInfo,
-        set.to_sorted_list(NeededPreds), PredTable0, PredTable),
+        set_tree234.to_sorted_list(NeededPreds), PredTable0, PredTable),
     module_info_set_predicate_table(PredTable, !ModuleInfo).
 
 :- pred dead_pred_elim_add_entity(entity::in, queue(pred_id)::in,
-    queue(pred_id)::out, set(pred_id)::in, set(pred_id)::out) is det.
+    queue(pred_id)::out, set_tree234(pred_id)::in, set_tree234(pred_id)::out)
+    is det.
 
 dead_pred_elim_add_entity(entity_type_ctor(_, _, _), !Queue, !Preds).
 dead_pred_elim_add_entity(entity_table_struct(_, _), !Queue, !Preds).
 dead_pred_elim_add_entity(entity_proc(PredId, _), !Queue, !Preds) :-
     svqueue.put(PredId, !Queue),
-    svset.insert(PredId, !Preds).
+    set_tree234.insert(PredId, !Preds).
 
 :- pred dead_pred_elim_initialize(pred_id::in,
     pred_elim_info::in, pred_elim_info::out) is det.
@@ -1002,7 +1014,7 @@
                 pred_info_get_goal_type(PredInfo, goal_type_promise(_))
             )
         ->
-            svset.insert(qualified(PredModule, PredName), !NeededNames),
+            set_tree234.insert(qualified(PredModule, PredName), !NeededNames),
             svqueue.put(PredId, !Queue)
         ;
             true
@@ -1018,12 +1030,12 @@
         !.DeadInfo = pred_elim_info(ModuleInfo, !:Queue, !:Examined,
             !:Needed, NeededNames),
         ( svqueue.get(PredId, !Queue) ->
-            ( set.member(PredId, !.Examined) ->
+            ( set_tree234.member(!.Examined, PredId) ->
                 !:DeadInfo = pred_elim_info(ModuleInfo, !.Queue, !.Examined,
                     !.Needed, NeededNames)
             ;
-                svset.insert(PredId, !Needed),
-                svset.insert(PredId, !Examined),
+                set_tree234.insert(PredId, !Needed),
+                set_tree234.insert(PredId, !Examined),
                 !:DeadInfo = pred_elim_info(ModuleInfo, !.Queue, !.Examined,
                     !.Needed, NeededNames),
                 module_info_pred_info(ModuleInfo, PredId, PredInfo),
@@ -1118,11 +1130,11 @@
     some [!Queue, !NeededNames] (
         !.DeadInfo = pred_elim_info(ModuleInfo, !:Queue, Examined,
             Needed, !:NeededNames),
-        ( set.member(Name, !.NeededNames) ->
+        ( set_tree234.member(!.NeededNames, Name) ->
             true
         ;
             module_info_get_predicate_table(ModuleInfo, PredicateTable),
-            svset.insert(Name, !NeededNames),
+            set_tree234.insert(Name, !NeededNames),
             (
                 predicate_table_search_sym(PredicateTable,
                     may_be_partially_qualified, Name, PredIds)
cvs diff: Diffing compiler/notes
cvs diff: Diffing debian
cvs diff: Diffing debian/patches
cvs diff: Diffing deep_profiler
cvs diff: Diffing deep_profiler/notes
cvs diff: Diffing doc
cvs diff: Diffing extras
cvs diff: Diffing extras/base64
cvs diff: Diffing extras/cgi
cvs diff: Diffing extras/complex_numbers
cvs diff: Diffing extras/complex_numbers/samples
cvs diff: Diffing extras/complex_numbers/tests
cvs diff: Diffing extras/concurrency
cvs diff: Diffing extras/curs
cvs diff: Diffing extras/curs/samples
cvs diff: Diffing extras/curses
cvs diff: Diffing extras/curses/sample
cvs diff: Diffing extras/dynamic_linking
cvs diff: Diffing extras/error
cvs diff: Diffing extras/fixed
cvs diff: Diffing extras/gator
cvs diff: Diffing extras/gator/generations
cvs diff: Diffing extras/gator/generations/1
cvs diff: Diffing extras/graphics
cvs diff: Diffing extras/graphics/easyx
cvs diff: Diffing extras/graphics/easyx/samples
cvs diff: Diffing extras/graphics/mercury_allegro
cvs diff: Diffing extras/graphics/mercury_allegro/examples
cvs diff: Diffing extras/graphics/mercury_allegro/samples
cvs diff: Diffing extras/graphics/mercury_allegro/samples/demo
cvs diff: Diffing extras/graphics/mercury_allegro/samples/mandel
cvs diff: Diffing extras/graphics/mercury_allegro/samples/pendulum2
cvs diff: Diffing extras/graphics/mercury_allegro/samples/speed
cvs diff: Diffing extras/graphics/mercury_glut
cvs diff: Diffing extras/graphics/mercury_opengl
cvs diff: Diffing extras/graphics/mercury_tcltk
cvs diff: Diffing extras/graphics/samples
cvs diff: Diffing extras/graphics/samples/calc
cvs diff: Diffing extras/graphics/samples/gears
cvs diff: Diffing extras/graphics/samples/maze
cvs diff: Diffing extras/graphics/samples/pent
cvs diff: Diffing extras/lazy_evaluation
cvs diff: Diffing extras/lex
cvs diff: Diffing extras/lex/samples
cvs diff: Diffing extras/lex/tests
cvs diff: Diffing extras/log4m
cvs diff: Diffing extras/logged_output
cvs diff: Diffing extras/moose
cvs diff: Diffing extras/moose/samples
cvs diff: Diffing extras/moose/tests
cvs diff: Diffing extras/mopenssl
cvs diff: Diffing extras/morphine
cvs diff: Diffing extras/morphine/non-regression-tests
cvs diff: Diffing extras/morphine/scripts
cvs diff: Diffing extras/morphine/source
cvs diff: Diffing extras/net
cvs diff: Diffing extras/odbc
cvs diff: Diffing extras/posix
cvs diff: Diffing extras/posix/samples
cvs diff: Diffing extras/quickcheck
cvs diff: Diffing extras/quickcheck/tutes
cvs diff: Diffing extras/references
cvs diff: Diffing extras/references/samples
cvs diff: Diffing extras/references/tests
cvs diff: Diffing extras/solver_types
cvs diff: Diffing extras/solver_types/library
cvs diff: Diffing extras/trailed_update
cvs diff: Diffing extras/trailed_update/samples
cvs diff: Diffing extras/trailed_update/tests
cvs diff: Diffing extras/windows_installer_generator
cvs diff: Diffing extras/windows_installer_generator/sample
cvs diff: Diffing extras/windows_installer_generator/sample/images
cvs diff: Diffing extras/xml
cvs diff: Diffing extras/xml/samples
cvs diff: Diffing extras/xml_stylesheets
cvs diff: Diffing java
cvs diff: Diffing java/runtime
cvs diff: Diffing library
Index: library/set_tree234.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/set_tree234.m,v
retrieving revision 1.10
diff -u -b -r1.10 set_tree234.m
--- library/set_tree234.m	23 Oct 2006 00:33:00 -0000	1.10
+++ library/set_tree234.m	18 Aug 2009 11:58:55 -0000
@@ -1,5 +1,5 @@
 %---------------------------------------------------------------------------%
-% vim:ts=4 sw=4 expandtab
+% vim: ts=4 sw=4 et ft=mercury
 %---------------------------------------------------------------------------%
 % Copyright (C) 2005-2006 The University of Melbourne.
 % This file may only be copied under the terms of the GNU Library General
cvs diff: Diffing mdbcomp
cvs diff: Diffing profiler
cvs diff: Diffing robdd
cvs diff: Diffing runtime
cvs diff: Diffing runtime/GETOPT
cvs diff: Diffing runtime/machdeps
cvs diff: Diffing samples
cvs diff: Diffing samples/c_interface
cvs diff: Diffing samples/c_interface/c_calls_mercury
cvs diff: Diffing samples/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/mercury_calls_c
cvs diff: Diffing samples/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/standalone_c
cvs diff: Diffing samples/diff
cvs diff: Diffing samples/muz
cvs diff: Diffing samples/rot13
cvs diff: Diffing samples/solutions
cvs diff: Diffing samples/solver_types
cvs diff: Diffing samples/tests
cvs diff: Diffing samples/tests/c_interface
cvs diff: Diffing samples/tests/c_interface/c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/tests/c_interface/mercury_calls_c
cvs diff: Diffing samples/tests/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/tests/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/tests/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/tests/diff
cvs diff: Diffing samples/tests/muz
cvs diff: Diffing samples/tests/rot13
cvs diff: Diffing samples/tests/solutions
cvs diff: Diffing samples/tests/toplevel
cvs diff: Diffing scripts
cvs diff: Diffing slice
cvs diff: Diffing ssdb
cvs diff: Diffing tests
cvs diff: Diffing tests/analysis
cvs diff: Diffing tests/analysis/ctgc
cvs diff: Diffing tests/analysis/excp
cvs diff: Diffing tests/analysis/ext
cvs diff: Diffing tests/analysis/sharing
cvs diff: Diffing tests/analysis/table
cvs diff: Diffing tests/analysis/trail
cvs diff: Diffing tests/analysis/unused_args
cvs diff: Diffing tests/benchmarks
cvs diff: Diffing tests/debugger
cvs diff: Diffing tests/debugger/declarative
cvs diff: Diffing tests/dppd
cvs diff: Diffing tests/general
cvs diff: Diffing tests/general/accumulator
cvs diff: Diffing tests/general/string_format
cvs diff: Diffing tests/general/structure_reuse
cvs diff: Diffing tests/grade_subdirs
cvs diff: Diffing tests/hard_coded
cvs diff: Diffing tests/hard_coded/exceptions
cvs diff: Diffing tests/hard_coded/purity
cvs diff: Diffing tests/hard_coded/sub-modules
cvs diff: Diffing tests/hard_coded/typeclasses
cvs diff: Diffing tests/invalid
cvs diff: Diffing tests/invalid/purity
cvs diff: Diffing tests/misc_tests
cvs diff: Diffing tests/mmc_make
cvs diff: Diffing tests/mmc_make/lib
cvs diff: Diffing tests/par_conj
cvs diff: Diffing tests/recompilation
cvs diff: Diffing tests/stm
cvs diff: Diffing tests/stm/orig
cvs diff: Diffing tests/stm/orig/stm-compiler
cvs diff: Diffing tests/stm/orig/stm-compiler/test1
cvs diff: Diffing tests/stm/orig/stm-compiler/test10
cvs diff: Diffing tests/stm/orig/stm-compiler/test2
cvs diff: Diffing tests/stm/orig/stm-compiler/test3
cvs diff: Diffing tests/stm/orig/stm-compiler/test4
cvs diff: Diffing tests/stm/orig/stm-compiler/test5
cvs diff: Diffing tests/stm/orig/stm-compiler/test6
cvs diff: Diffing tests/stm/orig/stm-compiler/test7
cvs diff: Diffing tests/stm/orig/stm-compiler/test8
cvs diff: Diffing tests/stm/orig/stm-compiler/test9
cvs diff: Diffing tests/stm/orig/stm-compiler-par
cvs diff: Diffing tests/stm/orig/stm-compiler-par/bm1
cvs diff: Diffing tests/stm/orig/stm-compiler-par/bm2
cvs diff: Diffing tests/stm/orig/stm-compiler-par/stmqueue
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test1
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test10
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test11
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test2
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test3
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test4
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test5
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test6
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test7
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test8
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test9
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test1
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test2
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test3
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test4
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test5
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test6
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test7
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test8
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test9
cvs diff: Diffing tests/tabling
cvs diff: Diffing tests/term
cvs diff: Diffing tests/trailing
cvs diff: Diffing tests/valid
cvs diff: Diffing tests/warnings
cvs diff: Diffing tools
cvs diff: Diffing trace
cvs diff: Diffing util
cvs diff: Diffing vim
cvs diff: Diffing vim/after
cvs diff: Diffing vim/ftplugin
cvs diff: Diffing vim/syntax
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------
Previous message: [m-rev.] for review: improve typeclass constraints error messages
Next message: [m-rev.] diff: 3% speedup on tools/speedtest
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the reviews mailing list