Closed Bug 403878 Opened 17 years ago Closed 17 years ago

Replacing js_InternalCall => js_Invoke in Array.sort implementation

Categories

(Core :: JavaScript Engine, enhancement, P2)

enhancement

Tracking

()

RESOLVED FIXED
mozilla1.9beta2

People

(Reporter: igor, Assigned: crowderbt)

References

Details

Attachments

(1 file, 2 obsolete files)

[This is a spin-off of bug 371636 comment 18.]

Currently sort_compare from jsarray.c uses js_InternalCall to invoke the comparator function. This is suboptimal since it adds an overhead of js_AllocStack/js_FreeCall for each compare operation. It would be nice to allocate the stack only once as array_extra implementation does.
Assignee: general → crowder
Flags: blocking1.9+
Priority: -- → P2
Attached patch Implementation v1 (obsolete) — Splinter Review
Seemed too easy, but it works in my testing.  I will run the full testsuite if this looks right to Igor.
Attachment #289059 - Flags: review?(igor)
Comment on attachment 289059 [details] [diff] [review]
Implementation v1

>-        ok = js_InternalCall(cx,
>-                             OBJ_GET_PARENT(cx, JSVAL_TO_OBJECT(fval)),
>-                             fval, 2, argv, ca->localroot);
>+        invokevp = ca->elemroot + 1;
>+        sp = invokevp;
>+        *sp++ = ca->fval;
>+        *sp++ = JSVAL_NULL;;

Single ; is good enough here ;)

>+        void *mark;
>+
>         ca.context = cx;
>         ca.fval = fval;
>         /* local GC root for temporary string */
>         ca.localroot = &vec[tvr.count++];
>         *ca.localroot = JSVAL_NULL;
>+        ca.elemroot  = js_AllocStack(cx, 1 + 2 + 2, &mark);

what is the purpose of allocating the fifth elements besides fval-this-arg1-arg2 ?
> >+        *sp++ = JSVAL_NULL;;
> 
> Single ; is good enough here ;)
> 

Yeah, I left two there just to be safe!  ;;)

> >+        ca.elemroot  = js_AllocStack(cx, 1 + 2 + 2, &mark);

Sorry, I think this is the result of a bad cut and paste.  Fixed patch coming right up.
Do we have any favorite benchmarks we'd like to run this against?  Seems like a very nice optimization, and easy/safe-ish to boot.  Great idea, Igor.
Attachment #289059 - Attachment is obsolete: true
Attachment #289059 - Flags: review?(igor)
A benchmark to test this is simple:

var N = 1<<16;
var a = [];
for (var i = 0; i != N; ++i) a[i] = i;
a.reverse();
var start = Date.now();
a.sort(function(a, b) { return a - b; });
var time = Date.now() - start;
print(time);
Comment on attachment 289063 [details] [diff] [review]
Implementation v1a, now with less semicolons and stack-slots.

>Index: jsarray.c
>===================================================================
>RCS file: /cvsroot/mozilla/js/src/jsarray.c,v
>retrieving revision 3.126
>diff -u -p -8 -r3.126 jsarray.c
>--- jsarray.c	13 Oct 2007 20:09:48 -0000	3.126
>+++ jsarray.c	16 Nov 2007 23:16:27 -0000
>@@ -989,16 +989,17 @@ js_MergeSort(void *src, size_t nel, size
> 
>     return JS_TRUE;
> }
> 
> typedef struct CompareArgs {
>     JSContext   *context;
>     jsval       fval;
>     jsval       *localroot;     /* need one local root, for sort_compare */
>+    jsval       *elemroot;      /* stack needed for js_Invoke */
> } CompareArgs;
> 
> static JSBool
> sort_compare(void *arg, const void *a, const void *b, int *result)
> {
>     jsval av = *(const jsval *)a, bv = *(const jsval *)b;
>     CompareArgs *ca = (CompareArgs *) arg;
>     JSContext *cx = ca->context;
>@@ -1032,26 +1033,29 @@ sort_compare(void *arg, const void *a, c
>             astr = js_ValueToString(cx, av);
>             *ca->localroot = STRING_TO_JSVAL(astr);
>             if (astr && (bstr = js_ValueToString(cx, bv)))
>                 *result = js_CompareStrings(astr, bstr);
>             else
>                 ok = JS_FALSE;
>         }
>     } else {
>+        jsval *invokevp, *sp;
>         jsdouble cmp;
>-        jsval argv[2];
> 
>-        argv[0] = av;
>-        argv[1] = bv;
>-        ok = js_InternalCall(cx,
>-                             OBJ_GET_PARENT(cx, JSVAL_TO_OBJECT(fval)),
>-                             fval, 2, argv, ca->localroot);
>+        invokevp = ca->elemroot + 1;

The patch needs less pluses as well: the line above should be invokevp = ca->elemroot;
I got a crash testing that, investigating now.
The extra +1 was of course the cause of the crash.
Without the patch, for me, this test produces results in the range of approximately 179.  With the patch, I get results more like 157.
Attachment #289063 - Attachment is obsolete: true
v1b patch does not introduce any new test-suite failures.
Attachment #289070 - Flags: review?(igor)
Comment on attachment 289070 [details] [diff] [review]
Implementation v1b

>+        void *mark;
>+
>         ca.context = cx;
>         ca.fval = fval;
>         /* local GC root for temporary string */

As a bonus it would be nice to add a blank line before the comment here as style enforcement.
Attachment #289070 - Flags: review?(igor) → review+
jsarray.c: 3.127
Status: NEW → RESOLVED
Closed: 17 years ago
Resolution: --- → FIXED
Reopening.  I backed this out due to a suspicion that it causes a unit-test failure.
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Sorry this took so long.  I finally got mochitests to work on my build system.

I am unable to duplicate any mochitest issues with a build including this patch.
Great, thanks, Bill.  I will re-land later tonight when I have more time to watch the tree.
Keywords: checkin-needed
Checking in js/src/jsarray.c;
/cvsroot/mozilla/js/src/jsarray.c,v  <--  jsarray.c
new revision: 3.129; previous revision: 3.128
done
Status: REOPENED → RESOLVED
Closed: 17 years ago17 years ago
Keywords: checkin-needed
Resolution: --- → FIXED
Target Milestone: --- → mozilla1.9 M10
Flags: in-testsuite-
Flags: in-litmus-
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: