1795434 - Domain autocomplete provider uses inefficient linear search algorithm, excess power usage?

Status: NEW

(Firefox for Android :: Toolbar, task)

Description

[Christian Sadilek [:csadilek]]

From github: https://github.com/mozilla-mobile/android-components/issues/11638.

afaict, for each character typed, we execute autocomplete. We have two autocomplete providers: history and domains. For each character, the domain provider iterates over all of its domains:

https://github.com/mozilla-mobile/android-components/blob/54eee416e027d388535431013ad8c1f8c92913ed/components/browser/domains/src/main/java/mozilla/components/browser/domains/autocomplete/Providers.kt#L74-L95

iiuc, the US has ~500 domains – the US list has 49 and the global list has 444 lines. That's about 1000 startsWith calls per character typed, which seems excessive.

If we used a more efficient algorithm, we could save CPU and power. We haven't noticed any unreasonable delays (though it's not instantaneous on the Moto G5) so this is primarily about power. My naive solution would be to sort the domain list and do binary search (note that binarySearch is built in), getting it down to O(log n). Perhaps we can do better. Ideally, we'd measure the power difference because it's possible additional operations required to binary search are less efficient than linear traversal.

We could also consider adding a brief delay after each character typed before we start autocomplete so that we don't autocomplete if a user is just going to type over the result anyway.

We should double-check the places/history provider to make sure it's also efficient.

┆Issue is synchronized with this Jira Task

Change performed by the Move to Bugzilla add-on.

Comment 1

[BugBot [:suhaib / :marco/ :calixte]]

The severity field is not set for this bug.
:cpeterson, could you have a look please?

For more information, please visit auto_nag documentation.