Profiling indicates that we spend a significant amount of time in set operations for gfx::AnimationContainer::elements_. This is a std::set that is inserted to once per animation, deleted from once per animation, and duplicated and iterated over once per animation update.

Since this typically contains a small number of elements, replacing this with a base::flat_set makes all of these much faster. Set operations may now be O(n), but creating/copying/iterating/destroying is significantly faster and more than offsets this. This has been tested with 1000s of simultaneous animations and is still much more performant.

The second hottest location in profiling indicates that a significant portion of time is spent in gfx::AnimationContainer::GetMinInterval.

This is called each time an animation is removed from the container in order to determine the new minimum update interval. Using a min-heap would be a good solution, but unfortunately we'd require arbitrary element removal and back-pointers from the elements_ set. Possible, but a fair amount of work.

Investigation into the intervals being used shows that the vast majority of them are animating at exactly the same interval (60Hz being the most common case), and thus the O(n) amount of work being performed is essentially calculating a constant. Adding a simple count of the number of animations that share the same minimum update interval vastly improves this, as most cases the logic runs in O(1). An O(n) scan update only needs to occur once all elements sharing the same minimum update interval have been removed.

The two changes described above make the session restore stress test described here (http://www.techradar.com/news/firefoxs-blazing-speed-with-huge-numbers-of-tabs-leaves-chrome-in-the-dust) perform much better.

When restoring a session with 1691 tabs in a single window, initial time to render is now ~4s on a Z840 as compared to 55s without the fixes (~12x).

Re #3 blink::scheduler::IntrusiveHeap<> might be interesting (it's a min heap with arbitrary element erasure) although it'd need to be moved out of blink.

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

commit 2b1d619712c2ddd5d35c1909f24cd302936b2ad7
Author: Chris Hamilton <chrisha@chromium.org>
Date: Thu Aug 17 21:14:56 2017

Use base::flat_set in gfx::AnimationController and improve GetMinInterval logic.

This change is in response to profiling when stress testing the browser with an extremely large
session restore profile containing 1691 tabs.

Profiling indicated that most time was spent in constructing/destroying/updating/iterating over
the std::set. Replacing this with a base::flat_set improves performance enormously, even for 100s
to 1000s of simultaneous animations (which is very rare).

Profiling then indicated that the linear scan logic of GetMinInterval consumed a lot of time as
each animation finished. Since most animations in a container occur with the same update interval
updating this to count the number of elements sharing the same interval makes the common case O(1)
rather than O(n). It is possible to further refine this with a secondary map of (update_interval ->
element_count) which would make the rare case O(lg n) and the common case O(1), however the
additional code and storage complexity didn't yield any tangible further benefit.

The session restore stress test improved from ~55s on a (powerful) dev machine to ~4s (~12x).

BUG= 753897 

Change-Id: I1c0b2e4365baeb5a0c9cbcfee174f1fda34c4361
Reviewed-on: https://chromium-review.googlesource.com/608756
Reviewed-by: Scott Violet <sky@chromium.org>
Commit-Queue: Chris Hamilton <chrisha@chromium.org>
Cr-Commit-Position: refs/heads/master@{#495320}
[modify] https://crrev.com/2b1d619712c2ddd5d35c1909f24cd302936b2ad7/ui/gfx/animation/animation_container.cc
[modify] https://crrev.com/2b1d619712c2ddd5d35c1909f24cd302936b2ad7/ui/gfx/animation/animation_container.h