Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2917963003:
Refactor DocumentMarkerListEditor::ShiftMarkersContent{Ind,D}ependent (Closed)
DescriptionRefactor DocumentMarkerListEditor::ShiftMarkersContent{Ind,D}ependent
The current implementations of
DocumentMarkerListEditor::ShiftMarkersContentDependent() and
ShiftMarkersContentIndependent() can potentially take quadratic time in the
number of markers if we have to remove them all, since we call Vector::erase()
on them one-by-one. We can avoid this by creating a new MarkerList and swapping
afterward. The best-case runtime should still be linear for both the old and new
implementations.
BUG=707867
Review-Url: https://codereview.chromium.org/2917963003
Cr-Commit-Position: refs/heads/master@{#477055}
Committed: https://chromium.googlesource.com/chromium/src/+/6ee691bbd589760fec30ee27dcb408a70feb66d3
Patch Set 1 #
Total comments: 5
Patch Set 2 : Use std::move() #Patch Set 3 : Rewrite to be more efficient #
Total comments: 4
Patch Set 4 : Fix nits #Messages
Total messages: 25 (15 generated)
Description was changed from
==========
Refator DocumentMarkerListEditor::ShiftMarkersContent{Ind,D}epdent
The current implementations of
DocumentMarkerListEditor::ShiftMarkersContentDependent() and
ShiftMarkersContentIndependent() can potentially take quadratic time in the
number of markers if we have to remove them all, since we call Vector::erase()
on them one-by-one. We can avoid this by creating a new MarkerList and swapping
afterward. The best-case runtime should still be linear for both the old and new
implementations.
BUG=707867
==========
to
==========
Refactor DocumentMarkerListEditor::ShiftMarkersContent{Ind,D}epdent
The current implementations of
DocumentMarkerListEditor::ShiftMarkersContentDependent() and
ShiftMarkersContentIndependent() can potentially take quadratic time in the
number of markers if we have to remove them all, since we call Vector::erase()
on them one-by-one. We can avoid this by creating a new MarkerList and swapping
afterward. The best-case runtime should still be linear for both the old and new
implementations.
BUG=707867
==========
rlanday@chromium.org changed reviewers: + xiaochengh@chromium.org, yosin@chromium.org
https://codereview.chromium.org/2917963003/diff/1/third_party/WebKit/Source/c... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp (right): https://codereview.chromium.org/2917963003/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp:112: std::swap(*list, new_list); nit: |*list = std::move(new_list);| Let's do C++11-ish, we don't need to make |new_list| to have contents of |list|. https://codereview.chromium.org/2917963003/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp:113: return did_shift_marker; Could you get rid of |did_shift_marker|? Once we have |new_lsit|, we could write: if (list->size() == new_list.size()) return false; *list = std::move(new_list); return true; https://codereview.chromium.org/2917963003/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp:143: std::swap(*list, new_list); nit: |*list = std::move(new_list);| Let's do C++11-ish, we don't need to make |new_list| to have contents of |list|. https://codereview.chromium.org/2917963003/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp:144: return did_shift_marker; Could you get rid of |did_shift_marker|? Once we have |new_lsit|, we could write: if (list->size() == new_list.size()) return false; *list = std::move(new_list); return true;
The CQ bit was checked by rlanday@chromium.org to run a CQ dry run
Updated to use std::move()
https://codereview.chromium.org/2917963003/diff/1/third_party/WebKit/Source/c... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp (right): https://codereview.chromium.org/2917963003/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp:113: return did_shift_marker; On 2017/06/02 at 04:28:56, yosin_UTC9 wrote: > Could you get rid of |did_shift_marker|? > > Once we have |new_lsit|, we could write: > > if (list->size() == new_list.size()) > return false; > *list = std::move(new_list); > return true; I don't think this is quite right because we want to return true if a marker is shifted (without being removed), but your code returns false.
Dry run: CQ is trying da patch. Follow status at: https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
I think we should not create a new list, which adds burden to GC. It's better to find the first and last marker to be removed, and then remove them all at once after the main loop.
On 2017/06/02 at 17:53:43, xiaochengh wrote: > I think we should not create a new list, which adds burden to GC. > > It's better to find the first and last marker to be removed, and then remove them all at once after the main loop. Good call. I've also added a binary search to find the first marker that might need updating to try to get some extra efficiency. We'll need a separate version of this marker for suggestion markers, which can overlap and will be stored non-sorted, but I think that's fine.
The CQ bit was checked by rlanday@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at: https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: linux_android_rel_ng on master.tryserver.chromium.android (JOB_FAILED, https://build.chromium.org/p/tryserver.chromium.android/builders/linux_androi...)
lgtm
lgtm w/ nits https://codereview.chromium.org/2917963003/diff/40001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp (right): https://codereview.chromium.org/2917963003/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp:84: MarkerList::iterator shift_range_begin = nit: s/MarkerList::iterator/const MarkerList::iterator&/ https://codereview.chromium.org/2917963003/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp:98: erase_range_end = it + 1; nit: s/it + 1/std::next(it)/ https://codereview.chromium.org/2917963003/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp:125: MarkerList::iterator shift_range_begin = nit: s/MarkerList::iterator/const MarkerList::iterator&/ https://codereview.chromium.org/2917963003/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.cpp:142: erase_range_end = it + 1; nit: s/it + 1/std::next(it);
Description was changed from
==========
Refactor DocumentMarkerListEditor::ShiftMarkersContent{Ind,D}epdent
The current implementations of
DocumentMarkerListEditor::ShiftMarkersContentDependent() and
ShiftMarkersContentIndependent() can potentially take quadratic time in the
number of markers if we have to remove them all, since we call Vector::erase()
on them one-by-one. We can avoid this by creating a new MarkerList and swapping
afterward. The best-case runtime should still be linear for both the old and new
implementations.
BUG=707867
==========
to
==========
Refactor DocumentMarkerListEditor::ShiftMarkersContent{Ind,D}ependent
The current implementations of
DocumentMarkerListEditor::ShiftMarkersContentDependent() and
ShiftMarkersContentIndependent() can potentially take quadratic time in the
number of markers if we have to remove them all, since we call Vector::erase()
on them one-by-one. We can avoid this by creating a new MarkerList and swapping
afterward. The best-case runtime should still be linear for both the old and new
implementations.
BUG=707867
==========
The CQ bit was checked by rlanday@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from yosin@chromium.org, xiaochengh@chromium.org Link to the patchset: https://codereview.chromium.org/2917963003/#ps60001 (title: "Fix nits")
CQ is trying da patch. Follow status at: https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
CQ is committing da patch.
Bot data: {"patchset_id": 60001, "attempt_start_ts": 1496682137008040,
"parent_rev": "9e0a18b3e858c685893f1b9c2c59646fa555f187", "commit_rev":
"6ee691bbd589760fec30ee27dcb408a70feb66d3"}
Message was sent while issue was closed.
Description was changed from
==========
Refactor DocumentMarkerListEditor::ShiftMarkersContent{Ind,D}ependent
The current implementations of
DocumentMarkerListEditor::ShiftMarkersContentDependent() and
ShiftMarkersContentIndependent() can potentially take quadratic time in the
number of markers if we have to remove them all, since we call Vector::erase()
on them one-by-one. We can avoid this by creating a new MarkerList and swapping
afterward. The best-case runtime should still be linear for both the old and new
implementations.
BUG=707867
==========
to
==========
Refactor DocumentMarkerListEditor::ShiftMarkersContent{Ind,D}ependent
The current implementations of
DocumentMarkerListEditor::ShiftMarkersContentDependent() and
ShiftMarkersContentIndependent() can potentially take quadratic time in the
number of markers if we have to remove them all, since we call Vector::erase()
on them one-by-one. We can avoid this by creating a new MarkerList and swapping
afterward. The best-case runtime should still be linear for both the old and new
implementations.
BUG=707867
Review-Url: https://codereview.chromium.org/2917963003
Cr-Commit-Position: refs/heads/master@{#477055}
Committed:
https://chromium.googlesource.com/chromium/src/+/6ee691bbd589760fec30ee27dcb4...
==========
Message was sent while issue was closed.
Committed patchset #4 (id:60001) as https://chromium.googlesource.com/chromium/src/+/6ee691bbd589760fec30ee27dcb4... |
