Closed Bug 347306 Opened 13 years ago Closed 13 years ago

toSource of long functions seems O(n^2).

Categories

(Core :: JavaScript Engine, defect, P1, critical)

defect

Tracking

()

VERIFIED FIXED
mozilla1.9alpha1

People

(Reporter: jruderman, Assigned: brendan)

References

Details

(4 keywords)

Attachments

(7 files, 5 obsolete files)

326 bytes, text/html
Details
9.50 KB, patch
igor
: review+
Details | Diff | Splinter Review
9.50 KB, patch
brendan
: review+
Details | Diff | Splinter Review
1.29 KB, patch
brendan
: review+
Details | Diff | Splinter Review
366 bytes, text/plain
Details
16.25 KB, patch
brendan
: review+
Details | Diff | Splinter Review
7.54 KB, patch
Details | Diff | Splinter Review
This testcase demonstrates that toSource of long functions seems O(n^2) in time.  It does not use an excessive amount of memory.

Size: 10, Time: 0 ms
Size: 100, Time: 4 ms
Size: 1000, Time: 377 ms
Size: 10000, Time: 33985 ms
Blocks: 355805
Attached patch fix (obsolete) — Splinter Review
Test results in a patched, optimized js shell:

Size: 10, Time: 0 ms
Size: 100, Time: 0 ms
Size: 1000, Time: 7 ms
Size: 10000, Time: 58 ms

Best of three results without the patch:

Size: 10, Time: 0 ms
Size: 100, Time: 5 ms
Size: 1000, Time: 72 ms
Size: 10000, Time: 6352 ms

Good for js1.7src/1.8.1.1?  Comments welcome.

/be
Assignee: general → brendan
Status: NEW → ASSIGNED
Attachment #241525 - Flags: review?(igor.bukanov)
OS: Mac OS X 10.4 → All
Priority: -- → P1
Hardware: Macintosh → All
Target Milestone: --- → mozilla1.9alpha
Attachment #241525 - Attachment is obsolete: true
Attachment #241525 - Flags: review?(igor.bukanov)
Attached patch fix, ahem (obsolete) — Splinter Review
Jesse, please test this with the fuzzer.

/be
Attachment #241527 - Flags: review?(igor.bukanov)
Time with patch:

Size: 10, Time: 1 ms
Size: 100, Time: 1 ms
Size: 1000, Time: 6 ms
Size: 10000, Time: 63 ms

/be
Attached patch fix, for sure (obsolete) — Splinter Review
Late night hacking...

/be
Attachment #241527 - Attachment is obsolete: true
Attachment #241528 - Flags: review?(igor.bukanov)
Attachment #241527 - Flags: review?(igor.bukanov)
js> function() { with({}) { } }
Assertion failure: !js_GetSrcNoteCached(cx, jp->script, pc), at jsopcode.c:2268

You could save us both a lot of time by running the fuzzer for a minute or two yourself :)
js> function() { for(let i in j) { } }
Assertion failure: (((*(sn) >> 3) >= SRC_XDELTA) ? SRC_XDELTA : *(sn) >> 3) == SRC_CATCH, at jsopcode.c:2414
Comment on attachment 241528 [details] [diff] [review]
fix, for sure

>+    if (cx->gsnCache.script == script) {

Explaining to myself: such checks are safe since all code paths that free the script clear the cache. That is, js_DestroyScript and GC do that. Thus, a new script can not be allocated with the same address as the old one. 

So this is fine, but what is the source of the bugs the fuzzer has exposed? One is that js_GetSrcNoteCached should be able to return NULL even for cached scripts. But is another one is that several notes can have the same pc? Or I am wrong here?
Jesse_: I promise to run the fuzzer, but it wasn't gonna happen last night!  Hacking on the verge of sleep...zzzzzz.  Thanks for your help.

New patch soon.

/be
Attached patch fix, for real! (obsolete) — Splinter Review
Sorry, bug was simply that I changed js_GetSrcNote to never return null -- it returns the terminating (zero) sn pointer.  Restructuring the for loop fixes.  I promise not to hack so late at night (written 100x on a blackboard a la Bart Simpson).

Getting the fuzzer downloaded and set up next.

/be
Attachment #241528 - Attachment is obsolete: true
Attachment #241564 - Flags: review?(igor.bukanov)
Attachment #241528 - Flags: review?(igor.bukanov)
Attachment #241564 - Attachment is obsolete: true
Attachment #241566 - Flags: review?(igor.bukanov)
Attachment #241564 - Flags: review?(igor.bukanov)
Comment on attachment 241566 [details] [diff] [review]
fix, with cache metering ifdef'ed off

mrbkap was interested in this O(n^2) problem too, IIRC.

/be
Attachment #241566 - Flags: review?(mrbkap)
Attachment #241566 - Flags: review?(igor.bukanov) → review+
With typo fix in jsscript.h comment.

Checking in jscntxt.c;
/cvsroot/mozilla/js/src/jscntxt.c,v  <--  jscntxt.c
new revision: 3.92; previous revision: 3.91
done
Checking in jscntxt.h;
/cvsroot/mozilla/js/src/jscntxt.h,v  <--  jscntxt.h
new revision: 3.123; previous revision: 3.122
done
Checking in jsgc.c;
/cvsroot/mozilla/js/src/jsgc.c,v  <--  jsgc.c
new revision: 3.179; previous revision: 3.178
done
Checking in jsscript.c;
/cvsroot/mozilla/js/src/jsscript.c,v  <--  jsscript.c
new revision: 3.118; previous revision: 3.117
done
Checking in jsscript.h;
/cvsroot/mozilla/js/src/jsscript.h,v  <--  jsscript.h
new revision: 3.33; previous revision: 3.32
done

/be
Attachment #241572 - Flags: review+
Attachment #241572 - Flags: approval1.8.1.1?
Attachment #241566 - Flags: review?(mrbkap)
Attachment #241572 - Flags: review?(mrbkap)
I'd like to get this into 1.8.1.1 and the JS1.7 source release.  From bug 355805 it seems to be biting strict warning option users with real-world Ajax content.

/be
Blocks: js1.7src
Status: ASSIGNED → RESOLVED
Closed: 13 years ago
Flags: blocking1.8.1.1?
Resolution: --- → FIXED
Comment on attachment 241572 [details] [diff] [review]
patch I checked in

Branch patch in a minute.

/be
Attachment #241572 - Flags: review?(mrbkap)
Attachment #241572 - Flags: approval1.8.1.1?
I'm checking this in right now.  jsdhash.h explicitly warns that it's up to the caller of JS_DHashTableInit to clear the table, or at least ops or another tested member, on failure.  This patch does that.

/be
Attachment #241574 - Flags: review+
Attached patch 1.8 branch patch (obsolete) — Splinter Review
Attachment #241575 - Flags: review+
Attachment #241575 - Flags: approval1.8.1.1?
Attachment #241575 - Flags: review?(mrbkap)
RCS file: /cvsroot/mozilla/js/tests/js1_5/Regress/regress-347306-01.js,v
done
Checking in regress-347306-01.js;
/cvsroot/mozilla/js/tests/js1_5/Regress/regress-347306-01.js,v  <--  regress-347306-01.js
initial revision: 1.1
done
RCS file: /cvsroot/mozilla/js/tests/js1_5/Regress/regress-347306-02.js,v
done
Checking in regress-347306-02.js;
/cvsroot/mozilla/js/tests/js1_5/Regress/regress-347306-02.js,v  <--  regress-347306-02.js
initial revision: 1.1
done
Flags: in-testsuite+
Attachment #241575 - Flags: review?(mrbkap) → review+
verified fixed 20061009 1.9 windows/linux
note to self: the BigO calc needs to better handle cases where the elapsed times are small.
Status: RESOLVED → VERIFIED
Flags: blocking1.8.1.1? → blocking1.8.1.1+
Comment on attachment 241575 [details] [diff] [review]
1.8 branch patch

> #ifdef JS_THREADSAFE
>     /*
>      * Set all thread local freelists to NULL. We may visit a thread's
>      * freelist more than once. To avoid redundant clearing we unroll the
>      * current thread's step.
>+     *
>+     * Also, in case a JSScript wrapped in an object was finalized, we clear
>+     * the acx->gsnCache.script pointer and finish the cache's hashtable.
>      */
>     memset(cx->thread->gcFreeLists, 0, sizeof cx->thread->gcFreeLists);
>     iter = NULL;
>     while ((acx = js_ContextIterator(rt, JS_FALSE, &iter)) != NULL) {
>         if (!acx->thread || acx->thread == cx->thread)
>             continue;
>         memset(acx->thread->gcFreeLists, 0, sizeof acx->thread->gcFreeLists);
>+        JS_CLEAR_GSN_CACHE(acx);
>     }
> #endif

This would not clean cache in any context associated with the current thread. Dues to checks in DestroyScript it is OK to skip the current context. But I do not think that it is safe to skip other context associated with the current thread!
(In reply to comment #20)
> This would not clean cache in any context associated with the current thread.
> Dues to checks in DestroyScript it is OK to skip the current context. But I do
> not think that it is safe to skip other context associated with the current
> thread! 

Indeed not -- thanks for pointing this out.  It's safe only if the gsnCache is in cx->thread, not in cx.  Or, we could iterate acx over the cx->thread's contextList and JS_CLEAR_GSN_CACHE(acx) as a separate pass.  Would you please file a new bug?

/be
Blocks: 360612
(In reply to comment #21)
> Would you please file a new bug?

See bug 360612.
Comment on attachment 241575 [details] [diff] [review]
1.8 branch patch

approved for 1.8 branch, a=dveditz for drivers
Attachment #241575 - Flags: approval1.8.1.1? → approval1.8.1.1+
(In reply to comment #23)
> (From update of attachment 241575 [details] [diff] [review] [edit])
> approved for 1.8 branch, a=dveditz for drivers

We need the fix for bug 360612 first, and a combined patch against the 1.8 branch for this bug and that bug second.

/be

Updated to include fix for bug 360612 using cvs up -j automation (two trivial merge conflicts in jsgc.c hand-resolved).  I hope bugzilla interdiff works.

/be
Attachment #241575 - Attachment is obsolete: true
Attachment #246507 - Flags: review+
Attachment #246507 - Flags: approval1.8.1.1?
For easier branch re-approval reviewing.

/be
(In reply to comment #27)
> Created an attachment (id=246508) [edit]
> interdiff -U0 of cvs diff -U0 of previous and current 1.8 branch patches
> 
> For easier branch re-approval reviewing.

Since both bugzilla interdiff and interdiff(1) failed.

/be
No longer blocks: 360612
Depends on: 360612
Blocks: 360612
No longer depends on: 360612
No longer blocks: 360612
Depends on: 360612
Comment on attachment 246507 [details] [diff] [review]
updated 1.8 branch patch

approved for 1.8 branch, a=dveditz for drivers
Attachment #246507 - Flags: approval1.8.1.1? → approval1.8.1.1+
Fixed on the 1.8 branch:

Checking in jsapi.c;
/cvsroot/mozilla/js/src/jsapi.c,v  <--  jsapi.c
new revision: 3.214.2.30; previous revision: 3.214.2.29
done
Checking in jscntxt.c;
/cvsroot/mozilla/js/src/jscntxt.c,v  <--  jscntxt.c
new revision: 3.60.4.10; previous revision: 3.60.4.9
done
Checking in jscntxt.h;
/cvsroot/mozilla/js/src/jscntxt.h,v  <--  jscntxt.h
new revision: 3.80.4.18; previous revision: 3.80.4.17
done
Checking in jsgc.c;
/cvsroot/mozilla/js/src/jsgc.c,v  <--  jsgc.c
new revision: 3.104.2.28; previous revision: 3.104.2.27
done
Checking in jsscript.c;
/cvsroot/mozilla/js/src/jsscript.c,v  <--  jsscript.c
new revision: 3.79.2.17; previous revision: 3.79.2.16
done
Checking in jsscript.h;
/cvsroot/mozilla/js/src/jsscript.h,v  <--  jsscript.h
new revision: 3.25.4.4; previous revision: 3.25.4.3
done

/be
Keywords: fixed1.8.1.1
verified fixed 20061128 1.8.1.1 windows/linux/mac, 1.9 windows/linux.

note that -02 showed a failure in windows/opt but this was not reproducible and was primarily due to the very small time measurements with the fixed build and the unreliability of the BigO estimation code with small values.
(In reply to comment #31)
> verified fixed 20061128 1.8.1.1 windows/linux/mac, 1.9 windows/linux.
> 
> note that -02 showed a failure in windows/opt but this was not reproducible and
> was primarily due to the very small time measurements with the fixed build and
> the unreliability of the BigO estimation code with small values.

Need appropriate fuzziness when estimating BigO -- do you have plans to generalize and tune the tests' various O(f(n)) checkers?

/be

(In reply to comment #32)
> 
> do you have plans to generalize and tune the tests' various O(f(n)) checkers?

Its been on my to-do list for a while. I'll push it higher for the js1.6 release.
fixed bug number is tests:

Checking in regress-347306-01.js;
/cvsroot/mozilla/js/tests/js1_5/Regress/regress-347306-01.js,v  <--  regress-347306-01.js
new revision: 1.3; previous revision: 1.2
done
Checking in regress-347306-02.js;
/cvsroot/mozilla/js/tests/js1_5/Regress/regress-347306-02.js,v  <--  regress-347306-02.js
new revision: 1.3; previous revision: 1.2
done

You need to log in before you can comment on or make changes to this bug.