Javascript: Why does equality of strings take longer for longer strings?

Question

In the following code, 1Mil strings of equal length get created. Then they are looped through to find a matching string. The first run has strings that are 3 times longer than the second run.

The expected outcome was that the time it takes to do equality comparison of strings of different length would not vary due to 'string interning'. However, results show that a string with 3 times the length takes about 3 times to do an equality check. Why is that?

import { v4 as uuidv4 } from 'uuid';

export const uuid = () => {
  return uuidv4();
};

function createSingleId(howManyUuidsInOneId1: number) {
  let id = '';
  for (let j = 0; j < howManyUuidsInOneId1; j++) {
    id += uuid();
  }
  return id;
}

function generate(howManyIds: number, howManyUuidsInOneId: number) {
  const ids = [];
  for (let i = 0; i < howManyIds; i++) {
    ids.push(createSingleId(howManyUuidsInOneId));
  }
  return ids;
}

const main = (howManyIds: number, howManyUuidsInOneId:number) => {

  const ids = generate(howManyIds, howManyUuidsInOneId);

  const toFind = createSingleId(howManyUuidsInOneId);

  console.log(`Sample id being compared: '${toFind}'`);

  const before = new Date().getTime();

  ids.filter(id => id === toFind);

  console.log(`Took '${new Date().getTime() - before}ms' to loop through and equal compare '${howManyIds}' when stacked '${howManyUuidsInOneId}' in single id`);
};

main(1000000, 3);
main(1000000, 1);

Output:

Sample id being compared: 'dc03bf00-6f2a-48d9-b3ca-b6ac45782c5cefaa92c0-9372-4f47-bcec-f9fbb41d4625e0c5c278-b574-4a9f-a77e-110cbc6bf601'
Took '64ms' to loop through and equal compare '1000000' when stacked '3' in single id
Sample id being compared: '07e693ce-49a1-4cc6-90e1-0bd99629123b'
Took '19ms' to loop through and equal compare '1000000' when stacked '1' in single id

> node --version
v15.14.0

It does need to compare strings character by character, and that takes longer for longer strings…?! Interning merely means that you won't have multiple copies of the string in memory. The engine could be clever and realise that it's trying to compare the same memory location and thereby skip it entirely, but apparently it doesn't do that, and/or the strings aren't being interned (why do you think they should be?). — deceze
– deceze ♦, Commented Sep 21, 2021 at 8:13

Bergi · Accepted Answer · 2021-09-21 09:38:41Z

4

The expected outcome was that the time it takes to do equality comparison of strings of different length would not vary due to 'string interning'.

No, string interning only means that for some strings you know they're the same because they're stored in the same location, e.g. for string values created from the same string literals. But not all strings (especially not dynamically created ones) are getting interned, and having different memory addresses says nothing about the contents of the strings. If the memory location check fails, you still need to compare the string contents as usual.

Some example to demonstrate this:

function generateString(len) {
  let x = "";
  for (let i=0; i<len; i++) x+= String.fromCharCode(64+i%64);
  return x;
}
function time(callback, desc) {
  const before = performance.now();
  const res = callback();
  console.log(`Took ${performance.now()-before}ms to ${desc}`);
  return res;
}

const strLen = 5000000;
const a = generateString(strLen);
const b = generateString(strLen);
console.assert(a === b);
const str = a;
time(() => str === a, 'compare a with itself');
time(() => str === b, 'compare a with b');

a and b have the same contents, but are different string objects (in memory) because they were accumulated in different generateString calls. str references the same value that a does.

edited Sep 21, 2021 at 9:38

answered Sep 21, 2021 at 9:20

Bergi

671k162 gold badges1k silver badges1.5k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user7858768 Over a year ago

Makes, a lot of sense. For some reason, I thought all strings are interned dynamic or not.

Collectives™ on Stack Overflow

Javascript: Why does equality of strings take longer for longer strings?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related