# [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,
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).

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)
```