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 dcba2d9a13fc49ec5eb3f454267770c6711eae9a..43f38a7620aa4f6ba52c8f04a95de030e53b37b4 100644
--- a/Source/core/page/animation/KeyframeAnimation.cpp
+++ b/Source/core/page/animation/KeyframeAnimation.cpp
@@ -97,22 +97,47 @@ 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 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;
+        float key = m_keyframes[currentIndex].key();
+        distance = lastIndex - currentIndex;
+
+        if (key == fractionalTime)

[apavlov, 2013/04/22 14:23:02]

I think this will _rarely_ be true, as you are comparing a double and a float
(see e.g.
http://stackoverflow.com/questions/1839422/strange-output-in-comparison-of-fl...).

Now that you have introduced the exact comparison, consider turning
|fractionalTime| into float (or |key| into double) or making use of inexact
comparison (using epsilon).

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

[apavlov, 2013/04/22 14:23:02]

The condition should definitely be "i >= 0"

+        const KeyframeValue& keyFrame = m_keyframes[i];
+        if (keyFrame.containsProperty(property) && keyFrame.key() <= fractionalTime) {
+            prevIndex = i;
+            break;
+        }
     }
 
     double scale = 1;