586145 - JM: improve string concatenation speed in date-format-xparb.js

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nicholas Nethercote [inactive]]

Currently on arewefastyet.com we have these times for xparb:

- JM:  40.4ms
- TM:  36.4ms
- JSC: 19.4ms
- V8:  19.4ms

Here are some TM vs JM comparisons of instruction counts in certain functions, as found by Cachegrind:

                                   TM      JM
- total                         99.5M   114.3M
- Add()                         --        4.2M
- js_String()                    0.0M    ~2.2M
- generated code                11.2M    13.2M
- js_LookupPropertyWithFlags:    0.9M     3.1M  *
- js_GetPropertyHelper           1.5M     2.2M  *
- JS_DHashTableOperate           0.0M     1.2M
- js_InternalInvoke              --       1.1M  *
- InlineGetProp                  --       1.1M
...
- ComputeThisFromArg             2.0M     0.8M

String concatenation is a big part of this:  Add(), maybe js_String().
The ones marked '*' are called by DefaultValue(), which is also involved in string concatenation.

Shark says:
- js_concatStrings()            8.8%
- Add()                         2.9%
- js_LookupPropertyWithFlag()   2.1%   (1.5% of which is comes via Add())

In the TM code there are several places where calls to js_ConcatStrings() are chained, ie. the result of one call is used as an argument to another call.  At least TM calls js_ConcatStrings directly, JM has to use the horrible indirection via Add().  Surely there can be a way to avoid this.

Comment 1

[David Anderson [:dvander] - inactive, e-mail if emergency]

I wonder what property we're looking up?

Comment 2

[Nicholas Nethercote [inactive]]

I forgot to mention this from shark, which is also due to strings:

- js_NewFinalizableGCThing      2.9%

The vast majority of the concatenations are due to these two sequences, which repeat with minor variations in the date a bazillion times:

"2017" + "-"
"0" + "9"
"2017-" + "09"
"2017-09" + "-"
"0" + "5"
"2017-09-" + "05"

"Tuesday" + ","
"Tuesday," + " "
"Tuesday, " + "September"
"Tuesday, September" + " "
"0" + "5"
"Tuesday, September " + "05"
"Tuesday, September 05" + ","
"Tuesday, September 05," + " "
"Tuesday, September 05, " + "2017"
"Tuesday, September 05, 2017" + " "
"Tuesday, September 05, 2017 " + "8"
"Tuesday, September 05, 2017 8" + ":"
"Tuesday, September 05, 2017 8:" + "43"
"Tuesday, September 05, 2017 8:43" + ":"
"Tuesday, September 05, 2017 8:43:" + "48"
"Tuesday, September 05, 2017 8:43:48" + " "
"Tuesday, September 05, 2017 8:43:48 " + "AM"

apierce, how will the rope code handle this kind of concatenation sequence?

Comment 3

[Nicholas Nethercote [inactive]]

(In reply to comment #1)
> I wonder what property we're looking up?

counts of the top five:

( 1) 60003 (55.1%, 55.1%): valueOf
( 2) 12009 (11.0%, 66.1%): Y-m-d
( 3) 12007 (11.0%, 77.2%): l, F d, Y g:i:s A
( 4) 12002 (11.0%, 88.2%): format0
( 5) 12002 (11.0%, 99.2%): format1

Comment 4

[Nicholas Nethercote [inactive]]

We have 86824 calls to Add(), with the following case frequencies:

( 1)  54822 (63.1%, 63.1%): str + str
( 2)  20000 (23.0%, 86.2%): str + obj
( 3)   8002 ( 9.2%, 95.4%): str + num
( 4)   4000 ( 4.6%, 100.0%): num + str

Comment 5

[Brian Hackett [Laid off!]]

For the first one, 20k seem to be ints passed to 'new String' in String.leftPad, and at least 12k of the remainder are ints used in concatenation operations in the two functions eval'ed by createNewFormat.  Can't the slot for Number.prototype.valueOf be precomputed?

The latter four are all properties on Date.formatFunctions and Date.prototype, and accessed inside the dateFormat function.  The shape of these two objects should stabilize after the first run of the 'i < 4000' loop at the bottom, shouldn't the getelem PIC be catching these?

Date.prototype.dateFormat = function(format) {
    if (Date.formatFunctions[format] == null) {
        Date.createNewFormat(format);
    }
    var func = Date.formatFunctions[format];
    return this[func]();
}

Comment 6

[Brian Hackett [Laid off!]]

Er, above was replying to comment 3.  The 'str + obj' will be another 20k valueOf's.

Comment 7

[Nicholas Nethercote [inactive]]

For the 35 calls to jsop_binary(), we have this breakdown in terms of what we know about the types of the operands:

( 1) 15 (42.9%, 42.9%): unknown, string
( 2) 12 (34.3%, 77.1%): unknown, unknown
( 3)  4 (11.4%, 88.6%): string, unknown
( 4)  4 (11.4%, 100.0%): unknown, int

I don't yet know how these static counts correlate to the dynamic counts in comment 4.

Comment 8

[Nicholas Nethercote [inactive]]

Another fun fact: under the interpreter and JM, DefaultValue() is called 20,000 times.  Under TM it's called 82 times.  So TM is doing something right that JM isn't.

Comment 9

[Brendan Eich [:brendan]]

(In reply to comment #8)
> Another fun fact: under the interpreter and JM, DefaultValue() is called 20,000
> times.  Under TM it's called 82 times.  So TM is doing something right that JM
> isn't.

Imacros FTW! :-)

/be

Comment 10

[Brendan Eich [:brendan]]

To say a bit more, tracing means static types on-trace, and where one or both operands of an implicitly-converting operator are objects, we expand the fat op to skinny ops in order to shape-guard on the toString or valueOf method and then inline it if it is interpreted.

In principle JM can do something similar but with PICs and (alas) no inlining.

/be

Comment 11

[Nicholas Nethercote [inactive]]

(In reply to comment #7)
> For the 35 calls to jsop_binary(), we have this breakdown in terms of what we
> know about the types of the operands:
> 
> ( 1) 15 (42.9%, 42.9%): unknown, string
> ( 2) 12 (34.3%, 77.1%): unknown, unknown
> ( 3)  4 (11.4%, 88.6%): string, unknown
> ( 4)  4 (11.4%, 100.0%): unknown, int
> 
> I don't yet know how these static counts correlate to the dynamic counts in
> comment 4.

I do now:  72030 (83%) of the dynamic calls to Add() are for cases (1) and (3).

Comment 12

[Alan Pierce]

(In reply to comment #2)
> The vast majority of the concatenations are due to these two sequences, which
> repeat with minor variations in the date a bazillion times:
> 
> "2017" + "-"
> ...
> "2017-09-" + "05"
> 
> "Tuesday" + ","
> ...
> "Tuesday, September 05, 2017 8:43:48 " + "AM"
> 
> apierce, how will the rope code handle this kind of concatenation sequence?

In the first sequence, ropes don't ever come into play since they fit inside short strings (bug 578205. See from the SS results of that bug that xparb got a little faster).

For the second sequence, we build a rope. Each small concatenation costs an extra string header and a few branches in js_ConcatStrings. It also makes the flattening time a little longer, but I think the tree traversal in JSString::flatten is really fast regardless. We lose some from having to malloc and free buffers of size 32 and 64 while building the rope. Enforcing a minimum empty buffer size of 128 for ropes avoids these mallocs and frees, and brings the test time from 27ms to 26ms on my machine.

Comment 13

[Nicholas Nethercote [inactive]]

Sayre thought we might be saved on this one by '-j -m' giving results as good as -j.  Unfortunately it doesn't appear to be the case, at least with the JM vs TM heuristics in 50586:f6dcaa717899.

Comment 14

[Nicholas Nethercote [inactive]]

(In reply to comment #0)
> Currently on arewefastyet.com we have these times for xparb:
> 
> - JM:  40.4ms
> - TM:  36.4ms
> - JSC: 19.4ms
> - V8:  19.4ms

We now have this:

- JM:    15.3ms
- JM+TM: 15.3ms
- TM:    21.6ms
- V8:    18.9ms
- JSC:   20.1ms

I suspect Luke's rope improvements (fallible chars()) improved this a lot.  This bug can be closed.