639883 - use a JSString (not JSShortString) for strlen < 4

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Luke Wagner [:luke]]

For string lengths < 4, we can just use the 4 inline chars of a JSString without creating a JSShortString.  Even better, there are several paths (js_NewStringCopy*, js_ConcatStrings) where we don't attempt to use static strings.  Static string lookup isn't free, so measurement is required to get a feel for how often this would apply.

Comment 1

[Nicholas Nethercote [inactive]]

True.  JSShortString is something of a misnomer, then :)

Comment 2

[Luke Wagner [:luke]]

Attachment: WIP 1

WIP

Comment 3

[Luke Wagner [:luke]]

Attachment: rm js_FinalizeStringRT

I had a bug in WIP 1 because I forgot about js_FinalizeStringRT.  This function may have done more stuff a while ago but, now, its just the finalizer for atoms (where we don't already know the arena).  So this function makes a JSAtom::finalize and factors finalization of flat strings so that WIP 1 wouldn't have had a bug.

Comment 4

[Luke Wagner [:luke]]

Attachment: use a single JSString header when it fits

The patch is pretty simple.  I added atomized/unatomized (JSInlineString/JSInlineAtom) types to represent this new set of cases.

On the microbenchmark:

  a = [X]
  for (var i = 0; i < Y; ++i)
    a.join('')

I get a pretty reliable 10-12% speedup for Y = { 50K, 500K, 5M } and X = { ['a'], ['a','b'], ['a','b','c']}.  Cachegrind shows me that the icount is about the same (actually a teensy bit worse b/c of extra logic to choose JSInlineString) but the number of L2 refs is almost cut in half.  SS/V8 are unaffected.

So what about the other part of comment 0, viz., adding lookupStatic?  Clearly, for any micro-benchmark where it hits every time, its a big speedup.  However, when it doesn't hit and JSInlineString *does* hit (e.g., X = ['a', 'b', 'c'] above) the speedup from JSInlineString seems to be neutralized by the extra lookupStatic logic.

So the question is: how much does lookupStatic (in js_NewStringCopy*) hit?  I instrumented a browser to measure all strings created along the js_NewStringCopy* path, and then how many of these strings hit the different optimizations:

                      total   JSShortString JSInlineString JSStaticAtom
V8                    45.0K   12.3K           .3K           .6K
SS                    11.3K    4.8K           .9K           ~0
Gmail session         60.5K   18.8K         19.5K           .6K
Zimbra session        56.2K   18.5K          1.5K           .2K
news.google+browsing  98.0K   41.0K          5.7K          1.7K
280 slides session    31.0K    8.8K           .6K           .1K
google.com+1 search   20.5K    7.7K           .7K           ~0
twitter session       32.5K   12.4K          1.0K           .4K
Facebook session      43.3K   15.7K          1.7K           .9K
random browsing      234.0K   81.0K         20.0K          9.0K

Notes:
 - K is not bytes, but number of strings
 - "JSStaticAtom" column is not total number of JSStaticAtom hits, just number of *new* JSStaticAtoms hits we can return from js_NewStringCopy* paths (where we don't now)
 - JSInlineString+JSStaticAtom+JSShortString = number of JSShortStrings we *currently* create

Conclusions:
 - The real webz definitely benefit from JSShortString.
 - Sometimes, JSInlineString helps a lot (Sayre pointed out that sites using packers (like GMail above) are going to have a lot of short strings).
 - Given that each JSInlineString is saving 4 words in the GC heap, JSInlineString's benefit will mostly be cache locality, not overall memory usage.
 - We are not missing many JSStaticAtoms.  Several hot clients (e.g., Atomize) already do the check so adding lookupStatic to js_NewStringCopy* for those paths is wasted computation.

Therefore, this patch does create inline strings but does not add JSAtom::lookupStatic.

Comment 5

[Nicholas Nethercote [inactive]]

Comment on attachment 523204 [details] [diff] [review]
use a single JSString header when it fits

>+            jschar                 inlineStorage[NUM_INLINE_CHARS]; /* JS(Inline,Short)String */

I've seen you use that syntax before.  It doesn't matter, but wouldn't
"JS{Inline,Short}String" (a la bash) or "JS(Inline|Short)String" (a la
regexps) be better?

>      *   JSRope                xxx1
>      *   JSLinearString        xxx0
>      *   JSDependentString     xx1x
>      *   JSFlatString          xx00
>      *   JSExtensibleString    1100
>      *   JSFixedString         xy00 where xy != 11
>+     *   JSInlineString        0100 and chars != inlineStorage
>      *   JSShortString         0100 and in FINALIZE_SHORT_STRING arena
>      *   JSExternalString      0100 and in FINALIZE_EXTERNAL_STRING arena

Shouldn't that be "chars == inlineStorage" for JSInlineString?

The rest looks fine.  Two thumbs up for the detailed measurements.

Comment 6

[Igor Bukanov]

Comment on attachment 523196 [details] [diff] [review]
rm js_FinalizeStringRT

Nice!

Comment 7

[Luke Wagner [:luke]]

(In reply to comment #5)
Yes and yes, thanks!

Comment 8

[Luke Wagner [:luke]]

http://hg.mozilla.org/tracemonkey/rev/77c996c34974
http://hg.mozilla.org/tracemonkey/rev/6dd4f6649105

Comment 9

[Chris Leary [:cdleary] (not checking bugmail)]

http://hg.mozilla.org/mozilla-central/rev/77c996c34974
http://hg.mozilla.org/mozilla-central/rev/6dd4f6649105