Remove JSString::EXTENSIBLE

RESOLVED WONTFIX

Status

()

Core
JavaScript Engine
RESOLVED WONTFIX
7 years ago
7 years ago

People

(Reporter: njn, Assigned: njn)

Tracking

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment)

(Assignee)

Description

7 years ago
Created attachment 492238 [details] [diff] [review]
patch (against TM 57773:da7fd699ddcb)

This patch removes the EXTENSIBLE flag from JSString.  AFAICT it's not doing
anything useful.  The only place extensible strings are created is when a rope
is flattened;  the top node converts to an extensible string.  And the only
place where an extensible string behaves differently to a non-extensible string
is in js_ConcatStrings, in the case containing this comment:

   /*
    * If left has enough unused space at the end of its buffer that we can
    * fit the entire new string there, just write there.
    */

But this case hardly ever triggers -- not once during SunSpider or V8, nor any
time during jit-tests.  It does trigger a few times during jstests.

(Note also that flatSetExtensible() is dead even before this patch.)

Sunspider results are below, you can see it's a tiny improvement, i.e. no loss.

Now, it's possible that this patch is a bad idea -- that EXTENSIBLE is a good
optimization but for some unknown reason isn't being applied nearly as often as
it should be.  I'd be happy to hear arguments along those lines.  Otherwise,
it's just unhelpful complexity.  Perhaps it was more effective pre-ropes?

(BTW, I read through bug 608778 in which jorendorff seemed to be arguing in
favour of making all non-atomic, non-shared string EXTENSIBLE.  To which I
again respond:  if extensible strings don't give us a performance boost, the
simplicity of non-estensible strings should be preferred.)

---------------------------------------------------------------
| millions of instructions executed                           |
| total                        | compiled (may overestimate)  |
---------------------------------------------------------------
|    69.029    69.027 (------) |    44.148    44.148 (------) | 3d-cube
|    39.709    39.708 (------) |    24.716    24.716 (------) | 3d-morph
|    64.515    64.505 (------) |    37.109    37.109 (------) | 3d-raytrace
|    24.317    24.316 (------) |    11.010    11.010 (------) | access-binary-
|    88.341    88.340 (------) |    83.306    83.306 (------) | access-fannkuc
|    28.193    28.192 (------) |    16.264    16.264 (------) | access-nbody
|    35.079    35.078 (------) |    28.735    28.735 (------) | access-nsieve
|     7.474     7.474 (------) |     3.255     3.255 (------) | bitops-3bit-bi
|    35.330    35.329 (------) |    30.400    30.400 (------) | bitops-bits-in
|    15.908    15.908 (------) |    12.019    12.019 (------) | bitops-bitwise
|    38.071    38.070 (------) |    32.966    32.966 (------) | bitops-nsieve-
|    17.048    17.047 (------) |    12.875    12.875 (------) | controlflow-re
|    23.575    23.573 (------) |    11.835    11.835 (------) | crypto-md5
|    19.572    19.570 (------) |     8.528     8.528 (------) | crypto-sha1
|    65.961    65.959 (------) |    21.184    21.184 (------) | date-format-to
|    61.975    61.853 (1.002x) |     9.944     9.944 (------) | date-format-xp
|    43.547    43.546 (------) |    29.513    29.513 (------) | math-cordic
|    22.898    22.897 (------) |     6.310     6.310 (------) | math-partial-s
|    31.257    31.256 (------) |    26.189    26.189 (------) | math-spectral-
|    48.487    48.486 (------) |    34.589    34.589 (------) | regexp-dna
|    28.604    28.473 (1.005x) |     9.272     9.272 (------) | string-base64
|    63.537    63.525 (------) |    31.954    31.954 (------) | string-fasta
|   102.360   102.261 (1.001x) |    17.218    17.218 (------) | string-tagclou
|    99.648    99.647 (------) |    12.992    12.992 (------) | string-unpack-
|    42.495    42.293 (1.005x) |     8.573     8.573 (------) | string-validat
-------
|  1116.939  1116.346 (1.001x) |   564.914   564.914 (------) | all
Attachment #492238 - Flags: review?(jorendorff)

Comment 1

7 years ago
Heh, I almost just did this in bug 609075 b/c of the same small measurable speedup.  In bug 609075 comment 3, I recalled how it avoids O(n^2) behavior where we are currently O(n).  What I did in bug 608776 is to push the extensibility checking to JSString::flatten which is (usually) colder than js_ConcatStrings.  Now, I have since decided to avoid the eager-malloc cost with bug 609440 (which I can resume now that bug 607292 is fixed-in-tracemonkey) instead.  The patch isn't written, but I had planned on doing a similar movement of the check.  Now, maybe the O(n^2) case isn't that important, but the runtime and complexity cost is low and it seems like it could show up in real code.
(Assignee)

Comment 2

7 years ago
Luke, sounds like you're recommending WONTFIX?
(Assignee)

Comment 3

7 years ago
I like the complexity reduction, but I'm remembering Brendan's mantra about 0(n^2) algorithms on the web.  Luke, can you remove flatSetExtensible() and add a comment that includes the code from bug 609075 so the utility of that case is clear?
Status: ASSIGNED → RESOLVED
Last Resolved: 7 years ago
Resolution: --- → WONTFIX

Comment 4

7 years ago
You bet.  I had already filed a personal TODO about the comment :)
Attachment #492238 - Flags: review?(jorendorff)
You need to log in before you can comment on or make changes to this bug.