Bug 135247 - [MSE] High CPU usage in SampleMap::findSamplesWithinPresentationRange() with a large number of buffered samples.
Summary: [MSE] High CPU usage in SampleMap::findSamplesWithinPresentationRange() with ...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: New Bugs (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Jer Noble
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2014-07-24 12:07 PDT by Jer Noble
Modified: 2014-12-16 13:26 PST (History)
9 users (show)

See Also:


Attachments
Patch (5.80 KB, patch)
2014-07-24 14:10 PDT, Jer Noble
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Jer Noble 2014-07-24 12:07:20 PDT
[MSE] High CPU usage in SampleMap::findSamplesWithinPresentationRange() with a large number of buffered samples.
Comment 1 Jer Noble 2014-07-24 14:10:03 PDT
Created attachment 235458 [details]
Patch
Comment 2 WebKit Commit Bot 2014-07-24 14:11:16 PDT
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.
Comment 3 Geoffrey Garen 2014-07-24 15:30:55 PDT
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.
Comment 4 Jer Noble 2014-07-24 16:25:05 PDT
(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.
Comment 5 WebKit Commit Bot 2014-07-25 14:35:52 PDT
Comment on attachment 235458 [details]
Patch

Clearing flags on attachment: 235458

Committed r171616: <http://trac.webkit.org/changeset/171616>
Comment 6 WebKit Commit Bot 2014-07-25 14:35:55 PDT
All reviewed patches have been landed.  Closing bug.
Comment 7 Geoffrey Garen 2014-07-25 14:57:04 PDT
> > (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?
Comment 8 Jer Noble 2014-07-25 15:42:18 PDT
(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.
Comment 9 Jer Noble 2014-12-16 13:26:08 PST
<rdar://problem/19268993>