ryanhagfors@ - Thanks for filing the issue...!!

Could you please provide a sample webpage having field to enter state's address.
This will help us in triaging the issue further.

Thanks...!!

Attached is an example of a webpage having this field.  This actually happens on any form on any website that has a City, State, Zip field that doesn't have the "autocomplete=no" attribute.  It also happens to the city and zip code fields, but not quite as bad as the state field.

Deleted: webex.html 166 KB

webex.html 166 KB View Download

Problem is when autofill tries to identify profiles that are subsets of other profiles here: https://cs.chromium.org/chromium/src/components/autofill/core/browser/personal_data_manager.cc?q=personal_data_manager&dr=C&l=997

This is a O(n^2) operation, with 100 profiles, this would require 10000 loops and each takes about 1ms, which is 10 seconds.

There is no easy way to bring the complexity down, the best way to do this is probably do the subset 
checking when user updates/creates profile and mark them in the db. 

I can try to bring down the cost of each loop from 1ms to maybe .3ms by caching some of the results
(phone number parsing/normalized value), but it'd still take up to seconds when there is more than 100
profile.

Given this is such a rare use case, and we now have disused profile deletion in place, and when there is a lot profiles, removing profiles that are a subset will not help a lot, i'd suggest to only do
the subset checking when there is less than 30(so autofill should return within a second).

Thanks for the explanation! 

I think that showing 100 suggestions is not a good UX regardless of the time it takes, since the goal of Autofill is to enable to user to fill forms faster. We should probably show only to 15 or so most relevant profiles? We could make an experiment with this to make sure it does not affect usage negatively. But, I'm pretty confident it will not.

Also, for profiles not shown initially, if the user starts typing the suggestions are recomputed to include only matching profile. Therefore they should still be able to fill any of their profiles.

What do you think?

Make sense..

On my desktop though, autofill already only show at most 3 suggestions. 

Maybe it's because https://cs.chromium.org/chromium/src/components/autofill/core/browser/personal_data_manager.cc?q=personal_data_manager&dr=C&l=1036

I don't mind lower the limit to 15 for subset removing.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/dbd3b1c8e4f101cc90b11052cfa0a516e26f647e

commit dbd3b1c8e4f101cc90b11052cfa0a516e26f647e
Author: Hui(Andy) Wu <wuandy@chromium.org>
Date: Fri Jan 05 19:43:28 2018

[Autofill] Only run subset removing when profiles are <= 15.

Subset removing for user profiles is a O(n^2) operation, where n is the
number of profiles. This easily runs up to seconds even minutes if user
has more than 50 profiles.

Given that such user cases are rare, and we already have profile deletion
running, and when there is a lot profiles, subset removing does not bring
a lot value, we will only run it when the profiles are less or equal to
15.

Bug:  793089 
Change-Id: I8930d55789fd74b88ce8b7423aa5059975aeec42
Reviewed-on: https://chromium-review.googlesource.com/852369
Commit-Queue: Hui Wu <wuandy@chromium.org>
Commit-Queue: Sebastien Seguin-Gagnon <sebsg@chromium.org>
Reviewed-by: Sebastien Seguin-Gagnon <sebsg@chromium.org>
Cr-Commit-Position: refs/heads/master@{#527344}
[modify] https://crrev.com/dbd3b1c8e4f101cc90b11052cfa0a516e26f647e/components/autofill/core/browser/personal_data_manager.cc
[modify] https://crrev.com/dbd3b1c8e4f101cc90b11052cfa0a516e26f647e/components/autofill/core/browser/personal_data_manager_unittest.cc