Closed
Bug 769791
Opened 12 years ago
Closed 12 years ago
Optimize adding ranges to the end of mRanges in nsSelection
Categories
(Core :: DOM: Selection, defect)
Core
DOM: Selection
Tracking
()
RESOLVED
FIXED
mozilla17
People
(Reporter: unusualtears, Assigned: unusualtears)
References
Details
Attachments
(1 file, 7 obsolete files)
2.16 KB,
patch
|
smaug
:
review+
jaws
:
checkin+
|
Details | Diff | Splinter Review |
For highlight, and possibly other consumers, intervals added to the ranges are either after all ranges or adjacent to the last range. I believe we should check if we're at/after the end, first. If we're touching the last range, let the regular adjustments occur. This is a tradeoff, where we will be doing an extra comparison for all other consumers that add ranges not at the end, but that cost is much smaller than doing two binary searches for adding a range to the end.
Attachment #637993 -
Flags: review?(bugs)
Comment 2•12 years ago
|
||
Comment on attachment 637993 [details] [diff] [review] Implementation of the optimization A coding style nit, if (expr) { stmt; } My review queue is a bit long now. I'll try to get to this next week, at latest.
Attachment #637993 -
Attachment is obsolete: true
Attachment #637993 -
Flags: review?(bugs)
Attachment #638010 -
Flags: review?(bugs)
Comment 4•12 years ago
|
||
Comment on attachment 638010 [details] [diff] [review] Fix bracing of if/else > if (beginsAfterIndex == (PRInt32) mRanges.Length()) > return; // optimization: all ranges are strictly before us So can this code ever run? Perhaps remove it.
Attachment #638010 -
Flags: review?(bugs) → review+
Thanks, smaug!
Attachment #638010 -
Attachment is obsolete: true
Keywords: checkin-needed
Comment 6•12 years ago
|
||
Have you pushed the patch to try?
Comment 7•12 years ago
|
||
https://tbpl.mozilla.org/?tree=Try&rev=0442e3bf8b80
Comment 9•12 years ago
|
||
Backed out in https://hg.mozilla.org/integration/mozilla-inbound/rev/6f871f3c25cf That order of operations was: 1. checkin-needed 2. "try?" 3. try 4. checkin 5. try results come through For future reference, 2. "try?" + removing checkin-neeeded or 2. "try?" 3. removing checkin-needed would be more likely to work out well.
Assignee | ||
Comment 10•12 years ago
|
||
Previous patch was checking if the interval was collapsed, and wrongly assuming that meant the end index should match the start index. This version explicitly checks if the end index should be at last or last + 1. This fixes the failing desktop test (toolkit/content/tests/chrome/test_textbox_dictionary.xul), which failed because the context menu was opened outside of the spellcheck range when it shouldn't have been. If the Android problems were due to this, it should fix those as well.
Attachment #638910 -
Attachment is obsolete: true
Comment 11•12 years ago
|
||
Slight bitrotting in the patch but nothing serious. I've pushed it to tryserver now: https://tbpl.mozilla.org/?tree=Try&rev=f4f40242c589 Adam, please request review so that we can do these two things simultaneously.
Assignee | ||
Comment 12•12 years ago
|
||
Attachment #639198 -
Attachment is obsolete: true
Attachment #645059 -
Flags: review?(bugs)
Assignee | ||
Comment 13•12 years ago
|
||
Attachment #645059 -
Attachment is obsolete: true
Attachment #645059 -
Flags: review?(bugs)
Attachment #645079 -
Flags: review?(bugs)
Comment 14•12 years ago
|
||
Repushed to tryserver: https://tbpl.mozilla.org/?tree=Try&rev=4cf718a62563
Target Milestone: mozilla16 → ---
Version: unspecified → Trunk
Comment 15•12 years ago
|
||
Comment on attachment 645079 [details] [diff] [review] Reunbitrot (correctly, this time :) This feels too complicated... but I haven't figured out yet how to make this better. Would it help if you just changed FindInsertionPoint to check first the last range in the array, and then do binary search on the rest of the ranges? And maybe move PRInt32 beginsAfterIndex; if (NS_FAILED(FindInsertionPoint(&mRanges, aBeginNode, aBeginOffset, &CompareToRangeEnd, &beginsAfterIndex))) { return NS_OK; } if (beginsAfterIndex == (PRInt32) mRanges.Length()) return NS_OK; // optimization: all ranges are strictly before us to happen before the endnode/offset check
Attachment #645079 -
Flags: review?(bugs) → review-
Assignee | ||
Comment 16•12 years ago
|
||
Thanks, smaug!
> Would it help if you just changed FindInsertionPoint to check first the
> last range in the array, and then do binary search on the rest of the ranges?
Much cleaner and just as fast.
Attachment #645079 -
Attachment is obsolete: true
Attachment #645167 -
Flags: review?(bugs)
Comment 17•12 years ago
|
||
Would this be simpler *aPoint = 0; PRInt32 beginSearch = 0; PRInt32 endSearch = aElementArray->Length(); // one beyond what to check if (endSearch) { PRInt32 center = endSearch - 1; // Check the last index first, then binary search. do { nsRange* range = (*aElementArray)[center].mRange; PRInt32 cmp; nsresult rv = aComparator(aPointNode, aPointOffset, range, &cmp); NS_ENSURE_SUCCESS(rv, rv); if (cmp < 0) { // point < cur endSearch = center; } else if (cmp > 0) { // point > cur beginSearch = center + 1; } else { // found match, done beginSearch = center; break; } center = (endSearch - beginSearch) / 2 + beginSearch; } while (endSearch - beginSearch > 0); }
Assignee | ||
Comment 18•12 years ago
|
||
That's so simple it almost hurts. Great work!
Attachment #645167 -
Attachment is obsolete: true
Attachment #645167 -
Flags: review?(bugs)
Attachment #645480 -
Flags: review?(bugs)
Summary: Optimize nsSelection::GetIndicesForInterval for adding ranges to the end → Optimize adding ranges to the end of mRanges in nsSelection
Comment 19•12 years ago
|
||
Comment on attachment 645480 [details] [diff] [review] Supersimplified version Pushed to try https://tbpl.mozilla.org/?tree=Try&rev=731b34130f80
Attachment #645480 -
Flags: review?(bugs) → review+
Updated•12 years ago
|
Component: Find Toolbar → Selection
Product: Toolkit → Core
Comment 20•12 years ago
|
||
Comment on attachment 645480 [details] [diff] [review] Supersimplified version Looks like the patch passed the tests on try.
Attachment #645480 -
Flags: checkin?
Assignee | ||
Comment 21•12 years ago
|
||
The checkin? flag apparently didn't get noticed, so adding keywords.
Keywords: checkin-needed
Comment 22•12 years ago
|
||
Pushed to inbound: https://hg.mozilla.org/integration/mozilla-inbound/rev/0a329df2f15e
Keywords: checkin-needed
Target Milestone: --- → mozilla17
Updated•12 years ago
|
Attachment #645480 -
Flags: checkin? → checkin+
Comment 23•12 years ago
|
||
https://hg.mozilla.org/mozilla-central/rev/0a329df2f15e
Status: ASSIGNED → RESOLVED
Closed: 12 years ago
Resolution: --- → FIXED
You need to log in
before you can comment on or make changes to this bug.
Description
•