commit a3c9a66d306935f8b0dd9f49d7516aaf1be5955d
author Fredrik Söderquist <fs@opera.com> Sat Feb 09 14:34:45 2019
committer Commit Bot <commit-bot@chromium.org> Sat Feb 09 14:34:45 2019
tree 187c1195e2270487c2be0a1015075b9bebbaceb8
parent 99d98c846f9b5f762151277d8c24fbab1add0d31

Optimize SVGSMILElement::AddInstanceTime

Find the proper spot to insert the new instance time at directly and
insert it there rather than adding it to the end and std::sort'ing.
Inline SortTimeList into the one remaining caller.

Bug: 927232
Change-Id: Ic161cf5f1a1007c62103536c9ad77225579714d7
Reviewed-on: https://chromium-review.googlesource.com/c/1460921
Commit-Queue: Fredrik Söderquist <fs@opera.com>
Reviewed-by: Stephen Chenney <schenney@chromium.org>
Cr-Commit-Position: refs/heads/master@{#630634}

third_party/blink/renderer/core/svg/animation/svg_smil_element.cc

diff --git a/third_party/blink/renderer/core/svg/animation/svg_smil_element.cc b/third_party/blink/renderer/core/svg/animation/svg_smil_element.cc
index 291f56a0..1c727cd 100644
--- a/third_party/blink/renderer/core/svg/animation/svg_smil_element.cc
+++ b/third_party/blink/renderer/core/svg/animation/svg_smil_element.cc
@@ -411,10 +411,6 @@
   return result;
 }
 
-static void SortTimeList(Vector<SMILTimeWithOrigin>& time_list) {
-  std::sort(time_list.begin(), time_list.end());
-}
-
 bool SVGSMILElement::ParseCondition(const String& value,
                                     BeginOrEnd begin_or_end) {
   String parse_string = value.StripWhiteSpace();
@@ -509,7 +505,7 @@
           SMILTimeWithOrigin(value, SMILTimeWithOrigin::kParserOrigin));
     }
   }
-  SortTimeList(time_list);
+  std::sort(time_list.begin(), time_list.end());
 }
 
 void SVGSMILElement::ParseAttribute(const AttributeModificationParams& params) {
@@ -711,6 +707,12 @@
   return std::min(Dur(), SMILTime::Indefinite());
 }
 
+static void InsertSorted(Vector<SMILTimeWithOrigin>& list,
+                         SMILTimeWithOrigin time) {
+  auto* position = std::lower_bound(list.begin(), list.end(), time);
+  list.insert(position - list.begin(), time);
+}
+
 void SVGSMILElement::AddInstanceTime(BeginOrEnd begin_or_end,
                                      SMILTime time,
                                      SMILTimeWithOrigin::Origin origin) {
@@ -725,8 +727,7 @@
     return;
   Vector<SMILTimeWithOrigin>& list =
       begin_or_end == kBegin ? begin_times_ : end_times_;
-  list.push_back(time_with_origin);
-  SortTimeList(list);
+  InsertSorted(list, time_with_origin);
   if (begin_or_end == kBegin)
     BeginListChanged(elapsed);
   else