KeyframeAnimation::fetchIntervalEndpointsForProperty could use binary search to lookup keyframes

Source/core/page/animation/KeyframeAnimation.cpp

Index: Source/core/page/animation/KeyframeAnimation.cpp
diff --git a/Source/core/page/animation/KeyframeAnimation.cpp b/Source/core/page/animation/KeyframeAnimation.cpp
index be416e2384a392c30f31d14808e3ad4758e894aa..b48625edafc4af866c6d959a5c8a191e69891b7e 100644
--- a/Source/core/page/animation/KeyframeAnimation.cpp
+++ b/Source/core/page/animation/KeyframeAnimation.cpp
@@ -71,7 +71,8 @@ static const Animation* getAnimationFromStyleByName(const RenderStyle* style, co
     if (!style->animations())
         return 0;
 
-    for (size_t i = 0; i < style->animations()->size(); i++) {
+    size_t animationCount = style->animations()->size();
+    for (size_t i = 0; i < animationCount; i++) {
         if (name == style->animations()->animation(i)->name())
             return style->animations()->animation(i);
     }
@@ -94,23 +95,50 @@ void KeyframeAnimation::fetchIntervalEndpointsForProperty(CSSPropertyID property
     
     ASSERT(!m_keyframes[0].key());
     ASSERT(m_keyframes[m_keyframes.size() - 1].key() == 1);
-    
+
+    size_t currentIndex = 0;
+    size_t backIterIndex = 0;

[apavlov, 2013/04/30 13:16:11]

This is making the algorithm a bit more complicated, and it is not so easy to
understand what's going on here (is backIterIndex-- just an optimization, since
the backward iteration will still hit only the keyFrame that is BEFORE the
fractionalTime?)

I believe the result computed by the loop below should be stated more explicitly
(now it is just "Find keyframe that is closest to elapsed time," but clearly,
there's a bit more to it.) Perhaps, you could design the loop to always
terminate in a certain state (for example, currentIndex points to the first
keyframe whose key >= fractionalTime, pointing past the last element if
necessary).

Also, the approximateBinarySearch() function found in wtf/StdLibExtras.h might
be of some interest to you.

+    size_t firstIndex = 0;
+    size_t lastIndex = numKeyframes - 1;
+    size_t distance = numKeyframes;
+
+    // Find keyframe that is closest to elapsed time.
+    while (distance > 1) {
+        currentIndex = (lastIndex + firstIndex) >> 1;
+        backIterIndex =  currentIndex;

[apavlov, 2013/04/30 13:16:11]

extra whitespace after '='

+        float key = m_keyframes[currentIndex].key();
+        distance = lastIndex - currentIndex;
+
+        if (key < fractionalTime) {
+            if (distance < 2)
+                currentIndex++;
+            firstIndex = currentIndex;
+        } else {
+            if (distance < 2 && backIterIndex)
+                backIterIndex--;
+            lastIndex = currentIndex;
+        }
+    }
+
     int prevIndex = -1;
     int nextIndex = -1;
-    
-    // FIXME: with a lot of keys, this linear search will be slow. We could binary search.
-    for (size_t i = 0; i < numKeyframes; ++i) {
-        const KeyframeValue& currKeyFrame = m_keyframes[i];
 
-        if (!currKeyFrame.containsProperty(property))
-            continue;
-
-        if (fractionalTime < currKeyFrame.key()) {
+    // Interate forward to find next keyframe that is used to animate CSS property.

[apavlov, 2013/04/30 13:16:11]

Interate -> Iterate

+    for (size_t i = currentIndex; i < numKeyframes; ++i) {
+        const KeyframeValue& keyFrame = m_keyframes[i];
+        if (keyFrame.key() > fractionalTime && keyFrame.containsProperty(property)) {
             nextIndex = i;
             break;
         }
-        
-        prevIndex = i;
+    }
+
+    // Interate backward to find previous keyframe.

[apavlov, 2013/04/30 13:16:11]

Ditto

+    for (size_t i = backIterIndex; i < numKeyframes; --i) {
+        const KeyframeValue& keyFrame = m_keyframes[i];
+        if (keyFrame.key() <= fractionalTime && keyFrame.containsProperty(property)) {
+            prevIndex = i;
+            break;
+        }
     }
 
     double scale = 1;
@@ -120,7 +148,7 @@ void KeyframeAnimation::fetchIntervalEndpointsForProperty(CSSPropertyID property
         prevIndex = 0;
 
     if (nextIndex == -1)
-        nextIndex = m_keyframes.size() - 1;
+        nextIndex = numKeyframes - 1;
 
     const KeyframeValue& prevKeyframe = m_keyframes[prevIndex];
     const KeyframeValue& nextKeyframe = m_keyframes[nextIndex];