Closed Bug 614653 Opened 9 years ago Closed 9 years ago

avoid O(n^2) rope node marking

Categories

(Core :: JavaScript Engine, defect)

defect
Not set

Tracking

()

RESOLVED FIXED

People

(Reporter: luke, Assigned: luke)

Details

(Whiteboard: fixed-in-tracemonkey)

Attachments

(1 file)

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.
Attached patch fixSplinter Review
Using "isMarked" as "visited" wasn't such a hot idea.  This patch just avoids the O(n^2) behavior.
Attachment #493124 - Flags: review?(igor)
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.
Attachment #493124 - Flags: review?(igor) → review-
Ok.  So, is there an equivalent to isMarked() for generic markers?
Also, why is it valid for TypedMarker to call str->asCell()->markIfUnmarked (which uses str->asCell()->isMarked()) a few lines later?
Perhaps Gregor has an answer?
(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.
Attachment #493124 - Flags: review- → review?(anygregor)
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?
Attachment #493124 - Flags: review?(anygregor) → review+
(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?
http://hg.mozilla.org/tracemonkey/rev/9aa8c290f633
Whiteboard: fixed-in-tracemonkey
http://hg.mozilla.org/mozilla-central/rev/9aa8c290f633
Status: ASSIGNED → RESOLVED
Closed: 9 years ago
Resolution: --- → FIXED
Depends on: 629974
No longer depends on: 629974
You need to log in before you can comment on or make changes to this bug.