Closed Bug 419152 Opened 12 years ago Closed 12 years ago

base64 test shows lots of time in str_resolve

Categories

(Core :: JavaScript Engine, defect)

x86
macOS
defect
Not set

Tracking

()

VERIFIED FIXED
mozilla1.9beta4

People

(Reporter: sayrer, Assigned: shaver)

References

Details

(Keywords: perf)

Attachments

(1 file, 6 obsolete files)

46% in 
js_GetProperty-->js_LookupPropertyWithFlags-->str_resolve->js_DefineProperty
Wonder if we can do something here like we do with arrays, which no longer has to define props for index access...
Improves base64 a ton, but hurts all other string tests, likely because we're allocating a new depstring for every get.  5% net win on strings, next step is to cache the depstrings in a dense vector: tonight!
Keywords: perf
So, I played a little with allocating a dense vector of jsvals to cache the depstrings, but I ended up regressing base64 perf more than 10x: spent most of my time initializing the vector for 24K strings which access only a handful of elements.  (To say nothing of the time spent tracing that vector in GC, ahem.)

Skip list for them might work, or atomizing in the ASCII case?  Clearly I need to think more about it...
With 64vals, we can probably just stick one-char strings in the jsval proper, and this will be unmitigated win, so maybe I'll just wait on that?
Comment on attachment 305193 [details] [diff] [review]
WIP: avoid property definition for elements

Too much code (to paraphrase the Emperor in "Amadeus"). First, you should use js_GetUnitString -- and so should str_resolve already (my bad, sorry!).

Second, the real point: no need for all this specialization. Just put a fast path directly in JSOP_GETELEM's case, based on string lval and in-range index.

/be
Attachment #305193 - Flags: review-
See, we really want (always) to strive to

* stay in js_Interpret
* avoid wrapping primitives in object clothing
* use memoized common values
* avoid exploding jsval type tag combinatorics

The last is why I do not intend to add a single-char type. js_GetUnitString ftw!

Shaver, thanks for taking this. Don't forget str_resolve needing to call js_GetUnitString (backstop for API usage, e.g., JS_GetElement). Thanks,

/be
Assignee: general → shaver
Flags: blocking1.9+
Target Milestone: --- → mozilla1.9beta4
Version: unspecified → Trunk
This destroys base64 (205 to 75), but hurts md5 by 39% and a bunch of others by a few percent, probably due to alignment effects?  Not sure what our current plan is there, but until then it's a net win of only like 2% overall on my MBP for a non-threadsafe shell.  Should we land it anyway?

It's sort of tempting to specialize GETELEM for dense arrays, too, I must confess...
Attachment #305193 - Attachment is obsolete: true
Attachment #305280 - Flags: review?(brendan)
> It's sort of tempting to specialize GETELEM for dense arrays, too, I must
> confess...

Too tempting!  I cannot contain myself!
Attachment #305280 - Attachment is obsolete: true
Attachment #305282 - Flags: review?(brendan)
Attachment #305280 - Flags: review?(brendan)
I mean, while I'm in here, let's see about shaving off some more array access time, amirite?
Attachment #305282 - Attachment is obsolete: true
Attachment #305286 - Flags: review?
Attachment #305282 - Flags: review?(brendan)
I'll request review after I mochi, but won't turn away comments before that!
Attachment #305286 - Attachment is obsolete: true
Attachment #305286 - Flags: review?
Test fodder:

With bug:
js> a = [1,2,3];
1,2,3
js> a[5] = 6
6
js> a
1,2,3
js> a.length
3

Without bug:
js> a = [1,2,3]
1,2,3
js> a[5] = 6;
6
js> a
1,2,3,,,6
js> a.length
6
Comment on attachment 305287 [details] [diff] [review]
5: when storing between LENGTH and DENSELEN, update LENGTH

>+#define ARRAY_DENSELEN(obj) ((obj)->dslots ? (uint32)(obj)->dslots[-1] : 0)

Finally dawned on me that ARRAY_DENSELEN looks funny, esp. with names like JSSLOT_ARRAY_LENGTH nearby. How about ARRAY_DENSE_LENGTH?

>+          {
>+            /* Open-coded ELEMENT_OP specialized for "string"[i]. */
>+            jsval idval;

Use rval, no need for a local.

>+                int32 i;

jsint i is in js_Interpret's body block, use it.

>+                JSString *str, *unit;

str and str2 are in js_Interpret too.

>+                str = JSVAL_TO_STRING(lval);
>+                i = JSVAL_TO_INT(idval);
>+                if (i < JSSTRING_LENGTH(str)) {
>+                    unit = js_GetUnitString(cx, JSSTRING_CHARS(str)[i]);

But you really only need str -- note how its previous value dies here.

>+                    if (!unit)
>+                        goto error;
>+                    rval = STRING_TO_JSVAL(unit);
>+                    goto end_getelem;
>+                }
>+            }
>+            VALUE_TO_OBJECT(cx, -2, lval, obj);
>+            if (JSVAL_IS_INT(idval)) {
>+                if (OBJ_IS_DENSE_ARRAY(cx, obj)) {
>+                    jsuint denselen;
>+                    jsint i;

Again, use outer scope i.

>+                    denselen = ARRAY_DENSELEN(obj);

Why not use ARRAY_LENGTH(obj) (and call the block-local length, to match other places)? I use JSSLOT_ARRAY_LENGTH in a few other places (JSOP_LENGTH, JSOP_ARRAYPUSH), so you could imitated, but since you're exporting formerly file-local macros via jsarray.h, please fix those to use ARRAY_LENGTH(obj) too.

>@@ -4398,7 +4439,28 @@ interrupt:
> 
>           BEGIN_CASE(JSOP_SETELEM)
>             rval = FETCH_OPND(-1);
>-            ELEMENT_OP(-2, OBJ_SET_PROPERTY(cx, obj, id, &rval));
>+            SAVE_SP_AND_PC(fp);
>+            FETCH_OBJECT(cx, -3, lval, obj);
>+            FETCH_ELEMENT_ID(obj, -2, id);
>+            if (OBJ_IS_DENSE_ARRAY(cx, obj) && JSID_IS_INT(id)) {
>+                jsuint denselen;
>+                jsint i;

Ditto: length, outer i.

>+
>+                denselen = ARRAY_DENSELEN(obj);
>+                i = JSID_TO_INT(id);
>+                if (i < denselen) {
>+                    if (obj->dslots[i] == JSVAL_HOLE) {
>+                        if (i >= obj->fslots[JSSLOT_ARRAY_LENGTH])
>+                            obj->fslots[JSSLOT_ARRAY_LENGTH] = i + 1;
>+                        obj->fslots[JSSLOT_ARRAY_COUNT]++;

Hmm, maybe the macros just obscure the facts and micro-economics. I'd rather obj->fslots[JSSLOT_ARRAY_COUNT]++ than get, bump, and set tedium. In this light, reconsider exporting ARRAY_DENSELEN? Could use STOBJ_NSLOTS or equivalent.

Oh, that reminds me: you could be racing with an obj->dslots reallocator, so lock obj around shortest-path critical sections.

/be
I use DENSELEN because LENGTH can exceed the allocated storage (and often does, if it's set explicitly).  And DENSELEN can exceed LENGTH due to the realloc amortization.

I think I prefer the direct slot use too, indeed.  Can't lock obj until arrays get titles; crowder's working on that, which will need to include adding locking in these cases as well.

I'll update tmw, thanks!
DENSELEN makes me think of false cognates from natural languages (kind of like an inverted version of the Americans taking offense in Whit Stillman's film "Barcelona" at the way the Spaniards pronounce "EstaduniDENSE". Want to read "DENSElen" or "denseLEN" with stress. Anyway...

/be
Oh, sorry, I meant "I am checking the dense length here, rather than the length property, because...", not defending the awkward DENSELEN naming itself.  I shall repair to my editor posthaste and address your righteous commentary!
More test fodder:

a = [1,2,3,4];
a[-1] === undefined

s = "abcdef";
s[-1] === s.length /* I was surprised to discover this! */
s[-2] === undefined
Et encore:

a = [1,2,3];
a[-1] = 55;
a.length === 3
a.toString() === "1,2,3"
(In reply to comment #16)
> s[-1] === s.length /* I was surprised to discover this! */

This happens because String.length has a tinyid of -1 and the get hook can't tell the difference between getting a property '-1' and getting a tinyid of -1.
(In reply to comment #16)
> s[-1] === s.length /* I was surprised to discover this! */

I don't think this should be preserved; ES4 doesn't preserve this (value is |undefined|) and Safari doesn't emulate it.  Dunno about IE...
Also, it's hard to believe someone could unintentionally rely on that, since they'd have to be absolutely insane to intentionally rely on it.
jQuery can pass us -1 as an index to an empty array (which is how I encountered the bug, since I crashed then, ahem), but I doubt they rely on getting a 0 back.  Suspect they just test the truthiness of the result.

Embolden me while I rebuild and remochi with updated rest-of-tree!
The tinyid equivalence with negative index is as old as the hills (older), do not burden this bug with it. Don't add it where it did not exist before (i.e., don't add it to Array!).

Waldo, please file a bug if one isn't on file already (mrbkap may know of one).

/be
Status: NEW → ASSIGNED
Attached patch 6: reporting for duty (obsolete) — Splinter Review
Mochis clean, test-suites clean, handles the cases elaborated in this bug's test-fodder comments.  I would like to contribute this to our primary source repository!
Attachment #305412 - Flags: review?(brendan)
Comment on attachment 305412 [details] [diff] [review]
6: reporting for duty

>@@ -653,7 +645,7 @@ array_lookupProperty(JSContext *cx, JSOb
>      */
>     if ((!js_IdIsIndex(id, &i) &&
>          id != ATOM_TO_JSID(cx->runtime->atomState.lengthAtom)) ||
>-        ARRAY_LENGTH(obj) == 0 || i >= ARRAY_DENSELEN(obj) ||
>+        obj->fslots[JSSLOT_ARRAY_LENGTH] == 0 || i >= ARRAY_DENSE_LENGTH(obj) ||
..12345678901234567890123456789012345678901234567890123456789012345678901234567890

Nit: 80th column violation.

>+++ b/jsinterp.c	Sun Feb 24 14:47:19 2008 -0500
>@@ -4381,7 +4381,54 @@ interrupt:
>           END_CASE(JSOP_SETPROP)
> 
>           BEGIN_CASE(JSOP_GETELEM)
>-            ELEMENT_OP(-1, OBJ_GET_PROPERTY(cx, obj, id, &rval));
>+            /* Open-coded ELEMENT_OP optimized for strings and dense arrays. */
>+            SAVE_SP_AND_PC(fp);
>+            lval = FETCH_OPND(-2);
>+            rval = FETCH_OPND(-1);
>+            if (JSVAL_IS_STRING(lval) && JSVAL_IS_INT(rval)) {
>+                str = JSVAL_TO_STRING(lval);
>+                i = JSVAL_TO_INT(rval);
>+                if (i < 0) {
>+                    if (i == -1)
>+                        rval = INT_TO_JSVAL(JSSTRING_LENGTH(str));
>+                    else
>+                        rval = JSVAL_VOID;

Common the LHS via rval = ... ? ... : ...;

tinyid backward compat ftw, I guess. Thanks to Waldo, we have a bug which will get fixed and remove some code.

>+                    goto end_getelem;
>+                }
>+                if (i < (int32)JSSTRING_LENGTH(str)) {

At which point we could get rid of the i < 0 test and compare (size_t)i < JSSTRING_LENGTH(str) here, to let all the overlarge and negative indexes cause a full OBJ_GET_PROPERTY.

>+                    length = ARRAY_DENSE_LENGTH(obj);
>+                    i = JSVAL_TO_INT(rval);
>+                    if (i < 0) {
>+                        rval = JSVAL_VOID;
>+                        goto end_getelem;
>+                    }

Ok, if it was dense then it can't have negative indexes. But you could make those pay by falling into the OBJ_GET_PROPERTY, saving some code above (the if-then goes away), and changing this:

>+                    if (i < (int32)length && 

to (jsuint)i < length.

>+                        i < obj->fslots[JSSLOT_ARRAY_LENGTH]) {

Given the left operand of &&, this needs no casting.

>           BEGIN_CASE(JSOP_SETELEM)
>             rval = FETCH_OPND(-1);
>-            ELEMENT_OP(-2, OBJ_SET_PROPERTY(cx, obj, id, &rval));
>+            SAVE_SP_AND_PC(fp);
>+            FETCH_OBJECT(cx, -3, lval, obj);
>+            FETCH_ELEMENT_ID(obj, -2, id);
>+            if (OBJ_IS_DENSE_ARRAY(cx, obj) && JSID_IS_INT(id)) {
>+                jsuint length;
>+
>+                length = ARRAY_DENSE_LENGTH(obj);
>+                i = JSID_TO_INT(id);
>+                if (i < 0)
>+                    goto end_setelem;

This can't be right, it breaks the following:

js> a=[1,2,3]
1,2,3
js> a[-1]=4
4
js> a
1,2,3
js> a[-1]
4

>+                if (i < (int32)length) {

Again, you just want (jsuint)i < length here, and let the negative and overlarge index cases fall into the OBJ_SET_PROPERTY.

/be
If this doesn't pass review, why, why I'll edit it again, that's what I'll do!
Attachment #305287 - Attachment is obsolete: true
Attachment #305412 - Attachment is obsolete: true
Attachment #305573 - Flags: review?(brendan)
Attachment #305412 - Flags: review?(brendan)
Comment on attachment 305573 [details] [diff] [review]
7: let -ves and out of bounds eat OBJ_[GS]ET_PROPERTY

 >@@ -653,8 +645,8 @@ array_lookupProperty(JSContext *cx, JSOb
>      */
>     if ((!js_IdIsIndex(id, &i) &&
>          id != ATOM_TO_JSID(cx->runtime->atomState.lengthAtom)) ||
>-        ARRAY_LENGTH(obj) == 0 || i >= ARRAY_DENSELEN(obj) ||
>-        obj->dslots[i] == JSVAL_HOLE) {
>+        obj->fslots[JSSLOT_ARRAY_LENGTH] == 0 ||
>+        i >= ARRAY_DENSE_LENGTH(obj) || obj->dslots[i] == JSVAL_HOLE) {

Nit: once one bad boy is overlong and forces wrapping after || or &&, do 'em all -- easier to read for each clause and not miss one hiding out on the right.

Great (via interdiff) otherwise. I may land ASAP to get my further work merged on top without having to switch to hg or quilt, and for the good of the tree.

/be
Attachment #305573 - Flags: review?(brendan)
Attachment #305573 - Flags: review+
Attachment #305573 - Flags: approval1.9+
I committed like so:

$ cvs ci -m"Shaver's huge patch for 419152 (Huge, I say; r=me)." `cat shaver.list`

js/src/jsarray.c 3.161
js/src/jsarray.h 3.25
js/src/jsinterp.c 3.442
js/src/jsstr.c 3.196

/be
Status: ASSIGNED → RESOLVED
Closed: 12 years ago
Resolution: --- → FIXED
Letting indices >= length but < dense_length go to OBJ_SET_PROPERTY costs us in the common appending case, I believe (verifying in a minute; 3d-raytrace has this behaviour, IIRC).  Specifically, it'll cause us to hit OBJ_GET_PROPERTY every time we do |a[a.length = foo|, whereas with the earlier code from this bug we only hit that every 8th time, because of the amortized growth via EnsureLength.

I will add another patch here to restore that behaviour, once I am done with the testing.
I would like to strike my previous comment from the record.
Depends on: 419593
testcase fodder but not underlying timing issues.

/cvsroot/mozilla/js/tests/ecma_3/Regress/regress-419152.js,v  <--  regress-419152.js
initial revision: 1.1
Flags: in-testsuite+
Flags: in-litmus-
v 1.9.0 ecma_3/Regress/regress-419152.js only.
Status: RESOLVED → VERIFIED
You need to log in before you can comment on or make changes to this bug.