614653 - avoid O(n^2) rope node marking

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Luke Wagner [:luke]]

This pathological case takes 3s:

var arr = [];
var s = "abcdefghijklmnop";
for (var i = 0; i < 10000; ++i) {
    s = "<" + s + ">";
    arr.push(s);
}
gc();

Having TypedMarker return early when a rope node is already marked takes 2ms.  I think rope marking could be further improved to skip the initial "walk to the left-most node" step by using str->asCell()->isMarked() as the "visited" bit in a traditional tree traversal.

Comment 1

[Luke Wagner [:luke]]

Attachment: fix

Using "isMarked" as "visited" wasn't such a hot idea.  This patch just avoids the O(n^2) behavior.

Comment 2

[Igor Bukanov]

Comment on attachment 493124 [details] [diff] [review]
fix

>diff --git a/js/src/jsgcinlines.h b/js/src/jsgcinlines.h
> static JS_ALWAYS_INLINE void
>-TypedMarker(JSTracer *trc, JSString *thing)
>+TypedMarker(JSTracer *trc, JSString *str)
> {
>+    JSRopeNodeIterator iter;
>+    if (str->isRope()) {
>+        if (str->asCell()->isMarked())
>+            return;

That does not work as isMarked is only available for GCMarker. It does not work for a generic marker like CC one or various debug dumping.

Comment 3

[Luke Wagner [:luke]]

Ok.  So, is there an equivalent to isMarked() for generic markers?

Comment 4

[Luke Wagner [:luke]]

Also, why is it valid for TypedMarker to call str->asCell()->markIfUnmarked (which uses str->asCell()->isMarked()) a few lines later?

Comment 5

[Luke Wagner [:luke]]

Perhaps Gregor has an answer?

Comment 6

[Gregor Wagner [:gwagner]]

(In reply to comment #2)
> Comment on attachment 493124 [details] [diff] [review]
> fix
> 
> >diff --git a/js/src/jsgcinlines.h b/js/src/jsgcinlines.h
> > static JS_ALWAYS_INLINE void
> >-TypedMarker(JSTracer *trc, JSString *thing)
> >+TypedMarker(JSTracer *trc, JSString *str)
> > {
> >+    JSRopeNodeIterator iter;
> >+    if (str->isRope()) {
> >+        if (str->asCell()->isMarked())
> >+            return;
> 
> That does not work as isMarked is only available for GCMarker. It does not work
> for a generic marker like CC one or various debug dumping.

We don't even call TypedMarker if IS_GC_MARKING_TRACER returns false.

Comment 7

[Gregor Wagner [:gwagner]]

Comment on attachment 493124 [details] [diff] [review]
fix

>diff --git a/js/src/jsgcinlines.h b/js/src/jsgcinlines.h
>--- a/js/src/jsgcinlines.h
>+++ b/js/src/jsgcinlines.h
>@@ -346,28 +346,34 @@ TypedMarker(JSTracer *trc, JSFunction *t
> 
> static JS_ALWAYS_INLINE void
> TypedMarker(JSTracer *trc, JSShortString *thing)
> {
>     thing->asCell()->markIfUnmarked();
> }
> 
> static JS_ALWAYS_INLINE void
>-TypedMarker(JSTracer *trc, JSString *thing)
>+TypedMarker(JSTracer *trc, JSString *str)
> {
>     /*
>-     * Iterate through all nodes and leaves in the rope if this is part of a
>-     * rope; otherwise, we only iterate once: on the string itself.
>+     * When marking any node of a rope, mark the entire rope. This means if
>+     * a given rope node is already marked, we are done.
>      */
>-    JSRopeNodeIterator iter(thing);
>-    JSString *str = iter.init();
>+    JSRopeNodeIterator iter;
>+    if (str->isRope()) {
>+        if (str->asCell()->isMarked())
>+            return;
>+        str = iter.init(str);
>+        goto not_static;

Uhhh a goto from Luke :) I hope the jump target doesn't slow down the loop.

If I change your motivating example and always append a string at the beginning I still have to go the slow path right?

Comment 8

[Luke Wagner [:luke]]

(In reply to comment #7)
> Uhhh a goto from Luke :)

http://hg.mozilla.org/tracemonkey/annotate/67dd268276f3/js/src/jsstr.cpp#l136
Yeah, I've been using them a lot recently ;-)

> I hope the jump target doesn't slow down the loop.
> 
> If I change your motivating example and always append a string at the beginning
> I still have to go the slow path right?

I'm not sure what you mean by "append a string at the beginning", do you mean, switch the order of the two statements in the loop?  Also, which "slow path" are you referring to?

Comment 9

[Luke Wagner [:luke]]

http://hg.mozilla.org/tracemonkey/rev/9aa8c290f633

Comment 10

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/9aa8c290f633