Henrik Skupin [:whimboo][⌚️UTC+2] Reporter
	Description • 16 years ago

Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.1b3pre) Gecko/20081212 Shiretoko/3.1b3pre ID:20081212035014

With the patch on bug 449159 we have the possibility to seek inside OGG videos. If you run a test with attachment 346615 [details] and press the +/- 5s buttons, you will notice that the playback stops for about 5-10s until the playback starts again.

Hitting the seek buttons should seek the video/audio as fast as possible, like all the other video players.

	Henrik Skupin [:whimboo][⌚️UTC+2] Reporter
	Comment 1 • 16 years ago

Same happens in paused mode. Seeking +/- 5s within the given testcase takes about 10-15s until the new position is displayed.

	cajbir (:cajbir)
	Comment 2 • 16 years ago

Yes seeking is slow when the URL is a HTTP resource. Lots of byte range requests are done so it's very dependent on server speed, bandwidth, etc. Seeking on file:// resources is very fast.

Some options we've discussed are:

1) Better buffering
2) Write the downloaded video to disk and use that for seeking in the parts already viewed.
3) Improve the liboggz seeking algorithm (requires third party library maintainer)

	Henrik Skupin [:whimboo][⌚️UTC+2] Reporter
	Comment 3 • 16 years ago

Updating summary again to better reflect the real problem.

	cajbir (:cajbir)
	Comment 4 • 16 years ago

I did some digging on this issue. It turns out there is a bug introduced in bug 449159 to liboggz that causes the guesses for the seeks to be out sometimes. This results in many more http byte range requests than is needed. I'll attach the fix shortly.

This speeds up individual seeks but there are two further issues slowing things down.

The first is that the user interface seeks when you click on the thumb and seeks again when you finish dragging the slider. So that's two seeks (with multiple range requests) for every seek initiated by the UI.

The second is that each call to liboggplay for a seek results in liboggplay asking for the duration. This duration call results in two actual seeks. The first to the end of the file to get the timestamp. And the second to go back to where we were before. Each of these takes multiple byte range requests. I will fix this with a liboggplay patch to memoize the result of the duration call I think.

So currently a single seek request by the user results in approximate 6 seek requests, each composed of multiple byte range requests.

The liboggz fix reduces the number of byte range requests but there is still 6 seeks. The liboggplay fix for the duration will remove two of these seek calls. A UI fix drops it back to 1. This substantially decreases seek time to be actually usable.

	cajbir (:cajbir)
	Comment 5 • 16 years ago

Variable typo, picked up the wrong variable to compare with.

	cajbir (:cajbir)
	Comment 6 • 16 years ago

Comment on attachment 359214 [details] [diff] [review]
liboggz fix for guessing seek position

Moved to bug 475685

	cajbir (:cajbir)
	Comment 7 • 16 years ago

This changes the seeking algorithm used in liboggz to improve seek times. It takes advantage of the way buffering works currently in that it's better to underguess and scan forward, since seeks forward can take advantage of buffered data.

It's very simple in that it simply bisects the video until it finds close to the current time and then scans for the right page.

With this, and the patches this bug depends on, seek times on my machine are around 5 seconds.

I implemented this as a change to liboggz. I'll discuss with the liboggz maintainer about the changes before seeking review.

	Chris Pearce [:cpearce (Not reading bugmail)] Assignee
	Comment 8 • 15 years ago

* Adds a new file to liboggz, with a custom seek implementation for mozilla, which uses Chris Double's bisection from previous patch.
* Adds much of the infrastructure needed to implement buffered time ranges, (including nsMediaCacheStream::GetUncachedDataEndInternal()). It should be relatively easy to implement buffered ranges top of this patch.
* This reduces the average number of new channels required to seek by about 3. I have not observed any speed up in seek wall-clock time though, it's hard to measure; variations in network performance tends to throw out time based measurements.

	Chris Pearce [:cpearce (Not reading bugmail)] Assignee
	Comment 9 • 15 years ago

Opens a long video, hosted on tinyvid.tv. Use "Seek Test" to perform and time a bunch of random seeks.

	Robert O'Callahan (:roc) (email my personal email if necessary)
	Comment 10 • 15 years ago

+#if !defined(nsMediaPoint_h_)
+#define nsMediaPoint_h_

MediaMap_h_?

+// and if so will have value MediaPoint::Unknonw.

typo

+  nsresult Update(nsMediaStream *aStream, void* aOggz);

nsMediaStream* aStream

+  // List of known points, stored in increasing order of offset. This list
+  // is capped at length sMaxKnownPoints, if we add a new known point when
+  // this is length sMaxKnownPoints, we kick a random value.
+  nsTArray<MediaPoint> mPoints;

I don't think that's really a good idea. Can't we use a proper ordered-tree structure here?

 void nsMediaCacheStream::BlockList::Verify()
 {
+#ifndef PROFILE_MEDIA_SEEK

Why is this #ifndef here?

 nsMediaCache::Verify()
 {
+#ifndef PROFILE_MEDIA_SEEK

and here?

+  // Returns the end of the bytes starting at the given offset
+  // which are not in cache.

How about calling it GetNextCachedData with the specification
  // Returns the offset of the first byte of cached data at or after aOffset,
  // or -1 if there is no such cached data.

+  PRUint32 startBlockIndex = aOffset/BLOCK_SIZE;
+  if (startBlockIndex >= mBlocks.Length())
+    return -1;

mPartialBuffer might have cached data for the block mChannelOffset/BLOCK_SIZE, you should check that right at the begining of this method.

If all the blocks from aOffset on are uncached, you should just return -1.

+  virtual PRInt64 GetUncachedDataEnd(PRInt64 aOffset) { return 0; }

Should return aOffset if aOffset < mSize, -1 otherwise.

+class Meaner {

This name sounds really weird to me. Maybe MeanAccumulator?

What exactly are the offsets in MediaMap? Do they point precisely to some kind of Ogg packet?

	Chris Pearce [:cpearce (Not reading bugmail)] Assignee
	Comment 11 • 15 years ago

(In reply to comment #10)
> I don't think that's really a good idea. Can't we use a proper ordered-tree
> structure here?

Is there something I can reuse already? Like std::map?

> 
>  void nsMediaCacheStream::BlockList::Verify()
>  {
> +#ifndef PROFILE_MEDIA_SEEK
> 
> Why is this #ifndef here?
> 
>  nsMediaCache::Verify()
>  {
> +#ifndef PROFILE_MEDIA_SEEK
> 
> and here?

As the media cache gets full, these functions take longer and longer to run. I had to disable them when I was measuring performance, else performance degraded over time.

> What exactly are the offsets in MediaMap? Do they point precisely to some kind
> of Ogg packet?

Byte offsets into the stream/file, i.e. the read cursor position. They don't point precisely to an ogg packet. The time is the timestamp of the next frame after the offset.

	Robert O'Callahan (:roc) (email my personal email if necessary)
	Comment 12 • 15 years ago

(In reply to comment #11)
> (In reply to comment #10)
> > I don't think that's really a good idea. Can't we use a proper ordered-tree
> > structure here?
> 
> Is there something I can reuse already? Like std::map?

I'm not sure. Ask bsmedberg or bzbarsky?

> >  void nsMediaCacheStream::BlockList::Verify()
> >  {
> > +#ifndef PROFILE_MEDIA_SEEK
> > 
> > Why is this #ifndef here?
> > 
> >  nsMediaCache::Verify()
> >  {
> > +#ifndef PROFILE_MEDIA_SEEK
> > 
> > and here?
> 
> As the media cache gets full, these functions take longer and longer to run. I
> had to disable them when I was measuring performance, else performance degraded
> over time.

It's generally a good idea to measure performance in opt builds...

> > What exactly are the offsets in MediaMap? Do they point precisely to some kind
> > of Ogg packet?
> 
> Byte offsets into the stream/file, i.e. the read cursor position. They don't
> point precisely to an ogg packet. The time is the timestamp of the next frame
> after the offset.

I'm a bit worried about being vague here. I think we need to state as precisely as we can how the offset is related to the time.

	Chris Pearce [:cpearce (Not reading bugmail)] Assignee
	Comment 13 • 15 years ago

(In reply to comment #12)
> > As the media cache gets full, these functions take longer and longer to run. I
> > had to disable them when I was measuring performance, else performance degraded
> > over time.
> 
> It's generally a good idea to measure performance in opt builds...

Yeah, I was using --enable-optimize --enable-debug so that I had debug symbols in an optimized build; made debugging opt-only crashes easier... You have a point though...

> I'm a bit worried about being vague here. I think we need to state as precisely
> as we can how the offset is related to the time.

Ok, it looks pretty easy to get the correct offset from liboggz.

	Robert O'Callahan (:roc) (email my personal email if necessary)
	Comment 14 • 15 years ago

(In reply to comment #13)
> Yeah, I was using --enable-optimize --enable-debug so that I had debug symbols
> in an optimized build; made debugging opt-only crashes easier... You have a
> point though...

Use --enable-debug-modules=ALL_MODULES

	Chris Pearce [:cpearce (Not reading bugmail)] Assignee
	Comment 15 • 15 years ago

As v2 with following changes:
* Roc's review comments addressed.
* MediaPoints is still stored in an array, but it's managed by binary search, rather than converting it to a tree structure.
* MediaPoints now adjust their offsets to point to ogg page starts.
* I saved another couple of seeks in oggz_get_prev_start_page(). This seeks backwards page by page, which would require one HTTP request per seek. Instead I first seek backwards by several pages, to load them into the cache. This saves 2 or 3 HTTP requests.

	Robert O'Callahan (:roc) (email my personal email if necessary)
	Comment 16 • 15 years ago

+  MediaPoint(PRInt64 o) : mOffset(o),
+                          mTime(Unknown) {}
+
+  MediaPoint(PRInt64 o, PRInt64 t) : mOffset(o),
+                                     mTime(t) {}

Use aO and aT, I'm afraid

+  void AddKnownPoint(MediaPoint& aPoint);

const MediaPoint&?

More comments to come...

	Robert O'Callahan (:roc) (email my personal email if necessary)
	Comment 17 • 15 years ago

+BinSearch(nsTArray<MediaPoint>& aArray, PRInt64 aTarget)

BinarySearch. Also, const nsTArray. But I wonder if this should be a method of nsTArray?

+static bool

PRBool

+// belong to different multiplexed streams will have will be increasing by

will have will be?

Wrap VerifySorted in #ifdef DEBUG.

In MediaMap::Update, although data can't be removed from the stream while it's pinned, it can be added. The length can also change dynamically. So to keep things simple and robust, I wouldn't actually bother checking x against aStream->GetLength(), just keep calling GetCachedDataEnd and GetNextCachedData until you reach the end of the cached data.

+  for (PRUint32 i=0; i<points.Length(); i++) {
+  for (PRUint32 i=0; i<mPoints.Length(); i++) {

More consistent with other code to add spaces around = and <

+nsMediaCacheStream::GetNextCachedDataInternal(PRInt64 aOffset)

Add PR_ASSERT_CURRENT_THREAD_IN_MONITOR here

+  PRUint32 startBlockIndex = aOffset/BLOCK_SIZE;
+  if (startBlockIndex >= mBlocks.Length())
+    return -1;
+
+  if (startBlockIndex == mChannelOffset/BLOCK_SIZE &&
+      aOffset < mChannelOffset) {
+    // The block containing mChannelOffset is partially read, but not
+    // yet committed to the main cache. aOffset lies in the partially
+    // read portion, thus it is effectively cached.
+    return aOffset;
+  }

The second if should be before the first one. It's entirely possible that channelOffset/BLOCK_SIZE == mBlocks.Length() --- the block hasn't been committed yet so it's not in mBlocks.

One problem occurs to me. Suppose we have a partially filled buffer. GetNextCachedDataInternal and GetCachedDataEndInternal will report that this data is available. But if a seek operation occurs, we'll throw away that data *even if the stream is pinned*. That's pretty bad. So actually it would be better to report the partial data as uncached, but I don't know if that would mess you up.

Is there any way we can move the PROFILE_MEDIA_SEEK code out to a helper object or helper functions so it doesn't appear inline in a lot of places, which makes the code harder to read?

I haven't reviewed mozilla_oggz_seek.cpp, I hope Chris does that.

	Robert O'Callahan (:roc) (email my personal email if necessary)
	Comment 18 • 15 years ago

I still really really want this for 1.9.1 but we aren't going to block the release on it.

	Chris Pearce [:cpearce (Not reading bugmail)] Assignee
	Comment 20 • 15 years ago

* Reworks patch from bug 462957 ("HTMLMediaElement.buffered") so that the common code is here, not there. It's a pretty simple matter of connecting HTMLMediaElement.buffered to MediaMap::GetBuffered() in order to implement buffered ranges, I'll post the patch for that, based on this one, in bug 462957.
* Uses MediaMap to parse the ogg stream and get timestamps for byte-offsets, rather than relying on a hacked copy of liboggz/oggz_seek.c like in the last patch. We now apply a small patch on top of oggz_seek.c to limit the seek to specified bounds. This approach is less divergent from liboggz, and we can potentially benefit from other fixes that may come into liboggz easier.
* Seeking inside buffered ranges is fast with this patch!

	Robert O'Callahan (:roc) (email my personal email if necessary)
	Comment 21 • 15 years ago

The changes to content/html/content/src (addition of nsHTMLTimeRanges) should be moved to bug 462957, so I'm not reviewing them here. Ditto for nsMediaDecoder.h.

+// Note that mTime values are approximate, they correspond to the timestamp
+// of the first Ogg page either before or after mOffset which has a
+// granulepos greater than 0. Whether we look for the Ogg page before or after
+// mOffset is context dependant.

"dependent"

The uncertainty here is scary. You told me F2F that mOffset is always exactly the start of a page and mTime is the timestamp for that page, so this comment should say that (and the code should agree!)

+                      mFrameDenomonator(1),

Denominator

Let's call MediaMap OggMediaMap since it's Ogg-specific.

I'm not really happy about all the new Ogg-parsing code. At least it should be in its own file. Really this should live in liboggz or liboggplay and so we can reuse existing code. As is, I think it's quite scary and there's likely to be bugs lurking there, and I'm not excited about landing it on branch just before release :-(

How hard would it be to just do the optimization that compares the seek destination time with the current time, and bounds the search to before the current offset? It seems to me that that captures the really big win available.

	Chris Pearce [:cpearce (Not reading bugmail)] Assignee
	Comment 22 • 15 years ago

(In reply to comment #21)
> I'm not really happy about all the new Ogg-parsing code. At least it should be
> in its own file. Really this should live in liboggz or liboggplay and so we can
> reuse existing code. As is, I think it's quite scary and there's likely to be
> bugs lurking there, and I'm not excited about landing it on branch just before
> release :-(

We can't easily use liboggplay/liboggz code for HTMLMediaElement.buffered. HTMLMediaElement.buffered needs to run on the main thread, but our OggReader only works on the decode thread. Chris Double suggested yesterday that we could create another OggReader which only reads data from the media cache on the main thread, and then open another OggPlay on this reader and use liboggz internal APIs to carefully seek around and get the timestamps in that. I'll look into that.

> How hard would it be to just do the optimization that compares the seek
> destination time with the current time, and bounds the search to before the
> current offset? It seems to me that that captures the really big win available.

That's a sensible and easy optimization to make, but the big win is when the seek position is inside a buffered range, and we know to restrict our search to inside that range, then seek is almost instantaneous.

I could use the seek search range restriction changes in the last patch, and then try each seek inside every large buffered byte range before falling back to an unbounded seek (or bounded WRT the current read cursor). That would probably give us the most benefit for the least amount of risk.

	Chris Pearce [:cpearce (Not reading bugmail)] Assignee
	Comment 23 • 15 years ago

* Functionally equivalent to previous two patches, but with a lot less code!
* Patches liboggz's seek so that it restricts itself to an offset range. We then try to seek inside all buffered ranges first, and if they all fail, we fall back to seeking inside the entire media.
* Seek uses the known-read cursor position to reduce search range.

	Robert O'Callahan (:roc) (email my personal email if necessary)
	Comment 24 • 15 years ago

GetNextCachedDataInternal isn't quite right. if mChannelOffset%BLOCK_SIZE is nonzero then we've got part of a block even though mBlocks[mChannelOffset/BLOCK_SIZE] is -1, we probably should check for that as we scan uncached blocks (starting with block startBlockIndex + 1). Note that this can be true even if mChannelOffset/BLOCK_SIZE >= mBlocks.Length(). Maybe it would be simplest to compute the next-cached-data from the mBlocks list alone and then if we have a partial block take the minimum with that.

	Robert O'Callahan (:roc) (email my personal email if necessary)
	Comment 25 • 15 years ago

+      if (cachedLength > 64 * 1024) {

Add a comment explaining why we need this? Otherwise looks good.

	Chris Pearce [:cpearce (Not reading bugmail)] Assignee
	Comment 26 • 15 years ago

(In reply to comment #24)
> GetNextCachedDataInternal isn't quite right.

How's this:

PRInt64
nsMediaCacheStream::GetNextCachedDataInternal(PRInt64 aOffset)
{
  PR_ASSERT_CURRENT_THREAD_IN_MONITOR(gMediaCache->Monitor());
  if (aOffset == mStreamLength)
    return -1;
  
  PRUint32 startBlockIndex = aOffset/BLOCK_SIZE;
  PRUint32 channelBlockIndex = mChannelOffset/BLOCK_SIZE;

  if (startBlockIndex == channelBlockIndex &&
      aOffset < mChannelOffset) {
    // The block containing mChannelOffset is partially read, but not
    // yet committed to the main cache. aOffset lies in the partially
    // read portion, thus it is effectively cached.
    return aOffset;
  }

  if (startBlockIndex >= mBlocks.Length())
    return -1;

  // Is the current block cached?
  if (mBlocks[startBlockIndex] != -1)
    return aOffset;

  // Count the number of uncached blocks
  PRBool hasPartialBlock = (mChannelOffset % BLOCK_SIZE) != 0;
  PRUint32 blockIndex = startBlockIndex + 1;
  while (PR_TRUE) {
    if ((hasPartialBlock && blockIndex == channelBlockIndex) ||
        (blockIndex < mBlocks.Length() && mBlocks[blockIndex] != -1)) {
      // We at the incoming channel block, which has has data in it,
      // or are we at a cached block. Return index of block start.
      return blockIndex * BLOCK_SIZE;
    }

    // No more cached blocks?
    if (blockIndex >= mBlocks.Length())
      return -1;

    ++blockIndex;
  }

  NS_NOTREACHED("Should return in loop");
  return -1;
}

	Robert O'Callahan (:roc) (email my personal email if necessary)
	Comment 27 • 15 years ago

That'll do.

	Chris Pearce [:cpearce (Not reading bugmail)] Assignee
	Comment 28 • 15 years ago

(In reply to comment #25)
> +      if (cachedLength > 64 * 1024) {
> 
> Add a comment explaining why we need this?

Done.

(In reply to comment #26)
> (In reply to comment #24)
> > GetNextCachedDataInternal isn't quite right.

Done, as per comment 26.

I also altered comments in oggz_seek.h so that they explain oggz_bounded_seek_set()'s parameters and match the format of other comments there.

I will try to get the liboggz changes upstreamed.

	cajbir (:cajbir)
	Comment 29 • 15 years ago

Comment on attachment 377595 [details] [diff] [review]
Patch v6

+void
+GetBufferedBytes(nsMediaStream* aStream, nsTArray<ByteRange>& aRanges)

Standard for the file is to have the return value on the same line as the function. Also, should this be static function?

+      // Only bother trying to seek inside ranges greater than 64K, so that
+      // the bounded seek is unlikely to read outside of the range when
+      // finding Ogg page boundaries.
+      if (cachedLength > 64 * 1024) {

Why 64K? Should this be defined as a constant somewhere rather than a magic number?

README_MOZILLA in media/liboggz needs to be updated to mention the bounded seek patch and refer to this bug.

	Chris Pearce [:cpearce (Not reading bugmail)] Assignee
	Comment 30 • 15 years ago

As v6, with Mr Double's review comments addressed.

(In reply to comment #29)
> Why 64K? Should this be defined as a constant somewhere rather than a magic
> number?

1. It's big enough that liboggz is unlikely to try to read outside of the buffered range when trying to find pages.
2. Anything smaller than that is likely to only be buffered because a seek bisection landed there anyway, so I'd guess that the seek target is unlikely to be inside such a small range.

	Chris Pearce [:cpearce (Not reading bugmail)] Assignee
	Comment 31 • 15 years ago

The changes to liboggz were upstreamed: http://git.xiph.org/?p=liboggz.git;a=commit;h=6e924a13e1b8585536acb7cb249530ccfeaf8e51

	Robert O'Callahan (:roc) (email my personal email if necessary)
	Comment 32 • 15 years ago

http://hg.mozilla.org/mozilla-central/rev/6b73408c2776

	Robert O'Callahan (:roc) (email my personal email if necessary)
	Comment 33 • 15 years ago

Followup checkins to fix tests that make unwarranted assumptions about seeking:
http://hg.mozilla.org/mozilla-central/rev/4c6d522e3075
http://hg.mozilla.org/mozilla-central/rev/485b7d5cc2ee

	Robert O'Callahan (:roc) (email my personal email if necessary)
	Comment 34 • 15 years ago

Oh, this one too:
http://hg.mozilla.org/mozilla-central/rev/1118ade0b7ad

	Henrik Skupin [:whimboo][⌚️UTC+2] Reporter
	Comment 35 • 15 years ago

I crashed while seeking in the given testcase (bug 493936). But that should be not related to this bug.

Seeking works fine for HTTP resources now. Verified fixed on trunk with builds on OS and Windows like Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.2a1pre) Gecko/20090519 Minefield/3.6a1pre ID:20090519032945

Shouldn't it be possible to create a test for this while using the js httpd server?

	Robert O'Callahan (:roc) (email my personal email if necessary)
	Comment 36 • 15 years ago

http://hg.mozilla.org/releases/mozilla-1.9.1/rev/dd1aeaa6d766
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/d09d4a05b841

	Henrik Skupin [:whimboo][⌚️UTC+2] Reporter
	Comment 37 • 15 years ago

Verified fixed on 1.9.1 with builds on Windows and OS X: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.1pre) Gecko/20090521 Shiretoko/3.5pre ID:20090521135222

On Linux I have problems with seeking at all but I will mention this in bug 494316.