addMarker() optimizations.

Source/core/dom/DocumentMarkerController.cpp

Index: Source/core/dom/DocumentMarkerController.cpp
diff --git a/Source/core/dom/DocumentMarkerController.cpp b/Source/core/dom/DocumentMarkerController.cpp
index 0682b64d971844063c2305a976fcfb79acb7c53b..659d292b96107417202500ef698b2b0ba5d54cab 100644
--- a/Source/core/dom/DocumentMarkerController.cpp
+++ b/Source/core/dom/DocumentMarkerController.cpp
@@ -133,6 +133,16 @@ void DocumentMarkerController::removeMarkers(Range* range, DocumentMarker::Marke
     }
 }
 
+static bool startsFurther(const DocumentMarker& lhv, const DocumentMarker& rhv)

[groby-ooo-7-16, 2013/09/13 18:05:48]

Chromium preference is putting helper functions into an anonymous namespace
instead of declaring them static - but I'll defer final judgment to the Blink
reviewer. morrita1? tony?

[tony, 2013/09/13 18:18:49]

Most blink code uses static functions, but I don't think there's a rule one way
or another.  I don't have a strong preference.

+{
+    return lhv.startOffset() < rhv.startOffset();
+}
+
+static bool doesNotOverlap(const DocumentMarker& lhv, const DocumentMarker& rhv)

[groby-ooo-7-16, 2013/09/17 11:52:42]

I just woke up at 4am to realize this does not work :) doesNotOverlap assumes
the list is sorted by start _and_ end offset, but it's only sorted by start
offset. 

If the list only contained one marker type, the merging would assure we could
compare end & start offsets - but with multiple types we cannot.

[pstanek, 2013/09/17 12:46:30]

I thought about the same but I convinced myself it's ok as far as do-while
checks the type (which it does) but I might be wrong.

[groby-ooo-7-16, 2013/09/17 14:20:26]

Do-while is fine - but in line 194, you use doesNotOverlap for lower_bound. 

I fear that we'll need some sort of linear search after all. Maybe lower_bound
for a starting point, then scan to the left for merge candidates if it's a type
mismatch.


 

On 2013/09/17 12:46:30, pstanek wrote:

[pstanek, 2013/09/17 14:48:05]

But with lower_bound() we find the first overlapping marker regardless its type,
but if its type is different then the one's to insert we get back to searching
from the next position. If the container contained one type only do while
wouldn't be needed.

On 2013/09/17 14:20:26, groby wrote:

[groby-ooo-7-16, 2013/09/17 17:14:09]

Yes, but the vector is unsorted with respect to endOffset, so lower_bound will
return bad results. Example (marker types are X/O, then start offset, then end
offset)

existing:
X, 2, 8
O, 3, 4
X, 12, 20

Now try to insert (X, 7, 10)

Clearly, it _should_ start with overlapping = 0. Instead, it starts with
overlapping =2, never merging (X, 2, 8) with the new marker.

And by clearly, I mean I had to write a sample to convince myself I wasn't crazy
:) See  http://pastebin.com/eBqYj2hq

Change the end offset on the 'O' marker to 10, it's still a well-ordered list,
and now overlapping == 0




On 2013/09/17 14:48:05, pstanek wrote:

[pstanek, 2013/09/17 17:30:41]

Ah :/

On 2013/09/17 17:14:09, groby wrote:

[pstanek, 2013/09/17 17:39:45]

Then to make this efficient markers would have to be kept separated by type.
Otherwise there is no good starting point as all starting earlier has to be
checked unless I'm missing something.

On 2013/09/17 17:30:41, pstanek wrote:

[groby-ooo-7-16, 2013/09/17 18:39:37]

Separating them by type would certainly be helpful :)

If you don't want to do that - there are other functions that might rely on
mixed markers - there might be another way. (Or skip it, if the 10% improvement
isn't worth it)

Let me check the assumptions:

- We are guaranteed that we can insert before the first node that has
node.start() >= toInsert.start), since nodes are ordered by start.
- We are guaranteed that we're at most merging one node "to the left", since all
nodes are already merged. At most one node can start earlier than the insertion
node. (That part is a linear scan, though )
- We are guaranteed that we can stop merging once node.start() > insert.end(),
since nodes are ordered by start *and* insert.start() must be <= insert.end().

That seems to translate into basically your structure, except we can't use
lower_bound to find the overlapping one, and we use lower_bound for finding the
start of the overlapping search.

Alternatively, you can go for a single while loop by finding the end-node
(node.start() > insert.end()) and merging to the left.

Does that make sense? Or are there holes in this?

On 2013/09/17 17:39:45, pstanek wrote:

[pstanek, 2013/09/18 10:49:46]

Yes. The assumptions seem to be right but I fear using the linear search is a
step back to the starting point performance wise. I'll take a look at separating
markers how much work would that be. Note however that since the perceived
performance is OK atm this gets a lot lower priority for me now.

On 2013/09/17 18:39:37, groby wrote:

[groby-ooo-7-16, 2013/09/18 18:24:08]

Postponing this seems fine to me. (If you do, you might want to close this CL
and update the bug to reflect that status)

On 2013/09/18 10:49:46, pstanek wrote:

+{
+    return lhv.endOffset() < rhv.startOffset();
+}
+
 // Markers are stored in order sorted by their start offset.
 // Markers of the same type do not overlap each other.
 
@@ -151,42 +161,19 @@ void DocumentMarkerController::addMarker(Node* node, const DocumentMarker& newMa
         list->append(RenderedDocumentMarker(newMarker));
     } else {
         RenderedDocumentMarker toInsert(newMarker);
-        size_t numMarkers = list->size();
-        size_t i;
-        // Iterate over all markers whose start offset is less than or equal to the new marker's.
-        // If one of them is of the same type as the new marker and touches it or intersects with it
-        // (there is at most one), remove it and adjust the new marker's start offset to encompass it.
-        for (i = 0; i < numMarkers; ++i) {
-            DocumentMarker marker = list->at(i);
-            if (marker.startOffset() > toInsert.startOffset())
-                break;
-            if (marker.type() == toInsert.type() && marker.type() != DocumentMarker::TextMatch && marker.endOffset() >= toInsert.startOffset()) {
-                toInsert.setStartOffset(marker.startOffset());
-                list->remove(i);
-                numMarkers--;
-                break;
+        if (list->last().endOffset() >= newMarker.startOffset()) {

[groby-ooo-7-16, 2013/09/13 18:05:48]

Isn't that covered by lower_bound already?

[pstanek, 2013/09/14 08:18:50]

Yes, but the point was to avoid searching if no merging is needed.

[groby-ooo-7-16, 2013/09/17 02:23:47]

You probably want '>', though. if last.end == new.start, we probably want to
merge the two?

Definitely should be '>', though - if last.end == new.start, we probably want to
merge them :)
On 2013/09/14 08:18:50, pstanek wrote:

[pstanek, 2013/09/17 13:54:00]

But this if controls entering merging block so we'll merge if last().endOffset
>= toInsert.startOffset()

[groby-ooo-7-16, 2013/09/17 14:34:41]

Sigh. I misread that, sorry.

Done.
On 2013/09/17 13:54:00, pstanek wrote:

+            if (toInsert.type() != DocumentMarker::TextMatch) {
+                mergeOverlapping(list.get(), toInsert);
+            } else {
+                MarkerList::iterator pos = std::lower_bound(list->begin(), list->end(), toInsert, startsFurther);
+                if (pos != list->end())

[groby-ooo-7-16, 2013/09/13 18:05:48]

AFAIK, insert works for pos == list->end()-list->begin() too, so no need for the
else branch

[pstanek, 2013/09/17 16:57:00]

Done.

+                    list->insert(pos - list->begin(), RenderedDocumentMarker(toInsert));
+                else
+                    list->append(RenderedDocumentMarker(toInsert));
             }
+        } else {
+            list->append(RenderedDocumentMarker(toInsert));
         }
-        size_t j = i;
-        // Iterate over all markers whose end offset is less than or equal to the new marker's,
-        // removing markers of the same type as the new marker which touch it or intersect with it,
-        // adjusting the new marker's end offset to cover them if necessary.
-        while (j < numMarkers) {
-            DocumentMarker marker = list->at(j);
-            if (marker.startOffset() > toInsert.endOffset())
-                break;
-            if (marker.type() == toInsert.type() && marker.type() != DocumentMarker::TextMatch) {
-                list->remove(j);
-                if (toInsert.endOffset() <= marker.endOffset()) {
-                    toInsert.setEndOffset(marker.endOffset());
-                    break;
-                }
-                numMarkers--;
-            } else
-                j++;
-        }
-        // At this point i points to the node before which we want to insert.
-        list->insert(i, RenderedDocumentMarker(toInsert));
     }
 
     // repaint the affected node
@@ -194,6 +181,51 @@ void DocumentMarkerController::addMarker(Node* node, const DocumentMarker& newMa
         node->renderer()->repaint();
 }
 
+void DocumentMarkerController::mergeOverlapping(MarkerList* list, DocumentMarker& toInsert)

[groby-ooo-7-16, 2013/09/13 18:05:48]

I think this can be simplified - find the first overlapping marker
(lower_bound), then keep merging with the following markers as long as they
overlap.

(And if we had separate lists for each marker type, we could remove the whole
sequence and replace with the merged one. But unfortunately, we don't. We
_could_ do in-place moving during the merge and a final remove of a range, but I
doubt it buys us much)

[pstanek, 2013/09/14 08:18:50]

This is exactly what it does. upper_bound is used to find the stop place in
order to stop as soon as possible. Then lower_bound is done up to this place
(taking the marker type into account) and later all overlapping markers are
removed from the list and merged into toInsert which is inserted later.

[groby-ooo-7-16, 2013/09/17 02:23:47]

Caveat:I might be missing something and all this might be wrong :) 

But let me try to sketch out what I meant.

first = lower_bound();
first = list->insert(first, RenderedDocumentMarker(toInsert));

for(i = first + 1; i != list->end() && !startsFurther(*first, *i);  )
  if (toInsert.type == i->type) {
    *first = merge(*first, *i);  // merge just takes min(start), max(end), can
be done in-place
    list->remove(i-list->begin())
  } else {
    ++i;
  }
}

This would
* remove the need to scan lower_bound for the right type
* remove the special case for the first item
* remove the call to upper_bound
* shorten the code quite a bit.

In case I did miss something and we need to take the longer approach, I've added
feedback to that too.

On 2013/09/14 08:18:50, pstanek wrote:

[pstanek, 2013/09/17 16:20:38]

I'll try to combine your approach with the original code. Why not just using
yours? Because the original code merges one marker from each side only and there
is different stop condition for different sides startsFurther() when merging to
the left and i->startOffset() > inserted->endOffset() when merging to the right.

On 2013/09/17 02:23:47, groby wrote:

[pstanek, 2013/09/17 16:57:00]

Done. (at least partially)

+{
+    // Iterate over all markers whose start offset is less than or equal to the new marker's.
+    // If one of them is of the same type as the new marker and touches it or intersects with it
+    // (there is at most one), remove it and adjust the new marker's start offset to encompass it.
+    size_t numMarkers = list->size();
+    MarkerList::iterator end = std::upper_bound(list->begin(), list->end(), toInsert, startsFurther);
+    MarkerList::iterator overlapping = list->begin();
+    size_t offset = 0;
+    do {
+        overlapping = std::lower_bound(overlapping + offset, end, toInsert, doesNotOverlap);
+        offset = 1;
+    } while (overlapping != end && overlapping->type() != toInsert.type());
+
+    size_t index = numMarkers;
+    if (overlapping != list->end())
+        index = overlapping - list->begin();
+    if (overlapping != end) {
+        toInsert.setStartOffset(overlapping->startOffset());
+        list->remove(index);
+        --numMarkers;
+    }
+
+    // Iterate over all markers whose end offset is less than or equal to the new marker's,
+    // removing markers of the same type as the new marker which touch it or intersect with it,
+    // adjusting the new marker's end offset to cover them if necessary.
+    for (size_t i = index; i < numMarkers;) {
+        DocumentMarker marker = list->at(i);

[groby-ooo-7-16, 2013/09/17 02:23:47]

Calling at() will bounds-check each element - iterators would prevent that.

[pstanek, 2013/09/17 16:57:00]

Done.

+        if (marker.startOffset() > toInsert.endOffset())
+            break;
+        if (marker.type() == toInsert.type()) {
+            list->remove(i);
+            if (toInsert.endOffset() <= marker.endOffset()) {
+                toInsert.setEndOffset(marker.endOffset());
+                break;

[groby-ooo-7-16, 2013/09/17 02:23:47]

Why break here? Couldn't we potentially have more than one marker that need to
be merged? I realize this mirrors the old code, but the comment seemed to
indicate that we _could_ merge more than one marker.

I think the code is right and the comment is in need of an update.

[pstanek, 2013/09/17 16:57:00]

Done.

+            }
+            --numMarkers;
+        } else {
+            ++i;
+        }
+    }
+    // At this point index points to the node before which we want to insert.
+    list->insert(index, RenderedDocumentMarker(toInsert));
+}
+
 // copies markers from srcNode to dstNode, applying the specified shift delta to the copies.  The shift is
 // useful if, e.g., the caller has created the dstNode from a non-prefix substring of the srcNode.
 void DocumentMarkerController::copyMarkers(Node* srcNode, unsigned startOffset, int length, Node* dstNode, int delta)