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

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Jesse Ruderman]

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

Comment 1

[Jesse Ruderman]

Attachment: testcase (calls dump() with timing information)

Comment 2

[Brendan Eich [:brendan]]

Attachment: fix

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

Comment 3

[Brendan Eich [:brendan]]

Attachment: fix, ahem

Jesse, please test this with the fuzzer.

/be

Comment 4

[Brendan Eich [:brendan]]

Time with patch:

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

/be

Comment 5

[Brendan Eich [:brendan]]

Attachment: fix, for sure

Late night hacking...

/be

Comment 6

[Jesse Ruderman]

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 :)

Comment 7

[Jesse Ruderman]

js> function() { for(let i in j) { } }
Assertion failure: (((*(sn) >> 3) >= SRC_XDELTA) ? SRC_XDELTA : *(sn) >> 3) == SRC_CATCH, at jsopcode.c:2414

Comment 8

[Igor Bukanov]

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?

Comment 9

[Brendan Eich [:brendan]]

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

Comment 10

[Brendan Eich [:brendan]]

Attachment: fix, for real!

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

Comment 11

[Brendan Eich [:brendan]]

Attachment: fix, with cache metering ifdef'ed off

Comment 12

[Brendan Eich [:brendan]]

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

Comment 13

[Brendan Eich [:brendan]]

Attachment: patch I checked in

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

Comment 14

[Brendan Eich [:brendan]]

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

Comment 15

[Brendan Eich [:brendan]]

Comment on attachment 241572 [details] [diff] [review]
patch I checked in

Branch patch in a minute.

/be

Comment 16

[Brendan Eich [:brendan]]

Attachment: followup fix to subtle jsdhash API wart

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

Comment 17

[Brendan Eich [:brendan]]

Attachment: 1.8 branch patch

Comment 18

[Bob Clary [:bc] (inactive)]

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

Comment 19

[Bob Clary [:bc] (inactive)]

verified fixed 20061009 1.9 windows/linux
note to self: the BigO calc needs to better handle cases where the elapsed times are small.

Comment 20

[Igor Bukanov]

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!

Comment 21

[Brendan Eich [:brendan]]

(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

Comment 22

[Igor Bukanov]

(In reply to comment #21)
> Would you please file a new bug?

See bug 360612.

Comment 23

[Daniel Veditz [:dveditz]]

Comment on attachment 241575 [details] [diff] [review]
1.8 branch patch

approved for 1.8 branch, a=dveditz for drivers

Comment 24

[Brendan Eich [:brendan]]

(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

Comment 25

[Brendan Eich [:brendan]]

Attachment: version of testcase that works in the js shell too

Comment 26

[Brendan Eich [:brendan]]

Attachment: updated 1.8 branch patch

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

Comment 27

[Brendan Eich [:brendan]]

Attachment: interdiff -U0 of cvs diff -U0 of previous and current 1.8 branch patches

For easier branch re-approval reviewing.

/be

Comment 28

[Brendan Eich [:brendan]]

(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

Comment 29

[Daniel Veditz [:dveditz]]

Comment on attachment 246507 [details] [diff] [review]
updated 1.8 branch patch

approved for 1.8 branch, a=dveditz for drivers

Comment 30

[Brendan Eich [:brendan]]

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

Comment 31

[Bob Clary [:bc] (inactive)]

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.

Comment 32

[Brendan Eich [:brendan]]

(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

Comment 33

[Bob Clary [:bc] (inactive)]

(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.

Comment 34

[Bob Clary [:bc] (inactive)]

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