Bug 70452

Created attachment 112047 [details] Patch

Can you explain the algorithm you use for fast lookup. On the base of it, I would assume an IntervalMap to be a good data structure for this.

Also, if this is an optimization, can you please show the speedups through some sort of perf test (it doesn't have to be checked in, you just need to show that this is speeding something up).

'fast' is a relative term, so I probably should not have used it here as there is no current functionality to compare to (there are no demonstrable speedups because this is new). The intent of TextTrackCueIndex is a handy storage mechanism for TextTrackCues that may come from multiple text tracks to be used in HTMLMediaElement (or any other player). As cues are parsed or otherwise discovered, they will be stored in a TextTrackCueIndex in order of startTime/endTime so that as playback progresses, the cues that should be currently visible can be easily looked up. The alternative would be for HTMLMediaElement to iterate through it's list of tracks, finding cues with timestamps in the range of the current playback position, and then sort them in text track cue order before displaying them. TextTrackCueIndex and TextTrackCueSet make this process easier and likely more efficient.

Without any performance data, I don't think it makes sense to complicate the code with this. I also think an IntervalMap-type data structure would probably be a better fix for this type of optimization, should it be shown to be needed.

Sam, are you suggesting that TextTrackCueIndex and TextTrackCueSet not be included at all and HTMLMediaElement would be responsible for managing cues visible at runtime? Can you tell me more (and/or add a link) about IntervalMap. I don't see this as a WebKit data structure. Thanks for the feedback.

Created attachment 114304 [details] uses PODIntervalTree as data structure

This patch overlaps a bit with this one: https://bugs.webkit.org/show_bug.cgi?id=71123 so we'll need to take turns, but I thought I'd get the review process started. Thanks!

Comment on attachment 114304 [details] uses PODIntervalTree as data structure View in context: https://bugs.webkit.org/attachment.cgi?id=114304&action=review > Source/WebCore/html/HTMLMediaElement.h:523 > + typedef PODInterval<float, TextTrackCue*> CueInterval; > + PODIntervalTree<float, TextTrackCue*> m_cueTree; > + Vector<CueInterval> m_currentlyVisibleCues; This might read slightly cleaner if you wrote it as: typedef PODIntervalTree <float, TextTrackCue*> CueIntervalTree; CueIntervalTree m_cueTree; Vectore<CueIntervalTree::IntervalType> m_currentlyVisibleCues;

Comment on attachment 114304 [details] uses PODIntervalTree as data structure View in context: https://bugs.webkit.org/attachment.cgi?id=114304&action=review Every non-DOM object that is an EventTarget needs code (for JSC at lease, I don't know about V8) to make sure that the wrapper isn't collected during event dispatch or while the parent/owner object is reachable. For example, see JSTextTrackListOwner::isReachableFromOpaqueRoots and the tracklist-is-reachable.html test added in https://bugs.webkit.org/show_bug.cgi?id=71123. I think this is fine to do in a follow up patch, but please file a bug for the fix (and I am happy to make the changes for JSC). > Source/WebCore/html/HTMLMediaElement.cpp:852 > +void HTMLMediaElement::updateActiveTextTrackCues() > +{ > + float movieTime = currentTime(); > + Nit: it would be slightly more efficient if this function took the current time because one of the places it is called will have just fetched it. > Source/WebCore/html/HTMLMediaElement.h:522 > + typedef PODInterval<float, TextTrackCue*> CueInterval; > + PODIntervalTree<float, TextTrackCue*> m_cueTree; TextTrackCue startTime and endTime times both doubles, why use float ? > Source/WebCore/html/TextTrackCue.cpp:154 > + if (active) > + dispatchEvent(Event::create(eventNames().enterEvent, false, false), ec); > + else > + dispatchEvent(Event::create(eventNames().exitEvent, false, false), ec); > + This is missing a number of the steps listed in the spec. All of the cue events for a time should be put into a queue, sorted and filtered, and then fired asynchronously. Because the events have to fire in order across all of the tracks/cues, maybe it make sense for the media element to own and maintain a queue of cue events? > Source/WebCore/html/TextTrackCue.cpp:156 > + if (m_track) > + m_track->fireCueChangeEvent(); The 'cuechange' event must fire on both the TextTrack and <track> : ... queue a task to fire a simple event named cuechange at the TextTrack object, and, if the text track has a corresponding track element, to then fire a simple event named cuechange at the track element as well ... > LayoutTests/media/track/track-cues-cuechange.html:25 > + function cueChanged() > + { > + var cues = testTrack.track.cues; > + > + var currentCue = cues[Math.floor(cueChangeCount/2)]; > + Nit: I think it would be helpful to log "EVENT(cuechange)" here so the results make it obvious these checks happen in response to the event. > LayoutTests/media/track/track-cues-cuechange.html:49 > + testTrack = document.getElementById("testTrack"); > + testExpected("testTrack.track.cues.length", 3); > + testTrack.track.addEventListener('cuechange', cueChanged); This should also verify that 'cuechange' is fired on the <track>. > LayoutTests/media/track/track-cues-enter-exit.html:10 > + <p>Tests that TextTrack's cues are indexed and updated within 500ms during video playback. Test uses the enter and exits events on TextTrackCue.</p> How did you decide on 500ms? > LayoutTests/media/track/track-cues-enter-exit.html:22 > + function cueEntered() > + { > + var currentCue = testTrack.track.cues[cueCount]; Nit: I think it would be helpful to log "EVENT(enter)" here so the results make it obvious these checks happen in response to the event. > LayoutTests/media/track/track-cues-enter-exit.html:33 > + function cueExited() > + { > + var currentCue = testTrack.track.cues[cueCount]; Logging the event name would be good here as well.

Comment on attachment 114304 [details] uses PODIntervalTree as data structure View in context: https://bugs.webkit.org/attachment.cgi?id=114304&action=review Thanks Eric and Sam. I'll look into the changes needed for non-DOM objects to extend EventTarget as a follow up. >> Source/WebCore/html/HTMLMediaElement.cpp:852 >> + > > Nit: it would be slightly more efficient if this function took the current time because one of the places it is called will have just fetched it. Done. >> Source/WebCore/html/HTMLMediaElement.h:522 >> + PODIntervalTree<float, TextTrackCue*> m_cueTree; > > TextTrackCue startTime and endTime times both doubles, why use float ? Oops, thanks. Fixed >> Source/WebCore/html/HTMLMediaElement.h:523 >> + Vector<CueInterval> m_currentlyVisibleCues; > > This might read slightly cleaner if you wrote it as: > > typedef PODIntervalTree <float, TextTrackCue*> CueIntervalTree; > CueIntervalTree m_cueTree; > Vectore<CueIntervalTree::IntervalType> m_currentlyVisibleCues; Done. >> Source/WebCore/html/TextTrackCue.cpp:154 >> + > > This is missing a number of the steps listed in the spec. All of the cue events for a time should be put into a queue, sorted and filtered, and then fired asynchronously. > > Because the events have to fire in order across all of the tracks/cues, maybe it make sense for the media element to own and maintain a queue of cue events? Sounds like a great idea for a follow up patch. I'll file a bug >> Source/WebCore/html/TextTrackCue.cpp:156 >> + m_track->fireCueChangeEvent(); > > The 'cuechange' event must fire on both the TextTrack and <track> : > > ... queue a task to fire a simple event named cuechange at the TextTrack object, and, if the text track has a corresponding track element, to then fire a simple event named cuechange at the track element as well ... Done. >> LayoutTests/media/track/track-cues-cuechange.html:25 >> + > > Nit: I think it would be helpful to log "EVENT(cuechange)" here so the results make it obvious these checks happen in response to the event. Done. >> LayoutTests/media/track/track-cues-enter-exit.html:10 >> + <p>Tests that TextTrack's cues are indexed and updated within 500ms during video playback. Test uses the enter and exits events on TextTrackCue.</p> > > How did you decide on 500ms? We fire time updates every 250ms, so I figured every cue should be encountered and appropriate events should be fired within 500ms. I'm open to suggestions on the best way to check for this. >> LayoutTests/media/track/track-cues-enter-exit.html:22 >> + var currentCue = testTrack.track.cues[cueCount]; > > Nit: I think it would be helpful to log "EVENT(enter)" here so the results make it obvious these checks happen in response to the event. Done. >> LayoutTests/media/track/track-cues-enter-exit.html:33 >> + var currentCue = testTrack.track.cues[cueCount]; > > Logging the event name would be good here as well. Done.

Created attachment 114764 [details] addressing reviewer comments and updating to ToT

Comment on attachment 114764 [details] addressing reviewer comments and updating to ToT View in context: https://bugs.webkit.org/attachment.cgi?id=114764&action=review > Source/WebCore/html/HTMLMediaElement.cpp:-507 > - I believe this is no longer needed here because it is covered by trackWasAdded(). eric.carlson, please check my logic here as you recently added this.

Comment on attachment 114764 [details] addressing reviewer comments and updating to ToT View in context: https://bugs.webkit.org/attachment.cgi?id=114764&action=review >> Source/WebCore/html/HTMLMediaElement.cpp:-507 > > I believe this is no longer needed here because it is covered by trackWasAdded(). eric.carlson, please check my logic here as you recently added this. There is a problem, but I think it is that HTMLMediaElement::addTextTrack should call scheduleLoad(TextTrackResource) instead of configureTextTracks() because we need to start the load asynchronously. > Source/WebCore/html/HTMLMediaElement.cpp:1965 > + float movieTime = currentTime(); > + updateActiveTextTrackCues(movieTime); Nit: the local variable isn't necessary. > Source/WebCore/html/HTMLTrackElement.cpp:157 > + m_track = LoadableTextTrack::create(scriptExecutionContext(), this, kind(), label(), srclang(), isDefault()); You shouldn't need to pass a ScriptExecutionContext, the track can use the Document associated with the track element for the ScriptExecutionContext.

Created attachment 114799 [details] using scheduleLoad(TextTrackResource) instead of configureTextTracks()

Created attachment 114801 [details] addressing Eric's comments

Comment on attachment 114801 [details] addressing Eric's comments Clearing flags on attachment: 114801 Committed r100064: <http://trac.webkit.org/changeset/100064>

All reviewed patches have been landed. Closing bug.