aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/misc/hipe_sdi.erl
diff options
context:
space:
mode:
authorMagnus Lång <[email protected]>2016-03-18 11:42:31 +0100
committerMagnus Lång <[email protected]>2016-07-11 17:38:18 +0200
commite74636ef2489d436b38726ae19bca2d8e7455cec (patch)
tree288f498a860e692be512004dc58f625473493b68 /lib/hipe/misc/hipe_sdi.erl
parent1bdaee9393a3cf45d7a62fba815c2a73ab637781 (diff)
downloadotp-e74636ef2489d436b38726ae19bca2d8e7455cec.tar.gz
otp-e74636ef2489d436b38726ae19bca2d8e7455cec.tar.bz2
otp-e74636ef2489d436b38726ae19bca2d8e7455cec.zip
hipe_sdi: Use segment trees to represent PARENTS
This speeds up parentsOfChild/2 from O(n) to O(lg n + k). A new module misc/hipe_segment_trees.erl is introduced.
Diffstat (limited to 'lib/hipe/misc/hipe_sdi.erl')
-rw-r--r--lib/hipe/misc/hipe_sdi.erl60
1 files changed, 32 insertions, 28 deletions
diff --git a/lib/hipe/misc/hipe_sdi.erl b/lib/hipe/misc/hipe_sdi.erl
index fbb4b105f6..38a798875c 100644
--- a/lib/hipe/misc/hipe_sdi.erl
+++ b/lib/hipe/misc/hipe_sdi.erl
@@ -36,10 +36,13 @@
%%------------------------------------------------------------------------
-type hipe_array() :: integer(). % declare this in hipe.hrl or builtin?
+-type hipe_vector(E) :: {} | {E} | {E, E} | {E, E, E} | tuple().
-type label() :: non_neg_integer().
-type address() :: non_neg_integer().
+-type parents() :: {hipe_vector(_ :: integer()), hipe_segment_trees:tree()}.
+
%%------------------------------------------------------------------------
-record(label_data, {address :: address(),
@@ -168,9 +171,11 @@ mk_long(N) ->
%%% - Since the graph is traversed from child to parent nodes in
%%% Step 3, the edges are represented by a vector PARENTS[0..n-1]
%%% such that PARENTS[j] = { i | i is a parent of j }.
-%%% - An explicit PARENTS graph would have size O(n^2). Instead we
-%%% compute PARENTS[j] from the SDI vector when needed. This
-%%% reduces memory overheads, and may reduce time overheads too.
+%%% - An explicit PARENTS graph would have size O(n^2). Instead, we
+%%% observe that (i is a parent of j) iff (j \in range(i)), where
+%%% range(i) is a constant function. We can thus precompute all the
+%%% ranges i and insert them into a data structure built for such
+%%% queries. In this case, we use a segment tree.
-spec mk_span(non_neg_integer(), tuple()) -> hipe_array().
mk_span(N, SDIS) ->
@@ -188,7 +193,19 @@ initSPAN(SdiNr, N, SDIS, SPAN) ->
initSPAN(SdiNr+1, N, SDIS, SPAN)
end.
-mk_parents(N, SDIS) -> {N,SDIS}.
+-spec mk_parents(non_neg_integer(), tuple()) -> parents().
+mk_parents(N, SDIS) ->
+ Ranges = parents_generate_ranges(N-1, SDIS, []),
+ hipe_segment_trees:build(Ranges).
+
+parents_generate_ranges(-1, _SDIS, Acc) -> Acc;
+parents_generate_ranges(SdiNr, SDIS, Acc) ->
+ #sdi_data{prevSdi=PrevSdi} = vector_sub(SDIS, SdiNr),
+ {LO,HI} = % inclusive
+ if SdiNr =< PrevSdi -> {SdiNr+1, PrevSdi}; % forwards
+ true -> {PrevSdi+1, SdiNr-1} % backwards
+ end,
+ parents_generate_ranges(SdiNr-1, SDIS, [{LO,HI}|Acc]).
%%% "After the structure is built we process it as follows.
%%% For any node i whose listed span exceeds the architectural
@@ -209,7 +226,7 @@ mk_parents(N, SDIS) -> {N,SDIS}.
%%% and PARENTS are no longer useful.
-spec update_long(non_neg_integer(), tuple(), hipe_array(),
- {non_neg_integer(),tuple()},hipe_array()) -> 'ok'.
+ parents(),hipe_array()) -> 'ok'.
update_long(N, SDIS, SPAN, PARENTS, LONG) ->
WKL = initWKL(N-1, SDIS, SPAN, []),
processWKL(WKL, SDIS, SPAN, PARENTS, LONG).
@@ -225,14 +242,14 @@ initWKL(SdiNr, SDIS, SPAN, WKL) ->
end.
-spec processWKL([non_neg_integer()], tuple(), hipe_array(),
- {non_neg_integer(), tuple()}, hipe_array()) -> 'ok'.
+ parents(), hipe_array()) -> 'ok'.
processWKL([], _SDIS, _SPAN, _PARENTS, _LONG) -> ok;
processWKL([Child|WKL], SDIS, SPAN, PARENTS, LONG) ->
WKL2 = updateChild(Child, WKL, SDIS, SPAN, PARENTS, LONG),
processWKL(WKL2, SDIS, SPAN, PARENTS, LONG).
-spec updateChild(non_neg_integer(), [non_neg_integer()], tuple(), hipe_array(),
- {non_neg_integer(),tuple()}, hipe_array()) -> [non_neg_integer()].
+ parents(), hipe_array()) -> [non_neg_integer()].
updateChild(Child, WKL, SDIS, SPAN, PARENTS, LONG) ->
case array_sub(SPAN, Child) of
0 -> WKL; % removed
@@ -245,26 +262,9 @@ updateChild(Child, WKL, SDIS, SPAN, PARENTS, LONG) ->
updateParents(PS, Child, Incr, SDIS, SPAN, WKL)
end.
--spec parentsOfChild({non_neg_integer(),tuple()},
- non_neg_integer()) -> [non_neg_integer()].
-parentsOfChild({N,SDIS}, Child) ->
- parentsOfChild(N-1, SDIS, Child, []).
-
--spec parentsOfChild(integer(), tuple(), non_neg_integer(),
- [non_neg_integer()]) -> [non_neg_integer()].
-parentsOfChild(-1, _SDIS, _Child, PS) -> PS;
-parentsOfChild(SdiNr, SDIS, Child, PS) ->
- SdiData = vector_sub(SDIS, SdiNr),
- #sdi_data{prevSdi=PrevSdi} = SdiData,
- {LO,HI} = % inclusive
- if SdiNr =< PrevSdi -> {SdiNr+1, PrevSdi}; % forwards
- true -> {PrevSdi+1, SdiNr-1} % backwards
- end,
- NewPS =
- if LO =< Child, Child =< HI -> [SdiNr | PS];
- true -> PS
- end,
- parentsOfChild(SdiNr-1, SDIS, Child, NewPS).
+-spec parentsOfChild(parents(), non_neg_integer()) -> [non_neg_integer()].
+parentsOfChild(IntervalTree, Child) ->
+ hipe_segment_trees:intersect(Child, IntervalTree).
-spec updateParents([non_neg_integer()], non_neg_integer(),
byte(), tuple(), hipe_array(),
@@ -361,9 +361,11 @@ applyIncr([{Label,LabelData}|List], INCREMENT, LabelMap) ->
%%% Currently implemented as tuples.
%%% Used for the 'SDIS' and 'PARENTS' vectors.
--spec vector_from_list([#sdi_data{}]) -> tuple().
+-spec vector_from_list([E]) -> hipe_vector(E).
vector_from_list(Values) -> list_to_tuple(Values).
+-compile({inline, vector_sub/2}).
+-spec vector_sub(hipe_vector(E), non_neg_integer()) -> V when V :: E.
vector_sub(Vec, I) -> element(I+1, Vec).
%%% ADT for mutable integer arrays, indexed from 0 to N-1.
@@ -373,8 +375,10 @@ vector_sub(Vec, I) -> element(I+1, Vec).
-spec mk_array_of_zeros(non_neg_integer()) -> hipe_array().
mk_array_of_zeros(N) -> hipe_bifs:array(N, 0).
+-compile({inline, array_update/3}).
-spec array_update(hipe_array(), non_neg_integer(), integer()) -> hipe_array().
array_update(A, I, V) -> hipe_bifs:array_update(A, I, V).
+-compile({inline, array_sub/2}).
-spec array_sub(hipe_array(), non_neg_integer()) -> integer().
array_sub(A, I) -> hipe_bifs:array_sub(A, I).