Bug 1227396: P13. Refactor how MP4 buffered range is calculated. r=cpearce
authorJean-Yves Avenard <jyavenard@mozilla.com>
Fri, 27 Nov 2015 15:03:19 +1100
changeset 274543 0d8e85b5983278ed9c7ed0cbd88c6b1c9d1b307a
parent 274542 349eba21938c8503440a3d38bebbc1c6041f9c8d
child 274544 fd4d78b89cc0ee6f464c65b17b957e52572041ab
push id68621
push userjyavenard@mozilla.com
push dateMon, 30 Nov 2015 00:49:17 +0000
treeherdermozilla-inbound@fd4d78b89cc0 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerscpearce
bugs1227396
milestone45.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1227396: P13. Refactor how MP4 buffered range is calculated. r=cpearce We now use an index of samples made of block of samples delimited by keyframes. The search is performed using a binary search. This allows to quickly find which blocks are found within the media cache. On a 8 core mac pro, this leads to a 67% improvement on CPU time spent playing a long MP4 video (from 112s CPU to 45s CPU) The optimisation is only possible if all mp4 data chunks are continuous (which they almost always are)
dom/media/fmp4/MP4Demuxer.cpp
media/libstagefright/binding/Index.cpp
media/libstagefright/binding/include/mp4_demuxer/Index.h
--- a/dom/media/fmp4/MP4Demuxer.cpp
+++ b/dom/media/fmp4/MP4Demuxer.cpp
@@ -404,27 +404,18 @@ MP4TrackDemuxer::GetBuffered()
   EnsureUpToDateIndex();
   AutoPinned<MediaResource> resource(mParent->mResource);
   MediaByteRangeSet byteRanges;
   nsresult rv = resource->GetCachedRanges(byteRanges);
 
   if (NS_FAILED(rv)) {
     return media::TimeIntervals();
   }
-  nsTArray<mp4_demuxer::Interval<int64_t>> timeRanges;
 
-  mIndex->ConvertByteRangesToTimeRanges(byteRanges, &timeRanges);
-  // convert timeRanges.
-  media::TimeIntervals ranges = media::TimeIntervals();
-  for (size_t i = 0; i < timeRanges.Length(); i++) {
-    ranges +=
-      media::TimeInterval(media::TimeUnit::FromMicroseconds(timeRanges[i].start),
-                          media::TimeUnit::FromMicroseconds(timeRanges[i].end));
-  }
-  return ranges;
+  return mIndex->ConvertByteRangesToTimeRanges(byteRanges);
 }
 
 void
 MP4TrackDemuxer::NotifyDataArrived()
 {
   mNeedReIndex = true;
 }
 
--- a/media/libstagefright/binding/Index.cpp
+++ b/media/libstagefright/binding/Index.cpp
@@ -1,25 +1,25 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "mp4_demuxer/ByteReader.h"
 #include "mp4_demuxer/Index.h"
 #include "mp4_demuxer/Interval.h"
-#include "mp4_demuxer/MoofParser.h"
 #include "mp4_demuxer/SinfParser.h"
 #include "nsAutoPtr.h"
 #include "mozilla/RefPtr.h"
 
 #include <algorithm>
 #include <limits>
 
 using namespace stagefright;
 using namespace mozilla;
+using namespace mozilla::media;
 
 namespace mp4_demuxer
 {
 
 class MOZ_STACK_CLASS RangeFinder
 {
 public:
   // Given that we're processing this in order we don't use a binary search
@@ -40,41 +40,41 @@ private:
 
 bool
 RangeFinder::Contains(MediaByteRange aByteRange)
 {
   if (!mRanges.Length()) {
     return false;
   }
 
-  if (mRanges[mIndex].Contains(aByteRange)) {
+  if (mRanges[mIndex].ContainsStrict(aByteRange)) {
     return true;
   }
 
   if (aByteRange.mStart < mRanges[mIndex].mStart) {
     // Search backwards
     do {
       if (!mIndex) {
         return false;
       }
       --mIndex;
-      if (mRanges[mIndex].Contains(aByteRange)) {
+      if (mRanges[mIndex].ContainsStrict(aByteRange)) {
         return true;
       }
     } while (aByteRange.mStart < mRanges[mIndex].mStart);
 
     return false;
   }
 
   while (aByteRange.mEnd > mRanges[mIndex].mEnd) {
     if (mIndex == mRanges.Length() - 1) {
       return false;
     }
     ++mIndex;
-    if (mRanges[mIndex].Contains(aByteRange)) {
+    if (mRanges[mIndex].ContainsStrict(aByteRange)) {
       return true;
     }
   }
 
   return false;
 }
 
 SampleIterator::SampleIterator(Index* aIndex)
@@ -241,27 +241,72 @@ Index::Index(const nsTArray<Indice>& aIn
 {
   if (aIndex.IsEmpty()) {
     mMoofParser = new MoofParser(aSource, aTrackId, aIsAudio);
   } else {
     if (!mIndex.SetCapacity(aIndex.Length(), fallible)) {
       // OOM.
       return;
     }
-    for (size_t i = 0; i < aIndex.Length(); i++) {
-      const Indice& indice = aIndex[i];
+    media::IntervalSet<int64_t> intervalTime;
+    MediaByteRange intervalRange;
+    bool haveSync = false;
+    bool progressive = true;
+    int64_t lastOffset = 0;
+    for (const Indice& indice : aIndex) {
+      if (indice.sync) {
+        haveSync = true;
+      }
+      if (!haveSync) {
+        continue;
+      }
+
       Sample sample;
       sample.mByteRange = MediaByteRange(indice.start_offset,
                                          indice.end_offset);
       sample.mCompositionRange = Interval<Microseconds>(indice.start_composition,
                                                         indice.end_composition);
       sample.mDecodeTime = indice.start_decode;
       sample.mSync = indice.sync;
       // FIXME: Make this infallible after bug 968520 is done.
       MOZ_ALWAYS_TRUE(mIndex.AppendElement(sample, fallible));
+      if (indice.start_offset < lastOffset) {
+        NS_WARNING("Chunks in MP4 out of order, expect slow down");
+        progressive = false;
+      }
+      lastOffset = indice.end_offset;
+
+      if (sample.mSync && progressive) {
+        if (mDataOffset.Length()) {
+          auto& last = mDataOffset.LastElement();
+          last.mEndOffset = intervalRange.mEnd;
+          NS_ASSERTION(intervalTime.Length() == 1, "Discontinuous samples between keyframes");
+          last.mTime.start = intervalTime.GetStart();
+          last.mTime.end = intervalTime.GetEnd();
+        }
+        if (!mDataOffset.AppendElement(MP4DataOffset(mIndex.Length() - 1,
+                                                     indice.start_offset),
+                                       fallible)) {
+          // OOM.
+          return;
+        }
+        intervalTime = media::IntervalSet<int64_t>();
+        intervalRange = MediaByteRange();
+      }
+      intervalTime += media::Interval<int64_t>(sample.mCompositionRange.start,
+                                               sample.mCompositionRange.end);
+      intervalRange = intervalRange.Span(sample.mByteRange);
+    }
+
+    if (mDataOffset.Length() && progressive) {
+      auto& last = mDataOffset.LastElement();
+      last.mEndOffset = aIndex.LastElement().end_offset;
+      last.mTime = Interval<int64_t>(intervalTime.GetStart(), intervalTime.GetEnd());
+    } else {
+      mDataOffset.Clear();
     }
   }
 }
 
 Index::~Index() {}
 
 void
 Index::UpdateMoofIndex(const MediaByteRangeSet& aByteRanges)
@@ -296,24 +341,57 @@ Index::GetEndCompositionIfBuffered(const
     lastComposition = std::max(lastComposition, sample.mCompositionRange.end);
     if (sample.mSync) {
       return lastComposition;
     }
   }
   return 0;
 }
 
-void
-Index::ConvertByteRangesToTimeRanges(
-  const MediaByteRangeSet& aByteRanges,
-  nsTArray<Interval<Microseconds>>* aTimeRanges)
+TimeIntervals
+Index::ConvertByteRangesToTimeRanges(const MediaByteRangeSet& aByteRanges)
 {
+  if (aByteRanges == mLastCachedRanges) {
+    return mLastBufferedRanges;
+  }
+  mLastCachedRanges = aByteRanges;
+
+  if (mDataOffset.Length()) {
+    TimeIntervals timeRanges;
+    for (const auto& range : aByteRanges) {
+      uint32_t start = mDataOffset.IndexOfFirstElementGt(range.mStart - 1);
+      if (start == mDataOffset.Length()) {
+        continue;
+      }
+      uint32_t end = mDataOffset.IndexOfFirstElementGt(range.mEnd, MP4DataOffset::EndOffsetComparator());
+      if (end < start) {
+        continue;
+      }
+      if (end > start) {
+        timeRanges +=
+          TimeInterval(TimeUnit::FromMicroseconds(mDataOffset[start].mTime.start),
+                       TimeUnit::FromMicroseconds(mDataOffset[end-1].mTime.end));
+      }
+      if (end < mDataOffset.Length()) {
+        // Find samples in partial block contained in the byte range.
+        for (size_t i = mDataOffset[end].mIndex;
+             i < mIndex.Length() && range.ContainsStrict(mIndex[i].mByteRange);
+             i++) {
+          timeRanges +=
+            TimeInterval(TimeUnit::FromMicroseconds(mIndex[i].mCompositionRange.start),
+                         TimeUnit::FromMicroseconds(mIndex[i].mCompositionRange.end));
+        }
+      }
+    }
+    mLastBufferedRanges = timeRanges;
+    return timeRanges;
+  }
+
   RangeFinder rangeFinder(aByteRanges);
   nsTArray<Interval<Microseconds>> timeRanges;
-
   nsTArray<FallibleTArray<Sample>*> indexes;
   if (mMoofParser) {
     // We take the index out of the moof parser and move it into a local
     // variable so we don't get concurrency issues. It gets freed when we
     // exit this function.
     for (int i = 0; i < mMoofParser->Moofs().Length(); i++) {
       Moof& moof = mMoofParser->Moofs()[i];
 
@@ -348,17 +426,27 @@ Index::ConvertByteRangesToTimeRanges(
       }
 
       Interval<Microseconds>::SemiNormalAppend(timeRanges,
                                                sample.mCompositionRange);
     }
   }
 
   // This fixes up when the compositon order differs from the byte range order
-  Interval<Microseconds>::Normalize(timeRanges, aTimeRanges);
+  nsTArray<Interval<Microseconds>> timeRangesNormalized;
+  Interval<Microseconds>::Normalize(timeRanges, &timeRangesNormalized);
+  // convert timeRanges.
+  media::TimeIntervals ranges;
+  for (size_t i = 0; i < timeRangesNormalized.Length(); i++) {
+    ranges +=
+      media::TimeInterval(media::TimeUnit::FromMicroseconds(timeRangesNormalized[i].start),
+                          media::TimeUnit::FromMicroseconds(timeRangesNormalized[i].end));
+  }
+  mLastBufferedRanges = ranges;
+  return ranges;
 }
 
 uint64_t
 Index::GetEvictionOffset(Microseconds aTime)
 {
   uint64_t offset = std::numeric_limits<uint64_t>::max();
   if (mMoofParser) {
     // We need to keep the whole moof if we're keeping any of it because the
--- a/media/libstagefright/binding/include/mp4_demuxer/Index.h
+++ b/media/libstagefright/binding/include/mp4_demuxer/Index.h
@@ -2,28 +2,28 @@
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef INDEX_H_
 #define INDEX_H_
 
 #include "MediaData.h"
 #include "MediaResource.h"
+#include "TimeUnits.h"
+#include "mp4_demuxer/MoofParser.h"
 #include "mp4_demuxer/Interval.h"
 #include "mp4_demuxer/Stream.h"
 #include "nsISupportsImpl.h"
 
 template<class T> class nsAutoPtr;
 
 namespace mp4_demuxer
 {
 
 class Index;
-class MoofParser;
-struct Sample;
 
 typedef int64_t Microseconds;
 
 class SampleIterator
 {
 public:
   explicit SampleIterator(Index* aIndex);
   already_AddRefed<mozilla::MediaRawData> GetNext();
@@ -48,34 +48,74 @@ public:
     uint64_t start_offset;
     uint64_t end_offset;
     uint64_t start_composition;
     uint64_t end_composition;
     uint64_t start_decode;
     bool sync;
   };
 
+  struct MP4DataOffset
+  {
+    MP4DataOffset(uint32_t aIndex, int64_t aStartOffset)
+      : mIndex(aIndex)
+      , mStartOffset(aStartOffset)
+      , mEndOffset(0)
+    {}
+
+    bool operator==(int64_t aStartOffset) const {
+      return mStartOffset == aStartOffset;
+    }
+
+    bool operator!=(int64_t aStartOffset) const {
+      return mStartOffset != aStartOffset;
+    }
+
+    bool operator<(int64_t aStartOffset) const {
+      return mStartOffset < aStartOffset;
+    }
+
+    struct EndOffsetComparator {
+      bool Equals(const MP4DataOffset& a, const int64_t& b) const {
+        return a.mEndOffset == b;
+      }
+
+      bool LessThan(const MP4DataOffset& a, const int64_t& b) const {
+        return a.mEndOffset < b;
+      }
+    };
+
+    uint32_t mIndex;
+    int64_t mStartOffset;
+    int64_t mEndOffset;
+    Interval<Microseconds> mTime;
+  };
+
   Index(const nsTArray<Indice>& aIndex,
         Stream* aSource,
         uint32_t aTrackId,
         bool aIsAudio);
 
   void UpdateMoofIndex(const mozilla::MediaByteRangeSet& aByteRanges);
   Microseconds GetEndCompositionIfBuffered(
     const mozilla::MediaByteRangeSet& aByteRanges);
-  void ConvertByteRangesToTimeRanges(
-    const mozilla::MediaByteRangeSet& aByteRanges,
-    nsTArray<Interval<Microseconds>>* aTimeRanges);
+  mozilla::media::TimeIntervals ConvertByteRangesToTimeRanges(
+    const mozilla::MediaByteRangeSet& aByteRanges);
   uint64_t GetEvictionOffset(Microseconds aTime);
   bool IsFragmented() { return mMoofParser; }
 
   friend class SampleIterator;
 
 private:
   ~Index();
 
   Stream* mSource;
   FallibleTArray<Sample> mIndex;
+  FallibleTArray<MP4DataOffset> mDataOffset;
   nsAutoPtr<MoofParser> mMoofParser;
+
+  // ConvertByteRangesToTimeRanges cache
+  mozilla::MediaByteRangeSet mLastCachedRanges;
+  mozilla::media::TimeIntervals mLastBufferedRanges;
 };
 }
 
 #endif