array-indexof-simd.js 5.94 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202
// Copyright 2022 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

// Large array of packed Smi, and Smi search_element
(() => {
  let a = [];
  for (let i = 0; i < 200; i++) {
    a[i] = i;
  }
  function testArrayIndexOf(idx) {
    return a.indexOf(idx);
  }
  // Without fromIndex
  for (let i = 0; i < 200; i++) {
    assertEquals(i, testArrayIndexOf(i));
  }
  // With fromIndex
  for (let i = 0, from_index = 0; i+from_index < 200; i += 2, from_index++) {
    assertEquals(i, testArrayIndexOf(i, from_index));
  }
})();

// Large array of holey Smi, and Smi search_element
(() => {
  let a = [];
  // Skipping every other item when initializing
  for (let i = 0; i < 200; i+=2) {
    a[i] = i;
  }
  function testArrayIndexOf(idx) {
    return a.indexOf(idx);
  }
  // Without fromIndex
  for (let i = 0; i < 200; i++) {
    if (i % 2 == 0) {
      assertEquals(i, testArrayIndexOf(i));
    } else {
      assertEquals(-1, testArrayIndexOf(i));
    }
  }
  // With fromIndex
  for (let i = 0, from_index = 0; i + from_index < 200; i += 2, from_index++) {
    if (i % 2 == 0) {
      assertEquals(i, testArrayIndexOf(i, from_index));
    } else {
      assertEquals(-1, testArrayIndexOf(i, from_index));
    }
  }
})();

// Large array of packed Doubles, and Double search_element
(() => {
  let a = [];
  for (let i = 0; i < 200; i++) {
    a[i] = i + 0.5;
  }
  function testArrayIndexOf(idx) {
    return a.indexOf(idx);
  }
  // Without fromIndex
  for (let i = 0; i < 200; i++) {
    assertEquals(i, testArrayIndexOf(i + 0.5));
  }
  // With fromIndex
  for (let i = 0, from_index = 0; i+from_index < 200; i += 2, from_index++) {
    assertEquals(i, testArrayIndexOf(i+0.5, from_index));
  }
})();

// Large array of holey Doubles, and Double search_element
(() => {
  let a = [];
  // Skipping every other item when initializing
  for (let i = 0; i < 200; i+=2) {
    a[i] = i + 0.5;
  }
  function testArrayIndexOf(idx) {
    return a.indexOf(idx);
  }
  // Without fromIndex
  for (let i = 0; i < 200; i++) {
    if (i % 2 == 0) {
      assertEquals(i, testArrayIndexOf(i + 0.5));
    } else {
      assertEquals(-1, testArrayIndexOf(i + 0.5));
    }
  }
  // With fromIndex
  for (let i = 0, from_index = 0; i + from_index < 200; i += 2, from_index++) {
    if (i % 2 == 0) {
      assertEquals(i, testArrayIndexOf(i+0.5, from_index));
    } else {
      assertEquals(-1, testArrayIndexOf(i+0.5, from_index));
    }
  }
})();

// Large array of packed objects, and object search_element
(() => {
  let a = [];
  let b = [];
  for (let i = 0; i < 200; i++) {
    a[i] = { v: i };
    b[i] = a[i];
  }
  function testArrayIndexOf(idx) {
    return a.indexOf(idx);
  }
  // Without fromIndex
  for (let i = 0; i < 200; i++) {
    assertEquals(i, testArrayIndexOf(b[i]));
  }
  // With fromIndex
  for (let i = 0, from_index = 0; i+from_index < 200; i += 2, from_index++) {
    assertEquals(i, testArrayIndexOf(b[i], from_index));
  }
})();

// Large array of holey objects, and object search_element
(() => {
  let a = [];
  let b = [];
  // Skipping every other item when initializing
  for (let i = 0; i < 200; i++) {
    b[i] = { v: i };
    if (i % 2 == 0) {
      a[i] = b[i];
    }
  }
  function testArrayIndexOf(idx) {
    return a.indexOf(idx);
  }
  // Without fromIndex
  for (let i = 0; i < 200; i++) {
    if (i % 2 == 0) {
      assertEquals(i, testArrayIndexOf(b[i]));
    } else {
      assertEquals(-1, testArrayIndexOf(b[i]));
    }
  }
  // With fromIndex
  for (let i = 0, from_index = 0; i + from_index < 200; i += 2, from_index++) {
    if (i % 2 == 0) {
      assertEquals(i, testArrayIndexOf(b[i], from_index));
    } else {
      assertEquals(-1, testArrayIndexOf(b[i], from_index));
    }
  }
})();

// This test checks that when the item that IndexOf searches is present multiple
// time, the correct index is returned (in particular, when a single SIMD vector
// had multiple matches). For instance, if we do:
//
//   [1, 2, 1, 3].indexOf(1)
//
// Then it should return 0 rather than 2.
(() => {


  // The patterns that this function will check, where for instance patternABAB
  // means that we'd like to build a vector containing {A, B, A, B}.
  let patterns = {
    patternABAB : (a, b, c, d) => [a, b, a, b, c, d, c, d],
    patternAABB : (a, b, c, d) => [a, a, b, b, c, c, d, d],
    patternABBA : (a, b, c, d) => [a, b, b, a, c, d, d, c],
    patternABAA : (a, b, c, d) => [a, b, a, a, c, d, c, c],
    patternAABA : (a, b, c, d) => [a, a, b, a, c, c, d, c],
    patternAAAB : (a, b, c, d) => [a, a, a, b, c, c, c, d],
    patternBAAA : (a, b, c, d) => [b, a, a, a, d, c, c, c]
  };

  // Starting |a| with a bunch of 0s, which might be handled by the scalar loop
  // that the SIMD code does to reach 16/32-byte alignment.
  let a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
  let next_int = 1;
  for (const [_, pattern] of Object.entries(patterns)) {
    // It's a bit tricky to ensure that 2 items will be in the same SIMD batch
    // because we can't control the alignment of the array from JS, and the
    // SIMD code will start by skipping the first items to have the memory
    // aligned on 16/32 bytes. So, we put each pattern 8 times in a row in |a|,
    // but each time with an additional item, to make sure that each of those 8
    // repeated pattern have a different alignment.
    for (let i = 0; i < 8; i++) {
      a = a.concat(pattern(next_int, next_int + 1, next_int + 2, next_int + 3));
      a.push(next_int + 4);  // By adding a 9th item, we make sure that the
                             // alignment of the next batch is not the same as
                             // the current one.
      next_int += 5;
    }
  }

  let b = a.slice();
  b[10000] = 42;  // Switch b to dictionary mode so that the SIMD code won't be
                  // used for it. We can then use `b.indexOf` as reference.

  for (let x of b) {
    if (x == undefined) break;
    assertEquals(b.indexOf(x), a.indexOf(x));
  }
})();