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 53 matching lines @@
     // Make sure to tell the renderer that we are ending. This will make sure any accelerated animations are removed.
     if (!postActive())
         endAnimation();
 }
 
 static const Animation* getAnimationFromStyleByName(const RenderStyle* style, const AtomicString& name)
 {
     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);
     }
 
     return 0;
 }
 
 void KeyframeAnimation::fetchIntervalEndpointsForProperty(CSSPropertyID property, const RenderStyle*& fromStyle, const RenderStyle*& toStyle, double& prog) const
 {
     // Find the first key
     double elapsedTime = getElapsedTime();
     if (m_animation->duration() && m_animation->iterationCount() != Animation::IterationCountInfinite)
         elapsedTime = min(elapsedTime, m_animation->duration() * m_animation->iterationCount());
 
     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 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;
     double offset = 0;
 
     if (prevIndex == -1)
         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];
 
     fromStyle = prevKeyframe.style();
     toStyle = nextKeyframe.style();
     
     offset = prevKeyframe.key();
     scale = 1.0 / (nextKeyframe.key() - prevKeyframe.key());
 
@@ skipping 305 matching lines @@
 
     if (acceleratedPropertiesOnly) {
         bool isLooping;
         getTimeToNextEvent(t, isLooping);
     }
 
     return t;
 }
 
 } // namespace WebCore