Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
955443002:
Replace open-coded binary search in TextTrackCueList::add with upper_bound (Closed)
|
Created:
5 years, 10 months ago by fs Modified:
5 years, 10 months ago Reviewers:
philipj_slow CC:
blink-reviews, nessy, gasubic, fs, eric.carlson_apple.com, blink-reviews-html_chromium.org, dglazkov+blink, vcarbune.chromium Base URL:
svn://svn.chromium.org/blink/trunk Target Ref:
refs/heads/master Project:
blink Visibility:
Public. |
DescriptionReplace open-coded binary search in TextTrackCueList::add with upper_bound
TextTrackCueList::add is implemented as a recursive binary search. This
add() method is used both for adding (new) cues to the list, and to update
the position of a cue in the list after mutation of it.
These two use-cases have slightly different requirement, but it still
makes sense to reuse some parts of it.
Split out the binary search into a method of its own - replacing it with
std::upper_bound - and then call this from add() and updateCueIndex() while
open-coding the actual Vector::insert() and index-cache invalidation.
Add some notes about potential future improvements.
BUG=321654
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=190908
Patch Set 1 #
Total comments: 16
Patch Set 2 : More FIXMEs; Update URL; Drop returned bool. #Patch Set 3 : Re-add add() in updateCueIndex. #
Messages
Total messages: 13 (2 generated)
fs@opera.com changed reviewers: + philipj@opera.com
https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... File Source/core/html/track/TextTrackCueList.cpp (right): https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... Source/core/html/track/TextTrackCueList.cpp:85: // http://www.whatwg.org/specs/web-apps/current-work/#text-track-cue-order https://html.spec.whatwg.org/#text-track-cue-order https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... Source/core/html/track/TextTrackCueList.cpp:123: bool TextTrackCueList::updateCueIndex(TextTrackCue* cue) Here or in another CL the return value can be dropped, it isn't used. https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... Source/core/html/track/TextTrackCueList.cpp:136: bool indexChanged = newIndex != oldIndex; I'm not sure what the benefit of this over add(cue) is going to be. Is there anything other than getting the return value right that matters? https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... Source/core/html/track/TextTrackCueList.cpp:138: // FIXME: If moving from oldIndex to newIndex and newIndex > oldIndex, TextTrackCueList::remove has the same problem, right? https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... Source/core/html/track/TextTrackCueList.cpp:155: // FIXME: When iterating cues we could as well update their cached indices too. Heh, yeah :)
https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... File Source/core/html/track/TextTrackCueList.cpp (right): https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... Source/core/html/track/TextTrackCueList.cpp:123: bool TextTrackCueList::updateCueIndex(TextTrackCue* cue) On 2015/02/25 02:28:40, philipj_UTC7 wrote: > Here or in another CL the return value can be dropped, it isn't used. Yes, it's a bit strange both that it wasn't used... I might as well drop it in this CL. I want to conditionalize calling this on whether the cue order could actually have changed at all (this method is O(n) after all). https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... Source/core/html/track/TextTrackCueList.cpp:136: bool indexChanged = newIndex != oldIndex; On 2015/02/25 02:28:40, philipj_UTC7 wrote: > I'm not sure what the benefit of this over add(cue) is going to be. Is there > anything other than getting the return value right that matters? The main reason would be the comment below - i.e. it make sense to have both of the index-values available when invalidating the cue index. Did not intend to actually fix anything in this CL though. https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... Source/core/html/track/TextTrackCueList.cpp:138: // FIXME: If moving from oldIndex to newIndex and newIndex > oldIndex, On 2015/02/25 02:28:40, philipj_UTC7 wrote: > TextTrackCueList::remove has the same problem, right? In a sense, yes. Theoretically remove() does not invalidate the cue order property though (cueIndex(list[i]) < cueIndex(list[i+2]) still hold etc.). You're quite likely to end up in a bad place eventually though. I have some plans for how to change the "cue index" management that ought to address all the FIXMEs in this CL - just putting the spotlight on them here basically.
I think this will be OK with the return value dropped given your future ambitions to clean this up. https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... File Source/core/html/track/TextTrackCueList.cpp (right): https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... Source/core/html/track/TextTrackCueList.cpp:123: bool TextTrackCueList::updateCueIndex(TextTrackCue* cue) On 2015/02/25 13:09:49, fs wrote: > On 2015/02/25 02:28:40, philipj_UTC7 wrote: > > Here or in another CL the return value can be dropped, it isn't used. > > Yes, it's a bit strange both that it wasn't used... I might as well drop it in > this CL. I want to conditionalize calling this on whether the cue order could > actually have changed at all (this method is O(n) after all). Thanks, I think that may make things a bit clearer, as it currently appears as if some effort is spent trying to return the right thing, but it sounds like avoiding O(n) is the real reason. https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... Source/core/html/track/TextTrackCueList.cpp:138: // FIXME: If moving from oldIndex to newIndex and newIndex > oldIndex, On 2015/02/25 13:09:49, fs wrote: > On 2015/02/25 02:28:40, philipj_UTC7 wrote: > > TextTrackCueList::remove has the same problem, right? > > In a sense, yes. Theoretically remove() does not invalidate the cue order > property though (cueIndex(list[i]) < cueIndex(list[i+2]) still hold etc.). > You're quite likely to end up in a bad place eventually though. I have some > plans for how to change the "cue index" management that ought to address all the > FIXMEs in this CL - just putting the spotlight on them here basically. Throw a FIXME in remove as well to make this class appear maximally in need of fixing? :)
https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... File Source/core/html/track/TextTrackCueList.cpp (right): https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... Source/core/html/track/TextTrackCueList.cpp:85: // http://www.whatwg.org/specs/web-apps/current-work/#text-track-cue-order On 2015/02/25 02:28:40, philipj_UTC7 wrote: > https://html.spec.whatwg.org/#text-track-cue-order Done. https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... Source/core/html/track/TextTrackCueList.cpp:123: bool TextTrackCueList::updateCueIndex(TextTrackCue* cue) On 2015/02/25 15:38:54, philipj_UTC7 wrote: > On 2015/02/25 13:09:49, fs wrote: > > On 2015/02/25 02:28:40, philipj_UTC7 wrote: > > > Here or in another CL the return value can be dropped, it isn't used. > > > > Yes, it's a bit strange both that it wasn't used... I might as well drop it in > > this CL. I want to conditionalize calling this on whether the cue order could > > actually have changed at all (this method is O(n) after all). > > Thanks, I think that may make things a bit clearer, as it currently appears as > if some effort is spent trying to return the right thing, but it sounds like > avoiding O(n) is the real reason. Return-value dropped. "Avoiding" O(n) here can only be achieved by not calling this method at all =) (all actions on m_list in this method - find, remove, insert - are worst/average-case O(n)). https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... Source/core/html/track/TextTrackCueList.cpp:138: // FIXME: If moving from oldIndex to newIndex and newIndex > oldIndex, On 2015/02/25 15:38:54, philipj_UTC7 wrote: > On 2015/02/25 13:09:49, fs wrote: > > On 2015/02/25 02:28:40, philipj_UTC7 wrote: > > > TextTrackCueList::remove has the same problem, right? > > > > In a sense, yes. Theoretically remove() does not invalidate the cue order > > property though (cueIndex(list[i]) < cueIndex(list[i+2]) still hold etc.). > > You're quite likely to end up in a bad place eventually though. I have some > > plans for how to change the "cue index" management that ought to address all > the > > FIXMEs in this CL - just putting the spotlight on them here basically. > > Throw a FIXME in remove as well to make this class appear maximally in need of > fixing? :) Done.
https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... File Source/core/html/track/TextTrackCueList.cpp (right): https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... Source/core/html/track/TextTrackCueList.cpp:123: bool TextTrackCueList::updateCueIndex(TextTrackCue* cue) On 2015/02/25 16:39:49, fs wrote: > On 2015/02/25 15:38:54, philipj_UTC7 wrote: > > On 2015/02/25 13:09:49, fs wrote: > > > On 2015/02/25 02:28:40, philipj_UTC7 wrote: > > > > Here or in another CL the return value can be dropped, it isn't used. > > > > > > Yes, it's a bit strange both that it wasn't used... I might as well drop it > in > > > this CL. I want to conditionalize calling this on whether the cue order > could > > > actually have changed at all (this method is O(n) after all). > > > > Thanks, I think that may make things a bit clearer, as it currently appears as > > if some effort is spent trying to return the right thing, but it sounds like > > avoiding O(n) is the real reason. > > Return-value dropped. "Avoiding" O(n) here can only be achieved by not calling > this method at all =) (all actions on m_list in this method - find, remove, > insert - are worst/average-case O(n)). OK, looks like I'm still confused. Specifically, why can't updateCueIndex() call add() like it did before? Is it because you want add() to eventually call updateCueIndex() directly or indirectly via invalidateCueIndexes()?
https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... File Source/core/html/track/TextTrackCueList.cpp (right): https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... Source/core/html/track/TextTrackCueList.cpp:123: bool TextTrackCueList::updateCueIndex(TextTrackCue* cue) On 2015/02/26 01:54:34, philipj_UTC7 wrote: > On 2015/02/25 16:39:49, fs wrote: > > On 2015/02/25 15:38:54, philipj_UTC7 wrote: > > > On 2015/02/25 13:09:49, fs wrote: > > > > On 2015/02/25 02:28:40, philipj_UTC7 wrote: > > > > > Here or in another CL the return value can be dropped, it isn't used. > > > > > > > > Yes, it's a bit strange both that it wasn't used... I might as well drop > it > > in > > > > this CL. I want to conditionalize calling this on whether the cue order > > could > > > > actually have changed at all (this method is O(n) after all). > > > > > > Thanks, I think that may make things a bit clearer, as it currently appears > as > > > if some effort is spent trying to return the right thing, but it sounds like > > > avoiding O(n) is the real reason. > > > > Return-value dropped. "Avoiding" O(n) here can only be achieved by not calling > > this method at all =) (all actions on m_list in this method - find, remove, > > insert - are worst/average-case O(n)). > > OK, looks like I'm still confused. Specifically, why can't updateCueIndex() call > add() like it did before? Is it because you want add() to eventually call > updateCueIndex() directly or indirectly via invalidateCueIndexes()? It's more because I want to be able to use oldIndex when invalidating cue indices, so this just "lifting" the carpet to show that someone forgot to clean there. So what I'll do here in a follow-up is essentially: invalidateCueIndex(std::min(oldIndex, newIndex)); but I suppose I could also do: m_list.remove(...); invalidateCueIndex(oldIndex); ... m_list.insert(...); invalidateCueIndex(newIndex); and hence just use remove() and add directly. So let me re-add add() here and adjust the FIXME a bit, and hopefully you'll end up less confused...
https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... File Source/core/html/track/TextTrackCueList.cpp (right): https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... Source/core/html/track/TextTrackCueList.cpp:123: bool TextTrackCueList::updateCueIndex(TextTrackCue* cue) On 2015/02/26 09:37:57, fs wrote: > On 2015/02/26 01:54:34, philipj_UTC7 wrote: > > On 2015/02/25 16:39:49, fs wrote: > > > On 2015/02/25 15:38:54, philipj_UTC7 wrote: > > > > On 2015/02/25 13:09:49, fs wrote: > > > > > On 2015/02/25 02:28:40, philipj_UTC7 wrote: > > > > > > Here or in another CL the return value can be dropped, it isn't used. > > > > > > > > > > Yes, it's a bit strange both that it wasn't used... I might as well drop > > it > > > in > > > > > this CL. I want to conditionalize calling this on whether the cue order > > > could > > > > > actually have changed at all (this method is O(n) after all). > > > > > > > > Thanks, I think that may make things a bit clearer, as it currently > appears > > as > > > > if some effort is spent trying to return the right thing, but it sounds > like > > > > avoiding O(n) is the real reason. > > > > > > Return-value dropped. "Avoiding" O(n) here can only be achieved by not > calling > > > this method at all =) (all actions on m_list in this method - find, remove, > > > insert - are worst/average-case O(n)). > > > > OK, looks like I'm still confused. Specifically, why can't updateCueIndex() > call > > add() like it did before? Is it because you want add() to eventually call > > updateCueIndex() directly or indirectly via invalidateCueIndexes()? > > It's more because I want to be able to use oldIndex when invalidating cue > indices, so this just "lifting" the carpet to show that someone forgot to clean > there. So what I'll do here in a follow-up is essentially: > > invalidateCueIndex(std::min(oldIndex, newIndex)); > > but I suppose I could also do: > > m_list.remove(...); > invalidateCueIndex(oldIndex); > ... > m_list.insert(...); > invalidateCueIndex(newIndex); > > and hence just use remove() and add directly. So let me re-add add() here and > adjust the FIXME a bit, and hopefully you'll end up less confused... Uploaded as PS3.
On 2015/02/26 09:37:57, fs wrote: > https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... > File Source/core/html/track/TextTrackCueList.cpp (right): > > https://codereview.chromium.org/955443002/diff/1/Source/core/html/track/TextT... > Source/core/html/track/TextTrackCueList.cpp:123: bool > TextTrackCueList::updateCueIndex(TextTrackCue* cue) > On 2015/02/26 01:54:34, philipj_UTC7 wrote: > > On 2015/02/25 16:39:49, fs wrote: > > > On 2015/02/25 15:38:54, philipj_UTC7 wrote: > > > > On 2015/02/25 13:09:49, fs wrote: > > > > > On 2015/02/25 02:28:40, philipj_UTC7 wrote: > > > > > > Here or in another CL the return value can be dropped, it isn't used. > > > > > > > > > > Yes, it's a bit strange both that it wasn't used... I might as well drop > > it > > > in > > > > > this CL. I want to conditionalize calling this on whether the cue order > > > could > > > > > actually have changed at all (this method is O(n) after all). > > > > > > > > Thanks, I think that may make things a bit clearer, as it currently > appears > > as > > > > if some effort is spent trying to return the right thing, but it sounds > like > > > > avoiding O(n) is the real reason. > > > > > > Return-value dropped. "Avoiding" O(n) here can only be achieved by not > calling > > > this method at all =) (all actions on m_list in this method - find, remove, > > > insert - are worst/average-case O(n)). > > > > OK, looks like I'm still confused. Specifically, why can't updateCueIndex() > call > > add() like it did before? Is it because you want add() to eventually call > > updateCueIndex() directly or indirectly via invalidateCueIndexes()? > > It's more because I want to be able to use oldIndex when invalidating cue > indices, so this just "lifting" the carpet to show that someone forgot to clean > there. So what I'll do here in a follow-up is essentially: > > invalidateCueIndex(std::min(oldIndex, newIndex)); > > but I suppose I could also do: > > m_list.remove(...); > invalidateCueIndex(oldIndex); > ... > m_list.insert(...); > invalidateCueIndex(newIndex); > > and hence just use remove() and add directly. So let me re-add add() here and > adjust the FIXME a bit, and hopefully you'll end up less confused... Ah, add() doesn't know about oldIndex. If both remove() and add() were to invalidate independently that'd be a bit of wasted work. PS3 LGTM, and hopefully this will all be sorted soon :)
The CQ bit was checked by fs@opera.com
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/955443002/40001
Message was sent while issue was closed.
Committed patchset #3 (id:40001) as https://src.chromium.org/viewvc/blink?view=rev&revision=190908 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
