856178 - IonMonkey: Optimize append operations on strings.

Status: NEW

(Core :: JavaScript Engine: JIT, defect, P5)

Description

[Nicolas B. Pierron [:nbp]]

In PdfJS octane benchmark we can notice the following loop:

    var eexecStr = '';
    for (var i = 0, ii = eexec.length; i < ii; i++)
      eexecStr += String.fromCharCode(eexec[i]);

which also exists in different variants where the right hand side is likely a one-character string.  Such string is then either constantly read with eexecStr[i] or compared against constants.  Which means that we are currently creating a linked list of characters (ropes), and then we linearized everything for reading from the string.

At the moment, IonMonkey does not inline the string concat operation.  If we can ensure that nothing will hold the string in one state, we can use an extensible string and inline the concatenation operations with an amortized log case for the reallocation of the string buffer.

Note: Also, this kind of operations is likely to become more common at the interface boundaries of asm.js functions.

Comment 1

[Nicolas B. Pierron [:nbp]]

Attachment: Micro benchmark

Comment 2

[Nicolas B. Pierron [:nbp]]

Attachment: Append characters to extensible strings in loops.

This patch check that a string buffer is not escaped and optimize loops of append by allocating an extensible array and replace concatenations by appends.

This optimization is made to be equivalent to the result of a rope creation which is then flattened.  The only trick is that we should avoid other flatten to prevent our extensible buffer to be converted to a dependent string.

@luke: Can you check if the string logic is correct there or if I missed some corner cases?

Comment 3

[Luke Wagner [:luke]]

Comment on attachment 731715 [details] [diff] [review]
Append characters to extensible strings in loops.

The concept makes sense.  The only worrying thing is the size of the patch, so it'd be good to get a confirmation of how much this helps Octane or how often it matches real code (or Emscripten glue code, per comment 0).

Comment 4

[Mayank Bansal]

Attachment: Original testcase with increased iterations

Comment 5

[Mayank Bansal]

With the slightly modified testcase, I get the following numbers:

Nightly: 4.5s (https://share.firefox.dev/3AoYzWY)
Chrome: 19s

Given these numbers, should this bug be closed?