[m-rev.] for review: speedup up tree_bitset.difference
Peter Wang
novalazy at gmail.com
Mon Aug 8 11:30:27 AEST 2011
On 2011-08-05, Zoltan Somogyi <zs at csse.unimelb.edu.au> wrote:
> library/tree_bitset.m:
> Speed up tree_bitset.difference by tailoring its actions to the forms
> of the input operands, instead of its previous approach of transforming
> every operand into the same general form.
>
> Zoltan.
>
Let's see if I can follow...
> Index: library/tree_bitset.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/library/tree_bitset.m,v
> retrieving revision 1.14
> diff -u -b -r1.14 tree_bitset.m
> --- library/tree_bitset.m 4 Aug 2011 02:01:36 -0000 1.14
> +++ library/tree_bitset.m 5 Aug 2011 02:27:07 -0000
> @@ -2120,13 +2120,13 @@
> LeafNodesA = [],
> List = ListA
> ;
> - LeafNodesA = [FirstNodeA | LaterNodesA],
> - raise_leaves_to_level(LevelB, FirstNodeA, LaterNodesA,
> - InteriorNodeA),
> - head_and_tail(InteriorNodesB, InteriorHeadB, InteriorTailB),
> - interiornode_difference(LevelB, InteriorNodeA, [],
> - LevelB, InteriorHeadB, InteriorTailB, Level, InteriorNodes),
> - List = interior_list(Level, InteriorNodes)
> + LeafNodesA = [FirstNodeA | _LaterNodesA],
> + range_of_parent_node(FirstNodeA ^ leaf_offset, 0,
> + ParentInitOffsetA, ParentLimitOffsetA),
> + find_leaf_nodes_at_parent_offset(LevelB, InteriorNodesB,
> + ParentInitOffsetA, ParentLimitOffsetA, LeafNodesB),
> + leaflist_difference(LeafNodesA, LeafNodesB, LeafNodes),
> + List = leaf_list(LeafNodes)
> )
> ;
> ListA = interior_list(LevelA, InteriorNodesA),
Ok.
> @@ -2136,31 +2136,340 @@
> List = ListA
> ;
> LeafNodesB = [FirstNodeB | LaterNodesB],
> - raise_leaves_to_level(LevelA, FirstNodeB, LaterNodesB,
> - InteriorNodeB),
> - head_and_tail(InteriorNodesA, InteriorHeadA, InteriorTailA),
> - interiornode_difference(LevelA, InteriorHeadA, InteriorTailA,
> - LevelA, InteriorNodeB, [], Level, InteriorNodes),
> + raise_leaves_to_interior(FirstNodeB, LaterNodesB, InteriorNodeB),
> + descend_and_difference_one(LevelA, InteriorNodesA,
> + 1, InteriorNodeB, Level, InteriorNodes),
> List = interior_list(Level, InteriorNodes)
> )
Ok.
> ;
> ListA = interior_list(LevelA, InteriorNodesA),
> ListB = interior_list(LevelB, InteriorNodesB),
> + ( LevelA > LevelB ->
> + head_and_tail(InteriorNodesB, InteriorHeadB, InteriorTailB),
> + descend_and_difference_list(LevelA, InteriorNodesA,
> + LevelB, InteriorHeadB, InteriorTailB, Level, InteriorNodes),
> + List = interior_list(Level, InteriorNodes)
Ok.
> + ; LevelA = LevelB ->
> head_and_tail(InteriorNodesA, InteriorHeadA, InteriorTailA),
> head_and_tail(InteriorNodesB, InteriorHeadB, InteriorTailB),
> -
> - int.max(LevelA, LevelB, LevelAB),
> - raise_interiors_to_level(LevelAB, LevelA, InteriorHeadA, InteriorTailA,
> - RaisedHeadA, RaisedTailA),
> - raise_interiors_to_level(LevelAB, LevelB, InteriorHeadB, InteriorTailB,
> - RaisedHeadB, RaisedTailB),
> - interiornode_difference(LevelAB, RaisedHeadA, RaisedTailA,
> - LevelAB, RaisedHeadB, RaisedTailB, Level, InteriorNodes),
> + interiornode_difference(LevelA, InteriorHeadA, InteriorTailA,
> + LevelB, InteriorHeadB, InteriorTailB, Level, InteriorNodes),
> + List = interior_list(Level, InteriorNodes)
Ok.
> + ;
> + % LevelA < LevelB
> + head_and_tail(InteriorNodesA, InteriorHeadA, InteriorTailA),
> + range_of_parent_node(InteriorHeadA ^ init_offset, LevelA,
> + ParentInitOffsetA, ParentLimitOffsetA),
> + find_interior_nodes_at_parent_offset(LevelB, InteriorNodesB,
> + LevelA+1, ParentInitOffsetA, ParentLimitOffsetA,
> + SelectedNodesB),
Maybe name ParentLevelA = LevelA + 1 explicitly.
> + (
> + SelectedNodesB = [],
> + List = ListA
> + ;
> + SelectedNodesB = [SelectedHeadB | SelectedTailB],
> + interiornode_difference(LevelA, InteriorHeadA, InteriorTailA,
> + LevelA, SelectedHeadB, SelectedTailB,
> + Level, InteriorNodes),
Does LevelA go with SelectedNodesB here? If so, please add a comment
explaining why.
> List = interior_list(Level, InteriorNodes)
> + )
> + )
> ),
> prune_top_levels(List, PrunedList),
> Set = wrap_tree_bitset(PrunedList).
>
> +:- pred find_leaf_nodes_at_parent_offset(int::in, list(interior_node)::in,
> + int::in, int::in, list(leaf_node)::out) is det.
> +
> +find_leaf_nodes_at_parent_offset(_LevelB, [],
> + _ParentInitOffsetA, _ParentLimitOffsetA, []).
> +find_leaf_nodes_at_parent_offset(LevelB, [HeadB | TailB],
> + ParentInitOffsetA, ParentLimitOffsetA, LeafNodesB) :-
> + ( HeadB ^ init_offset > ParentInitOffsetA ->
> + % The leaf nodes in ListA cover at most one level 1 interior's node
> + % span of bits. HeadB ^ init_offset should be a multiple of (a power
> + % of) that span, so if it is greater than the initial offset of a
> + % hypothetical level 1 interior node covering ListA's leaf nodes,
> + % then it should be greater the final offset of that hypothetical
> + % node as well. The limit offset is one bigger than the final offset.
I found that comment hard to parse. How about:
The leaf nodes in ListA cover at most one level 1 interior node's
span of bits. Call that the hypothetical level 1 interior node.
HeadB ^ init_offset should be a multiple of (a power of) that span,
so if it is greater than the initial offset of that hypothetical
node, then it should be greater than the final offset of that
hypothetical node as well. The limit offset is one bigger than the
final offset.
Otherwise, there were a couple of errors:
interior's node -> interior node's
greater the -> greater than the
> + trace [compile_time(flag("tree-bitset-checks"))] (
> + ( HeadB ^ init_offset >= ParentLimitOffsetA ->
> + true
> + ;
> + unexpected($module, $pred, "screwed-up offsets")
> + )
> + ),
> + LeafNodesB = []
Ok.
> + ; ParentInitOffsetA < HeadB ^ limit_offset ->
> + % ListA's range is inside HeadB's range.
> + HeadNodeListB = HeadB ^ components,
> + (
> + HeadNodeListB = leaf_list(HeadLeafNodesB),
> + trace [compile_time(flag("tree-bitset-checks"))] (
> + expect(unify(LevelB, 1), $module, $pred, "LevelB != 1")
> + ),
> + LeafNodesB = HeadLeafNodesB
> + ;
> + HeadNodeListB = interior_list(HeadSubLevelB, HeadInteriorNodesB),
> + trace [compile_time(flag("tree-bitset-checks"))] (
> + expect_not(unify(LevelB, 1), $module, $pred, "LevelB = 1"),
> + expect(unify(HeadSubLevelB, LevelB - 1),
> + $module, $pred, "HeadSubLevelB != LevelB - 1")
> + ),
> + find_leaf_nodes_at_parent_offset(HeadSubLevelB, HeadInteriorNodesB,
> + ParentInitOffsetA, ParentLimitOffsetA, LeafNodesB)
> + )
> + ;
> + find_leaf_nodes_at_parent_offset(LevelB, TailB,
> + ParentInitOffsetA, ParentLimitOffsetA, LeafNodesB)
> + ).
Ok.
> +:- pred find_interior_nodes_at_parent_offset(int::in, list(interior_node)::in,
> + int::in, int::in, int::in, list(interior_node)::out) is det.
> +
> +find_interior_nodes_at_parent_offset(_LevelB, [],
> + _ParentLevelA, _ParentInitOffsetA, _ParentLimitOffsetA, []).
> +find_interior_nodes_at_parent_offset(LevelB, [HeadB | TailB],
> + ParentLevelA, ParentInitOffsetA, ParentLimitOffsetA, NodesB) :-
> + ( LevelB > ParentLevelA ->
> + ( HeadB ^ init_offset > ParentInitOffsetA ->
> + % ListA's range is before HeadB's range.
> + % The nodes in ListA cover at most one level ParentLevelA span
> + % of bits. HeadB ^ init_offset should be a multiple of (a power of)
> + % that span, so if it is greater than the initial offset of a
> + % hypothetical level ParentLevelA interior node covering ListA's
> + % interior nodes, then it should be greater the final offset
> + % of that hypothetical node as well. The limit offset is one bigger
> + % than the final offset.
As for find_leaf_nodes_at_parent_offset.
> + trace [compile_time(flag("tree-bitset-checks"))] (
> + ( HeadB ^ init_offset >= ParentLimitOffsetA ->
> + true
> + ;
> + unexpected($module, $pred, "screwed-up offsets")
> + )
> + ),
> + NodesB = []
> + ; ParentInitOffsetA < HeadB ^ limit_offset ->
> + % ListA's range is inside HeadB's range.
> + HeadNodeListB = HeadB ^ components,
> + (
> + HeadNodeListB = leaf_list(_),
> + unexpected($module, $pred, "HeadNodeListB is a leaf list")
> + ;
> + HeadNodeListB = interior_list(HeadSubLevelB,
> + HeadInteriorNodesB),
> + trace [compile_time(flag("tree-bitset-checks"))] (
> + expect_not(unify(LevelB, 1), $module, $pred, "LevelB = 1"),
> + expect(unify(HeadSubLevelB, LevelB - 1),
> + $module, $pred, "HeadSubLevelB != LevelB - 1")
> + ),
> + find_interior_nodes_at_parent_offset(HeadSubLevelB,
> + HeadInteriorNodesB,
> + ParentLevelA, ParentInitOffsetA, ParentLimitOffsetA, NodesB)
> + )
> + ;
> + % ListA's range is after HeadB's range.
> + find_interior_nodes_at_parent_offset(LevelB, TailB,
> + ParentLevelA, ParentInitOffsetA, ParentLimitOffsetA, NodesB)
> + )
> + ;
> + trace [compile_time(flag("tree-bitset-checks"))] (
> + expect(unify(ParentLevelA, LevelB), $module, $pred,
> + "ParentLevelA != LevelB")
> + ),
> + ( HeadB ^ init_offset > ParentInitOffsetA ->
> + % ListA's range is before HeadB's range.
> + % The nodes in ListA cover at most one level ParentLevelA span
> + % of bits. HeadB ^ init_offset should be a multiple of (a power of)
> + % that span, so if it is greater than the initial offset of a
> + % hypothetical level ParentLevelA interior node covering ListA's
> + % interior nodes, then it should be greater the final offset
> + % of that hypothetical node as well. The limit offset is one bigger
> + % than the final offset.
As previously.
> + trace [compile_time(flag("tree-bitset-checks"))] (
> + ( HeadB ^ init_offset >= ParentLimitOffsetA ->
> + true
> + ;
> + unexpected($module, $pred, "screwed-up offsets")
> + )
> + ),
> + NodesB = []
> + ; HeadB ^ init_offset = ParentInitOffsetA ->
> +% NodesB = [HeadB]
Stray line.
> + ComponentsB = HeadB ^ components,
> + (
> + ComponentsB = leaf_list(_),
> + unexpected($module, $pred, "leaf_list")
> + ;
> + ComponentsB = interior_list(_, NodesB)
> + )
> + ;
> + find_interior_nodes_at_parent_offset(LevelB, TailB,
> + ParentLevelA, ParentInitOffsetA, ParentLimitOffsetA, NodesB)
> + )
> + ).
> +
> +:- pred descend_and_difference_one(int::in, list(interior_node)::in,
> + int::in, interior_node::in, int::out, list(interior_node)::out) is det.
> +
> +descend_and_difference_one(LevelA, InteriorNodesA, LevelB, InteriorNodeB,
> + Level, List) :-
> + ( LevelA > LevelB ->
> + (
> + InteriorNodesA = [],
> + Level = LevelA,
> + List = []
> + ;
> + InteriorNodesA = [HeadA | TailA],
> + ( HeadA ^ limit_offset =< InteriorNodeB ^ init_offset ->
> + % All of the region covered by HeadA is before the region
> + % covered by InteriorNodeB.
> + descend_and_difference_one(LevelA, TailA, LevelB, InteriorNodeB,
> + LevelTail, ListTail),
> + trace [compile_time(flag("tree-bitset-checks"))] (
> + expect(unify(LevelTail, LevelA),
> + $module, $pred, "LevelTail != LevelA")
> + ),
> + Level = LevelA,
> + List = [HeadA | ListTail]
Ok.
> + ; HeadA ^ init_offset =< InteriorNodeB ^ init_offset ->
> + % The region covered by HeadA contains the region
> + % covered by InteriorNodeB.
> + trace [compile_time(flag("tree-bitset-checks"))] (
> + ( InteriorNodeB ^ limit_offset =< HeadA ^ limit_offset ->
> + true
> + ;
> + unexpected($module, $pred, "weird region relationship")
> + )
> + ),
> + (
> + HeadA ^ components = leaf_list(_),
> + % LevelB is at least 1, LevelA is greater than LevelB,
> + % so stepping one level down from levelA should get us
> + % to at least level 1; level 0 cannot happen.
> + unexpected($module, $pred,
> + "HeadA ^ components is leaf_list")
> + ;
> + HeadA ^ components = interior_list(HeadASubLevel,
> + HeadASubNodes)
> + ),
> + descend_and_difference_one(HeadASubLevel, HeadASubNodes,
> + LevelB, InteriorNodeB, LevelSub, ListSub),
> + (
> + ListSub = [],
> + Level = LevelA,
> + List = TailA
> + ;
> + ListSub = [ListSubHead | ListSubTail],
> + raise_interiors_to_level(LevelA, LevelSub,
> + ListSubHead, ListSubTail, RaisedHead, RaisedTail),
> + trace [compile_time(flag("tree-bitset-checks"))] (
> + expect(unify(RaisedTail, []),
> + $module, $pred, "RaisedTail != []")
> + ),
> + Level = LevelA,
> + List = [RaisedHead | TailA]
> + )
Maybe add a version of raise_interiors_to_level, so the reader does not
wonder about the assertion on RaisedTail.
> + ;
> + % All of the region covered by HeadA is after the region
> + % covered by InteriorNodeB, and therefore so are all the
> + % regions covered by TailA.
> + Level = LevelA,
> + List = InteriorNodesA
> + )
> + )
> + ; LevelA = LevelB ->
> + interiorlist_difference(InteriorNodesA, [InteriorNodeB], List),
> + Level = LevelA
> + ;
> + unexpected($module, $pred, "LevelA < LevelB")
> + ).
Ok.
> +:- pred descend_and_difference_list(int::in, list(interior_node)::in,
> + int::in, interior_node::in, list(interior_node)::in,
> + int::out, list(interior_node)::out) is det.
> +
> +descend_and_difference_list(LevelA, InteriorNodesA,
> + LevelB, InteriorNodeB, InteriorNodesB, Level, List) :-
> + ( LevelA > LevelB ->
> + (
> + InteriorNodesA = [],
> + Level = LevelA,
> + List = []
Ok.
> + ;
> + InteriorNodesA = [HeadA | TailA],
> + ( HeadA ^ limit_offset =< InteriorNodeB ^ init_offset ->
> + % All of the region covered by HeadA is before the region
> + % covered by [InteriorNodeB | InteriorNodesB].
> + trace [compile_time(flag("tree-bitset-checks"))] (
> + list.det_last([InteriorNodeB | InteriorNodesB], LastB),
> + expect((HeadA ^ limit_offset =< LastB ^ init_offset),
> + $module, $pred,
> + "HeadA ^ limit_offset > LastB ^ init_offset")
> + ),
> + descend_and_difference_list(LevelA, TailA,
> + LevelB, InteriorNodeB, InteriorNodesB,
> + LevelTail, ListTail),
> + trace [compile_time(flag("tree-bitset-checks"))] (
> + expect(unify(LevelTail, LevelA),
> + $module, $pred, "LevelTail != LevelA")
> + ),
> + Level = LevelA,
> + List = [HeadA | ListTail]
Ok.
> + ; HeadA ^ init_offset =< InteriorNodeB ^ init_offset ->
> + % The region covered by HeadA contains the region
> + % covered by InteriorNodeB.
> + trace [compile_time(flag("tree-bitset-checks"))] (
> + ( InteriorNodeB ^ limit_offset =< HeadA ^ limit_offset ->
> + true
> + ;
> + unexpected($module, $pred, "weird region relationship")
> + )
> + ),
> + (
> + HeadA ^ components = leaf_list(_),
> + % LevelB is at least 1, LevelA is greater than LevelB,
> + % so stepping one level down from levelA should get us
> + % to at least level 1; level 0 cannot happen.
> + unexpected($module, $pred,
> + "HeadA ^ components is leaf_list")
> + ;
> + HeadA ^ components = interior_list(HeadASubLevel,
> + HeadASubNodes)
> + ),
> + descend_and_difference_list(HeadASubLevel, HeadASubNodes,
> + LevelB, InteriorNodeB, InteriorNodesB, LevelSub, ListSub),
> + (
> + ListSub = [],
> + Level = LevelA,
> + List = TailA
> + ;
> + ListSub = [ListSubHead | ListSubTail],
> + raise_interiors_to_level(LevelA, LevelSub,
> + ListSubHead, ListSubTail, RaisedHead, RaisedTail),
> + trace [compile_time(flag("tree-bitset-checks"))] (
> + expect(unify(RaisedTail, []),
> + $module, $pred, "RaisedTail != []")
> + ),
> + Level = LevelA,
> + List = [RaisedHead | TailA]
> + )
As for descend_and_difference_one.
> + ;
> + % All of the region covered by HeadA is after the region
> + % covered by InteriorNodeB, and therefore so are all the
> + % regions covered by TailA.
> + Level = LevelA,
> + List = InteriorNodesA
> + )
> + )
Ok.
> + ; LevelA = LevelB ->
> + interiorlist_difference(InteriorNodesA,
> + [InteriorNodeB | InteriorNodesB], List),
> + Level = LevelA
> + ;
> + unexpected($module, $pred, "LevelA < LevelB")
> + ).
Ok.
Peter
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------
More information about the reviews
mailing list