356856 - Bitscanning operation can be made much faster with x86 instructions

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Steve Snyder]

User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.0.7) Gecko/20060911 SUSE/1.5.0.7-1.6 Firefox/1.5.0.7
Build Identifier: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.0.7) Gecko/20060911 SUSE/1.5.0.7-1.6 Firefox/1.5.0.7

The Log2 and hibit/lobit functions in JS can be made much faster by using
native x86 instructions rather than a series of shifts and compares.


Reproducible: Always

Steps to Reproduce:
1. Look at existing Log2 and hibit/lobit functions.
2. Be appalled at the contortions needed to reproduce what a single x86 opcode
can do.

Actual Results:  
Functions execute much slower than needed on x86 platforms.

Expected Results:  
Software should better utilize that hardware it is running on.


I selected "Windows XP" as the OS but any x86 build using GCC can be improved. 
Patch was tested on Windows2K and on Linux.

Comment 1

[Steve Snyder]

Attachment: Conditionally use x86 instructions for bit-scan operations

This patch is broken out from a larger patch that enhanced bit-scan operations
for both the JS and NSPR components.  I hope that this component-specific patch
will be deemed acceptable.  See bug #351532 for background and benchmarking
info.

Comment 2

[Steve Snyder]

Notes:

0. This patch is against JS, as found in Firefox v2.0RC3.  As such it adds MSVC support to the existing use of GCC built-in bit-scan functions.

1. Unlike the original code, the bit-scan enhancements are extended to the lo0bits() and hi0bits() functions.

Comment 3

[Steve Snyder]

Attachment: Previous patch reduced to NSPR-owned files only

Comment 4

[Steve Snyder]

Posted patch to wrong bug.  Sorry.

Comment 5

[Jesse Ruderman]

Igor, want to review this patch?

Comment 6

[Igor Bukanov]

Comment on attachment 242424 [details] [diff] [review]
Conditionally use x86 instructions for bit-scan operations

>+# define js_BitScanForward(val)  __BitScanForward(val)
>+# define js_BitScanReverse(val)  __BitScanReverse(val)

I would prefer to call the functions using the names they originally became known in literature, that is count-leading-zeros/count-trailing-zeros or clz/ctz or nlz/ntz from number-of-leading-zerors/number-of-trailing-zeros perhaps with 32 suffix to indicate their 32-bit nature.

Also, doesn't Visual C has 64 bit counterpart for the functions? 

>+# define JS_HAS_BUILTIN_BITSCAN
>+#elif (__GNUC__ >= 4) || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
>+# define js_BitScanForward(val)  __builtin_ctz(val)
>+# define js_BitScanReverse(val)  __builtin_clz(val)
>+# define JS_HAS_BUILTIN_BITSCAN
> # define JS_HAS_GCC_BUILTIN_CLZ
> #endif
> 
>@@ -80,7 +97,7 @@
> ** Macro version of JS_CeilingLog2: Compute the log of the least power of
> ** 2 greater than or equal to _n. The result is returned in _log2.
> */
>-#ifdef JS_HAS_GCC_BUILTIN_CLZ
>+#ifdef JS_HAS_BUILTIN_BITSCAN
> /*
>  * Use __builtin_clz or count-leading-zeros to calculate ceil(log2(_n)).
>  * The macro checks for "n <= 1" and not "n != 0" as __builtin_clz(0) is
>@@ -90,7 +107,7 @@
>     JS_BEGIN_MACRO                                                            \
>         JS_STATIC_ASSERT(sizeof(unsigned int) == sizeof(JSUint32));           \
>         unsigned int j_ = (unsigned int)(_n);                                 \
>-        (_log2) = (j_ <= 1 ? 0 : 32 - __builtin_clz(j_ - 1));                 \
>+        (_log2) = (j_ <= 1 ? 0 : 32 - js_BitScanReverse(j_ - 1));             \
>     JS_END_MACRO
> #else
> # define JS_CEILING_LOG2(_log2,_n)                                            \
>@@ -118,7 +135,7 @@
> **
> ** This is equivalent to finding the highest set bit in the word.
> */
>-#if JS_GCC_HAS_BUILTIN_CLZ
>+#ifdef JS_HAS_BUILTIN_BITSCAN
> /*
>  * Use __builtin_clz or count-leading-zeros to calculate floor(log2(_n)).
>  * Since __builtin_clz(0) is undefined, the macro set the loweset bit to 1
>@@ -127,7 +144,7 @@
> # define JS_FLOOR_LOG2(_log2,_n)                                              \
>     JS_BEGIN_MACRO                                                            \
>         JS_STATIC_ASSERT(sizeof(unsigned int) == sizeof(JSUint32));           \
>-        (_log2) = 31 - __builtin_clz(((unsigned int)(_n)) | 1);               \
>+        (_log2) = 31 - js_BitScanReverse(((unsigned int)(_n)) | 1);           \
>     JS_END_MACRO
> #else
> # define JS_FLOOR_LOG2(_log2,_n)                                              \
>diff -Nru mozilla.orig-1.8.1/js/src/jsdtoa.c mozilla/js/src/jsdtoa.c
>--- mozilla.orig-1.8.1/js/src/jsdtoa.c	2006-07-13 15:56:29.000000000 -0400
>+++ mozilla/js/src/jsdtoa.c	2006-10-11 20:24:23.000000000 -0400
>@@ -48,6 +48,7 @@
> #include "jsutil.h" /* Added by JSIFY */
> #include "jspubtd.h"
> #include "jsnum.h"
>+#include "jsbit.h"
> 
> #ifdef JS_THREADSAFE
> #include "prlock.h"
>@@ -540,6 +541,9 @@
> /* Return the number (0 through 32) of most significant zero bits in x. */
> static int32 hi0bits(register ULong x)
> {
>+#ifdef JS_HAS_BUILTIN_BITSCAN
>+    return( (!x) ? 32 : js_BitScanReverse(x) );
>+#else
>     register int32 k = 0;
> 
>     if (!(x & 0xffff0000)) {
>@@ -564,6 +568,7 @@
>             return 32;
>     }
>     return k;
>+#endif /* JS_HAS_BUILTIN_BITSCAN */
> }
> 
> 
>@@ -572,6 +577,16 @@
>  * least significant bit will be set unless y was originally zero. */
> static int32 lo0bits(ULong *y)
> {
>+#ifdef JS_HAS_BUILTIN_BITSCAN
>+    int32 k;
>+    ULong x = *y;
>+    static const int32 lo0tbl[2]={32, 0};
>+
>+   if (x>1)
>+      *y = ( x >> (k = js_BitScanForward(x)) );
>+   else
>+      k = lo0tbl[x];
>+#else

Since x in k = lo0tbl[x]; is 0 or 1, you can replace the table lookup via something like  k = ((x ^ 1) << 5) for smaller code.

Comment 7

[Steve Snyder]

>I would prefer to call the functions using the names they originally became
>known in literature, that is count-leading-zeros/count-trailing-zeros or
>clz/ctz or nlz/ntz from number-of-leading-zerors/number-of-trailing-zeros
>perhaps with 32 suffix to indicate their 32-bit nature.

Fine with me.  

>Also, doesn't Visual C has 64 bit counterpart for the functions? 

Yes, it does.  But: a) I can't test that with my pathetically obsolete 32-bit x86 machines, and b) the functions specify types of "int32" or "JSUint32" so they aren't expecting to scan 64 bits of input data.

>Since x in k = lo0tbl[x]; is 0 or 1, you can replace the table lookup via
>something like  k = ((x ^ 1) << 5) for smaller code.

Good idea.

Updated patch to follow addressing above comments.

Comment 8

[Steve Snyder]

Attachment: Patch v2: updated to reflect comments

Changes:

1. Modified macro naming per Igor's comments, to reflect their 32-bitness.  Replaced lo0bits() table look-up with xor/shift.

2. Extended GCC/MSVC generic macro to use in js_FloorLog2wImpl() definition (replaced use of GCC-specific intrinsic function).

Note that this patch only addresses 32-bit bit-scanning.  The MSVC intrinsic functions _BitScanForward64() and _BitScanReverse64() can be handled in a similar fashion to their 32-bit counterparts.  Since I can't test the 64-bit functionality, though, I will leave that task to someone else.

Comment 9

[Igor Bukanov]

Comment on attachment 244199 [details] [diff] [review]
Patch v2: updated to reflect comments

>+# define js_bitscan_ctz32(val)  __BitScanForward32(val)
>+# define js_bitscan_clz32(val)  __BitScanReverse32(val)

I like the names :)

> # define JS_HAS_GCC_BUILTIN_CLZ

> #ifdef JS_HAS_GCC_BUILTIN_CLZ
> 
>-# if JS_BYTES_PER_WORD == 4
>+# if defined(JS_HAS_BUILTIN_BITSCAN32) && (JS_BYTES_PER_WORD == 4)
> JS_STATIC_ASSERT(sizeof(unsigned) == sizeof(JSUword));
> #  define js_FloorLog2wImpl(n)                                                \
>-    ((JSUword)(JS_BITS_PER_WORD - 1 - __builtin_clz(n)))
>-# elif JS_BYTES_PER_WORD == 8
>+    ((JSUword)(JS_BITS_PER_WORD - 1 - js_bitscan_clz32(n)))
>+# elif defined(JS_HAS_GCC_BUILTIN_CLZ) && (JS_BYTES_PER_WORD == 8)
> JS_STATIC_ASSERT(sizeof(unsigned long long) == sizeof(JSUword));
> #  define js_FloorLog2wImpl(n)                                                \
>     ((JSUword)(JS_BITS_PER_WORD - 1 - __builtin_clzll(n)))
> # else
> #  error "NOT SUPPORTED"

This fragment I think should become just 

#if JS_BYTES_PER_WORD == 4 && defined(JS_HAS_BUILTIN_BITSCAN32)
...
#elif JS_BYTES_PER_WORD == 8 && defined(JS_HAS_BUILTIN_BITSCAN64)
...
#else
 declare external function
#end

without any error detection for simplicity. Then JS_HAS_GCC_BUILTIN_CLZ is no longer necessary but JS_HAS_BUILTIN_BITSCAN64 should be defined but only for GCC for now and only when JS_BYTES_PER_WORD == 8. The later is necessary long-long version of GCC-builtins  is available only when long-long is defined which may not be the case when SpiderMonkey is compiled with -pedantic -ansi.

But this would require to update jslog.c with new conditions when to define js_FloorLog2wImpl.

Comment 10

[Steve Snyder]

Attachment: Added 64-bit macros (GCC only) & cleaned up js_FloorLog2wImpl defs

File jsbit.h is so chopped up with nested conditional declarations and modified lines that it is hard to readily see from the patch file what is different.  This is the most significant difference from the previous patch:

/* 32-bit intrinsic */
#if (JS_BYTES_PER_WORD == 4) && defined(JS_HAS_BUILTIN_BITSCAN32)
JS_STATIC_ASSERT(sizeof(unsigned) == sizeof(JSUword));
# define js_FloorLog2wImpl(n)                                                \
   ((JSUword)(JS_BITS_PER_WORD - 1 - js_bitscan_clz32(n)))
/* 64-bit intrinsic */
#elif (JS_BYTES_PER_WORD == 8) && defined(JS_HAS_BUILTIN_BITSCAN64)
JS_STATIC_ASSERT(sizeof(unsigned long long) == sizeof(JSUword));
# define js_FloorLog2wImpl(n)                                                \
   ((JSUword)(JS_BITS_PER_WORD - 1 - js_bitscan_clz64((n)))
/* no intrinsic; uses functions */
#else
# if JS_BYTES_PER_WORD == 4
#  define js_FloorLog2wImpl(n) ((JSUword)JS_FloorLog2(n))
# elif JS_BYTES_PER_WORD == 8
   extern JSUword js_FloorLog2wImpl(JSUword n);
# endif
#endif


For clarity I should note that the 64-bit macros are #ifdef'd (JS_BYTES_PER_WORD == 8) to address the SpiderMonkey concern raised earlier.  32-bit builds of GCC do support the 64-bit built-ins, but they compile to functions rather than inline code.  FYI.

Comment 11

[Igor Bukanov]

Please ask for review on the patch: just select in the edit attachment r=? and use [e-mail] as reviwere. You will get r=+ AFAICS, but I will do it in the morning (my timezone is CEST).

Also do not hesitate to reassign the bug to yourself so it would be known who made the bulk of work for the fix.

Comment 12

[Steve Snyder]

(In reply to comment #11)
> Also do not hesitate to reassign the bug to yourself so it would be known who
> made the bulk of work for the fix.

How do I do that?  When I clicked on the "Assigned To" link above it just showed me a description of what "Assigned To" means.

Thanks.

Comment 13

[Igor Bukanov]

(In reply to comment #12)
> How do I do that?  When I clicked on the "Assigned To" link above it just
> showed me a description of what "Assigned To" means.

You just select the radio-button "Reassign bug to" and type your bugzilla email, [e-mail] , to replace the current [e-mail] value, then press the "Commit" button.

Comment 14

[:Gavin Sharp [email: [e-mail]]]

(In reply to comment #13)
> You just select the radio-button "Reassign bug to" and type your bugzilla
> email, [e-mail] , to replace the current [e-mail] value,
> then press the "Commit" button.

He actually didn't have editbugs or canconfirm. I asked timeless on IRC to grant them to you, Steve, so you should see the "reassign" radio button now.

Comment 15

[Igor Bukanov]

Comment on attachment 244242 [details] [diff] [review]
Added 64-bit macros (GCC only) & cleaned up js_FloorLog2wImpl defs

The final nits:

>+  __forceinline static int __BitScanForward32(unsigned long val)
>+    { unsigned long idx; _BitScanForward(&idx, val); return((int)idx);  }
>+  __forceinline static int __BitScanReverse32(unsigned long val)
>+    { unsigned long idx; _BitScanReverse(&idx, val); return((int)(31-idx)); }

__builtin_ctz|clz in GCC takes unsigned, not unsigned long. Thus for consistency should do __BitScanForward32. Also for the style write the functions as in:

__forceinline static int 
__BitScanForward32(unsigned long val)
{
    unsigned long idx; 

    _BitScanForward(&idx, val); 
    return((int)idx);  
}
>+/* 32-bit intrinsic */
>+#if (JS_BYTES_PER_WORD == 4) && defined(JS_HAS_BUILTIN_BITSCAN32)
> JS_STATIC_ASSERT(sizeof(unsigned) == sizeof(JSUword));
>+# define js_FloorLog2wImpl(n)                                                \
...

With JS_HAS_BUILTIN_BITSCAN32/JS_HAS_BUILTIN_BITSCAN64 much more readable result would be to write js_FloorLog2wImpl definitions as:

#if JS_BYTES_PER_WORD == 4

# ifdef JS_HAS_BUILTIN_BITSCAN32
JS_STATIC_ASSERT(sizeof(unsigned) == sizeof(JSUword));
#  define js_FloorLog2wImpl(n)                                                \
   ((JSUword)(JS_BITS_PER_WORD - 1 - js_bitscan_clz32(n)))
# else
#  define js_FloorLog2wImpl(n) ((JSUword)JS_FloorLog2(n))
#endif

#elif JS_BYTES_PER_WORD == 8

# ifdef JS_HAS_BUILTIN_BITSCAN64
JS_STATIC_ASSERT(sizeof(unsigned long long) == sizeof(JSUword));
#  define js_FloorLog2wImpl(n)                                                \
   ((JSUword)(JS_BITS_PER_WORD - 1 - js_bitscan_clz64((n)))
# else
extern JSUword js_FloorLog2wImpl(JSUword n);
# endif

#else

# error "NOT SUPPORTED"

#endif

Comment 16

[Steve Snyder]

Attachment: Final nits addressed

No changes to functionality, just in style.

Comment 17

[Igor Bukanov]

I committed the patch from comment 16 to the trunk:

Checking in jsbit.h;
/cvsroot/mozilla/js/src/jsbit.h,v  <--  jsbit.h
new revision: 3.16; previous revision: 3.15
done
Checking in jsdtoa.c;
/cvsroot/mozilla/js/src/jsdtoa.c,v  <--  jsdtoa.c
new revision: 3.35; previous revision: 3.34
done
Checking in jslog2.c;
/cvsroot/mozilla/js/src/jslog2.c,v  <--  jslog2.c
new revision: 3.14; previous revision: 3.13
done


Thanks Steve for your efforts.

Comment 18

[Mats Palmgren (inactive)]

This broke my build, gcc 4.1.2 on Linux 2.6/x86_64.
You need to add a closing paren:

diff -u -r3.16 jsbit.h
--- js/src/jsbit.h      1 Nov 2006 20:08:44 -0000       3.16
+++ js/src/jsbit.h      2 Nov 2006 14:30:34 -0000
@@ -213,7 +213,7 @@
 # ifdef JS_HAS_BUILTIN_BITSCAN64
 JS_STATIC_ASSERT(sizeof(unsigned long long) == sizeof(JSUword));
 #  define js_FloorLog2wImpl(n)                                                \
-   ((JSUword)(JS_BITS_PER_WORD - 1 - js_bitscan_clz64((n)))
+   ((JSUword)(JS_BITS_PER_WORD - 1 - js_bitscan_clz64((n))))
 # else
 extern JSUword js_FloorLog2wImpl(JSUword n);
 # endif

Comment 19

[Igor Bukanov]

Attachment: Fix for 64-bit-only bug and better comments

The fix + better comments + style enforcement.

Comment 20

[Igor Bukanov]

Mats, could you check that the patch compiles for you?

Comment 21

[Mats Palmgren (inactive)]

Yes, it works fine.

Comment 22

[Igor Bukanov]

I committed the patch from comment 19 to fix the compilation problem on 64-bits platforms:

Checking in jsbit.h;
/cvsroot/mozilla/js/src/jsbit.h,v  <--  jsbit.h
new revision: 3.17; previous revision: 3.16
done