Closed Bug 608120 Opened 9 years ago Closed 9 years ago

optimize js_ValueToString on int32s

Categories

(Core :: JavaScript Engine, defect)

defect
Not set

Tracking

()

RESOLVED FIXED

People

(Reporter: luke, Assigned: luke)

Details

(Whiteboard: fixed-in-tracemonkey)

Attachments

(1 file, 1 obsolete file)

Attached patch patch (obsolete) — Splinter Review
Given an int32 value, js_ValueToString calls js_NumberToString (which takes a double), which dynamically checks if the arg is an int, and converts into a buffer, then copies into a new string.

The attached patch adds js::Int32ToString and calls it from js_ValueToString.  This skips the double detour.  Also, Int32ToString can write chars directly into a JSShortString (since it is always big enough).

The following micro-bench shows a 37% speedup with the patch:

    var s = "ab";
    var t = 0;
    for (var i = 0; i < 10000000; ++i)
        s + i;

On date-format-xparb, Valgrind shows a reduction of 2M (2%) instructions and I can observe a .5ms speedup.
Attachment #486757 - Flags: review?(jwalden+bmo)
Comment on attachment 486757 [details] [diff] [review]
patch

>diff --git a/js/src/jsnum.cpp b/js/src/jsnum.cpp

>+    JS_STATIC_ASSERT(JSShortString::MAX_SHORT_STRING_LENGTH >= 11);

That magic 11 would be better as sizeof("-2147483648") - 1 (note your assertion seems off-by-one due to forgetting the potential minus sign).


>+    do {
>+        jsuint newui = ui / 10;
>+        *--cp = (char)(ui - newui * 10) + '0';
>+        ui = newui;
>+    } while (ui != 0);

This would be slightly clearer to me as:

>+    do {
>+        jsuint newui = ui / 10, digit = ui % 10;
>+        *--cp = '0' + digit;
>+        ui = newui;
>+    } while (ui != 0);

This conceivably might also help compilers that can't recognize your pattern as equivalent to modulus, by making the divmod operation more obvious.


>diff --git a/js/src/jsnum.h b/js/src/jsnum.h

> /*
>+ * This function first tries to use static int and length-2 strings before
>+ * falling back on short strings. All of this is faster to NumberToCString
>+ * follwed by js_NewStringCopyN.
>+ */
>+extern JSString *
>+Int32ToString(JSContext *cx, int32 i);

Your last sentence is mangled, please fix.

But is this description really necessary?  It doesn't seem like the reader should know about string optimizations that this function might perform, so long as the returned string is functionally equivalent to any other containing those characters, and it's pretty self-explanatory from the name.


>diff --git a/js/src/jsstr.cpp b/js/src/jsstr.cpp

>     } else if (v.isInt32()) {
>-        str = js_NumberToString(cx, v.toInt32());
>+        str = Int32ToString(cx, v.toInt32());
>     } else if (v.isDouble()) {

Right on.  Strange someone's spider sense didn't tingle writing or reviewing this...


This needs tests to deliberately check for proper conversion, rather than relying on existing tests to not change -- try checking the relevant numbers against the corresponding literal strings, for the ranges [-2147483649, -2147483647], [-1, 257], and [2147483646, 2147483648], should be easy to do.


Basically looks good, but there are enough little nits that I'd like to take a second look.
Attachment #486757 - Flags: review?(jwalden+bmo) → review-
(In reply to comment #1)
> This would be slightly clearer to me as:
> 
> >+    do {
> >+        jsuint newui = ui / 10, digit = ui % 10;
> >+        *--cp = '0' + digit;
> >+        ui = newui;
> >+    } while (ui != 0);
> 
> This conceivably might also help compilers that can't recognize your pattern as
> equivalent to modulus, by making the divmod operation more obvious.

I just cargo-culted this from IntToCString below (which says "We use multiply and subtraction instead of modulus because that's much faster").  I checked out the assembly, and, in both cases, they seem to avoid any integer division/modulus:

   mov $0xcccccccd,%eax
   mul %esi
   shr $0x3,%edx
   lea (%edx,%edx,4),%eax
   add %eax,%eax
   sub %eax,%esi
   mov %esi,%eax

I am now told this is to be expected: http://www.cs.uiowa.edu/~jones/bcd/divide.html.  So I'll go with the cleaner version :)
Attached patch patch 2Splinter Review
Assignee: general → lw
Attachment #486757 - Attachment is obsolete: true
Status: NEW → ASSIGNED
Attachment #488615 - Flags: review?(jwalden+bmo)
Comment on attachment 488615 [details] [diff] [review]
patch 2

>diff --git a/js/src/jsnum.cpp b/js/src/jsnum.cpp

>+    do {
>+        jsuint newui = ui / 10, digit = ui % 10;  /* optimizers are our friends */
>+        *--cp = (char)digit + '0';
>+        ui = newui;

|*--cp = '0' + digit| reads more clearly to me, is more idiomatic for SpiderMonkey (at least as far as I can remember for the pattern), and eliminates the cast.

Your range-testing code seems a little unorthodox (magical range of 260?), but it's mostly readable and works, so whatever, it's test code.  :-)
Attachment #488615 - Flags: review?(jwalden+bmo) → review+
http://hg.mozilla.org/tracemonkey/rev/95c792930e93
Whiteboard: fixed-in-tracemonkey
http://hg.mozilla.org/mozilla-central/rev/95c792930e93
Status: ASSIGNED → RESOLVED
Closed: 9 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.