KeyframeAnimation::fetchIntervalEndpointsForProperty could use binary search to lookup keyframes

Source/core/page/animation/KeyframeAnimation.cpp

 /*
  * Copyright (C) 2007, 2012 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  *
  * 1.  Redistributions of source code must retain the above copyright
  *     notice, this list of conditions and the following disclaimer. 
  * 2.  Redistributions in binary form must reproduce the above copyright
@@ skipping 79 matching lines @@
 
     const double fractionalTime = this->fractionalTime(1, elapsedTime, 0);
 
     size_t numKeyframes = m_keyframes.size();
     if (!numKeyframes)
         return;
     
     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;
     double offset = 0;
 
     if (prevIndex == -1)
         prevIndex = 0;
 
     if (nextIndex == -1)
         nextIndex = m_keyframes.size() - 1;
@@ skipping 318 matching lines @@
 
     if (acceleratedPropertiesOnly) {
         bool isLooping;
         getTimeToNextEvent(t, isLooping);
     }
 
     return t;
 }
 
 } // namespace WebCore