578171 - Keep a static table of all length-2 strings

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Alan Pierce]

The sunspider test string-unpack-code spends about 7% of its time (about 1% of SS as a whole) in js_AtomizeString. Almost all of these calls are given strings of length 2, since the test packs symbols into base-62 strings and the number of symbols never goes above 62^2.

We can avoid almost all of this by keeping a table of length-2 strings, similar to unit strings and int strings. The unpacking code in string-unpack-code is reasonably common, so this change is probably justified.

Comment 1

[Alan Pierce]

Attachment: Sunspider before/after

The straightforward way to do this creates a gigantic static table (2MB on 64-bit x86, 1MB on 32-bit), which is probably an unacceptable amount to add to the shell binary for a relatively small optimization such as this. The table size can be cut down by a factor of 4 if we only statically store characters that fit in 7 bits, and another factor of 4 (for a total factor of 16) if we only store base-64 characters. There may be other ways around this, such as lazily filling in the table at runtime, or some other way to avoid the hash and comparison in js_AtomizeString.

That said, here are the results from implementing this the stupid way (with a 2MB table). unpack-code gets about 10% faster. The slowdowns in other places may be noise or may be legitimate slowdowns; it's hard to tell.

Comment 2

[Alan Pierce]

Attachment: Patch

The patch only special-cases alphanumeric length-2 strings, and keeps them in a 64 by 64 table (there are 62 alphanumeric characters, so there are 2 extra spots that aren't used right now). The table is 128K on x86-64, and 64K on 32-bit x86.

While I was at it, I made it so unit strings and int strings keep their characters in the string header (like JSShortStrings, but without the extra string header at the end).

Comment 3

[Alan Pierce]

Attachment: SunSpider before/after

With this patch, it's a pretty clear win on string-unpack-code, somewhere between 1% and 2% of SS as a whole.

Comment 4

[Nicholas Nethercote [inactive]]

(In reply to comment #2)
>
> The table is 128K on x86-64, and 64K on
> 32-bit x86.

That's still pretty big!

Comment 5

[Brendan Eich [:brendan]]

If pav is ok with it, it's not too big -- we dropped the Amiga port :->.

/be

Comment 6

[Brendan Eich [:brendan]]

Comment on attachment 460130 [details] [diff] [review]
Patch

Cool patch, sometimes you need the C pre-processor -- nothing else will do.

Prevailing style wants \ in column 79. Always.

/be

Comment 7

[Alan Pierce]

Attachment: Patch, v2

I fixed up the macros to always have the \ in column 79, and fixed a few minor style issues.

Comment 8

[Alan Pierce]

Here's a more detailed breakdown of the memory usage changes with the patch:

-I removed the UnitStringData table (unit strings now keep their information in the string header, so it's not necessary anymore), which had 256 entries, each one 4 bytes, so that's 1K removed.

-I added the tables toSmallChar (128 entries, each 2 bytes) and fromSmallChar (64 entries, each 2 bytes), so that's 384 bytes added.

-(The big one) I added length2StringTable, which has 4096 entries, each of which is 32 (on 64-bit) or 16 bytes (on 32-bit). So that's 128K or 64K added.

-I added deflatedLength2StringTable, which has 4096 entries, each of which is 3 bytes, so that's 12K added.

-I removed the table Hundreds, which had 156 entries, each of which is 8 bytes, so that's 1248 bytes removed.


The thought was that after compression, the table size won't be such a big deal. I compared the firefox installer/binary sizes on my tryserver build ( http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-a77321dd52e1/ ) compared with recent tinderbox builds for tracemonkey, and here's what I got:

Windows 32-bit:
Before:  8,878,301
After:   8,882,463

Mac 32-bit:
Before: 27,052,949
After:  27,095,777

Mac 64-bit:
Before: 15,524,082
After:  15,566,799

Linux 32-bit:
Before: 11,694,684
After:  11,630,299

Linux 64-bit:
Before: 13,131,544
After:  13,163,918

(yes, it seems to be saying that the Linux 32-bit binary got smaller)

The tryserver build also has maemo and android numbers, but I couldn't find a tinderbox build for reference.


If we need to get the table size down, here are a few (undesirable, in my opinion) options:

-We only really need the first half of string headers for statically defined strings. The last half is currently (with my change) used to store the string data itself, but we could move that string data into a separate table, and have the string header point into that table. This would let us have a table of half-string-headers. This may break some assumptions about JSString alignment elsewhere in the code, so I'd have to investigate that. This would reduce the table size by 5/16 on 64-bit and 1/16 on 32-bit.

-Since the string-unpack-code test never uses more than 1976 distinct base-62 values, we could only generate the bottom half of the 2-digit base-62 space and still get the same speedup on the benchmark. This would cut our table size in half, at the cost of some added complexity and fewer real-world cases where the change helps.

Comment 9

[Brendan Eich [:brendan]]

I'm going to make an executive decision that we don't need to reduce table size here. Anyone want to impeach me?

/be

Comment 10

[Mike Shaver (:shaver emeritus)]

I support your brave and patriotic choice.

Comment 11

[Luke Wagner [:luke]]

Comment on attachment 460313 [details] [diff] [review]
Patch, v2

Great job!  I like R.

>+jschar JSString::toSmallChar[] = { R7(0) };

Is there any reason this can't be a uint8/char?  Also, it would be nice to have a syntactic distinction between small chars and jschars.  Something like a member typedef in JSString:

  typedef uint8 SmallChar;

Used everywhere for SmallChars.

>+        } e; /* Grr, no anonymous structs in ISO C++. */

I understand the frustration, but this shows up in enough places that we probably don't need the comment.

>+inline JSString *
> JSString::intString(jsint i)
> {
>     jsuint u = jsuint(i);
> 
>     JS_ASSERT(u < INT_STRING_LIMIT);
>     if (u < 10) {
>         /* To avoid two ATOMIZED JSString copies of 0-9. */
>         return &JSString::unitStringTable['0' + u];
>     }
>+    if (u < 100)
>+        return length2String('0' + (u / 10), '0' + (u % 10));
>     return &JSString::intStringTable[u];
> }

So js_AtomizeString avoids calling JSString::intString(i) with i < 100, but I see a few other potentially-hot intString calls which are now going to be smacked with an integer division.  It's probably not a huge deal.  I played with:

var x = 99;
for (var i = 0; i < 1000000; ++i) {
    x.toString();
    x.toString();
    x.toString();
    x.toString();
    x.toString();
}

and switching from 99 to 100 made it run about 3ms (10%) slower.  Perhaps you could try out a table mapping [0-99] --> JSString* ?

Comment 12

[Alan Pierce]

Attachment: Patch, v3

I added a JSString::SmallChar type, typedefed as uint8 and I use it when appropriate. One potential issue is that when indexing into the short string table with two short strings, we need to generate a table that is more than 8 bits, so we need a cast, so maybe it's better to define SmallChar to be bigger.

To solve the int string issue, I redid the way we store int strings. The table of int string headers now just keeps strings for the numbers 100 through 255 (the lower ones were being wasted before), and the new intStringTable is an array of pointers, each one pointing to the correct int string (which might be a unit string a length-2 string).

Comment 13

[Luke Wagner [:luke]]

Comment on attachment 460471 [details] [diff] [review]
Patch, v3

Thanks!  For fun I compared on SS and it saw a 2% (11ms) speedup.

Comment 14

[Luke Wagner [:luke]]

http://hg.mozilla.org/tracemonkey/rev/04dd1a764b5a

Comment 15

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/04dd1a764b5a