|
|
DescriptionOptimize SpellChecker::GetSpellCheckMarkerUnderSelection()
Currently, this method does a linear scan over all spell check markers contained
in the text node(s) containing the selection. This takes about 0.553 ms on the
source for the "List of Australian treaties" Wikipedia page. This CL refactors
this method to instead use the newly-added
DocumentMarkerController::FirstMarkerIntersectingRange() method, which is more
efficient as it uses binary search. With this change, we now spend about
~0.02 ms in this method doing the same test.
BUG=736181
Review-Url: https://codereview.chromium.org/2947093003
Cr-Commit-Position: refs/heads/master@{#488577}
Committed: https://chromium.googlesource.com/chromium/src/+/eef04de483168c40a8eadfc840fc8ddf4432f55a
Patch Set 1 #
Total comments: 1
Patch Set 2 : Use const reference for node_marker_pairs #
Total comments: 1
Patch Set 3 : Remove GetSpellCheckMarkerTouchingSelection() #
Total comments: 1
Patch Set 4 : Rebase #Patch Set 5 : Keep GetSpellCheckMarkerUnderSelection() #
Total comments: 1
Patch Set 6 : Rebase #
Total comments: 1
Patch Set 7 : Rebase #Patch Set 8 : Rebase, cite bug #Patch Set 9 : Rebase #Patch Set 10 : Rebase #
Total comments: 4
Patch Set 11 : FirstEphemeralRangeOf(), return {} #Messages
Total messages: 61 (40 generated)
rlanday@chromium.org changed reviewers: + xiaochengh@chromium.org, yosin@chromium.org
https://codereview.chromium.org/2947093003/diff/1/third_party/WebKit/Source/c... File third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp (right): https://codereview.chromium.org/2947093003/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp:878: ExpandSelectionRangeIfNecessary(selection); I still need to optimize ExpandSelectionRangeIfNecessary; I will do so in a follow-up CL
https://codereview.chromium.org/2947093003/diff/20001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp (right): https://codereview.chromium.org/2947093003/diff/20001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp:878: ExpandSelectionRangeIfNecessary(selection); I think I'm probably going to get rid of this and only do this check in TextSuggestionController (once in HandlePotentialMisspelledWordTap() and once in the replace method I'm going to implement instead of calling the one in SpellChecker)
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...
Description was changed from ========== Refactor SpellChecker::GetSpellCheckMarkerTouchingSelection() Currently, this method does a linear scan over all spell check markers contained in the text node(s) containing the selection. This takes about 0.553 ms on the source for the "List of Australian treaties" Wikipedia page. This CL refactors this method to use the newly-added DocumentMarkerController::MarkersIntersectingRange() method, which is more efficient as it uses binary search. With this change, we now spend about 0.023 ms in this method doing the same test. BUG=715365 ========== to ========== Refactor SpellChecker::ReplaceMisspelling() Currently, this method uses a helper method called GetSpellCheckMarkerTouchingSelection() that does a linear scan over all spell check markers contained in the text node(s) containing the selection. This takes about 0.553 ms on the source for the "List of Australian treaties" Wikipedia page. This CL refactors this method to instead use the newly-added DocumentMarkerController::MarkersIntersectingRange() method, which is more efficient as it uses binary search. With this change, we now spend about 0.023 ms in this method doing the same test. Additionally, this CL removes the ExpandSelectionRangeIfNecessary() helper function I added to support the Android spellcheck menu, which we show even in the case where a user taps right at the start/end of a word (we don't show spell check options in the context menu on other platforms unless the user clicks in the interior of the word). Now that we have DMC::MarkersIntersectingRange(), I can put this functionality somewhere else instead without having to re-implement a bunch of logic. BUG=715365 ==========
Description was changed from ========== Refactor SpellChecker::ReplaceMisspelling() Currently, this method uses a helper method called GetSpellCheckMarkerTouchingSelection() that does a linear scan over all spell check markers contained in the text node(s) containing the selection. This takes about 0.553 ms on the source for the "List of Australian treaties" Wikipedia page. This CL refactors this method to instead use the newly-added DocumentMarkerController::MarkersIntersectingRange() method, which is more efficient as it uses binary search. With this change, we now spend about 0.023 ms in this method doing the same test. Additionally, this CL removes the ExpandSelectionRangeIfNecessary() helper function I added to support the Android spellcheck menu, which we show even in the case where a user taps right at the start/end of a word (we don't show spell check options in the context menu on other platforms unless the user clicks in the interior of the word). Now that we have DMC::MarkersIntersectingRange(), I can put this functionality somewhere else instead without having to re-implement a bunch of logic. BUG=715365 ========== to ========== Refactor SpellChecker::ReplaceMisspelledRange() Currently, this method uses a helper method called GetSpellCheckMarkerTouchingSelection() that does a linear scan over all spell check markers contained in the text node(s) containing the selection. This takes about 0.553 ms on the source for the "List of Australian treaties" Wikipedia page. This CL refactors this method to instead use the newly-added DocumentMarkerController::MarkersIntersectingRange() method, which is more efficient as it uses binary search. With this change, we now spend about 0.023 ms in this method doing the same test. Additionally, this CL removes the ExpandSelectionRangeIfNecessary() helper function I added to support the Android spellcheck menu, which we show even in the case where a user taps right at the start/end of a word (we don't show spell check options in the context menu on other platforms unless the user clicks in the interior of the word). Now that we have DMC::MarkersIntersectingRange(), I can put this functionality somewhere else instead without having to re-implement a bunch of logic. BUG=715365 ==========
Ok, I've removed GetSpellCheckMarkerTouchingSelection() and ExpandSelectionRangeIfNecessary() to simplify the spell check code
https://codereview.chromium.org/2947093003/diff/40001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp (right): https://codereview.chromium.org/2947093003/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp:852: SelectionInDOMTree::Builder() I just tried copy-pasting something from here and it seems this code review tool is skipping over lines 918 and 919...bizarre...
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...)
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: win_chromium_compile_dbg_ng on master.tryserver.chromium.win (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_comp...)
I'm in doubt about current implementation[1]. It seems complete fix takes lots of changes, so I propose short time fix, using same algorithm between SelectMisspellingAsync() and SpellCheck::ReplaceMisspelledRange(), instead of this refactor. [1] http://crbug.com/736181 ⚐ SpellCheck::ReplaceMisspelledRange() should be robust
On 2017/06/23 at 03:50:08, yosin wrote: > I'm in doubt about current implementation[1]. > > It seems complete fix takes lots of changes, so I propose short time fix, > using same algorithm between SelectMisspellingAsync() and SpellCheck::ReplaceMisspelledRange(), > instead of this refactor. > > > [1] http://crbug.com/736181 ⚐ SpellCheck::ReplaceMisspelledRange() should be robust The implementation in SelectMisspellingAsync() has the same inefficiency problem (it copies the entire list of spell check markers using DMC::MarkersFor()) and I think it should be refactored the same way. You don't like the implementation I have here?
On 2017/06/23 at 04:43:46, rlanday wrote: > On 2017/06/23 at 03:50:08, yosin wrote: > > I'm in doubt about current implementation[1]. > > > > It seems complete fix takes lots of changes, so I propose short time fix, > > using same algorithm between SelectMisspellingAsync() and SpellCheck::ReplaceMisspelledRange(), > > instead of this refactor. > > > > > > [1] http://crbug.com/736181 ⚐ SpellCheck::ReplaceMisspelledRange() should be robust > > The implementation in SelectMisspellingAsync() has the same inefficiency problem (it copies the entire list of spell check markers using DMC::MarkersFor()) and I think it should be refactored the same way. You don't like the implementation I have here? I would like to use one function to get a misspelled marker for selection for both SelectMisspellingAsync() and ReplaceMisspelledRange(). According to SelectMisspellingAsync(), we only need to have one marker instead of markers. ReplaceMisppeledRange() should work only for one marker instead of markers.
On 2017/06/23 at 05:53:08, yosin wrote: > I would like to use one function to get a misspelled marker for selection for both SelectMisspellingAsync() and ReplaceMisspelledRange(). > According to SelectMisspellingAsync(), we only need to have one marker instead of markers. ReplaceMisppeledRange() should work only for > one marker instead of markers. Do you not think using DMC::MarkersIntersectingRange() and taking the first marker is an acceptable solution? The current implementations, which do not use that method, are less efficient.
On 2017/06/23 at 06:21:34, rlanday wrote: > On 2017/06/23 at 05:53:08, yosin wrote: > > I would like to use one function to get a misspelled marker for selection for both SelectMisspellingAsync() and ReplaceMisspelledRange(). > > According to SelectMisspellingAsync(), we only need to have one marker instead of markers. ReplaceMisppeledRange() should work only for > > one marker instead of markers. > > Do you not think using DMC::MarkersIntersectingRange() and taking the first marker is an acceptable solution? The current implementations, which do not use that method, are less efficient. No. In this case we only need one marker, DMC::MarkerIntersectingRange(Text*, start, end) is enough according to SelectMisspellingAsync(). ReplaceMissspelledRange() can be applied this restriction, selection is on (Text*, start, end) == we can simplify ReplaceMissspelledRange().
On 2017/06/23 at 06:35:40, yosin wrote: > On 2017/06/23 at 06:21:34, rlanday wrote: > > On 2017/06/23 at 05:53:08, yosin wrote: > > > I would like to use one function to get a misspelled marker for selection for both SelectMisspellingAsync() and ReplaceMisspelledRange(). > > > According to SelectMisspellingAsync(), we only need to have one marker instead of markers. ReplaceMisppeledRange() should work only for > > > one marker instead of markers. > > > > Do you not think using DMC::MarkersIntersectingRange() and taking the first marker is an acceptable solution? The current implementations, which do not use that method, are less efficient. > > No. In this case we only need one marker, DMC::MarkerIntersectingRange(Text*, start, end) is enough according to SelectMisspellingAsync(). > ReplaceMissspelledRange() can be applied this restriction, selection is on (Text*, start, end) == we can simplify ReplaceMissspelledRange(). Ok. I will put up another CL to rename GetSpellCheckMarkerTouchingSelection() to GetSpellCheckMarkerUnderSelection() (and remove the behavior where it finds markers merely touching the selection), and then update this CL to do the refactor you're requesting.
Description was changed from ========== Refactor SpellChecker::ReplaceMisspelledRange() Currently, this method uses a helper method called GetSpellCheckMarkerTouchingSelection() that does a linear scan over all spell check markers contained in the text node(s) containing the selection. This takes about 0.553 ms on the source for the "List of Australian treaties" Wikipedia page. This CL refactors this method to instead use the newly-added DocumentMarkerController::MarkersIntersectingRange() method, which is more efficient as it uses binary search. With this change, we now spend about 0.023 ms in this method doing the same test. Additionally, this CL removes the ExpandSelectionRangeIfNecessary() helper function I added to support the Android spellcheck menu, which we show even in the case where a user taps right at the start/end of a word (we don't show spell check options in the context menu on other platforms unless the user clicks in the interior of the word). Now that we have DMC::MarkersIntersectingRange(), I can put this functionality somewhere else instead without having to re-implement a bunch of logic. BUG=715365 ========== to ========== Optimize SpellChecker::GetSpellCheckMarkerUnderSelection() Currently, this method uses a helper method called GetSpellCheckMarkerTouchingSelection() that does a linear scan over all spell check markers contained in the text node(s) containing the selection. This takes about 0.553 ms on the source for the "List of Australian treaties" Wikipedia page. This CL refactors this method to instead use the newly-added DocumentMarkerController::MarkersIntersectingRange() method, which is more efficient as it uses binary search. With this change, we now spend about 0.023 ms in this method doing the same test. Additionally, this CL removes the ExpandSelectionRangeIfNecessary() helper function I added to support the Android spellcheck menu, which we show even in the case where a user taps right at the start/end of a word (we don't show spell check options in the context menu on other platforms unless the user clicks in the interior of the word). Now that we have DMC::MarkersIntersectingRange(), I can put this functionality somewhere else instead without having to re-implement a bunch of logic. BUG=715365 ==========
Description was changed from ========== Optimize SpellChecker::GetSpellCheckMarkerUnderSelection() Currently, this method uses a helper method called GetSpellCheckMarkerTouchingSelection() that does a linear scan over all spell check markers contained in the text node(s) containing the selection. This takes about 0.553 ms on the source for the "List of Australian treaties" Wikipedia page. This CL refactors this method to instead use the newly-added DocumentMarkerController::MarkersIntersectingRange() method, which is more efficient as it uses binary search. With this change, we now spend about 0.023 ms in this method doing the same test. Additionally, this CL removes the ExpandSelectionRangeIfNecessary() helper function I added to support the Android spellcheck menu, which we show even in the case where a user taps right at the start/end of a word (we don't show spell check options in the context menu on other platforms unless the user clicks in the interior of the word). Now that we have DMC::MarkersIntersectingRange(), I can put this functionality somewhere else instead without having to re-implement a bunch of logic. BUG=715365 ========== to ========== Optimize SpellChecker::GetSpellCheckMarkerUnderSelection() Currently, this method does a linear scan over all spell check markers contained in the text node(s) containing the selection. This takes about 0.553 ms on the source for the "List of Australian treaties" Wikipedia page. This CL refactors this method to instead use the newly-added DocumentMarkerController::MarkerIntersectingRange() method, which is more efficient as it uses binary search. With this change, we now spend about 0.023 ms in this method doing the same test. BUG=736181 ==========
Ok, now I'm just optimizing GetSpellCheckMarkerUnderSelection(). I'm going to update ContextMenuClient::SelectMisspellingAsync() to use this method in a follow-up CL.
https://codereview.chromium.org/2947093003/diff/80001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp (right): https://codereview.chromium.org/2947093003/diff/80001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp:842: Node* const selection_start_container = This seems to involve a bunch of extra code vs. just giving DocumentMarkerController::MarkersIntersectingRange() the selection range and having that deal with it. I'm going to need to duplicate all this code in TextSuggestionController::HandlePotentialTextSuggestionTap() if we do it this way :(
On 2017/06/23 at 23:12:15, rlanday wrote: > https://codereview.chromium.org/2947093003/diff/80001/third_party/WebKit/Sour... > File third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp (right): > > https://codereview.chromium.org/2947093003/diff/80001/third_party/WebKit/Sour... > third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp:842: Node* const selection_start_container = > This seems to involve a bunch of extra code vs. just giving DocumentMarkerController::MarkersIntersectingRange() the selection range and having that deal with it. I'm going to need to duplicate all this code in TextSuggestionController::HandlePotentialTextSuggestionTap() if we do it this way :( Actually, in that method, we have to potentially check multiple nodes anyway (and therefore are forced to use MarkersIntersectingRange()), so I guess this is a moot point
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...
https://codereview.chromium.org/2947093003/diff/100001/third_party/WebKit/Sou... File third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp (right): https://codereview.chromium.org/2947093003/diff/100001/third_party/WebKit/Sou... third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp:847: // We don't currently support the case where a misspelling spans multiple Please cite crbug.com/720065 here.
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
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: ios-simulator on master.tryserver.chromium.mac (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-simulator/bui...)
The CQ bit was checked by rlanday@chromium.org to run a CQ dry run
On 2017/06/26 at 22:48:22, xiaochengh wrote: > https://codereview.chromium.org/2947093003/diff/100001/third_party/WebKit/Sou... > File third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp (right): > > https://codereview.chromium.org/2947093003/diff/100001/third_party/WebKit/Sou... > third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp:847: // We don't currently support the case where a misspelling spans multiple > Please cite crbug.com/720065 here. Updated
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: ios-simulator on master.tryserver.chromium.mac (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-simulator/bui...)
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: This issue passed the CQ dry run.
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: mac_chromium_rel_ng on master.tryserver.chromium.mac (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_chromium_rel_...)
https://codereview.chromium.org/2947093003/diff/180001/third_party/WebKit/Sou... File third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp (right): https://codereview.chromium.org/2947093003/diff/180001/third_party/WebKit/Sou... third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp:840: selection.ToNormalizedEphemeralRange(); Could you use |FirstEphemeralRangeOf(selection)| as original? Since VS::ToNormalizedRange() does lots of thing and we would like to deprecate it. https://codereview.chromium.org/2947093003/diff/180001/third_party/WebKit/Sou... third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp:850: return Optional<std::pair<Node*, SpellCheckMarker*>>(); Could you try to write |return {}| to make code simpler?
https://codereview.chromium.org/2947093003/diff/180001/third_party/WebKit/Sou... File third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp (right): https://codereview.chromium.org/2947093003/diff/180001/third_party/WebKit/Sou... third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp:836: return Optional<std::pair<Node*, SpellCheckMarker*>>(); Use |return WTF::nullopt| https://codereview.chromium.org/2947093003/diff/180001/third_party/WebKit/Sou... third_party/WebKit/Source/core/editing/spellcheck/SpellChecker.cpp:850: return Optional<std::pair<Node*, SpellCheckMarker*>>(); On 2017/07/20 at 01:12:11, yosin_UTC9 wrote: > Could you try to write |return {}| to make code simpler? I prefer WTF::nullopt
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...
Updated (note: I'm currently using {} and not WTF::nullopt)
lgtm Please update description: >DocumentMarkerController::MarkerIntersectingRange() method, which is more >efficient as it uses binary search. With this change, we now spend about >0.023 ms in this method doing the same test. Since this patch, we use DocumentMarkerController::FirstMarkerIntersectingRange()
Description was changed from ========== Optimize SpellChecker::GetSpellCheckMarkerUnderSelection() Currently, this method does a linear scan over all spell check markers contained in the text node(s) containing the selection. This takes about 0.553 ms on the source for the "List of Australian treaties" Wikipedia page. This CL refactors this method to instead use the newly-added DocumentMarkerController::MarkerIntersectingRange() method, which is more efficient as it uses binary search. With this change, we now spend about 0.023 ms in this method doing the same test. BUG=736181 ========== to ========== Optimize SpellChecker::GetSpellCheckMarkerUnderSelection() Currently, this method does a linear scan over all spell check markers contained in the text node(s) containing the selection. This takes about 0.553 ms on the source for the "List of Australian treaties" Wikipedia page. This CL refactors this method to instead use the newly-added DocumentMarkerController::FirstMarkerIntersectingRange() method, which is more efficient as it uses binary search. With this change, we now spend about ~0.02 ms in this method doing the same test. BUG=736181 ==========
The CQ bit was unchecked by rlanday@chromium.org
The CQ bit was checked by rlanday@chromium.org
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": 200001, "attempt_start_ts": 1500602655523950, "parent_rev": "5e4f0f6afdf869bdca0d648ff2152a977b2c8751", "commit_rev": "eef04de483168c40a8eadfc840fc8ddf4432f55a"}
Message was sent while issue was closed.
Description was changed from ========== Optimize SpellChecker::GetSpellCheckMarkerUnderSelection() Currently, this method does a linear scan over all spell check markers contained in the text node(s) containing the selection. This takes about 0.553 ms on the source for the "List of Australian treaties" Wikipedia page. This CL refactors this method to instead use the newly-added DocumentMarkerController::FirstMarkerIntersectingRange() method, which is more efficient as it uses binary search. With this change, we now spend about ~0.02 ms in this method doing the same test. BUG=736181 ========== to ========== Optimize SpellChecker::GetSpellCheckMarkerUnderSelection() Currently, this method does a linear scan over all spell check markers contained in the text node(s) containing the selection. This takes about 0.553 ms on the source for the "List of Australian treaties" Wikipedia page. This CL refactors this method to instead use the newly-added DocumentMarkerController::FirstMarkerIntersectingRange() method, which is more efficient as it uses binary search. With this change, we now spend about ~0.02 ms in this method doing the same test. BUG=736181 Review-Url: https://codereview.chromium.org/2947093003 Cr-Commit-Position: refs/heads/master@{#488577} Committed: https://chromium.googlesource.com/chromium/src/+/eef04de483168c40a8eadfc840fc... ==========
Message was sent while issue was closed.
Committed patchset #11 (id:200001) as https://chromium.googlesource.com/chromium/src/+/eef04de483168c40a8eadfc840fc... |