[$250] Performance: optimize LHN sidebar sorting with pre-computed sort keys

[mountiny]

Problem

Left-hand navigation (LHN) sidebar sorting used Intl.Collator.compare() on every comparison in each sort pass — on the order of hundreds of thousands of calls per sort on large accounts. Each call applies locale-sensitive collation rules and is relatively expensive.

Approach (PR)

Pre-compute sort keys per report name: lowercase, zero-pad numeric segments, cache at module scope. Sort primarily compares plain strings; fall back to Intl.Collator only when sort keys tie (a small fraction of comparisons).

Tradeoff: Locale-specific ordering for some diacritics (e.g. Swedish ä/ö, German ß, Spanish ñ) follows Unicode codepoint order instead of full locale collation. Numeric sorting is preserved.

Reported impact (author): iOS ~740ms → ~164ms; Android ~2.1s → ~380ms on tested accounts.

Implementation

#87847 — Optimize LHN sidebar sorting with pre-computed sort keys

Related (from PR)

• #80560
• #77173

QA / verification

• Fresh/small account: create chats, pin one (stays on top), type in another (ordering updates as before).
• High–chat-count account: sidebar still sorts sensibly; spot-check names with diacritics if relevant to your locale.
• No new JS console errors.

Upwork Automation - Do Not Edit

• Upwork Job URL: https://www.upwork.com/jobs/~022044208373635887976
• Upwork Job ID: 2044208373635887976
• Last Price Increase: 2026-04-15

Issue Owner

Current Issue Owner: @mallenexpensify

[MelvinBot]

Proposal

Problem: LHN sidebar sorting calls Intl.Collator.compare() on every comparison during each sort pass — hundreds of thousands of calls on large accounts, causing iOS ~740ms and Android ~2.1s sort times.

Solution: Pre-compute a normalized sort key per report name (lowercase + zero-padded numerics), compare with plain </> operators, and fall back to Intl.Collator only when sort keys tie.

The implementation in Expensify/App#87847 is correct and well-structured. Two observations worth noting:

1. Unbounded cache (low risk)

sortKeyCache is a module-level Map with no eviction. Each entry is two short strings (~50–100 bytes), so even 10,000 unique names use under 1MB. Stale entries (from renamed reports) are harmless — they're keyed by display name, so old names just become unreachable. Other caches in the codebase (e.g., SearchQueryUtils.ts:585) use a max-size bound; adding one here (e.g., 500–1000) would be consistent but isn't strictly necessary.

2. Locale ordering tradeoff (low-to-moderate impact)

The fallback to Intl.Collator only triggers when sort keys are identical. Names that differ in locale-sensitive ways but produce different toLowerCase() codepoints will never reach the fallback:

• German: Intl.Collator('de') treats ö ≈ oe, sorting "Möller" near "Moeller". The new code places ö (U+00F6) after all ASCII, so "Möller" sorts after "Mzz".
• Spanish: ñ should sort between n and o. The new code places ñ (U+00F1) after all ASCII letters.
• Swedish: ä/ö sort after z in Swedish — which coincidentally matches Unicode codepoint order, so this works by accident.

Practical impact is low: most LHN display names are ASCII (workspace names, auto-generated report names, English user names). The 4–5× performance improvement on large accounts is a worthwhile tradeoff. No locale-sensitive sort tests exist in the test suite currently.

What needs to happen:

1. Merge Expensify/App#87847 — the approach is sound and the perf gains are significant
2. Optionally: add a size cap to sortKeyCache (e.g., if (sortKeyCache.size > 1000) sortKeyCache.clear()) for consistency with other caches in the codebase
3. QA per the issue description: test with small accounts (pin/unpin, ordering updates) and large accounts (sidebar sorts sensibly)

---

Next Steps for Contributor+ team: Reply with @MelvinBot implement this to create a draft PR, @MelvinBot <your feedback> to refine this analysis, or explain why you are rejecting Melvin's proposal.

[melvin-bot]

Current assignee @abzokhattab is eligible for the External assigner, not assigning anyone new.

[melvin-bot]

Job added to Upwork: https://www.upwork.com/jobs/~022044208373635887976

[yuvrajangadsingh]

Proposal

Please re-state the problem that we are trying to solve in this issue.

The LHN sidebar sort calls Intl.Collator.compare() on every pair comparison across all five sorted categories. On large accounts this produces hundreds of thousands of collator calls per sort pass, causing iOS sort times around 740ms and Android around 2.1s.

What is the root cause of that problem?

The hot path is sortCategorizedReports in src/libs/SidebarUtils.ts:502. At line 522, compareDisplayNames calls localeCompare(a.displayName, b.displayName) on every comparison:

// SidebarUtils.ts:522
const compareDisplayNames = (a: MiniReport, b: MiniReport) =>
    (a?.displayName && b?.displayName ? localeCompare(a.displayName, b.displayName) : 0);

localeCompare comes from useLocalize() in useSidebarOrderedReports.tsx:74, and bottoms out at LocaleContextProvider.tsx:166:

const localeCompare: LocaleContextProps['localeCompare'] = (a, b) => collator.compare(a, b);

where collator = new Intl.Collator(currentLocale, COLLATOR_OPTIONS) (line 144). Intl.Collator.compare() is expensive per call. With 5000 reports, O(N log N) sort passes across five categories produce ~hundreds of thousands of calls.

Note that categorizeReportsForLHN already does a single-pass precomputation loop at lines 428-470 (computing display names, pinned state, draft state, etc.) and builds MiniReport objects (type defined at line 206). The sort key computation can slot in here.

What changes do you think we should make in order to solve the problem?

The approach in PR #87847 is correct. Concretely:

1. Add a sortKey field to MiniReport (SidebarUtils.ts:206-210)

type MiniReport = {
    reportID?: string;
    displayName: string;
    sortKey: string;           // pre-computed: lowercase + zero-padded numerics
    lastVisibleActionCreated?: string;
};

2. Compute sortKey once in the existing precomputation loop (categorizeReportsForLHN, ~line 447-452)

Display name is already computed at line 447. Compute the sort key right there, before pushing to precomputedReports:

const displayName = getReportName({report, conciergeReportID});
const sortKey = displayName.toLowerCase().replace(/\d+/g, (n) => n.padStart(10, '0'));
const miniReport: MiniReport = {reportID, displayName, sortKey, lastVisibleActionCreated: report.lastVisibleActionCreated};

3. Change compareDisplayNames to use plain string comparison, falling back to localeCompare only on ties (SidebarUtils.ts:522)

const compareDisplayNames = (a: MiniReport, b: MiniReport): number => {
    if (!a?.displayName || !b?.displayName) {
        return 0;
    }
    if (a.sortKey < b.sortKey) { return -1; }
    if (a.sortKey > b.sortKey) { return 1; }
    return localeCompare(a.displayName, b.displayName); // tie-break with full locale collation
};

Storing sortKey on MiniReport (computed once per report during categorization) avoids a module-level Map lookup on every comparison and keeps all precomputation in one place. The computation cost is O(N) during categorization vs O(N log N) Intl.Collator.compare() calls during sorting.

The existing perf test at tests/perf-test/SidebarUtils.perf-test.ts uses 15,000 reports and is the right baseline to run before/after to confirm the gains.

Tradeoff: names that differ only in diacritics with the same codepoint as ASCII will bypass locale collation. Tie-break via localeCompare still handles names that are identical under lowercase + numeric normalization. This is the same tradeoff acknowledged in the issue and acceptable given the 4-5x perf improvement on large accounts.

What alternative solutions did you explore? (Optional)

An alternative is a module-level Map<string, string> cache (keyed by display name) computed lazily at sort time. This would persist sort keys across multiple sort passes without recomputing. Downside: unbounded growth. Using MiniReport.sortKey computed at categorization time is slightly simpler and keeps all data co-located. A bounded module-level cache could complement this if display names change infrequently.