432881 - SM: JSVAL_VOID as a pseudo-boolean

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Igor Bukanov]

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)

Comment 1

[Igor Bukanov]

Attachment: v1

This is work in progress that passes shell tests.

Comment 2

[Igor Bukanov]

Attachment: sunspider results, thread-safe jsshell, GCC 4.3, Fedora 9, Petium-M 1.1GHz

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.

Comment 3

[Igor Bukanov]

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).  

Comment 4

[Igor Bukanov]

Attachment: v2

The new version of the patch fixes the -JSVAL_INT_MIN issue.

Comment 5

[Bob Clary [:bc] (inactive)]

(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.

Comment 6

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

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?

Comment 7

[Bob Clary [:bc] (inactive)]

Attachment: ecma/Expressions/11.4.7-02.js

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?

Comment 8

[Igor Bukanov]

(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)

Comment 9

[Bob Clary [:bc] (inactive)]

Attachment: ecma/Expressions/11.4.7-02.js

Comment 10

[Bob Clary [:bc] (inactive)]

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

Comment 11

[Igor Bukanov]

Attachment: v2b

The new patch has updated comments for JSOP_NEG. It passes shell and mochi tests.

Comment 12

[Brendan Eich [: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

Comment 13

[Igor Bukanov]

(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. 

Comment 14

[Igor Bukanov]

Attachment: v3

the new version of the patch addresses the nits and suggestions from the comment 12.

Comment 15

[Igor Bukanov]

(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 16

[Brendan Eich [:brendan]]

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

Comment 17

[Igor Bukanov]

Attachment: v3b

The new version of the patch addresses the nit from the comment 16.

Comment 18

[Brendan Eich [:brendan]]

Can this land? I hope so, we're using it in tracemonkey.

/be

Comment 19

[Igor Bukanov]

Attachment: v3b against mozilla-central

Comment 20

[Igor Bukanov]

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

changeset:   15538:7194bbc1c007
tag:         tip
user:        Igor Bukanov <[e-mail]>
date:        Wed Jun 25 11:43:02 2008 +0200
summary:     [Bug 432881] SM: JSVAL_VOID as a pseudo-boolean. r=brendan