One idea would be to arrange isolated origins in a tree like the following:
- org
  - foo.org
  - bar.org
      - a.bar.org
      - b.bar.org
- com
  - foo.com
  - etc.
The tree should be fairly shallow and deciding which subnode to descend into should the same as a map lookup - O(log N) for std::map and base::flat_map, O(1) for std::unordered_map (although some caveats from base/containers/README.md need to be taken into account).

Another idea would be to arrange isolated origins in a string that looks like "origin1|origin2|..." and rely on "suffix tree" representation of such string to perform substring lookups in O(<substring length>) rather than O(<full string length>) time.  This approach might make it easier to reuse code (i.e. the generic substring lookup part).

I also hear that similar optimizations might have been in the past for eTLD lookups, although I don't quite see them when looking at net::GetDomainAndRegistry.

The list is static I assume? So alternative could just have code cache the result instead of asking GetMatchingIsolatedOrigin every time, to avoid doing the same work again and again? Or build a small LRU cache

Trie is a bit complicated, especially since the logic isn't exactly string matching: https://cs.chromium.org/chromium/src/content/browser/isolated_origin_util.cc?rcl=27ebd00bcd3c6095c3626526cec2b7f438965757&l=14

I will be surprised if the traversal of the list is the bottleneck causing 10% fewer page loads. The UI thread doesn't call the lookup method as often - maybe a handful of times per navigation, mostly spaced between thread hops and network requests. However, the fact that it is traversed holding a lock might be a problem, since that blocks any checks on the IO thread, which are done on most subresource responses (due to CORB).

Looking at how it is used, it looks to me that we can just drop the lock. Currently the entries are initialized very early in the browser startup - BrowserMainLoop::PreCreateThreads(). They are only removed/added to in unit tests, which should have no threading issues. So if creation and mutation does not happen during the browser lifetime, then we don't need to lock during lookups.

This might be a cheap and easy thing to try first before going down the path of optimizing the data structure. I'm very skeptical that this lookup is that expensive, but I can always be proven wrong with some profiler data :).

(Catching up after OOO)  Thanks for filing this.  I started looking into how much overhead might be coming from large isolated origin lists.  For a list of ~1000 sites (taken from the IsolateTopPasswordSites Canary experiment), a simple a.com -> b.com navigation for a small text page with no subresources results in 32 calls to GetMatchingIsolatedOrigin, which added up to 16ms of overhead on my local Linux release build, which is definitely more than I'd expect for a basic page.  Worse, for a full page load of cnn.com, GetMatchingIsolatedOrigin was called ~800 times adding up to 600ms of overhead. (!)  I don't think this is CORB-related: SiteIsolationPolicy::IsCrossSiteDocumentBlockingEnabled() should be returning true since the  CrossSiteDocumentBlockingAlways feature is now enabled by default, which should prevent CrossSiteDocumentResourceHandler::ShouldBlockBasedOnHeaders() from checking isolated origins.  Instrumenting things a bit more, most of these calls seem to come as part of resolving GetSiteForURL inside ChildProcessSecurityPolicyImpl::CanAccessDataForOrigin(), called most frequently as part of looking up cookies in RenderFrameMessageFilter::GetCookies().

Based on this data, it's very reasonable to suspect that a long list of isolated origins is causing a lower # of page loads.  I'll experiment with various optimization approaches and see what helps the most.  E.g., it definitely make sense to avoid recomputing site URLs for isolated origins.

For now, the isolated origin list currently stays static after being initialized from field trials, command line, and built-in isolated origins.  At various points we've discussed allowing dynamic addition (e.g., for isolating sites from Safe Browsing) and might need to support this on Android, e.g. for adding a site that a user just logged in to, so that it's isolated in all future BrowsingInstances.  I think this is worth keeping in mind when working on this (e.g., if we add a cache, we should invalidate it after adding an isolated origin).

Status update.  I tried out some of the optimizations while loading some moderately complex pages (e.g., cnn.com, nytimes.com) and looking at overall delay per 1000 calls to GetMatchingIsolatedOrigin):

1.  Removing the locks.  This doesn't help that much (~10-15% improvement).  We can/should still do this, as it's easy and desirable, and we'll just need to be careful in supporting dynamic additions to the isolated origins list (e.g., for supporting one of the site isolation opt-in header proposals, adding a site that a user has just logged in to, etc).  Nasko points out that for additions we can clone the list, modify the copy, and atomically swap the list pointers.

2.  Reorganizing the list to be  map of sites -> { list of origins mapping to that site }, e.g. if foo.com, bar.foo.com, and baz.com are all isolated, we'd have 
  foo.com -> { foo.com, bar.foo.com }
  baz.com -> { baz.com }

Then for seeing if a URL is an isolated origin, we can compute its site first and then look up eligible isolated origins, which in the common case should just be zero or one origin.  This helps a lot, speeding up GetMatchingIsolatedOrigin by 15-20x.  OTOH, it requires storing both site URL and origin for each isolated origin.

3. Adding a base::MRUCache to GetMatchingIsolatedOrigin().  This was most effective, being 2x better than approach 2 and also smaller memory requirement, though we'd need to worry about sizing it properly, not creating when the list is small, etc, and it may not help as much depending on workload (e.g., when doing lots of parallel independent lookups during session restore or when ctrl-clicking a bunch of links).  Anecdotally, I had the best performance with ~32 entries in my manual tests.

I haven't tried the approach in #1 as it's a bit more involved to put together, and it will be more complicated to deal with corner cases (e.g., trailing dots, multi-dots, IP addresses).  I think for the short term, it might be enough to some combination of the first three approaches or even all three of them.

Also, of ~800 times that cnn.com calls GetMatchingIsolatedOrigin, roughly half of those are due to GetSiteForURL() called from either GetCookies() or SetCookie().  The rest seem to be mostly navigation-related GetSiteForURL() calls, with some of the major callers being RFHI::SetLastCommittedSiteUrl(), DoesSiteRequireDedicatedProcess(), and HasWrongProcessForURL() (cnn.com does have lots of iframes).  We should audit the GetSiteForURL() usage to see if all of it is really necessary, and see if we can avoid recomputing it unnecessarily.

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

commit 4e19b363a33c5a89a2cf6125b6182a47455b23c9
Author: Alex Moshchuk <alexmos@chromium.org>
Date: Mon Sep 10 21:14:36 2018

Reorganize isolated origins into a map indexed by site URLs.

Previously isolated origins were stored in a set.  This resulted in
large overheads when URLs needed to be checked against isolated
origins, since the set had to be walked through linearly, running a
fairly slow comparison function
(IsolatedOriginUtil::DoesOriginMatchIsolatedOrigin()) on each isolated
origin, and this lookup turned out to be fairly common.

This CL reorganizes the underlying data structure into a map keyed by
site URLs.  For example, if we add {https://foo.com,
https://bar.foo.com, https://www.bar.com} as isolated origins, the map
will look like this:
  https://foo.com -> { https://foo.com, https://bar.foo.com }
  https://bar.com -> { https://www.bar.com }

When checking a URL against isolated origins, we now can just look up
the map using the URL's site and then look for the most specific
isolated origins as before.  The site can be found in O(log n) time,
and the corresponding list of origins to search using
DoesOriginMatchIsolatedOrigin() changes from O(n) to O(originsPerSite),
which is expected to be ~1.

Bug: 877653
Change-Id: I41667f94cea7f1f8e5b53fa23443d83cfbb3c0ed
Reviewed-on: https://chromium-review.googlesource.com/1208942
Commit-Queue: Alex Moshchuk <alexmos@chromium.org>
Reviewed-by: Łukasz Anforowicz <lukasza@chromium.org>
Reviewed-by: Charlie Reis <creis@chromium.org>
Cr-Commit-Position: refs/heads/master@{#590063}
[modify] https://crrev.com/4e19b363a33c5a89a2cf6125b6182a47455b23c9/content/browser/child_process_security_policy_impl.cc
[modify] https://crrev.com/4e19b363a33c5a89a2cf6125b6182a47455b23c9/content/browser/child_process_security_policy_impl.h
[modify] https://crrev.com/4e19b363a33c5a89a2cf6125b6182a47455b23c9/content/browser/child_process_security_policy_unittest.cc
[modify] https://crrev.com/4e19b363a33c5a89a2cf6125b6182a47455b23c9/content/browser/site_instance_impl.cc
[modify] https://crrev.com/4e19b363a33c5a89a2cf6125b6182a47455b23c9/content/browser/site_instance_impl.h

The CL in #6 and the bug fix in r590407 should both be in 71.0.3550.0+ canary, and hopefully they're sufficient to unblock further public Android trials based on --isolate-origins.  I'll keep this open for now until we gather data to see how much this helps.  We've also discussed some further improvements that might be worthwhile to do, including keeping separate lists for isolated sites vs. origins, improvements around locking, and caching.

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

commit f01172ea04d6dc7a4d50975a10e442fe16749d4a
Author: Alex Moshchuk <alexmos@chromium.org>
Date: Wed Jan 16 00:54:17 2019

Use a finer-grained lock for isolated_origins_ in CPSPI.

This is a followup on a suggestion from
https://chromium-review.googlesource.com/c/chromium/src/+/1208942 to
make a separate lock for isolated_origins_.  This reduces contention
when looking up isolated origins, and it simplifies lock acquisitions
in CanAccessDataForOrigin, which needs to access both security state
and isolated origins.

Bug: 877653, 905513
Change-Id: Idb0126abc156315939141f6aa2b917db8b02141e
Reviewed-on: https://chromium-review.googlesource.com/c/1214102
Reviewed-by: Łukasz Anforowicz <lukasza@chromium.org>
Reviewed-by: Charlie Reis <creis@chromium.org>
Commit-Queue: Alex Moshchuk <alexmos@chromium.org>
Cr-Commit-Position: refs/heads/master@{#622950}
[modify] https://crrev.com/f01172ea04d6dc7a4d50975a10e442fe16749d4a/content/browser/child_process_security_policy_impl.cc
[modify] https://crrev.com/f01172ea04d6dc7a4d50975a10e442fe16749d4a/content/browser/child_process_security_policy_impl.h
[modify] https://crrev.com/f01172ea04d6dc7a4d50975a10e442fe16749d4a/content/browser/child_process_security_policy_unittest.cc