453402 - parseInt(double) and concatenation of static strings are slow

Status: RESOLVED WORKSFORME

(Core :: JavaScript Engine, defect)

Description

[Oleg Romashin (:romaxa)]

http://wd-testnet.world-direct.at/mozilla/dhtml/funo/jsTimeTest.htm

Even with enabled .jit.* URL js test slower than webkit... because
ParseInt and Concatenate Strings are very slow there.

Comment 1

[Mike Shaver (:shaver emeritus)]

ParseInt is easy to fix (we're hurting because we're creating the string and then parsing it).  String stuff will be a bit trickier, but we have A Plan.

Comment 2

[Mike Shaver (:shaver emeritus)]

Bug 454037 will address parseInt, narrowing and leaving this open until I know what escape-analysis or string-refcounting bug to dup against.

Comment 3

[Alfred Kayser]

For the string concat issue, the test concats two static strings, for which I
expect a smart JIT compiler to detect this situation, optimizing the add of two
constants into one new constant.

A long time, I developed an interpreter (DScheme) that did this kind of
'inline' formula optimization when translating a formula to a bytecode stream,
so this should also be possible for JavaScript.

Comment 4

[Alfred Kayser]

Could it be that GC keeps the malloc'd string allocated to 'string3' and re-use the next loop around? For example, when trying to assign a new string to string3, instead of free'ing the old, allocating a new buffer and then copy, it directly copies into the same string object. This will need some smart thing in the assignment operator. (e.g. if string3 where an nsString object, that should work in that way).

Comment 5

[Nicholas Nethercote [inactive]]

Firefox is still slow on both of these.  

Regardint the string concatenation, here's the relevant part of the microbenchmark code:

    for (var i=0; i<=1000000; i++)
    {       
        string3 = string1 + string2;
    }       

TraceMonkey doesn't statically compute the concatenation because the two strings are seen as stack parameters:

    $stack4 = ldi.s sp[-32]
    sti.s sp[0] = $stack4
    $stack5_2 = ldi.s sp[-24]
    sti.s sp[8] = $stack5_2
    js_ConcatStrings1 = calli. #js_ConcatStrings ( cx $stack4 $stack5_2 )

I.e. the fact that they are constant strings is not visible here, so the compiler cannot statically concatenate them.  

However, fixing this doesn't seem like a high priority;  I would posit that real programs don't concatenate static strings together frequently enough that this would make a difference in real code.  If you see real code where this behaviour does help, I'd love to hear about it.

Comment 6

[Alfred Kayser]

Actually, there are benchmarks such as v8 which are used a marketing tool that could benefit of optimizations like these. Especially the splay test of v8 has a lot of string concats from static strings.

Comment 7

[Andreas Gal :gal]

String concatenation is pretty common on the web, too, so I think its a good idea to optimize this, even benchmarks aside.

Comment 8

[Nicholas Nethercote [inactive]]

(In reply to comment #6)
> Actually, there are benchmarks such as v8 which are used a marketing tool that
> could benefit of optimizations like these. Especially the splay test of v8 has
> a lot of string concats from static strings.

The splay test doesn't do concatenations of static strings.  It does this:

  'String for key ' + key + ' in leaf node'

a lot, where 'key' is a randomly generated number.


(In reply to comment #7)
> String concatenation is pretty common on the web, too, so I think its a good
> idea to optimize this, even benchmarks aside.

String concatenation, yes, but static string concatenation?  eg. "abc" + "def"?  Colour me skeptical.

Comment 9

[Brendan Eich [:brendan]]

SpiderMonkey folds constant "foo" + "bar". It doesn't analyze variables that are always evaluated to constant string values though.

/be

Comment 10

[Mike Shaver (:shaver emeritus)]

Loop-constant string concat is found on the web for sure.  People use it for templating and HTML generation, for example:

function makeTableRows(rowClass, cellClass, entries)
{
    var gen = "";
    for (var i = 0; i < entries.length; i++) {
        gen += '<tr class="' + rowClass + '"><td class="' + cellClass + '">' + entries[i] + '</td></tr>';
    }
    return gen;
}

It's also not uncommon to see people declare a bunch of globals with HTML snippets, effectively as symbolic constants, and then glom them together in loops.  I found a bunch of these cases when I was looking at JSOP_CONCATN the first time, though apparently I didn't capture them in the bug.

Comment 11

[Nicholas Nethercote [inactive]]

So there's a spectrum of "static" string concatenations:

  "foo" + "bar"

which the SpiderMonkey front-end evaluates.

  var foo = "foo";
  var bar = "bar";
  var foobar = foo + bar

which doesn't get optimized and I hypothesize isn't common in practice.

And then more complex cases like in comment 10, which combines loops and/or function calls and/or array lookups;  I can believe that these are common but they are all difficult to statically evaluate.

So that's a nice discussion... does anyone have suggestions for concrete actions to take in response to this bug?

Comment 12

[Luke Wagner [:luke]]

The original URL is invalid.  Is there anything that can still be compared here?  Ropes should help comment 10 (although bug 648198 would improve further).

Comment 13

[Tom S]

http://web.archive.org/web/20080501123959/http://wd-testnet.world-direct.at/mozilla/dhtml/funo/jsTimeTest.htm

Comment 14

[Luke Wagner [:luke]]

Hah, thanks.  I ran us vs. Chrome and we are now faster on the parseInt() test, so that seems to have been resolved.  For concat strings, they are 2x faster, but this is the same create-garbage-each-iteration loop as in bug 625615, so no reason to duplicate here.  Thus, leaving WFM.