[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 contributors@expensify.com 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

[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:

[hannojg]

I just opened a PR hat shows a PoC for using web workers for running the search, which will unblock the main thread:

• [WIP] WebWorker Demo (to improve search performance) #47432

I am now seeking approval on this new technical design here.

(Note: I am OOO for the rest of the week and will continue next week Monday 19.08)

[sakluger]

Moving to weekly to make Melvin happy, we can move it back next week.

[sakluger]

@hannojg any updates on this one?

[hannojg]

It has been discussed here that our first proposal to offload the work to a different thread has been postponed (as we want to stay single threaded as long as possible).

We are now working on a new proposal to use a more efficient data structure and a very fast search algorithm. Will post the proposal and a PoC today/trmrw.

[sakluger]

I asked for updates in the main tracking issue: #46595

[sakluger]

Looks like we have a WIP PR that will speed up search by 2456x.

[marcaaron]

🤯 that's sick!

[sakluger]

Looks like the draft PR is coming along! I see commits and reviews.

[hannojg]

I am back from OOO and working on it - expect to have a reviewable PR by tmrw!

[hannojg]

Status update:

• I made good progress on the PR, its cleaned up, has tests and documentation and is very close to be completed
• There are two left todos:
  • One reassure test fails currently, indicating i introduced more renders than previously - i believe this to be a mistake, have to investigate
  • I found one edge case where the search function is currently returning not all results, investigating

Future Improvements:

Building the tree can take some time on lower end devices (taking in millisecond range here - will get definite numbers soon). As an optimisation we could store the search tree in mmkv using array buffers. I believe this to be a really good optimisation for lower end mobile devices - but i don't want to convolute the current PR and will open a follow up ticket. (Additionally i am trying to see how the construction of the tree can be further improved)

TL;DR: Very positive to have the PR ready and tested by TMRW!

[hannojg]

Status update:

• We weren't happy with the build time performance of the tree on android devices and spend time optimising it
• Main finding is that ArrayBuffers are way faster than regular arrays, so we migrated the tree structure to that (that would also enable us in the future to potentially share the array buffers from another thread if we want to go multi threaded)
• Build time in heavy load scenario improved from ~600ms to ~90ms (which is work we only have to do once)
• I am working on a revised version with array buffers here, will update the main PR tmrw and finish it off!

[hannojg]

PR is ready for review now!

Whats missing in the current PR is to save the created "FastSearch" (tree) instance to a context, so it can be reused (so that we don't need to recreate the tree from scratch every time our personal details / reports. change).
I figured that this would add another 200-400 lines of code and I wanted to make the lives of people reviewing not too hard - I will open an issue and do that as a follow up.

[sakluger]

This is exciting, thanks for the updates @hannojg! I can't wait to see these improvements go live, it'll be a big win.

[marcaaron]

Nice. Just catching up after OOO, but looks really impressive overall!