[Performance] Typing in search is very laggy for big accounts

[hannojg]

If you haven’t already, check out our contributing guidelines for onboarding and email [email protected] to request to join our Slack channel!

---

What performance issue do we need to solve?

On a very big account typing in search for the first time is incredibly laggy, see recording. The user is continuously trying to type but the application is dropping so many frames that the text is only updated in jumps:

slow_search.mov

What is the impact of this on end-users?

Very slow and frustrating search experience. Borderline functional.

List any benchmarks that show the severity of the issue

The customer shared a profile trace with us:

Firefox 2024-07-25 10.42 profile.json.gz

(note: the trace also contains other test cases as well)

The customer had ~15k reports loaded in onyx when these tests were conducted, although in focus mode only 6 chats were displayed.

Proposed solution (if any)

None yet, I will go through the profile and see what can be optimised, what exactly caused those lags.

List any benchmarks after implementing the changes to show impacts of the proposed solution (if any)

not available yet

Platforms:

Which of our officially supported platforms is this issue occurring on?

• Android: Native
• Android: mWeb Chrome
• iOS: Native
• iOS: mWeb Safari
• MacOS: Chrome / Safari
• MacOS: Desktop

Version Number: v9.0.11-5
Reproducible in staging?: not tested
Reproducible in production?: yes
Email or phone of affected tester (no customers): customer
Logs: See performance file
Notes/Photos/Videos: See attached video
Expensify/Expensify Issue URL: n/a
Issue reported by:@hannojg
Slack conversation:https://expensify.slack.com/archives/C05LX9D6E07/p1721919928992729

View all open jobs on Upwork

Issue Owner

Current Issue Owner: @sakluger

[melvin-bot]

Auto-assigning issues to engineers is no longer supported. If you think this issue should receive engineering attention, please raise it in #whatsnext.

[hannojg]

cc @sakluger (feel free to assign me as I (or someone from my team) will work on this ticket!)

[hannojg]

Just started working on this issue. I can see that OptionListUtils.filterOptions is particularly slow. The reduceRight function (which is called as of filterOptions) took 10s to complete for the customer.

I can kinda reproduce the lag if I enable lower performance settings in chrome (basically bringing my Cpu closer to the one the customer had). Working on ideas for improving the performance here!

[hannojg]

Created a PR that adds performance timings, so we can track upcoming performance improvements better:

• chore: add timing collection for filterOptions #46807

[hannojg]

Okay, I have a proposal for a solution moving forward:

Highlevel solution: use a trie structure for search

Right now our search data structure + search algorithm aren't really efficient. We loop over every item performing multiple comparison operations.

We can make this way more efficient by using a trie structure and prefix search.

Performance gains

I ran a test with the customers onyx data, right now only focusing on searching through the personal details.

• Device: Samsung S21
• Personal detail count: 16 039
• Only including personal details (will optimise report search later by same solution)
• Running 10 test iterations

	Before: OptionsListUtils.getSearchOptions	✨ After: using trie structure
mean	299.97ms	0.49ms
stdev	6.5ms	0.36ms

So, right now this user on mobile will have a dead JS thread for ~300ms when typing in the search (dropping 18 frames), while with a trie, its just ~0.5ms, so no frames dropped really.
Thats ~600x faster. For the customer where before this part of the function took 10s, this would only take ~16ms now approximately.

Tests were conducted here on this branch

Changes needed / roadmap

• We need to implement a trie structure that supports searching for substrings as well (our current trie implementation doesn't support that)
• We need to calculate the trie beforehand (it takes a bit time and space to calculate it)
• We need to calculate two tries I think, one for reports, one for personal details
• We might want to revisit our chain of getting search results, which currently is:
  • const options = OptionsListUtils.createOptionList(personalDetails, reports)
  • const searchOptions = OptionsListUtils.getSearchOptions(options, '', betas)
  • const filteredOptions = OptionsListUtils.filterOptions(searchOptions, searchValue)
  • ^ This can maybe be optimised into less steps, or getSearchOptions would be replaced with creating the search trie
• Wire everything together

Caveats

Right now building the trie takes some time and a fair amount of memory. I want to experiment a bit more using other DS such as generalised suffix tree or suffix arrays, and see which one works best!

[melvin-bot]

Reviewing label has been removed, please complete the "BugZero Checklist".

[melvin-bot]

The solution for this issue has been 🚀 deployed to production 🚀 in version 9.0.17-2 and is now subject to a 7-day regression period 📆. Here is the list of pull requests that resolve this issue:

• chore: add timing collection for filterOptions #46807

If no regressions arise, payment will be issued on 2024-08-14. 🎊

For reference, here are some details about the assignees on this issue:

• @hannojg does not require payment (Contractor)

[hannojg]

Started a discussion here how we want to move forward technically:

https://expensify.slack.com/archives/C05LX9D6E07/p1723209631007999

[sakluger]

No payment required for the above PR:

[melvin-bot]

Reviewing label has been removed, please complete the "BugZero Checklist".

[melvin-bot]

The solution for this issue has been 🚀 deployed to production 🚀 in version 9.0.54-11 and is now subject to a 7-day regression period 📆. Here is the list of pull requests that resolve this issue:

• Revert "Revert "Search suffix tree implementation"" #51332

If no regressions arise, payment will be issued on 2024-11-05. 🎊

For reference, here are some details about the assignees on this issue:

• @hannojg does not require payment (Contractor)
• @ahmedGaber93 requires payment (Needs manual offer from BZ)

[sakluger]

Okay I'll hold off on payment and ask again when it seems like things have settled a bit.

[hannojg]

New PR is available here for review:

• Search suffix tree implementation #51954

[melvin-bot]

Payment Summary

Upwork Job

• Contributor: @hannojg is from an agency-contributor and not due payment
• ROLE: @ahmedGaber93 paid $(AMOUNT) via Upwork (LINK)

BugZero Checklist (@sakluger)

• I have verified the correct assignees and roles are listed above and updated the neccesary manual offers
• I have verified that there are no duplicate or incorrect contracts on Upwork for this job (https://www.upwork.com/ab/applicants//hired)
• I have paid out the Upwork contracts or cancelled the ones that are incorrect
• I have verified the payment summary above is correct

[sakluger]

Removing the payment hold and updating the title since it doesn't seem like we're ready for payment quite yet.