Conversion of large array to a Set seems slow

[tomoakley]

Bug Description

A discussion came up in my company about the performance benefits of set.has over array.includes (eslint rule). I was interested if these performance benefits translated over to Hermes from v8 or whatever JS engine was used to benchmark those two methods.

Quick disclaimer - absolutely not a performance expert or anything. So I may have got this very wrong, and if so, I apologise and please close this issue.

I wrote a quick script to do both these operations on three differently sized large arrays/sets. I then ran the script on node.js (v18) and Hermes, compiled from source. Firstly, here's the script:

let log
try {
  log = print
} catch {
  log = console.log // so that I can log in both node and hermes
}

const rand = (size) => [...Array(size)].map(() => Math.floor(Math.random() * size));

const small = rand(100000);
const medium = rand(1000000);
const large = rand(10000000);

const arraySolution = arr => {
  const t0 = Date.now()
  for (let int = 1; int++;) {
    if (!arr.includes(int)) {
      const t1 = Date.now();
      log(`Array.includes start ${t0}`);
      log(`Array.includes end ${t1}`);
      log(`array.includes difference: ${t1 - t0}`);
      return int;
    }
  }

}

const setSolution = arr => {
  const tMinus1 = Date.now()
  const set = new Set(arr)
  const t0 = Date.now()
  for (let i = 1; i++) {
    if (!set.has(i)) {
      const t1 = Date.now();
      log(`set conversion ${t0 - tMinus1}`)
      log(`set.has start ${t0}`);
      log(`set.has end ${t1}`);
      log(`set.has difference: ${t1 - t0}`);
      return i
    }
  }

}


log('** Testing small array/set:');
arraySolution(small);
setSolution(small);

log('\n** Testing medium array/set:');
arraySolution(medium);
setSolution(medium);

log('\n** Testing large array/set:');
arraySolution(large);
setSolution(large);

The basics of the code is from here and modified by myself: https://stackoverflow.com/a/65240169

I ran both of these from the command line; the results are here:
hermes (build_release/bin/hermes test.js)

** Testing small array/set:
Array.includes start 1705422961511
Array.includes end 1705422961512
array.includes difference: 1
set conversion 28
set.has start 1705422961540
set.has end 1705422961540
set.has difference: 0

** Testing medium array/set:
Array.includes start 1705422961540
Array.includes end 1705422961545
array.includes difference: 5
set conversion 333
set.has start 1705422961878
set.has end 1705422961878
set.has difference: 0

** Testing large array/set:
Array.includes start 1705422961878
Array.includes end 1705422961959
array.includes difference: 81
set conversion 10312
set.has start 1705422972271
set.has end 1705422972271
set.has difference: 0

node (node test.js):

** Testing small array/set:
Array.includes start 1705422981216
Array.includes end 1705422981216
array.includes difference: 0
set conversion 4
set.has start 1705422981220
set.has end 1705422981220
set.has difference: 0

** Testing medium array/set:
Array.includes start 1705422981220
Array.includes end 1705422981221
array.includes difference: 1
set conversion 54
set.has start 1705422981275
set.has end 1705422981275
set.has difference: 0

** Testing large array/set:
Array.includes start 1705422981275
Array.includes end 1705422981281
array.includes difference: 6
set conversion 1160
set.has start 1705422982441
set.has end 1705422982441
set.has difference: 0

as you can see set.has is very quick on both (not sure how it can be 0? but I think the code is correct). But on Hermes, the conversion to a set (i.e new Set(array)) is much slower than on node (approaching 10x in some cases).

Is this conclusion correct? have I done anything wrong?
Hermes git revision (if applicable): 005897de9 (HEAD -> main, origin/main, origin/HEAD) Run API tests against the sandbox runtime (#1248) 17 hours ago
OS: macOS 14
RN version: N/A
Platform (most likely one of arm64-v8a, armeabi-v7a, x86, x86_64): arm64 (M1 macbook Pro)

Steps To Reproduce

1. Run the script in node and hermes

The Expected Behavior

For new Set to have comparable performance in Hermes to Node.

[avp]

We have fast paths for iterating arrays that bypass the (slow) Symbol.iterator lookup and next() calls, but those fast paths are currently only used in for..of, e.g.

Set and Map constructors from array are likely slow because they don't use fast paths for array iteration yet.

[tomoakley]

We have fast paths for iterating arrays that bypass the (slow) Symbol.iterator lookup and next() calls, but those fast paths are currently only used in for..of, e.g.

Set and Map constructors from array are likely slow because they don't use fast paths for array iteration yet.

thanks, that's interesting. I'm happy for you to close this as I assume using those fast paths for Sets/Maps will be done at some point (understandably not a priority I assume). But equally can be left open too!

[tmikov]

Lets keep it open until we add the fast paths

[efstathiosntonas]

@tmikov hi, does this PR fixes this?

• Fast path for Set constrution #1346

[tmikov]

@efstathiosntonas it is one of several. We are working on multiple improvements that have sped it up by more than 10x.