hipe: segment tree delete operation

Profiling showed that hipe_sdi spent most of its time in updateParents,
discarding nodes that were already deleted. By introducing a delete
operation to the segment trees, we can pay this cost only once, when
deleting the node from the graph.

Instead of keeping the ranges around, we recompute the range of the node
when we delete it, since this can be done in constant time, without any
memory allocation.

Although segment trees are not designed to be modified once built,
implementing a delete operation turned out to be a simple matter of
repeating insertion, but deleting the index from, instead of consing it
on, the appropriate nodes' values (segment lists).

This optimisation drastically sped up hipe_sdi to the point of no longer
being the bottleneck in the Assembly stage.

2 files changed, 82 insertions, 36 deletions

diff --git a/lib/hipe/misc/hipe_sdi.erl b/lib/hipe/misc/hipe_sdi.erl
index 38a798875c..5ca64bc669 100644
--- a/lib/hipe/misc/hipe_sdi.erl
+++ b/lib/hipe/misc/hipe_sdi.erl
@@ -195,17 +195,27 @@ initSPAN(SdiNr, N, SDIS, SPAN) ->
 
 -spec mk_parents(non_neg_integer(), tuple()) -> parents().
 mk_parents(N, SDIS) ->
-  Ranges = parents_generate_ranges(N-1, SDIS, []),
-  hipe_segment_trees:build(Ranges).
+  PrevSDIS = vector_from_list(select_prev_sdis(N-1, SDIS, [])),
+  Ranges = parents_generate_ranges(N-1, PrevSDIS, []),
+  {PrevSDIS, hipe_segment_trees:build(Ranges)}.
 
-parents_generate_ranges(-1, _SDIS, Acc) -> Acc;
-parents_generate_ranges(SdiNr, SDIS, Acc) ->
+select_prev_sdis(-1, _SDIS, Acc) -> Acc;
+select_prev_sdis(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]).
+  select_prev_sdis(SdiNr-1, SDIS, [PrevSdi|Acc]).
+
+parents_generate_ranges(-1, _PrevSDIS, Acc) -> Acc;
+parents_generate_ranges(SdiNr, PrevSDIS, Acc) ->
+  %% inclusive
+  {LO,HI} = parents_generate_range(SdiNr, PrevSDIS),
+  parents_generate_ranges(SdiNr-1, PrevSDIS, [{LO,HI}|Acc]).
+
+-compile({inline, parents_generate_range/2}).
+parents_generate_range(SdiNr, PrevSDIS) ->
+  PrevSdi = vector_sub(PrevSDIS, SdiNr),
+  if SdiNr =< PrevSdi -> {SdiNr+1, PrevSdi};	% forwards
+     true -> {PrevSdi+1, SdiNr-1}		% backwards
+  end.
 
 %%% "After the structure is built we process it as follows.
 %%% For any node i whose listed span exceeds the architectural
@@ -244,27 +254,30 @@ initWKL(SdiNr, SDIS, SPAN, WKL) ->
 -spec processWKL([non_neg_integer()], tuple(), hipe_array(),
 		 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([Child|WKL], SDIS, SPAN, PARENTS0, LONG) ->
+  {WKL2, PARENTS} =
+    case array_sub(SPAN, Child) of
+      0 -> {WKL, PARENTS0};				% removed
+      _ ->
+	SdiData = vector_sub(SDIS, Child),
+	Incr = sdiLongIncr(SdiData),
+	array_update(LONG, Child, Incr),
+	array_update(SPAN, Child, 0),			% remove child
+	PARENTS1 = deleteParent(PARENTS0, Child),
+	PS = parentsOfChild(PARENTS1, Child),
+	{updateParents(PS, Child, Incr, SDIS, SPAN, WKL), PARENTS1}
+    end,
   processWKL(WKL2, SDIS, SPAN, PARENTS, LONG).
 
--spec updateChild(non_neg_integer(), [non_neg_integer()], tuple(), hipe_array(),
-		  parents(), hipe_array()) -> [non_neg_integer()].
-updateChild(Child, WKL, SDIS, SPAN, PARENTS, LONG) ->
-  case array_sub(SPAN, Child) of
-    0 -> WKL;						% removed
-    _ ->
-      SdiData = vector_sub(SDIS, Child),
-      Incr = sdiLongIncr(SdiData),
-      array_update(LONG, Child, Incr),
-      array_update(SPAN, Child, 0),			% remove child
-      PS = parentsOfChild(PARENTS, Child),
-      updateParents(PS, Child, Incr, SDIS, SPAN, WKL)
-  end.
-
 -spec parentsOfChild(parents(), non_neg_integer()) -> [non_neg_integer()].
-parentsOfChild(IntervalTree, Child) ->
-  hipe_segment_trees:intersect(Child, IntervalTree).
+parentsOfChild({_PrevSDIS, SegTree}, Child) ->
+  hipe_segment_trees:intersect(Child, SegTree).
+
+-spec deleteParent(parents(), non_neg_integer()) -> parents().
+deleteParent({PrevSDIS, SegTree0}, Parent) ->
+  {LO,HI} = parents_generate_range(Parent, PrevSDIS),
+  SegTree = hipe_segment_trees:delete(Parent, LO, HI, SegTree0),
+  {PrevSDIS, SegTree}.
 
 -spec updateParents([non_neg_integer()], non_neg_integer(),
 		    byte(), tuple(), hipe_array(),
@@ -297,10 +310,12 @@ updateWKL(SdiNr, SDIS, SdiSpan, WKL) ->
     false -> [SdiNr|WKL]
   end.
 
+-compile({inline, sdiSpanIsShort/2}). %% Only called once
 -spec sdiSpanIsShort(#sdi_data{}, integer()) -> boolean().
 sdiSpanIsShort(#sdi_data{si = #sdi_info{lb = LB, ub = UB}}, SdiSpan) ->
   SdiSpan >= LB andalso SdiSpan =< UB.
 
+-compile({inline, sdiLongIncr/1}). %% Only called once
 -spec sdiLongIncr(#sdi_data{}) -> byte().
 sdiLongIncr(#sdi_data{si = #sdi_info{incr = Incr}}) -> Incr.
 
diff --git a/lib/hipe/misc/hipe_segment_trees.erl b/lib/hipe/misc/hipe_segment_trees.erl
index cbee328125..22146396c3 100644
--- a/lib/hipe/misc/hipe_segment_trees.erl
+++ b/lib/hipe/misc/hipe_segment_trees.erl
@@ -17,19 +17,16 @@
 %%%
 %%% %CopyrightEnd%
 %%%
-%%% Segment trees.
+%%% Segment trees, with a delete operation.
 %%%
 %%% Keys are the (0-based) indices into the list passed to build/1.
 %%%
 %%% Range bounds are inclusive.
 %%%
-%%% TODO: Change the shape of the tree to a perfect binary tree, and pack it as
-%%% an implicit data structure into tuples (like a binary heap would be) for
-%%% improved efficiency.
 
 -module(hipe_segment_trees).
 
--export([build/1, intersect/2]).
+-export([build/1, intersect/2, delete/4]).
 
 -record(segment_tree, {
 	  lo            :: integer(),
@@ -75,9 +72,7 @@ empty_tree_from_endpoints(Endpoints) ->
 
 leaves([Endpoint]) -> [?POINT_LEAF(Endpoint)];
 leaves([A | [B|_] = Tail]) ->
-    %% We could omit the range leaf if it's empty, but we want to pack this data
-    %% structure into an array (tuple) eventually, and then we *really* want
-    %% every other leaf to be a range
+    %% We omit the range leaf if it's empty
     case A<B-1 of
 	true  -> [?POINT_LEAF(A),?RANGE_LEAF(A+1,B-1) | leaves(Tail)];
 	false -> [?POINT_LEAF(A) | leaves(Tail)]
@@ -121,7 +116,7 @@ insert_interval(I, {_Lo,_Hi}, _NLo, _NHi, Leaf) -> [I|Leaf].
 
 intervals_intersect(ALo, AHi, BLo, BHi) ->
     (ALo =< AHi) andalso (BLo =< BHi) %% both nonempty
-	andalso (BLo =< AHi) andalso (ALo =< BHi).
+	andalso nonempty_intervals_intersect(ALo, AHi, BLo, BHi).
 
 %% Purely optional optimisation
 squash_empty_subtrees(?NODE(Left0, Right0, Mid, Segs)) ->
@@ -148,3 +143,39 @@ intersect_1(Point, ?NODE(Left, Right, Mid, Segs), Acc0) ->
     Child = if Point =< Mid -> Left; true -> Right end,
     intersect_1(Point, Child, Segs ++ Acc0);
 intersect_1(_, LeafSegs, Acc) -> LeafSegs ++ Acc.
+
+%% @doc Deletes the interval {Lo, Hi}, which had index Index in the list passed
+%%      to build/1.
+-spec delete(non_neg_integer(), integer(), integer(), tree()) -> tree().
+delete(_, _, _, nil) -> nil;
+delete(_, Lo, Hi, Tree) when Lo > Hi -> Tree;
+delete(_, Lo, Hi, Tree = #segment_tree{lo=TLo, hi=THi})
+  when Hi < TLo; Lo > THi -> Tree;
+delete(Index, Lo, Hi, Tree = #segment_tree{lo=TLo, hi=THi, root=Root0})
+  when is_integer(Lo), is_integer(Hi) ->
+    Root = delete_1(Index, Lo, Hi, TLo, THi, Root0),
+    Tree#segment_tree{root=Root}.
+
+delete_1(I, Lo, Hi, NLo, NHi, ?NODE(Left0, Right0, Mid, Segments)) ->
+    if Lo =< NLo, NHi =< Hi ->
+	    ?NODE(Left0, Right0, Mid, delete_2(Segments, I));
+       true ->
+	    Left = case nonempty_intervals_intersect(Lo, Hi, NLo, Mid) of
+		       true -> delete_1(I, Lo, Hi, NLo, Mid, Left0);
+		       false -> Left0
+		   end,
+	    Right = case nonempty_intervals_intersect(Lo, Hi, Mid+1, NHi) of
+			true -> delete_1(I, Lo, Hi, Mid+1, NHi, Right0);
+			false -> Right0
+		   end,
+	    %% We could do build_squash_node here, is it worth it?
+	    ?NODE(Left, Right, Mid, Segments)
+    end;
+delete_1(I, _Lo, _Hi, _NLo, _NHi, Leaf) -> delete_2(Leaf, I).
+
+delete_2([I|Segs], I) -> Segs;
+delete_2([S|Segs], I) -> [S|delete_2(Segs,I)].
+
+-compile({inline,nonempty_intervals_intersect/4}).
+nonempty_intervals_intersect(ALo, AHi, BLo, BHi) ->
+    (BLo =< AHi) andalso (ALo =< BHi).