JavaScript String or BigInt equality performance

This article discusses performance of String vs BigInt equality operations. This stems from the question, if I had a large list of 32-byte (256-bit) hashes that I want to evaluate, which value-type representation of that hash allows for the fastest equality operation. Of particular importance is the performance of checking for set inclusion.

We will compare two representations: String and the new BitInt type that is available since Node 10.

The test is setup like this:

  • Run a test for equality and set lookup for String or BigInt representation
  • Set lookup will perform 100k .has() lookups
  • Creates 100k hashes prior to performing equality operation so the timing is isolated to the equality operation
  • Run each check 20 times and obtain the mean

Some variation is to be expected based on processor load and garbage collection.

Results

Using Node v12.10.0:

  • String equality is slightly faster at 13.15ms vs BigInt at 16.57ms for 100k comparisons.

  • Set operations are slower with String taking 18.02ms and BigInt at 29.64ms for 100k has operations.

String

1 eq 13.23175197839737 set 17.189592957496643  
2 eq 13.600979030132294 set 12.019134998321533  
3 eq 15.073632001876831 set 12.628647029399872  
4 eq 14.114533007144928 set 27.956539034843445  
5 eq 13.381063997745514 set 18.252004981040955  
6 eq 13.017056047916412 set 16.98785400390625  
7 eq 14.498027980327606 set 13.097276985645294  
8 eq 11.781324028968811 set 34.796831011772156  
9 eq 12.341643989086151 set 6.570370018482208  
10 eq 12.617027997970581 set 22.389307022094727  
11 eq 13.271285951137543 set 12.08048701286316  
12 eq 13.382215976715088 set 16.717054963111877  
13 eq 13.256445050239563 set 23.208078026771545  
14 eq 14.246708035469055 set 7.033877968788147  
15 eq 12.464969038963318 set 27.308405995368958  
16 eq 12.984880983829498 set 17.228513956069946  
17 eq 13.156741976737976 set 18.262275993824005  
18 eq 15.240478992462158 set 22.551500976085663  
19 eq 11.217489004135132 set 12.099881052970886  
20 eq 10.300911962985992 set 22.074963986873627  
ave eq: 13.15895835161209 ave set: 18.022629898786544  

BigInt

1 eq 18.2114360332489 set 43.37821298837662  
2 eq 15.880737006664276 set 14.06153404712677  
3 eq 17.33941501379013 set 24.353480994701385  
4 eq 17.68426501750946 set 23.735161006450653  
5 eq 15.031556010246277 set 33.788013994693756  
6 eq 18.21529197692871 set 32.80000102519989  
7 eq 16.17084902524948 set 32.72683399915695  
8 eq 12.563468992710114 set 14.226978957653046  
9 eq 14.412819027900696 set 30.971244990825653  
10 eq 17.039519011974335 set 32.091638028621674  
11 eq 17.340678989887238 set 23.37364900112152  
12 eq 15.572706997394562 set 43.803456008434296  
13 eq 16.439077019691467 set 14.510381996631622  
14 eq 15.188311994075775 set 41.61436003446579  
15 eq 16.165686011314392 set 31.141061007976532  
16 eq 18.054711997509003 set 24.658231019973755  
17 eq 17.224171042442322 set 32.109862983226776  
18 eq 16.78733402490616 set 23.696675956249237  
19 eq 18.92676204442978 set 52.499163031578064  
20 eq 17.287310004234314 set 23.293012022972107  
ave eq: 16.576805362105368 ave set: 29.641647654771806  

Code

const crypto = require("crypto");  
const { performance } = require("perf_hooks");

function createRandom(num) {  
  let vectors = new Array(num);
  for (let i = 0; i < num; i++) {
    vectors[i] = crypto.randomBytes(32).toString("hex");
  }
  return vectors;
}

function timeEquality(val, vectors) {  
  const start = performance.now();
  for (let i = 0; i < vectors.length; i++) {
    if (val === vectors[i]) console.log("found");
  }
  return performance.now() - start;
}

function timeSet(val, set) {  
  const start = performance.now();
  for (let i = 0; i < set.size; i++) {
    if (set.has(val)) console.log("found");
  }
  return performance.now() - start;
}

function testString(n = 10 ** 6) {  
  const val = createRandom(1)[0].toString("hex");
  const vectors = createRandom(n).map(p => p.toString("hex"));
  const set = new Set(vectors);
  return [timeEquality(val, vectors), timeSet(val, set)];
}

function testBigInt(n = 10 ** 6) {  
  const val = BigInt("0x" + createRandom(1)[0].toString("hex"));
  const vectors = createRandom(n).map(p => BigInt("0x" + p.toString("hex")));
  const set = new Set(vectors);
  return [timeEquality(val, vectors), timeSet(val, set)];
}

function run(method, iter) {  
  console.log(method.name);
  let sumEq = 0;
  let sumSet = 0;
  for (let i = 0; i < iter; i++) {
    let [eq, set] = method();
    console.log(i + 1, "eq", eq, "set", set);
    sumEq += eq;
    sumSet += set;
  }
  console.log("ave eq:", sumEq / iter, "ave set:", sumSet / iter);
  console.log();
}

run(testString, 20);  
run(testBigInt, 20);
comments powered by Disqus