Bug 135247 – [MSE] High CPU usage in SampleMap::findSamplesWithinPresentationRange() with a large number of buffered samples.

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Jer Noble]

[MSE] High CPU usage in SampleMap::findSamplesWithinPresentationRange() with a large number of buffered samples.

[Jer Noble]

Created attachment 235458 [details]
Patch

[WebKit Commit Bot]

Attachment 235458 [details] did not pass style-queue:


ERROR: Source/WebCore/Modules/mediasource/SourceBuffer.cpp:1170:  Missing space before ( in while(  [whitespace/parens] [5]
Total errors found: 1 in 4 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Geoffrey Garen]

Comment on attachment 235458 [details]
Patch

Are the samples ordered in some way? If so, we should just do a fast check for "is the answer the last sample?" followed by a binary search. It seems like doing a linear search through a list of media times is probably never a good idea, since media can be hours long.

[Jer Noble]

(In reply to comment #3)
> (From update of attachment 235458 [details])
> Are the samples ordered in some way? If so, we should just do a fast check for "is the answer the last sample?" followed by a binary search. It seems like doing a linear search through a list of media times is probably never a good idea, since media can be hours long.

Effectively, that's what we're doing.  The last frame in the ordered set (trackBuffer.samples.presentationOrder()) defines the end of the buffered range. If the start of the search range (trackBuffer.highestPresentationTimestamp) is within one frame duration of the end of the buffered range, at most one frame will be searched.

[WebKit Commit Bot]

Comment on attachment 235458 [details]
Patch

Clearing flags on attachment: 235458

Committed r171616: <http://trac.webkit.org/changeset/171616>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Geoffrey Garen]

> > (From update of attachment 235458 [details] [details])
> > Are the samples ordered in some way? If so, we should just do a fast check for "is the answer the last sample?" followed by a binary search. It seems like doing a linear search through a list of media times is probably never a good idea, since media can be hours long.
> 
> Effectively, that's what we're doing.  The last frame in the ordered set (trackBuffer.samples.presentationOrder()) defines the end of the buffered range. If the start of the search range (trackBuffer.highestPresentationTimestamp) is within one frame duration of the end of the buffered range, at most one frame will be searched.

Right, but in the case where that last frame optimization fails, do we end up doing a linear search, or a binary search?

[Jer Noble]

(In reply to comment #7)
> > > (From update of attachment 235458 [details] [details] [details])
> > > Are the samples ordered in some way? If so, we should just do a fast check for "is the answer the last sample?" followed by a binary search. It seems like doing a linear search through a list of media times is probably never a good idea, since media can be hours long.
> > 
> > Effectively, that's what we're doing.  The last frame in the ordered set (trackBuffer.samples.presentationOrder()) defines the end of the buffered range. If the start of the search range (trackBuffer.highestPresentationTimestamp) is within one frame duration of the end of the buffered range, at most one frame will be searched.
> 
> Right, but in the case where that last frame optimization fails, do we end up doing a linear search, or a binary search?

We do a linear search of a set with [0, 1] entries.

[Jer Noble]

<rdar://problem/19268993>