Closed Bug 432881 Opened 12 years ago Closed 12 years ago

SM: JSVAL_VOID as a pseudo-boolean

Categories

(Core :: JavaScript Engine, enhancement)

enhancement
Not set

Tracking

()

RESOLVED FIXED

People

(Reporter: igor, Assigned: igor)

References

Details

(Keywords: perf)

Attachments

(4 files, 5 obsolete files)

The current presentation for JSVAL_VOID is -2**31 encoded as int jsval:

#define JSVAL_VOID              INT_TO_JSVAL(0 - JSVAL_INT_POW2(30))

Such encoding means that JSVAL_IS_INT must check for JSVAL_VOID explicitly since just checking for JSVAL_INT bit is not enough:

#define JSVAL_IS_INT(v)         (((v) & JSVAL_INT) && (v) != JSVAL_VOID)

The interpreter uses few hacks to minimize the cost of the extra check, but still the check tax has to be payed.

It would be nice to define JSVAL_VOID as a pseudo-boolean so JSVAL_IS_INT(v) can be made simple 

#define JSVAL_IS_INT(v)         ((v) & JSVAL_INT)
Attached patch v1 (obsolete) — Splinter Review
This is work in progress that passes shell tests.
SunSpider shows 1.018 speedup with the patch with most of the speedup coming from bit manipulations benchmark, which is expected.

To get the results I was compiling spider monkey using:

make -f Makefile.ref -k JS_THREADSAFE=1  BUILD_OPT=1 INTERP_OPTIMIZER="-falign-functions=4096 -O3 -fstrict-aliasing"

where -falign-functions=4096 is used to reduce noise from changes in the code cache access patterns resulting from moving js_Interpret code.
Stuart has pointed out that in the patch from the comment 1 I missed the need to update JSOP_NEG as now -JSVAL_INT_MIN does not fit int jsval. Now I have:

js> var i = -1073741824;
var i = -1073741824;
js> -i
-i
Assertion failure: INT_FITS_IN_JSVAL(i), at jsinterp.c:3731
Trace/breakpoint trap

It would be nice to have the test coverage for "-" applied to 0, -0.0, +-(1<<30), +-((1<<30)-1).  
Attached patch v2 (obsolete) — Splinter Review
The new version of the patch fixes the -JSVAL_INT_MIN issue.
Attachment #320047 - Attachment is obsolete: true
(In reply to comment #3)

> 
> It would be nice to have the test coverage for "-" applied to 0, -0.0,
> +-(1<<30), +-((1<<30)-1).  

I'll add it in a little bit.
Flags: in-testsuite?
Comment on attachment 320267 [details] [diff] [review]
v2

>           BEGIN_CASE(JSOP_NEG)
>             /*
>              * Optimize the case of an int-tagged operand by noting that
>              * INT_FITS_IN_JSVAL(i) => INT_FITS_IN_JSVAL(-i) unless i is 0
>              * when -i is the negative zero which is jsdouble.
>              */

Comment needs updating, I think?
Attached file ecma/Expressions/11.4.7-02.js (obsolete) —
Igor, There turns out not to be tests of unary -. I've created a test based off of ecma/Expressions/11.4.6.js and will add it as ecma/Expressions/11.4.7-01.js. This test is for the boundaries you requested. Is this test sufficient?
Attachment #320290 - Flags: review?(igor)
(In reply to comment #7)
> Created an attachment (id=320290) [details]
> ecma/Expressions/11.4.7-02.js
> Is this test sufficient?

The new tests would test the interpreter but rather test the parser due to constant folding. To do the regression tests for the interpreter the tests should go at least via path like:

var i = 0.0;
if (-i != -0.0) bad.

Even better is to use a function like:

function test_negation(value, expected)
{
    var actual = -value;
    test_actual_and_expected;
} 

with a series of calls like:

test_negation(0, -0.0);
test_negation(-0.0, 0);
test_negation(1, -1);
test_negation(1.0/0.0, -1.0/0.0);
test_negation(-1.0/0.0, 1.0/0.0);

//1073741824 == (1 << 30)
test_negation(1073741824, -1073741824);
test_negation(-1073741824, 1073741824);
test_negation(1073741823, -1073741823);
test_negation(-1073741823, 1073741823);

// The same for 2147483648 == (1 << 31)
Attachment #320290 - Attachment is obsolete: true
Attachment #320325 - Flags: review?(igor)
Attachment #320290 - Flags: review?(igor)
Attachment #320325 - Flags: review?(igor) → review+
if there are additional tests for this bug, please toggle in-testsuite back to ?

/cvsroot/mozilla/js/tests/ecma/Expressions/11.4.7-01.js,v  <--  11.4.7-01.js
initial revision: 1.1
/cvsroot/mozilla/js/tests/ecma/Expressions/11.4.7-02.js,v  <--  11.4.7-02.js
initial revision: 1.1
Flags: in-testsuite? → in-testsuite+
Attached patch v2b (obsolete) — Splinter Review
The new patch has updated comments for JSOP_NEG. It passes shell and mochi tests.
Attachment #320267 - Attachment is obsolete: true
Attachment #320367 - Flags: review?(brendan)
Comment on attachment 320367 [details] [diff] [review]
v2b

Would it be better than this:

#define JSVAL_IS_BOOLEAN(v)     (((v) == JSVAL_TRUE) | ((v) == JSVAL_FALSE))

to use:

#define JSVAL_IS_BOOLEAN(v)     (((v) & ~((jsval)1 << JSVAL_TAGBITS)) ==      \
                                 JSVAL_BOOLEAN)

Nit:

#define INT_FITS_IN_JSVAL(i)    ((jsuint)(i)+JSVAL_INT_MAX+1<=                \

needs some spaces around operators

In js_AtomizePrimitiveValue:

                  v == JSVAL_NULL || JSVAL_IS_VOID(v));

why not use JSVAL_IS_NULL(v)?

jsbool.h should comment "NB: BOOLEAN_TO_JSVAL(2) is JSVAL_VOID (see jsapi.h)." or similar.

/be
(In reply to comment #12)
> (From update of attachment 320367 [details] [diff] [review])
> Would it be better than this:
> 
> #define JSVAL_IS_BOOLEAN(v)     (((v) == JSVAL_TRUE) | ((v) == JSVAL_FALSE))
> 
> to use:
> 
> #define JSVAL_IS_BOOLEAN(v)     (((v) & ~((jsval)1 << JSVAL_TAGBITS)) ==      \
>                                  JSVAL_BOOLEAN)

You are absolutely right. Here is a proof how much better the new version with GCC 4.3 for x86 (JSVAL_IS_BOOLEAN2 in the session below):

~/s $ cat x.c
#define JSVAL_TAGBITS           3
#define JSVAL_BOOLEAN           0x6     /* tagged boolean value */
#define JSVAL_SETTAG(v,t)       ((v) | (t))

#define BOOLEAN_TO_JSVAL(b)     JSVAL_SETTAG((b) << JSVAL_TAGBITS, \
                                             JSVAL_BOOLEAN)

#define JSVAL_FALSE             BOOLEAN_TO_JSVAL(0)
#define JSVAL_TRUE              BOOLEAN_TO_JSVAL(1)
#define JSVAL_IS_BOOLEAN(v)     (((v) == JSVAL_TRUE) | ((v) == JSVAL_FALSE))

#define JSVAL_IS_BOOLEAN2(v)     (((v) & ~(1 << JSVAL_TAGBITS)) ==      \
                                 JSVAL_BOOLEAN)

int f(int i)
{
    return JSVAL_IS_BOOLEAN(i);
}

int f2(int i)
{
    return JSVAL_IS_BOOLEAN2(i);
}
~/s $ gcc -c -O3 x.c
~/s $ objdump -d x.o

x.o:     file format elf32-i386


Disassembly of section .text:

00000000 <f>:
   0:	55                   	push   %ebp
   1:	89 e5                	mov    %esp,%ebp
   3:	8b 55 08             	mov    0x8(%ebp),%edx
   6:	5d                   	pop    %ebp
   7:	83 fa 0e             	cmp    $0xe,%edx
   a:	0f 94 c0             	sete   %al
   d:	83 fa 06             	cmp    $0x6,%edx
  10:	0f 94 c2             	sete   %dl
  13:	09 d0                	or     %edx,%eax
  15:	0f b6 c0             	movzbl %al,%eax
  18:	c3                   	ret    
  19:	8d b4 26 00 00 00 00 	lea    0x0(%esi,%eiz,1),%esi

00000020 <f2>:
  20:	55                   	push   %ebp
  21:	89 e5                	mov    %esp,%ebp
  23:	8b 45 08             	mov    0x8(%ebp),%eax
  26:	5d                   	pop    %ebp
  27:	83 e0 f7             	and    $0xfffffff7,%eax
  2a:	83 f8 06             	cmp    $0x6,%eax
  2d:	0f 94 c0             	sete   %al
  30:	0f b6 c0             	movzbl %al,%eax
  33:	c3                   	ret    

That is, tye new version uses 9 bytes versus 14 with the version in the patch. 
Attached patch v3 (obsolete) — Splinter Review
the new version of the patch addresses the nits and suggestions from the comment 12.
Attachment #320367 - Attachment is obsolete: true
Attachment #322115 - Flags: review?(brendan)
Attachment #320367 - Flags: review?(brendan)
(In reply to comment #14)
> Created an attachment (id=322115) [details]
> v3

Here is a delta against the previous version:

~/m/ff/mozilla/> env DIFF_U_VALUE=1 quilt diff -z
--- /home/igor/m/ff/mozilla/quilt.El2nmL/js/src/jsapi.h	2008-05-22 18:01:01.000000000 +0200
+++ js/src/jsapi.h	2008-05-22 17:33:11.000000000 +0200
@@ -75,3 +75,4 @@ JS_BEGIN_EXTERN_C
 #define JSVAL_IS_STRING(v)      (JSVAL_TAG(v) == JSVAL_STRING)
-#define JSVAL_IS_BOOLEAN(v)     (((v) == JSVAL_TRUE) | ((v) == JSVAL_FALSE))
+#define JSVAL_IS_BOOLEAN(v)     (((v) & ~((jsval)1 << JSVAL_TAGBITS)) ==      \
+                                 JSVAL_BOOLEAN)
 #define JSVAL_IS_NULL(v)        ((v) == JSVAL_NULL)
@@ -104,4 +105,4 @@ JS_BEGIN_EXTERN_C
 #define JSVAL_INT_MAX           (JSVAL_INT_POW2(30) - 1)
-#define INT_FITS_IN_JSVAL(i)    ((jsuint)(i)+JSVAL_INT_MAX+1<=                \
-                                 2*JSVAL_INT_MAX+1)
+#define INT_FITS_IN_JSVAL(i)    ((jsuint)(i) + JSVAL_INT_MAX + 1 <=           \
+                                 2 * JSVAL_INT_MAX + 1)
 #define JSVAL_TO_INT(v)         ((jsint)(v) >> 1)
--- /home/igor/m/ff/mozilla/quilt.El2nmL/js/src/jsatom.c	2008-05-22 18:01:01.000000000 +0200
+++ js/src/jsatom.c	2008-05-22 17:33:49.000000000 +0200
@@ -793,3 +793,3 @@ js_AtomizePrimitiveValue(JSContext *cx, 
         JS_ASSERT(JSVAL_IS_INT(v) || JSVAL_IS_BOOLEAN(v) ||
-                  v == JSVAL_NULL || JSVAL_IS_VOID(v));
+                  JSVAL_IS_NULL(v) || JSVAL_IS_VOID(v));
         atom = (JSAtom *)v;
--- /home/igor/m/ff/mozilla/quilt.El2nmL/js/src/jsbool.h	2008-05-22 18:01:01.000000000 +0200
+++ js/src/jsbool.h	2008-05-22 17:35:01.000000000 +0200
@@ -55,2 +55,4 @@ JS_BEGIN_EXTERN_C
  * JSVAL_ARETURN is used to throw asynchronous return for generator.close().
+ *
+ * NB: BOOLEAN_TO_JSVAL(2) is JSVAL_VOID (see jsapi.h).
  */
--- /home/igor/m/ff/mozilla/quilt.El2nmL/js/src/jsbool.c	2008-02-08 16:01:11.000000000 +0100
+++ js/src/jsbool.c	2008-05-22 17:37:02.000000000 +0200
@@ -56,2 +56,7 @@
 
+/* Check pseudo-booleans values. */
+JS_STATIC_ASSERT(JSVAL_VOID == JSVAL_TRUE + JSVAL_ALIGN);
+JS_STATIC_ASSERT(JSVAL_HOLE == JSVAL_VOID + JSVAL_ALIGN);
+JS_STATIC_ASSERT(JSVAL_ARETURN == JSVAL_HOLE + JSVAL_ALIGN);
+
 JSClass js_BooleanClass = {
Comment on attachment 322115 [details] [diff] [review]
v3

>+++ js/src/jsbool.h	22 May 2008 15:58:27 -0000
>@@ -47,21 +47,23 @@ JS_BEGIN_EXTERN_C
> 
> /*
>  * Crypto-booleans, not visible to script but used internally by the engine.

s/Crypto/Pseudo/

False, not hidden, booleans. Thanks, r=me with this last (pre-existing nit) fix.

/be
Attachment #322115 - Flags: review?(brendan) → review+
Blocks: js1.8.5
Attached patch v3bSplinter Review
The new version of the patch addresses the nit from the comment 16.
Attachment #322115 - Attachment is obsolete: true
Attachment #322130 - Flags: review+
Can this land? I hope so, we're using it in tracemonkey.

/be
I pushed the patch from the comment 19 to mozilla-central:

changeset:   15538:7194bbc1c007
tag:         tip
user:        Igor Bukanov <igor@mir2.org>
date:        Wed Jun 25 11:43:02 2008 +0200
summary:     [Bug 432881] SM: JSVAL_VOID as a pseudo-boolean. r=brendan
Status: NEW → RESOLVED
Closed: 12 years ago
Resolution: --- → FIXED
Flags: wanted1.9.1+
Blocks: 360324
Depends on: 442242
Depends on: 577757
You need to log in before you can comment on or make changes to this bug.