[m-dev.] Re: e-mail and work
Zoltan Somogyi
zs at csse.unimelb.edu.au
Mon Dec 11 18:34:25 AEDT 2006
I found another quadratic algorithm in the compiler that shows up when
compiling Doug Auclair's training cars example, which has a predicate
contaning more than a hundred thousand variables.
The problem is in requantification. When implicitly_quantify_goal_2 looks
at an atomic goal such as a deconstruction unification, it adds the set
of variables in that goal to the set of seen variables. The problem is
that, since we allocate variable numbers sequentially, the set of variables
so far will typically include all (or at least most) variables up to some
variable number, say N, while the variables of the atomic goal will typically
include some variables with numbers higher than N (as well as some with numbers
lower than N). Since sparse bitsets use a list of bitmaps ordered on (in this
case) on variable number, constructing the list representing the union requires
traversing to the end of the list. If there are M atomic goals, then there
will be M calls to sparse_bitset.union, with the number of list cells looked
at each union operation itself being proportional to M. (The constant of
proportionality is of course still much smaller for sparse_bitset.m than
for our other set representations.)
I think the solution is to change the representation used in sparse_bitset.m
to be hierarchical. Besides leaf nodes just like the current bitset_elem,
that contain information about up to bits_per_int adjacent potential elements,
we should also have nonleaf nodes that represent information about larger and
larger groups of potential elements. For example, we could have a level N
nonleaf nodes representing information about bits_per_int * 2^N potential
elements (naturally aligned, as bitset_elems are). These nodes wouldn't contain
that information directly; they would point to an ordered list of lower level
nodes, with bitset_elems at the bottom of the pile.
Since we are looking at sparse_bitsets in general (though the bitset is
actually dense with the training cars example), we wouldn't want to require
every bitset_elem to be included in a level 1 nonleaf node, which would be
included in a level 2 nonleaf node, and so on. Instead, we could allow a
level M node to contain a list of up to a fixed number k lower level nodes.
I am sure we could get a design that increases the constant factors only
slightly from the current ones, bur reduces worst case behavior for lookup
operations from being proportional to the size of the representation
to being proportional to the logarithm of the size of the representation.
We should also get logarithmic complexity for union operations in which
the two sets occupy distinct regions of element numbers (as with the situation
described above for requantification).
Any comments, especially from Simon (since sparse_bitset.m is your baby)?
And if there is (eventual) consensus that this is a good idea, any volunteers?
BTW, in my local workspace on my laptop, it now takes about 250 seconds
to compile /home/mercury/zs/mer/auclair/training_cars_full.m. About 90 seconds
of this is requantification being invoked from simplify at the end of semantic
analysis. The output of mtc_diff on the trace counts files before and after
simplification, processed with mslice, is attached.
Zoltan.
-------------- next part --------------
Procedure Path/Port File:Line Count (-1)
pred int.</2-0 CALL int.m:36 628,205,981 (-1)
pred int.</2-0 EXIT int.m:36 625,842,468 (-1)
func sparse_bitset.union_2/2-0 CALL sparse_bitset.m:977 615,128,244 (-1)
func sparse_bitset.union_2/2-0 EXIT sparse_bitset.m:977 615,128,244 (-1)
func sparse_bitset.intersect_2/2-0 CALL sparse_bitset.m:1003 17,676,861 (-1)
func sparse_bitset.intersect_2/2-0 EXIT sparse_bitset.m:1003 17,676,861 (-1)
pred tree234.search/3-0 CALL tree234.m:320 9,254,837 (-1)
pred check_hlds.inst_match.bound_inst_list_contains_instname/6-0 CALL inst_match.m:1892 8,280,292 (-1)
pred check_hlds.inst_match.bound_inst_list_contains_instname/6-0 EXIT inst_match.m:1892 8,280,292 (-1)
pred check_hlds.inst_match.inst_list_contains_instname/6-0 CALL inst_match.m:1910 8,134,197 (-1)
pred check_hlds.inst_match.inst_list_contains_instname/6-0 EXIT inst_match.m:1910 8,134,197 (-1)
pred tree234.search/3-0 EXIT tree234.m:320 5,845,165 (-1)
func int.unchecked_left_shift/2-0 CALL int.m:165 5,507,114 (-1)
func int.unchecked_left_shift/2-0 EXIT int.m:165 5,507,114 (-1)
func int.\//2-0 CALL int.m:195 5,337,041 (-1)
func int.\//2-0 EXIT int.m:195 5,337,041 (-1)
pred check_hlds.inst_match.bound_inst_list_contains_instname/6-0 <s2;> inst_match.m:1894 5,305,126 (-1)
pred check_hlds.inst_match.bound_inst_list_contains_instname/6-0 <s2;c6;s1;> inst_match.m:1903 5,305,126 (-1)
pred check_hlds.inst_match.inst_list_contains_instname/6-0 <s1;> inst_match.m:1910 5,305,126 (-1)
func int./\/2-0 CALL int.m:191 4,545,787 (-1)
func int./\/2-0 EXIT int.m:191 4,545,787 (-1)
func sparse_bitset.union/2-0 CALL sparse_bitset.m:972 3,601,489 (-1)
func sparse_bitset.union/2-0 EXIT sparse_bitset.m:972 3,601,489 (-1)
pred tree234.search/3-0 FAIL tree234.m:320 3,409,672 (-1)
func int.-/2-0 CALL int.m:96 3,207,310 (-1)
func int.-/2-0 EXIT int.m:96 3,207,310 (-1)
pred term.var_to_int/2-0 CALL term.m:1099 3,157,595 (-1)
pred term.var_to_int/2-0 EXIT term.m:1099 3,157,595 (-1)
func term.ClassMethod_for_enum__enum____term__var__arity1______enum__to_int_1/1-0 CALL term.m:1095 3,157,589 (-1)
func term.ClassMethod_for_enum__enum____term__var__arity1______enum__to_int_1/1-0 EXIT term.m:1095 3,157,589 (-1)
func term.var_to_int/1-0 CALL term.m:1279 3,157,589 (-1)
func term.var_to_int/1-0 EXIT term.m:1279 3,157,589 (-1)
pred check_hlds.inst_match.bound_inst_list_contains_instname/6-0 <s1;> inst_match.m:1892 2,975,166 (-1)
pred check_hlds.inst_match.inst_contains_instname_2/6-0 CALL inst_match.m:1844 2,975,166 (-1)
pred check_hlds.inst_match.inst_contains_instname_2/6-0 EXIT inst_match.m:1844 2,975,166 (-1)
pred check_hlds.inst_match.inst_contains_instname_2/6-0 <s3;> inst_match.m:1870 2,975,166 (-1)
func int.\/1-0 CALL int.m:206 2,878,558 (-1)
func int.\/1-0 EXIT int.m:206 2,878,558 (-1)
pred sparse_bitset.fold_bits/7-0 CALL sparse_bitset.m:569 2,878,558 (-1)
pred sparse_bitset.fold_bits/7-0 EXIT sparse_bitset.m:569 2,878,558 (-1)
pred check_hlds.inst_match.inst_list_contains_instname/6-0 <s2;> inst_match.m:1912 2,829,071 (-1)
pred check_hlds.inst_match.inst_list_contains_instname/6-0 <s2;c5;s1;> inst_match.m:1919 2,829,071 (-1)
func sparse_bitset.list_to_set_2/2-0 CALL sparse_bitset.m:825 2,746,272 (-1)
func sparse_bitset.list_to_set_2/2-0 EXIT sparse_bitset.m:825 2,746,272 (-1)
func int.unchecked_right_shift/2-0 CALL int.m:179 2,660,572 (-1)
func int.unchecked_right_shift/2-0 EXIT int.m:179 2,660,572 (-1)
pred int.</2-0 FAIL int.m:36 2,363,513 (-1)
func int.+/2-0 CALL int.m:82 2,091,057 (-1)
func int.+/2-0 EXIT int.m:82 2,091,057 (-1)
pred int.bits_per_int/1-0 CALL int.m:640 1,907,826 (-1)
pred int.bits_per_int/1-0 EXIT int.m:640 1,907,826 (-1)
func int.bits_per_int/0-0 CALL int.m:733 1,907,826 (-1)
func int.bits_per_int/0-0 EXIT int.m:733 1,907,826 (-1)
pred sparse_bitset.union/3-0 CALL sparse_bitset.m:1149 1,817,464 (-1)
pred sparse_bitset.union/3-0 EXIT sparse_bitset.m:1149 1,817,464 (-1)
pred tree234.tree234_to_assoc_list_2/3-0 CALL tree234.m:2416 1,806,120 (-1)
pred tree234.tree234_to_assoc_list_2/3-0 EXIT tree234.m:2416 1,806,120 (-1)
func sparse_bitset.list_to_set/1-0 CALL sparse_bitset.m:814 1,782,352 (-1)
func sparse_bitset.list_to_set/1-0 EXIT sparse_bitset.m:814 1,782,352 (-1)
pred hlds.hlds_goal.goal_info_get_determinism/2-0 CALL hlds_goal.m:1628 1,624,023 (-1)
pred hlds.hlds_goal.goal_info_get_determinism/2-0 EXIT hlds_goal.m:1628 1,624,023 (-1)
func sparse_bitset.insert_2/2-0 CALL sparse_bitset.m:675 1,614,435 (-1)
func sparse_bitset.insert_2/2-0 EXIT sparse_bitset.m:675 1,614,435 (-1)
pred map.search/3-0 CALL map.m:562 1,595,705 (-1)
pred sparse_bitset.insert_list/3-0 CALL sparse_bitset.m:1129 1,580,040 (-1)
pred sparse_bitset.insert_list/3-0 EXIT sparse_bitset.m:1129 1,580,040 (-1)
func sparse_bitset.insert_list/2-0 CALL sparse_bitset.m:695 1,580,040 (-1)
func sparse_bitset.insert_list/2-0 EXIT sparse_bitset.m:695 1,580,040 (-1)
pred sparse_bitset.insert/3-0 CALL sparse_bitset.m:1127 1,578,370 (-1)
pred sparse_bitset.insert/3-0 EXIT sparse_bitset.m:1127 1,578,370 (-1)
func sparse_bitset.insert/2-0 CALL sparse_bitset.m:670 1,578,370 (-1)
func sparse_bitset.insert/2-0 EXIT sparse_bitset.m:670 1,578,370 (-1)
pred int.>/2-0 CALL int.m:40 1,540,738 (-1)
pred int.>/2-0 FAIL int.m:40 1,527,282 (-1)
func int.floor_to_multiple_of_bits_per_int/1-0 CALL int.m:466 1,503,814 (-1)
func int.floor_to_multiple_of_bits_per_int/1-0 EXIT int.m:466 1,503,814 (-1)
func int.quot_bits_per_int/1-0 CALL int.m:647 1,503,814 (-1)
func int.quot_bits_per_int/1-0 EXIT int.m:647 1,503,814 (-1)
func int.times_bits_per_int/1-0 CALL int.m:654 1,503,814 (-1)
func int.times_bits_per_int/1-0 EXIT int.m:654 1,503,814 (-1)
pred hlds.quantification.goal_vars_2/6-0 CALL quantification.m:1106 1,397,793 (-1)
pred hlds.quantification.goal_vars_2/6-0 EXIT quantification.m:1106 1,397,793 (-1)
pred hlds.quantification.goal_vars_2/6-0 <s11;> quantification.m:1106 1,379,400 (-1)
pred hlds.quantification.goal_vars_2/6-0 <s11;c12;?;> quantification.m:1108 1,379,400 (-1)
pred hlds.quantification.goal_vars_2/6-0 <s11;c12;t;> quantification.m:1114 1,379,400 (-1)
pred hlds.quantification.goal_vars_2/6-0 <s11;c12;t;c1;?;> quantification.m:1109 1,379,400 (-1)
pred hlds.quantification.goal_vars_2/6-0 <s11;c12;t;c1;e;> quantification.m:1113 1,379,400 (-1)
pred hlds.quantification.goal_vars_2/6-0 <s11;c12;t;c2;?;> quantification.m:1116 1,379,400 (-1)
pred hlds.quantification.goal_vars_2/6-0 <s11;c12;t;c2;e;> quantification.m:1120 1,379,400 (-1)
pred hlds.quantification.unify_rhs_vars/7-0 CALL quantification.m:1230 1,379,400 (-1)
pred hlds.quantification.unify_rhs_vars/7-0 EXIT quantification.m:1230 1,379,400 (-1)
pred hlds.quantification.unify_rhs_vars/7-0 <s1;> quantification.m:1233 1,379,400 (-1)
pred tree234.update/4-0 CALL tree234.m:687 1,305,052 (-1)
pred tree234.update/4-0 EXIT tree234.m:687 1,305,052 (-1)
pred check_hlds.simplify.simplify_info_get_simplifications/2-0 CALL simplify.m:2902 1,223,177 (1)
pred check_hlds.simplify.simplify_info_get_simplifications/2-0 EXIT simplify.m:2902 1,223,177 (1)
pred hlds.hlds_goal.goal_info_get_instmap_delta/2-0 CALL hlds_goal.m:1629 1,220,971 (-1)
pred hlds.hlds_goal.goal_info_get_instmap_delta/2-0 EXIT hlds_goal.m:1629 1,220,971 (-1)
pred map.select_2/4-0 CALL map.m:804 1,210,536 (-1)
pred map.select_2/4-0 EXIT map.m:804 1,210,536 (-1)
More information about the developers
mailing list