[HOLD for payment 2025-01-07] [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]

⚠️ Looks like this issue was linked to a Deploy Blocker here

If you are the assigned CME please investigate whether the linked PR caused a regression and leave a comment with the results.

If a regression has occurred and you are the assigned CM follow the instructions here.

If this regression could have been avoided please consider also proposing a recommendation to the PR checklist so that we can avoid it in the future.

[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.79-5 and is now subject to a 7-day regression period 📆. Here is the list of pull requests that resolve this issue:

• Search suffix tree implementation #51954

If no regressions arise, payment will be issued on 2025-01-07. 🎊

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

• @hannojg does not require payment (Contractor)
• @ahmedGaber93 requires payment through NewDot Manual Requests

[melvin-bot]

Payment Summary

Upwork Job

• Contributor: @hannojg is from an agency-contributor and not due payment
• Reviewer: @ahmedGaber93 owed $250 via NewDot

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]

Nice, excited to see this one done!

@danieldoglas and @ahmedGaber93, do you agree that $250 is the correct payment for this PR review? I know it was quite a big project, so I want to make sure we shouldn't be changing the price to reflect the amount of work.

[danieldoglas]

Yeah, I think that's fine since the review came from a second round of testings.

[ahmedGaber93]

do you agree that $250 is the correct payment for this PR review?

Yeah, it's fine.

[sakluger]

Great, thanks for confirming! Please use the payment summary above when requesting payment.

[JmillsExpensify]

$250 approved for @ahmedGaber93

[roryabraham]

I notice we never implemented the SuffixUkkonenTree for emojis, we're still using the slower Trie we created a few years ago. Would be good to upgrade that so that we don't have two Trie implementations forever