135247 2014-07-24 12:07:20 -0700 [MSE] High CPU usage in SampleMap::findSamplesWithinPresentationRange() with a large number of buffered samples. 2014-12-16 13:26:08 -0800 1 1 1 Unclassified WebKit New Bugs 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED InRadar P2 Normal --- 1 jer.noble jer.noble calvaris commit-queue eric.carlson ggaren glenn ltilve philipj sergio webkit-bug-importer oldest_to_newest 1024547 0 jer.noble 2014-07-24 12:07:20 -0700 [MSE] High CPU usage in SampleMap::findSamplesWithinPresentationRange() with a large number of buffered samples. 1024595 1 235458 jer.noble 2014-07-24 14:10:03 -0700 Created attachment 235458 Patch 1024597 2 commit-queue 2014-07-24 14:11:16 -0700 Attachment 235458 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. 1024635 3 235458 ggaren 2014-07-24 15:30:55 -0700 Comment on attachment 235458 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. 1024658 4 jer.noble 2014-07-24 16:25:05 -0700 (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. 1024920 5 235458 commit-queue 2014-07-25 14:35:52 -0700 Comment on attachment 235458 Patch Clearing flags on attachment: 235458 Committed r171616: <http://trac.webkit.org/changeset/171616> 1024921 6 commit-queue 2014-07-25 14:35:55 -0700 All reviewed patches have been landed. Closing bug. 1024929 7 ggaren 2014-07-25 14:57:04 -0700 > > (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? 1024938 8 jer.noble 2014-07-25 15:42:18 -0700 (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. 1056083 9 jer.noble 2014-12-16 13:26:08 -0800 <rdar://problem/19268993> 235458 2014-07-24 14:10:03 -0700 2014-07-25 14:35:52 -0700 Patch bug-135247-20140724140948.patch text/plain 5935 jer.noble U3VidmVyc2lvbiBSZXZpc2lvbjogMTcxNDg4CmRpZmYgLS1naXQgYS9Tb3VyY2UvV2ViQ29yZS9D aGFuZ2VMb2cgYi9Tb3VyY2UvV2ViQ29yZS9DaGFuZ2VMb2cKaW5kZXggNjVjMzFkODk3MzQ2YTEw ZTA2Y2RhZmE0MTNkMDNjNDM2YWNmZTc2MS4uMjRkYWQxN2Y5NmQyN2ZiODA3NjI1NTc2ZGUzZWZj ZWEwMWYxZWZkNSAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvQ2hhbmdlTG9nCisrKyBiL1Nv dXJjZS9XZWJDb3JlL0NoYW5nZUxvZwpAQCAtMSwzICsxLDIwIEBACisyMDE0LTA3LTI0ICBKZXIg Tm9ibGUgIDxqZXIubm9ibGVAYXBwbGUuY29tPgorCisgICAgICAgIFtNU0VdIEhpZ2ggQ1BVIHVz YWdlIGluIFNhbXBsZU1hcDo6ZmluZFNhbXBsZXNXaXRoaW5QcmVzZW50YXRpb25SYW5nZSgpIHdp dGggYSBsYXJnZSBudW1iZXIgb2YgYnVmZmVyZWQgc2FtcGxlcy4KKyAgICAgICAgaHR0cHM6Ly9i dWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTEzNTI0NworCisgICAgICAgIFJldmlld2Vk IGJ5IE5PQk9EWSAoT09QUyEpLgorCisgICAgICAgIEFuY2hvciBvdXIgc2VhcmNoIGZvciBvdmVy bGFwcGluZyBmcmFtZXMgdG8gdGhlIGVuZCBvZiB0aGUgc2VhcmNoIHJhbmdlIHdoZW4gdGhlIG92 ZXJsYXAgcmFuZ2UgaXMgc3VmZmljaWVudGx5CisgICAgICAgIGNsb3NlIHRvIHRoZSBlbmQgb2Yg dGhlIHNlYXJjaCByYW5nZS4gVGhlIGNvbW1vbiBjYXNlIGZvciB0aGlzIHNlYXJjaCBpcyB3aGVu IGEgc2FtcGxlIGlzIGFib3V0IHRvIGJlIGFwcGVuZGVkCisgICAgICAgIHRvIHRoZSBlbmQgb2Yg dGhlIHNhbXBsZSBxdWV1ZSwgc28gdGhpcyBzaG91bGQgdHVybiBtb3N0IHNlYXJjaGVzIGludG8g bm8tb3BzLgorCisgICAgICAgICogTW9kdWxlcy9tZWRpYXNvdXJjZS9TYW1wbGVNYXAuY3BwOgor ICAgICAgICAoV2ViQ29yZTo6UHJlc2VudGF0aW9uT3JkZXJTYW1wbGVNYXA6OmZpbmRTYW1wbGVz V2l0aGluUHJlc2VudGF0aW9uUmFuZ2VGcm9tRW5kKToKKyAgICAgICAgKiBNb2R1bGVzL21lZGlh c291cmNlL1NhbXBsZU1hcC5oOgorICAgICAgICAqIE1vZHVsZXMvbWVkaWFzb3VyY2UvU291cmNl QnVmZmVyLmNwcDoKKyAgICAgICAgKFdlYkNvcmU6OlNvdXJjZUJ1ZmZlcjo6c291cmNlQnVmZmVy UHJpdmF0ZURpZFJlY2VpdmVTYW1wbGUpOgorCiAyMDE0LTA3LTIyICBKZXIgTm9ibGUgIDxqZXIu bm9ibGVAYXBwbGUuY29tPgogCiAgICAgICAgIFtNU0VdW01hY10gU3VwcG9ydCBhYm9ydCgpIGlu IFNvdXJjZUJ1ZmZlclByaXZhdGVBVkZPYmpDLgpkaWZmIC0tZ2l0IGEvU291cmNlL1dlYkNvcmUv TW9kdWxlcy9tZWRpYXNvdXJjZS9TYW1wbGVNYXAuY3BwIGIvU291cmNlL1dlYkNvcmUvTW9kdWxl cy9tZWRpYXNvdXJjZS9TYW1wbGVNYXAuY3BwCmluZGV4IDQ1NDQ3MmQyYWM4MDE1ZGU4NmM1MGJj NWJmZjZlZDc2YTZlY2E2NDAuLmM0MDlkZDZiMWNmYzYzYmJlYzAzNzA5MjhjZjVmNzM5MjFlODUw NDEgMTAwNjQ0Ci0tLSBhL1NvdXJjZS9XZWJDb3JlL01vZHVsZXMvbWVkaWFzb3VyY2UvU2FtcGxl TWFwLmNwcAorKysgYi9Tb3VyY2UvV2ViQ29yZS9Nb2R1bGVzL21lZGlhc291cmNlL1NhbXBsZU1h cC5jcHAKQEAgLTIzOCw2ICsyMzgsMTkgQEAgUHJlc2VudGF0aW9uT3JkZXJTYW1wbGVNYXA6Oml0 ZXJhdG9yX3JhbmdlIFByZXNlbnRhdGlvbk9yZGVyU2FtcGxlTWFwOjpmaW5kU2FtcGwKICAgICBy ZXR1cm4gc3RkOjplcXVhbF9yYW5nZShiZWdpbigpLCBlbmQoKSwgcmFuZ2UsIFNhbXBsZVByZXNl bnRhdGlvblRpbWVJc1dpdGhpblJhbmdlQ29tcGFyYXRvcigpKTsKIH0KIAorUHJlc2VudGF0aW9u T3JkZXJTYW1wbGVNYXA6Oml0ZXJhdG9yX3JhbmdlIFByZXNlbnRhdGlvbk9yZGVyU2FtcGxlTWFw OjpmaW5kU2FtcGxlc1dpdGhpblByZXNlbnRhdGlvblJhbmdlRnJvbUVuZChjb25zdCBNZWRpYVRp bWUmIGJlZ2luVGltZSwgY29uc3QgTWVkaWFUaW1lJiBlbmRUaW1lKQoreworICAgIHJldmVyc2Vf aXRlcmF0b3IgcmFuZ2VFbmQgPSBzdGQ6OmZpbmRfaWYocmJlZ2luKCksIHJlbmQoKSwgWyZiZWdp blRpbWVdIChQcmVzZW50YXRpb25PcmRlclNhbXBsZU1hcDo6TWFwVHlwZTo6dmFsdWVfdHlwZSB2 YWx1ZSkgeworICAgICAgICByZXR1cm4gdmFsdWUuc2Vjb25kLT5wcmVzZW50YXRpb25UaW1lKCkg PD0gYmVnaW5UaW1lOworICAgIH0pOworCisgICAgcmV2ZXJzZV9pdGVyYXRvciByYW5nZVN0YXJ0 ID0gc3RkOjpmaW5kX2lmKHJiZWdpbigpLCByYW5nZUVuZCwgWyZlbmRUaW1lXSAoUHJlc2VudGF0 aW9uT3JkZXJTYW1wbGVNYXA6Ok1hcFR5cGU6OnZhbHVlX3R5cGUgdmFsdWUpIHsKKyAgICAgICAg cmV0dXJuIHZhbHVlLnNlY29uZC0+cHJlc2VudGF0aW9uVGltZSgpIDw9IGVuZFRpbWU7CisgICAg fSk7CisKKyAgICByZXR1cm4gaXRlcmF0b3JfcmFuZ2UocmFuZ2VTdGFydC5iYXNlKCksIHJhbmdl RW5kLmJhc2UoKSk7Cit9CisKIERlY29kZU9yZGVyU2FtcGxlTWFwOjpyZXZlcnNlX2l0ZXJhdG9y X3JhbmdlIERlY29kZU9yZGVyU2FtcGxlTWFwOjpmaW5kRGVwZW5kZW50U2FtcGxlcyhNZWRpYVNh bXBsZSogc2FtcGxlKQogewogICAgIEFTU0VSVChzYW1wbGUpOwpkaWZmIC0tZ2l0IGEvU291cmNl L1dlYkNvcmUvTW9kdWxlcy9tZWRpYXNvdXJjZS9TYW1wbGVNYXAuaCBiL1NvdXJjZS9XZWJDb3Jl L01vZHVsZXMvbWVkaWFzb3VyY2UvU2FtcGxlTWFwLmgKaW5kZXggODA0YWZjYjJkNDdkMjY0NWEx MTExMmQwODgzMmFmMDJjOTAwMzA3OS4uNTgwOWUxMTBlMTJhMzNjOThjYjE2ZTI3NzUzMzc5Yjhk YWY3NWFkZiAxMDA2NDQKLS0tIGEvU291cmNlL1dlYkNvcmUvTW9kdWxlcy9tZWRpYXNvdXJjZS9T YW1wbGVNYXAuaAorKysgYi9Tb3VyY2UvV2ViQ29yZS9Nb2R1bGVzL21lZGlhc291cmNlL1NhbXBs ZU1hcC5oCkBAIC01Nyw2ICs1Nyw3IEBAIHB1YmxpYzoKICAgICByZXZlcnNlX2l0ZXJhdG9yIHJl dmVyc2VGaW5kU2FtcGxlQmVmb3JlUHJlc2VudGF0aW9uVGltZShjb25zdCBNZWRpYVRpbWUmKTsK ICAgICBpdGVyYXRvcl9yYW5nZSBmaW5kU2FtcGxlc0JldHdlZW5QcmVzZW50YXRpb25UaW1lcyhj b25zdCBNZWRpYVRpbWUmLCBjb25zdCBNZWRpYVRpbWUmKTsKICAgICBpdGVyYXRvcl9yYW5nZSBm aW5kU2FtcGxlc1dpdGhpblByZXNlbnRhdGlvblJhbmdlKGNvbnN0IE1lZGlhVGltZSYsIGNvbnN0 IE1lZGlhVGltZSYpOworICAgIGl0ZXJhdG9yX3JhbmdlIGZpbmRTYW1wbGVzV2l0aGluUHJlc2Vu dGF0aW9uUmFuZ2VGcm9tRW5kKGNvbnN0IE1lZGlhVGltZSYsIGNvbnN0IE1lZGlhVGltZSYpOwog CiBwcml2YXRlOgogICAgIE1hcFR5cGUgbV9zYW1wbGVzOwpkaWZmIC0tZ2l0IGEvU291cmNlL1dl YkNvcmUvTW9kdWxlcy9tZWRpYXNvdXJjZS9Tb3VyY2VCdWZmZXIuY3BwIGIvU291cmNlL1dlYkNv cmUvTW9kdWxlcy9tZWRpYXNvdXJjZS9Tb3VyY2VCdWZmZXIuY3BwCmluZGV4IDk4MzJhOGQ0Mzcy ZjVmNzEwZmIzNzQwODhiNDk1YzIxMTM4NTYwMTEuLmEyZTYzMDk0NTgxNmExMDNlM2UzMjQ0ZDY4 MWUwOTMzNjRlZDkwODUgMTAwNjQ0Ci0tLSBhL1NvdXJjZS9XZWJDb3JlL01vZHVsZXMvbWVkaWFz b3VyY2UvU291cmNlQnVmZmVyLmNwcAorKysgYi9Tb3VyY2UvV2ViQ29yZS9Nb2R1bGVzL21lZGlh c291cmNlL1NvdXJjZUJ1ZmZlci5jcHAKQEAgLTExNDUsOSArMTE0NSwyOSBAQCB2b2lkIFNvdXJj ZUJ1ZmZlcjo6c291cmNlQnVmZmVyUHJpdmF0ZURpZFJlY2VpdmVTYW1wbGUoU291cmNlQnVmZmVy UHJpdmF0ZSosIFBhcwogICAgICAgICBpZiAodHJhY2tCdWZmZXIuaGlnaGVzdFByZXNlbnRhdGlv blRpbWVzdGFtcC5pc1ZhbGlkKCkgJiYgdHJhY2tCdWZmZXIuaGlnaGVzdFByZXNlbnRhdGlvblRp bWVzdGFtcCA8PSBwcmVzZW50YXRpb25UaW1lc3RhbXApIHsKICAgICAgICAgICAgIC8vIFJlbW92 ZSBhbGwgY29kZWQgZnJhbWVzIGZyb20gdHJhY2sgYnVmZmVyIHRoYXQgaGF2ZSBhIHByZXNlbnRh dGlvbiB0aW1lc3RhbXAgZ3JlYXRlciB0aGFuIGhpZ2hlc3QKICAgICAgICAgICAgIC8vIHByZXNl bnRhdGlvbiB0aW1lc3RhbXAgYW5kIGxlc3MgdGhhbiBvciBlcXVhbCB0byBmcmFtZSBlbmQgdGlt ZXN0YW1wLgotICAgICAgICAgICAgYXV0byBpdGVyX3BhaXIgPSB0cmFja0J1ZmZlci5zYW1wbGVz LnByZXNlbnRhdGlvbk9yZGVyKCkuZmluZFNhbXBsZXNXaXRoaW5QcmVzZW50YXRpb25SYW5nZSh0 cmFja0J1ZmZlci5oaWdoZXN0UHJlc2VudGF0aW9uVGltZXN0YW1wLCBmcmFtZUVuZFRpbWVzdGFt cCk7Ci0gICAgICAgICAgICBpZiAoaXRlcl9wYWlyLmZpcnN0ICE9IHRyYWNrQnVmZmVyLnNhbXBs ZXMucHJlc2VudGF0aW9uT3JkZXIoKS5lbmQoKSkKLSAgICAgICAgICAgICAgICBlcmFzZWRTYW1w bGVzLmFkZFJhbmdlKGl0ZXJfcGFpci5maXJzdCwgaXRlcl9wYWlyLnNlY29uZCk7CisgICAgICAg ICAgICBkbyB7CisgICAgICAgICAgICAgICAgLy8gTk9URTogU2VhcmNoaW5nIGZyb20gdGhlIGVu ZCBvZiB0aGUgdHJhY2tCdWZmZXIgd2lsbCBiZSB2YXN0bHkgbW9yZSBlZmZpY2llbnQgaWYgdGhl IHNlYXJjaCByYW5nZSBpcworICAgICAgICAgICAgICAgIC8vIG5lYXIgdGhlIGVuZCBvZiB0aGUg YnVmZmVyZWQgcmFuZ2UuIFVzZSBhIGxpbmVhci1iYWNrd2FyZHMgc2VhcmNoIGlmIHRoZSBzZWFy Y2ggcmFuZ2UgaXMgd2l0aGluIG9uZQorICAgICAgICAgICAgICAgIC8vIGZyYW1lIGR1cmF0aW9u IG9mIHRoZSBlbmQ6CisgICAgICAgICAgICAgICAgaWYgKCFtX2J1ZmZlcmVkKQorICAgICAgICAg ICAgICAgICAgICBicmVhazsKKworICAgICAgICAgICAgICAgIHVuc2lnbmVkIGJ1ZmZlcmVkTGVu Z3RoID0gbV9idWZmZXJlZC0+cmFuZ2VzKCkubGVuZ3RoKCk7CisgICAgICAgICAgICAgICAgaWYg KCFidWZmZXJlZExlbmd0aCkKKyAgICAgICAgICAgICAgICAgICAgYnJlYWs7CisKKyAgICAgICAg ICAgICAgICBib29sIGlnbm9yZVZhbGlkOworICAgICAgICAgICAgICAgIE1lZGlhVGltZSBoaWdo ZXN0QnVmZmVyZWRUaW1lID0gbV9idWZmZXJlZC0+cmFuZ2VzKCkuZW5kKGJ1ZmZlcmVkTGVuZ3Ro IC0gMSwgaWdub3JlVmFsaWQpOworCisgICAgICAgICAgICAgICAgUHJlc2VudGF0aW9uT3JkZXJT YW1wbGVNYXA6Oml0ZXJhdG9yX3JhbmdlIHJhbmdlOworICAgICAgICAgICAgICAgIGlmIChoaWdo ZXN0QnVmZmVyZWRUaW1lIC0gdHJhY2tCdWZmZXIuaGlnaGVzdFByZXNlbnRhdGlvblRpbWVzdGFt cCA8IHRyYWNrQnVmZmVyLmxhc3RGcmFtZUR1cmF0aW9uKQorICAgICAgICAgICAgICAgICAgICBy YW5nZSA9IHRyYWNrQnVmZmVyLnNhbXBsZXMucHJlc2VudGF0aW9uT3JkZXIoKS5maW5kU2FtcGxl c1dpdGhpblByZXNlbnRhdGlvblJhbmdlRnJvbUVuZCh0cmFja0J1ZmZlci5oaWdoZXN0UHJlc2Vu dGF0aW9uVGltZXN0YW1wLCBmcmFtZUVuZFRpbWVzdGFtcCk7CisgICAgICAgICAgICAgICAgZWxz ZQorICAgICAgICAgICAgICAgICAgICByYW5nZSA9IHRyYWNrQnVmZmVyLnNhbXBsZXMucHJlc2Vu dGF0aW9uT3JkZXIoKS5maW5kU2FtcGxlc1dpdGhpblByZXNlbnRhdGlvblJhbmdlKHRyYWNrQnVm ZmVyLmhpZ2hlc3RQcmVzZW50YXRpb25UaW1lc3RhbXAsIGZyYW1lRW5kVGltZXN0YW1wKTsKKwor ICAgICAgICAgICAgICAgIGlmIChyYW5nZS5maXJzdCAhPSB0cmFja0J1ZmZlci5zYW1wbGVzLnBy ZXNlbnRhdGlvbk9yZGVyKCkuZW5kKCkpCisgICAgICAgICAgICAgICAgICAgIGVyYXNlZFNhbXBs ZXMuYWRkUmFuZ2UocmFuZ2UuZmlyc3QsIHJhbmdlLnNlY29uZCk7CisgICAgICAgICAgICB9IHdo aWxlKGZhbHNlKTsKICAgICAgICAgfQogCiAgICAgICAgIC8vIDEuMTYgUmVtb3ZlIGRlY29kaW5n IGRlcGVuZGVuY2llcyBvZiB0aGUgY29kZWQgZnJhbWVzIHJlbW92ZWQgaW4gdGhlIHByZXZpb3Vz IHN0ZXA6Cg==