174341 - JS string concatenation perf problem, memory jumps from 16 MB to 250+ MB

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Ludovic Hirlimann]

Build ID is 2002101308 on w2k server sp3.
When going to http://www.ericsson.fr the loading bar goes approximatly to it's
half. When looking memory useage it VM use jumps from 16 Mb to 250 Mb very rapidly.

This is also true with Linux (Woody install) and build id 2002061503. Kernel
2.4.18, libc6 2.2.5. When launched load goes from 1 to 6.

Comment 1

[Ludovic Hirlimann]

On w2k when going to debug->Leak Detector->Dump memory link.
And trying to load the page after wards , the page loads and VM goes back to normal.

Comment 2

[Ludovic Hirlimann]

Changing sev and subject because the page loads if you wait long enough. Memory
goes back to normal too but for at least two minutes the machine becomes unuseable.
Adding perf keyword, loading the site is a real pain.

Comment 3

[Ludovic Hirlimann]

This is still true with build ID 2003021008.

Adding qawanted in order to have this bug changed from unconfirmed to NEW.

Comment 4

[Ludovic Hirlimann]

ccing Perf and footprint people.

Comment 5

[Giano]

Even on Mac OS X.....the same...Mozilla 13b

Comment 6

[Simon Fraser [no longer active]]

Some sampling shows lots of time spent in JS -- js_FoldConstants is being called
recursively.

Comment 7

[Simon Fraser [no longer active]]

The page document.writes a huge list of string literals into a <style> tag.

Comment 8

[Brendan Eich [:brendan]]

Where's a reduced testcase?

/be

Comment 9

[Simon Fraser [no longer active]]

coming right up...

Comment 10

[Simon Fraser [no longer active]]

Attachment: Testcase

Comment 11

[Phil Schwartau]

Attachment: Testcase (JS shell version)

Comment 12

[Phil Schwartau]

Using current trunk on WinNT4.0, 500MHz CPU, 128M RAM. 

The reduced testcases only contain JS string concatenation,
no document.write() or other DOM methods.

My box cannot load either the HTML testcase nor the JS testcase.
All available RAM is used up. In each case, the Windows alertbox
comes up, "Your system is running low on memory...".

With the HTML testcase, I have to kill Mozilla to prevent the box
from crashing. The JS testcase terminates with an "out of memory"
error in the JS shell.

By contrast, IE6 loads the HTML testcase quickly and without using
up much RAM. When I loaded the testcase, the WinNT Task Manager
showed my available RAM decreasing from 51K to 49K. The load took
just a couple seconds or so.

This bug is probably a duplicate of one already on file for 
JS string concatenation issues. I will look into that; in the 
meantime, let me reassign this to the JS Engine component.

Comment 13

[Phil Schwartau]

This same issue was raised in bug 56940,
"O(n**2) and O(n**3) growth too easy with JS string concat"

However, that bug was fixed and verified a long time ago.
Therefore, I'm holding this bug open and adding it as a dependency
to the meta-bug for JS performance, bug 117611.


The reporter in bug 56940 noted,

"If you use the += operator, the string concatenation is actually rather
quick. However, I don't see this method being used very often in web sites."

And indeed, the website given in this bug, http://www.ericsson.fr,
doesn't use that method. Instead, it does x = a + b + c + d + ...

See bug 56940 comment 9 for Brendan's comments on this issue -

Comment 14

[Brendan Eich [:brendan]]

Oh, this is easily diagnosed, but perhaps harder to fix: js_FoldConstants tries
to use the dependent/growable goodness introduced with the fix for bug 56940,
but then frustrates itself by atomizing the result of each "foo" + "bar" literal
concatenation (atomizing makes the resulting string immutable -- not growable as
well as independent).

The constant folder needs to defer atomizing string constants until it knows
they can't be combined via a growable string.  I'll attempt a patch.

/be

Comment 15

[Brendan Eich [:brendan]]

Attachment: Testcase (working JS shell version)

navigator needed an appName property (I used value 'Netscape' ;-), and wanted
to be an object initializer.

/be

Comment 16

[Brendan Eich [:brendan]]

Attachment: proposed fix

This patch looks bigger than it is only because the "Flatten a left-associative
(left-heavy) tree"-commented code moved from the bottom of js_FoldConstants
(way late) to NewBinary (conserve JSParseNodes early and often!), and because
the in-line FoldBinaryNumeric code is now out-of-line in that subroutine.

/be

Comment 17

[Brendan Eich [:brendan]]

Comment on attachment 115702 [details] [diff] [review]
proposed fix

I hope shaver has time to review this.

Phil, my new RH8.0 seemed to disagree with the js testsuite on
js1_5/Regress/regress-192465.js -- not sure why, but the process was chewing
stack *slowly* -- it should run out soon enough, but I got tired of waiting. 
Can you run this patch through a full testsuite pass?  Thanks.

/be

Comment 18

[Mike Shaver (:shaver emeritus)]

Comment on attachment 115702 [details] [diff] [review]
proposed fix

> +            /* Any one string literal operand means this is a concatenation. */
> +            JS_ASSERT(pn->pn_count > 2);
> +            for (pn2 = pn1; pn2; pn2 = pn2->pn_next) {
> +                if (pn2->pn_type == TOK_STRING)
> +                    break;
> +            }

Is it possible for us to track this state as we build the list in NewBinary,
rather than iterating over it again?  Maybe that's not a big problem, since our
lists will tend to be small, but I thought I'd ask.

Other than that, it looks good, but I want to read the patched version more
closely before I stamp.

Comment 19

[Brendan Eich [:brendan]]

Attachment: alterna-patch per shaver's request

Shaver: like this?  I aim to please :-).

/be

Comment 20

[Mike Shaver (:shaver emeritus)]

Comment on attachment 115717 [details] [diff] [review]
alterna-patch per shaver's request

That's what I'm talking about, right there.

r=shaver.

Comment 21

[Brendan Eich [:brendan]]

Attachment: better pn_extra alias and jsparse.h comments

I made a pn_strcat alias for pn_extra and commented the heck out of it, and
commented the left-assoc-binary-tree => list optimization, in jsparse.h. 
Shaver, can you re-stamp?  Thanks,

/be

Comment 22

[Phil Schwartau]

The latest patch (Comment #21) passes the JS testsuite both on
my Linux box (RedHat7.2) and my WinNT box. I ran the tests against 
both the debug and optimized JS shells, with the patch applied.
No test regressions were observed.

Furthermore, there is a spectacular improvement on the (corrected)
JS shell testcase for this bug (Comment #15). It now completes in
split-second time, and hardly uses any memory.

Brendan: I don't know why js1_5/Regress/regress-192465.js bogs down
for you on RedHat 8. I wonder if Perl is partly to blame? I wonder 
what happens if you run that test by hand, as in:

[ ]./js -f /d/JS_TRUNK/mozilla/js/tests/js1_5/shell.js
        -f /d/JS_TRUNK/mozilla/js/tests/js1_5/Regress/regress-192465.js

I get a segfault, almost immediately:
Segmentation fault (core dumped)

By contrast, when I allow the Perl test driver to run this test,
I get no indication of failure. For some reason, my Perl process 
does not get informed of the segfault. I have to run this test
by hand to get the true picture.

Comment 23

[Mike Shaver (:shaver emeritus)]

Comment on attachment 115777 [details] [diff] [review]
better pn_extra alias and jsparse.h comments

Comments!  Descriptive aliases!  It's like Christmas in February.

Once more, with feeling: r=shaver.

Comment 24

[Brendan Eich [:brendan]]

Phil and I found the cause of the (unrelated to this bug's patch) RH7.2 vs. RH8
anomaly seen running the testsuite (comment 22 second half): under RH7.2, which
Phil runs, ulimit -s says 8192; under RH8, I get "unlimited".

The test at js1_5/Regress/regress-192465.js nests objects up to a million deep,
and with an unlimited stack, the Object.prototype.toSource native implementation
is going to run for a long, long time.

Thanks, shaver -- checking in now with this essay as cvs log message:

- Move left-associative binary tree flattening from the post-order position
  in js_FoldConstants where it was added (suboptimally: it worked, but it ran
  so late that js_FoldConstants recursion was not reduced, only js_EmitTree
  recursion), to NewBinary, where it avoids JSParseNode allocations up front
  and reduces recursion in all parse-tree walking.
- This change enables js_FoldConstants to see a very long concatenation of
  string literals as a PN_LIST node, so it can quickly concatenate without
  running afoul of O(n^2) problems inherent in js_ConcatStrings applied to
  two atomized strings (the old way of folding string concatenations, still
  used for any pairwise string literal concatenation).
- Further optimize the first change for the second by having NewBinary set a
  new pn_strcat flag (overlaying the pn_extra field) of the PN_LIST arm of
  the JSParseNode.pn_u union, whenever it sees at least one string literal in
  a concatenation that might be folded (whose operands might all be constants
  of string or number type).
- Notes:
  - only string and number constants are folded (not boolean or null
    constants);
  - only all-constant left-associated binary expression chains are folded,
    so 2 * foo * 3 is not folded using commutativity of * over numbers, nor
    is "hi" + " there" + foo folded to "hi there" + foo.
  - gcc3.2 -O and objdump -x say I added 708 bytes of instructions with this
    change.  I tried to keep it down to what was necessary for common script;
    I don't think JS needs an optimizing-compiler-strength constant folder,
    and I don't think this 1K bloat is too high a price to pay for this fix.
    But I'll certainly work on reducing footprint elsewhere, if I can.
- Bug 174341, r=shaver.

/be

Comment 25

[Phil Schwartau]

Brendan had a good idea: try to make the JS test driver limit the JS
stack size to 8192, so that systems like RedHat8 won't churn forever
on testcases like js1_5/Regress/regress-192465.js.

However, there doesn't seem to be a direct interface between Perl
and the |ulimit| command. The usual backticks don't invoke this
command successfully from Perl.

Apparently there is a workaround, but it would require all users of
jsDriver.pl to download a non-standard Perl module called BSD::Resource.

In the meantime, I will add an early return to that test until I can
find the best solution to this problem -


REFERENCES:

How do you set ulimit -n 5000 in Perl?
http://www.experts-exchange.com/Programming/Programming_Languages/Perl/Q_10224927.html

Reply:
http://www.experts-exchange.com/Programming/Programming_Languages/Perl/Q_10224927.html#1

Comment 26

[Robert Ginda]

There may be a way to detect the presence of a module with Perl.  If so, we
could add a --stacksize argument to jsDriver.pl that is only valid if
BSD::Resource is installed.  Existing users wouldn't be affected at all.

Unfortunately I don't know how to recover from a "use" failure.  |use Dave ||
die "Dave's not here";| throws a syntax error.

Comment 27

[Phil Schwartau]

Verified FIXED.

In addition to the verifications in the JS shell (Comment #22),
I tested today's Mozilla builds on WinNT, Linux, and Mac OSX.

I was able to load the HTML testcase quickly, and also the URL
for this bug, http://www.ericsson.fr. The load time was roughly
the same as with IE6.

Comment 28

[Brendan Eich [:brendan]]

This bug's patch regressed bug 196290. :-(

/be