| Summary: | [MSE] High CPU usage in SampleMap::findSamplesWithinPresentationRange() with a large number of buffered samples. | ||||||
|---|---|---|---|---|---|---|---|
| Product: | WebKit | Reporter: | Jer Noble <jer.noble> | ||||
| Component: | New Bugs | Assignee: | Jer Noble <jer.noble> | ||||
| Status: | RESOLVED FIXED | ||||||
| Severity: | Normal | CC: | calvaris, commit-queue, eric.carlson, ggaren, glenn, ltilve, philipj, sergio, webkit-bug-importer | ||||
| Priority: | P2 | Keywords: | InRadar | ||||
| Version: | 528+ (Nightly build) | ||||||
| Hardware: | Unspecified | ||||||
| OS: | Unspecified | ||||||
| Attachments: |
|
||||||
|
Description
Jer Noble
2014-07-24 12:07:20 PDT
Created attachment 235458 [details]
Patch
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 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.
(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 on attachment 235458 [details] Patch Clearing flags on attachment: 235458 Committed r171616: <http://trac.webkit.org/changeset/171616> All reviewed patches have been landed. Closing bug. > > (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?
(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. |