Introduce keyframe_map_index_base_ to SourceBufferRange.

Currently during garbage collection we are deleting GOP one by one. Once we delete
GOP from front, we need to update all entries in the |keyframe_map_|. This
results in a computational complexity of O(MN), where M is the number of GOPs to
be deleted, and N is the number of key frames in the whole range. Note that for
audio, every buffer in the range is a key frame. Also, in a normal case, we could
end up having all buffered frames in one range. In that case, N is the number of
all buffered audio frames, which could be significantly larger than M.

To avoid this high complexity, this CL introduces a |keyframe_map_index_base_|
that offsets all indexs in the |keyframe_map_|. In other words, the real index
of a key frame in the range is

  keyframe_map_[k] - keyframe_map_index_base_

Now after we delete a GOP from front, we only need to update
keyframe_map_index_base_. This reduces the computational complexity to O(M).

TBR=vrk@chromium.org
TEST=Added a garbage collection performance unit test.

Review URL: https://codereview.chromium.org/11858002

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@176277 0039d316-1c4b-4281-b951-d872f2087c98

2 files changed, 44 insertions, 15 deletions

diff --git a/media/filters/source_buffer_stream.cc b/media/filters/source_buffer_stream.cc
index c49772b..069de93 100644
--- a/media/filters/source_buffer_stream.cc
+++ b/media/filters/source_buffer_stream.cc
@@ -205,6 +205,11 @@ class SourceBufferRange {
   // Maps keyframe timestamps to its index position in |buffers_|.
   KeyframeMap keyframe_map_;
 
+  // Index base of all positions in |keyframe_map_|. In other words, the
+  // real position of entry |k| of |keyframe_map_| in the range is:
+  //   keyframe_map_[k] - keyframe_map_index_base_
+  int keyframe_map_index_base_;
+
   // Index into |buffers_| for the next buffer to be returned by
   // GetNextBuffer(), set to -1 before Seek().
   int next_buffer_index_;
@@ -1137,7 +1142,8 @@ void SourceBufferStream::CompleteConfigChange() {
 SourceBufferRange::SourceBufferRange(
     const BufferQueue& new_buffers, base::TimeDelta media_segment_start_time,
     const InterbufferDistanceCB& interbuffer_distance_cb)
-    : next_buffer_index_(-1),
+    : keyframe_map_index_base_(0),
+      next_buffer_index_(-1),
       waiting_for_keyframe_(false),
       next_keyframe_timestamp_(kNoTimestamp()),
       media_segment_start_time_(media_segment_start_time),
@@ -1158,7 +1164,8 @@ void SourceBufferRange::AppendBuffersToEnd(const BufferQueue& new_buffers) {
 
     if ((*itr)->IsKeyframe()) {
       keyframe_map_.insert(
-          std::make_pair((*itr)->GetDecodeTimestamp(), buffers_.size() - 1));
+          std::make_pair((*itr)->GetDecodeTimestamp(),
+                         buffers_.size() - 1 + keyframe_map_index_base_));
 
       if (waiting_for_keyframe_ &&
           (*itr)->GetDecodeTimestamp() >= next_keyframe_timestamp_) {
@@ -1178,7 +1185,7 @@ void SourceBufferRange::Seek(base::TimeDelta timestamp) {
   waiting_for_keyframe_ = false;
 
   KeyframeMap::iterator result = GetFirstKeyframeBefore(timestamp);
-  next_buffer_index_ = result->second;
+  next_buffer_index_ = result->second - keyframe_map_index_base_;
   DCHECK_LT(next_buffer_index_, static_cast<int>(buffers_.size()));
 }
 
@@ -1205,7 +1212,7 @@ void SourceBufferRange::SeekAhead(base::TimeDelta timestamp,
     next_keyframe_timestamp_ = timestamp;
     return;
   }
-  next_buffer_index_ = result->second;
+  next_buffer_index_ = result->second - keyframe_map_index_base_;
   DCHECK_LT(next_buffer_index_, static_cast<int>(buffers_.size()));
 }
 
@@ -1227,7 +1234,8 @@ SourceBufferRange* SourceBufferRange::SplitRange(
 
   // Remove the data beginning at |keyframe_index| from |buffers_| and save it
   // into |removed_buffers|.
-  int keyframe_index = new_beginning_keyframe->second;
+  int keyframe_index =
+      new_beginning_keyframe->second - keyframe_map_index_base_;
   DCHECK_LT(keyframe_index, static_cast<int>(buffers_.size()));
   BufferQueue::iterator starting_point = buffers_.begin() + keyframe_index;
   BufferQueue removed_buffers(starting_point, buffers_.end());
@@ -1320,7 +1328,8 @@ int SourceBufferRange::DeleteGOPFromFront(BufferQueue* deleted_buffers) {
   // Now we need to delete all the buffers that depend on the keyframe we've
   // just deleted.
   int end_index = keyframe_map_.size() > 0 ?
-      keyframe_map_.begin()->second : buffers_.size();
+      keyframe_map_.begin()->second - keyframe_map_index_base_ :
+      buffers_.size();
 
   // Delete buffers from the beginning of the buffered range up until (but not
   // including) the next keyframe.
@@ -1333,12 +1342,9 @@ int SourceBufferRange::DeleteGOPFromFront(BufferQueue* deleted_buffers) {
     ++buffers_deleted;
   }
 
-  // Update indices to account for the deleted buffers.
-  for (KeyframeMap::iterator itr = keyframe_map_.begin();
-       itr != keyframe_map_.end(); ++itr) {
-    itr->second -= buffers_deleted;
-    DCHECK_GE(itr->second, 0);
-  }
+  // Update |keyframe_map_index_base_| to account for the deleted buffers.
+  keyframe_map_index_base_ += buffers_deleted;
+
   if (next_buffer_index_ > -1) {
     next_buffer_index_ -= buffers_deleted;
     DCHECK_GE(next_buffer_index_, 0);
@@ -1363,7 +1369,7 @@ int SourceBufferRange::DeleteGOPFromBack(BufferQueue* deleted_buffers) {
 
   // The index of the first buffer in the last GOP is equal to the new size of
   // |buffers_| after that GOP is deleted.
-  size_t goal_size = back->second;
+  size_t goal_size = back->second - keyframe_map_index_base_;
   keyframe_map_.erase(back);
 
   int total_bytes_deleted = 0;
@@ -1391,7 +1397,8 @@ bool SourceBufferRange::FirstGOPContainsNextBufferPosition() const {
 
   KeyframeMap::const_iterator second_gop = keyframe_map_.begin();
   ++second_gop;
-  return !waiting_for_keyframe_ && next_buffer_index_ < second_gop->second;
+  return !waiting_for_keyframe_ &&
+         next_buffer_index_ < second_gop->second - keyframe_map_index_base_;
 }
 
 bool SourceBufferRange::LastGOPContainsNextBufferPosition() const {
@@ -1404,7 +1411,8 @@ bool SourceBufferRange::LastGOPContainsNextBufferPosition() const {
 
   KeyframeMap::const_iterator last_gop = keyframe_map_.end();
   --last_gop;
-  return waiting_for_keyframe_ || last_gop->second <= next_buffer_index_;
+  return waiting_for_keyframe_ ||
+         last_gop->second - keyframe_map_index_base_ <= next_buffer_index_;
 }
 
 void SourceBufferRange::FreeBufferRange(
diff --git a/media/filters/source_buffer_stream_unittest.cc b/media/filters/source_buffer_stream_unittest.cc
index cd12d5d..67e431c 100644
--- a/media/filters/source_buffer_stream_unittest.cc
+++ b/media/filters/source_buffer_stream_unittest.cc
@@ -2349,6 +2349,27 @@ TEST_F(SourceBufferStreamTest, DISABLED_GarbageCollection_WaitingForKeyframe) {
   CheckExpectedRanges("{ [15,15) [20,28) }");
 }
 
+// Test the performance of garbage collection.
+TEST_F(SourceBufferStreamTest, GarbageCollection_Performance) {
+  // Force |keyframes_per_second_| to be equal to kDefaultFramesPerSecond.
+  SetStreamInfo(kDefaultFramesPerSecond, kDefaultFramesPerSecond);
+
+  const int kBuffersToKeep = 1000;
+  SetMemoryLimit(kBuffersToKeep);
+
+  int buffers_appended = 0;
+
+  NewSegmentAppend(0, kBuffersToKeep);
+  buffers_appended += kBuffersToKeep;
+
+  const int kBuffersToAppend = 1000;
+  const int kGarbageCollections = 3;
+  for (int i = 0; i < kGarbageCollections; ++i) {
+    AppendBuffers(buffers_appended, kBuffersToAppend);
+    buffers_appended += kBuffersToAppend;
+  }
+}
+
 TEST_F(SourceBufferStreamTest, ConfigChange_Basic) {
   gfx::Size kNewCodedSize(kCodedSize.width() * 2, kCodedSize.height() * 2);
   VideoDecoderConfig new_config(