Closed Bug 601689 Opened 14 years ago Closed 14 years ago

Optimize GetArrayElement for unmodified arguments objects

Categories

(Core :: JavaScript Engine, enhancement)

enhancement
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: evilpie, Unassigned)

Details

(Whiteboard: fixed-in-tracemonkey)

Attachments

(1 file, 3 obsolete files)

User-Agent:       Mozilla/5.0 (Windows NT 5.1; rv:2.0b7pre) Gecko/20101004 Firefox/4.0b7pre
Build Identifier: 

I found this benchmark 
http://kangax.github.com/jstests/arguments-arrayfication-test/
and started to wonder if this could be made faster. So digged a bit into the array code and eventually came up with a patch. For example it makes Array.forEach about 2x faster. You might check if normal arrays suffer to much (i currently see a 1 ms slowdon on Array.forEach, but i am not perfectly sure).

Reproducible: Always
Attached patch patch for GetArrayElement (obsolete) — Splinter Review
Me silly forgot to do to the test, and boom bug.
OS: Windows XP → All
Hardware: x86 → All
Status: UNCONFIRMED → NEW
Ever confirmed: true
Once you're happy with the patch (comment 2 is not making me sure you are), ask for review?
Great find Tom!  I think there is an additional piece missing: if the arguments object is for an active call, then obj->getArgsElement(i) doesn't give you the live arguments value, for that, you need to consult the stack frame.  Also, I don't think the overridden-ness of the length matters unless you are specifically looking up 'arguments.length'.  So I'm thinking:

 } else if (obj->isArguments() && index < obj->getArgsInitialLength() && 
            !(*vp = obj->getArgsElement(index)).isMagic(JS_ARRAY_HOLE)) {       
     *hole = JS_FALSE;
     if (JSStackFrame *fp = (JSStackFrame *)obj->getPrivate())
         *vp = fp->canonicalActualArg(i);
     return JS_TRUE;
 }
Comment on attachment 480689 [details] [diff] [review]
patch for GetArrayElement

>diff --git a/js/src/jsarray.cpp b/js/src/jsarray.cpp
>--- a/js/src/jsarray.cpp
>+++ b/js/src/jsarray.cpp
>@@ -451,16 +451,22 @@ GetArrayElement(JSContext *cx, JSObject 
>                 Value *vp)
> {
>     JS_ASSERT(index >= 0);
>     if (obj->isDenseArray() && index < obj->getDenseArrayCapacity() &&
>         !(*vp = obj->getDenseArrayElement(uint32(index))).isMagic(JS_ARRAY_HOLE)) {
>         *hole = JS_FALSE;
>         return JS_TRUE;
>     }
>+    else 

No else after return.

>+    if (obj->isArguments() && !obj->isArgsLengthOverridden() && 
>+        index < obj->getArgsInitialLength() && 
>+        !(*vp = obj->getArgsElement(index)).isMagic(JS_ARRAY_HOLE)) {        
>+        *hole = JS_FALSE;
>+        return JS_TRUE;
>+    }

Nice!

One nit: you might break after the first &&, just as after the rest -- that's typical style.

/be
Dont get to exicted yet, there is an bug because of some mysterious thing in es3. But i except to fix this tomorrow.
So my fixed patch works perfectly fine with mehtodjit, but at the point the tracer kicks in, i get access violation exception. What i found out is that the tracer has some special method for arguments. I have no idea how to access the arguments while tracing.
Attached patch working patch (obsolete) — Splinter Review
This patch actually works and passes all tests, but there is on mayor drawback which bugs me. When you create an new arguments object while tracing (eg by calling a function and retuning it arguments object), this patch gets useless.
Its still good for all other cases. I would love to hear of an solution.
Attachment #480689 - Attachment is obsolete: true
Attachment #480911 - Flags: review?(jorendorff)
Comment on attachment 480911 [details] [diff] [review]
working patch

>+        !obj->isArgsLengthOverridden()  &&

I still don't think this is necessary, or am I missing something?

>+        if (fp != JS_ARGUMENTS_OBJECT_ON_TRACE) {
>+            if (fp)
>+                *vp = fp->canonicalActualArg(index);
>+            return JS_TRUE;
>+        }

Good catch with the args-on-trace!

Nit: the two conditions can be merged: (fp && fp != JS_ARGUMENTS_OBJECT_ON_TRACE)
1. Last time i removed it i got tons about 5 test failures but i am rechecking.
2. I think this is correct.
   if fp == JS_ARGUMENTS_OBJECT_ON_TRACE
      goto normal way
   else
     if fp is defined
       set to canonicalActualArg
     else
       do nothing (will use vp from getArgArrayElement)
     return
Okay checked again 
>+        !obj->isArgsLengthOverridden()  &&
is not needed, must have been fallout from some other bug while working on the patch.
(In reply to comment #10)
2. yes, you are right, sorry, my brain was not all the way on yet :)

I also noticed you will need to add jsinterpinlines.h to the top of jsarray.cpp so that canonicalActualArg will be inlined.
Attached patch final patch (obsolete) — Splinter Review
Attachment #480911 - Attachment is obsolete: true
Attachment #480911 - Flags: review?(jorendorff)
Comment on attachment 480949 [details] [diff] [review]
final patch

>diff --git a/js/src/jsarray.cpp b/js/src/jsarray.cpp
>--- a/js/src/jsarray.cpp
>+++ b/js/src/jsarray.cpp
>@@ -100,16 +100,17 @@
> #include "jsscope.h"
> #include "jsstr.h"
> #include "jsstaticcheck.h"
> #include "jsvector.h"
> 
> #include "jsatominlines.h"
> #include "jsobjinlines.h"
> #include "jscntxtinlines.h"
>+#include "jsinterpinlines.h"
> 
> using namespace js;
> using namespace js::gc;
> 
> /* 2^32 - 1 as a number and a string */
> #define MAXINDEX 4294967295u
> #define MAXSTR   "4294967295"
> 
>@@ -444,23 +445,34 @@ IndexToId(JSContext* cx, JSObject* obj, 
>  * If the property at the given index exists, get its value into location
>  * pointed by vp and set *hole to false. Otherwise set *hole to true and *vp
>  * to JSVAL_VOID. This function assumes that the location pointed by vp is
>  * properly rooted and can be used as GC-protected storage for temporaries.
>  */
> static JSBool
> GetArrayElement(JSContext *cx, JSObject *obj, jsdouble index, JSBool *hole,
>                 Value *vp)
>{
>     JS_ASSERT(index >= 0);
>     if (obj->isDenseArray() && index < obj->getDenseArrayCapacity() &&
>         !(*vp = obj->getDenseArrayElement(uint32(index))).isMagic(JS_ARRAY_HOLE)) {
>         *hole = JS_FALSE;
>         return JS_TRUE;
>     }
>+    if (obj->isArguments() &&
>+        index < obj->getArgsInitialLength() &&
>+        !(*vp = obj->getArgsElement(uint32(index))).isMagic(JS_ARRAY_HOLE)) {
>+        *hole = JS_FALSE;   
>+        JSStackFrame *fp = (JSStackFrame *)obj->getPrivate();
>+        if (fp != JS_ARGUMENTS_OBJECT_ON_TRACE) {
>+            if (fp)
>+                *vp = fp->canonicalActualArg(index);
>+            return JS_TRUE;
>+        }
>+    }        
> 
>     AutoIdRooter idr(cx);
> 
>     *hole = JS_FALSE;
>     if (!IndexToId(cx, obj, index, hole, idr.addr()))
>         return JS_FALSE;
>     if (*hole) {
>         vp->setUndefined();
Attachment #480949 - Attachment description: final? patch → final patch
Attachment #480949 - Flags: review?(lw)
I don't think anything can be done to keep us on trace (yet). Note that to even test with tracing you need two loops: an outer JS loop and some inner C++ loop in jsarray.cpp that calls GetArrayElement.

The first time the inner loop calls GetArrayElement on trace, we will take the slow path, which ends up in ArgGetter, which calls LeaveTrace(). That will modify obj->private, and from then on the inner loop will hit the fast path here. So it should go fast.

But once the inner loop is done, the outer loop will put us on trace again, so we'll do the same thing next time. Not exactly pretty.
Comment on attachment 480949 [details] [diff] [review]
final patch

> static JSBool
> GetArrayElement(JSContext *cx, JSObject *obj, jsdouble index, JSBool *hole,
>                 Value *vp)
>-{
>+{    

You added some trailing whitespace. I'll get rid of it.

>         !(*vp = obj->getDenseArrayElement(uint32(index))).isMagic(JS_ARRAY_HOLE)) {
>         *hole = JS_FALSE;
>         return JS_TRUE;
>-    }
>+    }   

Here too.

>+    if (obj->isArguments() &&
>+        index < obj->getArgsInitialLength() &&
>+        !(*vp = obj->getArgsElement(uint32(index))).isMagic(JS_ARRAY_HOLE)) {
>+        *hole = JS_FALSE;   
>+        JSStackFrame *fp = (JSStackFrame *)obj->getPrivate();
>+        if (fp != JS_ARGUMENTS_OBJECT_ON_TRACE) {
>+            if (fp)
>+                *vp = fp->canonicalActualArg(index);
>+            return JS_TRUE;
>+        }
>+    }        

jimb, is this OK for strict arguments? If not, hit us with a test?
Attachment #480949 - Flags: review?(jimb)
Attachment #480949 - Attachment is obsolete: true
Attachment #480969 - Flags: review?(lw)
Attachment #480949 - Flags: review?(lw)
Attachment #480949 - Flags: review?(jimb)
Comment on attachment 480969 [details] [diff] [review]
wont call patches final anymore

Looks good to me.  Waldo checked for strict-arguments problems and found none.
Attachment #480969 - Flags: review?(lw) → review+
On a micro-benchmark I just wrote that does:
  Array.forEach(arguments, function(x) { return x+1 });
for 20 arguments, 3.3x speedup (even without bug 581893), so cool!
http://hg.mozilla.org/mozilla-central/rev/10f5615936c1
Status: NEW → RESOLVED
Closed: 14 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.