Bug 1779807 - Consume SIMD::memchr64 for array includes/indexof r=iain
authorDoug Thayer <dothayer@mozilla.com>
Fri, 29 Jul 2022 03:26:07 +0000
changeset 625461 60cacdcfafa39342687368dbbdd2d82513dfe83b
parent 625460 1a6105fe6fad388efe645807a8abe933d256dda7
child 625462 51823a43cd60a266b37eda01d3ea2c55de079a33
push id40054
push userabutkovits@mozilla.com
push dateFri, 29 Jul 2022 15:16:35 +0000
treeherdermozilla-central@62ef66035be0 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersiain
bugs1779807
milestone105.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1779807 - Consume SIMD::memchr64 for array includes/indexof r=iain This improved the time for a contrived benchmark. I don't know if we want to invest more time into benchmarking - I feel pretty strongly that this will be an improvement across most use cases, just judging from the more in-depth benchmarking of the string functions. The benchmark I did was basically as follows: make N arrays make N objects for i,j in 0..N,0..N if (hash(i,j) % K == 0) arrays[i].push(objects[j]) start performance timer for i,j in 0..N,0..N if arrays[i].includes(objects[j]) matches++ report matches and performance timings And our times were basically equal for small N, and up to 3 times faster for large N - so, basically what we would hope for. Differential Revision: https://phabricator.services.mozilla.com/D152298
js/src/builtin/Array.cpp
--- a/js/src/builtin/Array.cpp
+++ b/js/src/builtin/Array.cpp
@@ -5,16 +5,17 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "builtin/Array-inl.h"
 
 #include "mozilla/CheckedInt.h"
 #include "mozilla/DebugOnly.h"
 #include "mozilla/MathAlgorithms.h"
 #include "mozilla/Maybe.h"
+#include "mozilla/SIMD.h"
 #include "mozilla/TextUtils.h"
 
 #include <algorithm>
 #include <cmath>
 #include <iterator>
 
 #include "jsfriendapi.h"
 #include "jsnum.h"
@@ -64,16 +65,17 @@
 using namespace js;
 
 using mozilla::Abs;
 using mozilla::CeilingLog2;
 using mozilla::CheckedInt;
 using mozilla::DebugOnly;
 using mozilla::IsAsciiDigit;
 using mozilla::Maybe;
+using mozilla::SIMD;
 
 using JS::AutoCheckCannotGC;
 using JS::IsArrayAnswer;
 using JS::ToUint32;
 
 static inline bool ObjectMayHaveExtraIndexedOwnProperties(JSObject* obj) {
   if (!obj->is<NativeObject>()) {
     return true;
@@ -4068,16 +4070,29 @@ bool js::array_indexOf(JSContext* cx, un
     MOZ_ASSERT(len <= UINT32_MAX);
 
     NativeObject* nobj = &obj->as<NativeObject>();
     uint32_t start = uint32_t(k);
     uint32_t length =
         std::min(nobj->getDenseInitializedLength(), uint32_t(len));
     const Value* elements = nobj->getDenseElements();
 
+    if (CanUseBitwiseCompareForStrictlyEqual(searchElement) && length > start) {
+      const uint64_t* elementsAsBits =
+          reinterpret_cast<const uint64_t*>(elements);
+      const uint64_t* res = SIMD::memchr64(
+          elementsAsBits + start, searchElement.asRawBits(), length - start);
+      if (res) {
+        args.rval().setInt32(static_cast<int32_t>(res - elementsAsBits));
+      } else {
+        args.rval().setInt32(-1);
+      }
+      return true;
+    }
+
     auto iterator = [elements, start, length](JSContext* cx, auto cmp,
                                               MutableHandleValue rval) {
       static_assert(NativeObject::MAX_DENSE_ELEMENTS_COUNT <= INT32_MAX,
                     "code assumes dense index fits in Int32Value");
       for (uint32_t i = start; i < length; i++) {
         bool equal;
         if (MOZ_UNLIKELY(!cmp(cx, elements[i], &equal))) {
           return false;
@@ -4302,16 +4317,29 @@ bool js::array_includes(JSContext* cx, u
 
     // Trailing holes are treated as |undefined|.
     if (uint32_t(len) > length && searchElement.isUndefined()) {
       // |undefined| is strictly equal only to |undefined|.
       args.rval().setBoolean(true);
       return true;
     }
 
+    // For |includes| we need to treat hole values as |undefined| so we use a
+    // different path if searching for |undefined|.
+    if (CanUseBitwiseCompareForStrictlyEqual(searchElement) &&
+        !searchElement.isUndefined() && length > start) {
+      if (SIMD::memchr64(reinterpret_cast<const uint64_t*>(elements) + start,
+                         searchElement.asRawBits(), length - start)) {
+        args.rval().setBoolean(true);
+      } else {
+        args.rval().setBoolean(false);
+      }
+      return true;
+    }
+
     auto iterator = [elements, start, length](JSContext* cx, auto cmp,
                                               MutableHandleValue rval) {
       for (uint32_t i = start; i < length; i++) {
         bool equal;
         if (MOZ_UNLIKELY(!cmp(cx, elements[i], &equal))) {
           return false;
         }
         if (equal) {