localeCompare extremely slow sometimes #867

Activity

1. gnprice

   added

   bugSomething isn't workingSomething isn't working

   on Dec 16, 2022
2. tmikov commented on Dec 17, 2022

   

   tmikov

   on Dec 17, 2022

   Last edited by tmikov

   Contributor

   More actions

   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
   

   👍React with 👍2Reacted by Greg Price and Chris Bobbe
3. gnprice commented on Jan 11, 2023

   

   gnprice

   on Jan 11, 2023

   Author

   More actions

   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.
4. tmikov commented on Jan 11, 2023

   

   tmikov

   on Jan 11, 2023

   Contributor

   More actions

   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.
5. neildhar commented on Jan 11, 2023

   

   neildhar

   on Jan 11, 2023

   Contributor

   More actions

   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

   👍React with 👍3Reacted by Greg Price, mgvictor7 and Tomas Mozeris
6. majugurci commented on Dec 27, 2023

   

   majugurci

   on Dec 27, 2023

   Last edited by majugurci

   More actions

   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.

   👍React with 👍8Reacted by Tzvetan Mikov, Adam Horodyski, Hur Ali, Youssef Makhoul, Matthias Tylkowski, Raymond Penners, Kyle Thomson and Jamon Holmgren
7. jamonholmgren commented on Dec 29, 2025

   

   jamonholmgren

   on Dec 29, 2025

   Last edited by jamonholmgren

   More actions

   I wonder if this would be a good candidate for a new Hermes extension, moving to the Intl.Collator approach that @majugurci mentioned.

   EDIT: in our internal tests, the Intl.Collator approach is faster but still not fast enough. We ended up going with a crude (and limited) but very fast string compare instead -- something like this:

   type SortComparator<T> = (a: T, b: T) => number
   
   export function byStringAsc<T>(propName: keyof T): SortComparator<T> {
     return (a, b) => {
       const aVal = String(a[propName] ?? "")
       const bVal = String(b[propName] ?? "")
       return aVal < bVal ? -1 : aVal > bVal ? 1 : 0
     }
   }
   
   export function byStringDesc<T>(propName: keyof T): SortComparator<T> {
     return (a, b) => {
       const aVal = String(a[propName] ?? "")
       const bVal = String(b[propName] ?? "")
       return bVal < aVal ? -1 : bVal > aVal ? 1 : 0
     }
   }
8. AI091 commented on Nov 13, 2026

   

   AI091

   on Nov 13, 2026

   More actions

   The rare multi-second calls reproduce on arm64 Android, and they are garbage-collector waits caused by the same per-call collator creation that makes localeCompare slow in general. PR: #2320.

   What happens. On Android, every localeCompare call creates a new com.facebook.hermes.intl.Collator through JNI: locale resolution, an ICU collator clone, and several finalizable objects. That is about 2 KB of Java garbage per call, or about 950 MB for the 30,000-string sort above. When ART's concurrent collector cannot keep up, the next allocation on the JavaScript thread blocks until the collection finishes, and that one localeCompare call takes seconds.

   Repro. tmikov's sort above (30,000 strings, 474,595 comparisons, every call timed), run inside the Android Intl test app with ART's collector counters around the sort. On Firebase Test Lab's arm64 image (MediumPhone.arm, API 34), Hermes static_h:

   sort round	sort time	slowest call	calls over 1 s	blocking Java collections
   0	10.7 s	2,539 ms	1	26, 9.7 s
   1	20.6 s	4,962 ms	9	23, 19.7 s
   2	21.2 s	6,853 ms	5	25, 20.5 s

   The slowest calls match ART's log lines on the JavaScript thread to the millisecond:

   WaitForGcToComplete blocked Alloc on Background for 2.538s   (call: 2,539 ms)
   WaitForGcToComplete blocked Alloc on HeapTrim for 4.961s     (call: 4,962 ms)
   WaitForGcToComplete blocked Alloc on HeapTrim for 6.818s     (call: 6,853 ms)
   

   On the x86_64 emulator, the same sort has no blocking collections and its slowest call is 5 ms. It is still slow overall (6.7-8.5 s, about 1 GB of Java garbage). That fits "arm64 yes, x86_64 no" above. Our reading, not tested: whether a device blocks depends on how fast its collector runs compared with the allocation rate, not on the instruction set.

   Passing a locale is much worse. a.localeCompare(b, 'en') goes through the best-fit locale matcher on every call. On the emulator, the same sort took 617.7 s and allocated 103.7 GB of Java objects (41,196 collections). That matches the "a few seconds for 1000 items" report above.

   In a production app. In a React Native 0.88 app on Android, Collator.<init> was the largest single JavaScript cost we profiled, and most of the app's Java garbage was collators waiting to be finalized. On a physical Galaxy A03s (133 MB Java heap), the UI thread waited up to 22.8 s at a time for the collector. When the app stopped calling localeCompare, those waits went away on the A03s and on a Galaxy A54.

   With the fix (reuse the collator while locales, options and the default locale stay the same), the same arm64 run: sort 0.36-0.41 s, slowest call 9 ms, no blocking collections, 29 MB of Java allocation. With 'en': 0.39-0.44 s. Full numbers are in the PR.

   Not yet measured: the patched engine on a physical phone. We had no device quota left. The phone evidence above comes from an app that stopped calling localeCompare, not from the patched engine.

   Workaround until a release has the fix: create one collator and reuse it. new Intl.Collator().compare sorted the same strings in 0.23 s on the arm64 image without the fix, with no blocking collections:

   const collator = new Intl.Collator(); // create once, outside the comparator
   names.sort(collator.compare);