localeCompare extremely slow sometimes

[gnprice]

Bug Description

• I have run gradle clean and confirmed this bug does not occur with JSC

Hermes version: (whatever's in RN 0.70.6)
React Native version (if any): 0.70.6 (the current latest)
OS version (if any): Android 13
Platform (most likely one of arm64-v8a, armeabi-v7a, x86, x86_64): arm64-v8a

Steps To Reproduce

1. Clone https://github.com/gnprice/hermes-localecompare-repro .
2. Run it with npx react-native run-android.
3. Observe the log lines showing calls to String.prototype.localeCompare taking multiple seconds each. For example:

 LOG  sorting...
 LOG  slow localeCompare: 8836ms for 'vihmdxim' vs 'vlqkdtzn'
 LOG  slow localeCompare: 2078ms for 'ezkvpvbg' vs 'ivkpfinh'
 LOG  slow localeCompare: 6568ms for 'ctanfzkj' vs 'ctjhzdyi'
 LOG  slow localeCompare: 7639ms for 'hgyzpilj' vs 'hhpnlwqf'
 LOG  slow localeCompare: 7337ms for 'jzninmrt' vs 'orbuzdcq'
 LOG  slow localeCompare: 6872ms for 'rnarhxnr' vs 'rnauqlwl'
 LOG  slow localeCompare: 3648ms for 'nfdeptde' vs 'nfgpjekx'
 LOG  ...done, took 56938ms

Those extremely slow calls are rare relative to the total number of calls. But because they're so extremely slow, they account for most of the total time — about 75% of the whole sort in this example.

code example

The repro repo above just consists of a fresh React Native app on the latest version (from npx react-native init), with the following code added at the top of the render function:

  const randInt = (end, start = 0) =>
    Math.floor(Math.random() * (end - start) + start);
  const alphabet = 'abcdefghijklmnopqrstuvwxyz';
  const names = Array.from({length: 30000}, () =>
    Array.from({length: 8}, () => alphabet[randInt(alphabet.length)]).join(''),
  );

  console.log('sorting...');
  const s = Date.now();
  names.sort(localeCompare);
  console.log(`...done, took ${Date.now() - s}ms`);

  function localeCompare(a, b) {
    const s = Date.now();
    const result = a.localeCompare(b);
    const e = Date.now();
    if (e - s > 100) {
      console.log(`slow localeCompare: ${e - s}ms for '${a}' vs '${b}'`);
    }
    return result;
  }

That is, it makes up a long list of boring short alphabetic strings, and sorts them. The comparator just calls String.prototype.localeCompare, and times the call.

The Expected Behavior

Calling localeCompare on a string should be fast — certainly far less than a second, for any non-gigantic strings.

Other notes

I do not reproduce the issue when running in an emulated Android device, on x86_64. So it may be architecture-dependent.

[tmikov]

The following can be executed locally without the need of a RN app:

  print("gen...");
  const randInt = (end, start = 0) =>
    Math.floor(Math.random() * (end - start) + start);
  const alphabet = 'abcdefghijklmnopqrstuvwxyz';
  const names = Array.from({length: 30000}, () =>
    Array.from({length: 8}, () => alphabet[randInt(alphabet.length)]).join(''),
  );

  print('sorting...');
  const s = Date.now();
  names.sort(localeCompare);
  print(`...done, took ${Date.now() - s}ms`);

  function localeCompare(a, b) {
    const s = Date.now();
    const result = a.localeCompare(b);
    const e = Date.now();
    if (e - s > 1) {
      print(`slow localeCompare: ${e - s}ms for '${a}' vs '${b}'`);
    }
    return result;
  }

The results are shocking:

$ hermes-rel tt.js
gen...
sorting...
...done, took 1690ms

$ v8 --jitless tt.js
gen...
sorting...
...done, took 149ms

$ jsc --useJIT=false tt.js
gen...
sorting...
...done, took 93ms

[gnprice]

The results are shocking:

Yeah. Thanks for that additional demo.

So it seems there are two different symptoms here:

• In general, String.prototype.localeCompare is quite slow — well over 10x slower than in V8 or JSC.

  This is the one demonstrated in the above comment.

• A small fraction of the time, and apparently only on some architectures (yes on arm64, no on x86_64), localeCompare is extremely slow. This is quite infrequent (like 1 in ~10000 calls); but when it does happen, a single call takes thousands of milliseconds.

  This is the one demonstrated in my report at the top.

  Because the time for a single call is so very long, this issue makes it risky to use localeCompare at all, at least in any React Native app or anywhere else where the JS code is responsible for a UI — because using it means that occasionally the UI will go unresponsive for multiple seconds.

  The extremely slow calls are also slow enough that when sorting a long list, the small number of extremely slow calls take more time than all the rest — even though the others are themselves slow compared to V8 or JSC.

[tmikov]

It is interesting that this is reproducible both on MacOS and Android, since on Android localeCompare forwards to a Java implementation, while on MacOS it uses CoreFoundation. It appears that both are quite slow.

[neildhar]

I did some quick profiling on macOS, which suggests there is likely some low hanging fruit for optimisation. Specifically, with Intl disabled, I see most of the time being spent in CFStringCompareWithOptionsAndLocale. However, when Intl is enabled:

1. The overall execution time is halved
2. That function becomes a small fraction of execution time, most of the time is spent initialising the Collator

So it seems like we could achieve a dramatic speedup if we:

1. Avoid repeatedly recreating the Collator when Intl is enabled
2. Figure out why Intl is able to do the string comparison itself faster, and try to port that to the non-Intl build

[majugurci]

I have also bumped into this situation in react native using hermes.

I had a list of objects which needed to be sort in locale.
Using this code:

list.sort((a, b) => a.name.localeCompare(b.name, locale))

it would take few seconds to finish sorting for 1000 items.
On production where there are 10000 items it would take almost a minute.

When changed to this:

const collator = new Intl.Collator(locale);
list.sort((a, b) => collator.compare(a.name, b.name));

it would be over really fast. I haven't messured times but it is super fast compared to localeCompare.

Also I noticed if I leave the locale in localeCompare it is working just as fast as collator:

list.sort((a, b) => a.name.localeCompare(b.name))

So i guess there are some optimizations for default locale, probably the collator is reused when using default locale.

Anyway I wrote this just if it can help to track the issue and give more insight.