Last Comment Bug 769791 - Optimize adding ranges to the end of mRanges in nsSelection
: Optimize adding ranges to the end of mRanges in nsSelection
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: Selection (show other bugs)
: Trunk
: All All
: -- normal (vote)
: mozilla17
Assigned To: Adam [:hobophobe]
:
Mentors:
Depends on:
Blocks: 251862
  Show dependency treegraph
 
Reported: 2012-06-29 13:30 PDT by Adam [:hobophobe]
Modified: 2012-08-04 11:17 PDT (History)
5 users (show)
ryanvm: in‑testsuite-
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
Implementation of the optimization (2.62 KB, patch)
2012-06-29 13:32 PDT, Adam [:hobophobe]
no flags Details | Diff | Splinter Review
Fix bracing of if/else (2.64 KB, patch)
2012-06-29 14:12 PDT, Adam [:hobophobe]
bugs: review+
Details | Diff | Splinter Review
Remove unreachable code. (2.96 KB, patch)
2012-07-03 16:29 PDT, Adam [:hobophobe]
no flags Details | Diff | Splinter Review
Explicitly check and set end of range (3.06 KB, patch)
2012-07-04 16:41 PDT, Adam [:hobophobe]
no flags Details | Diff | Splinter Review
Unbitrotted (3.09 KB, patch)
2012-07-23 14:02 PDT, Adam [:hobophobe]
no flags Details | Diff | Splinter Review
Reunbitrot (correctly, this time :) (3.10 KB, patch)
2012-07-23 14:30 PDT, Adam [:hobophobe]
bugs: review-
Details | Diff | Splinter Review
Move optimization to FindInsertionPoint (1.76 KB, patch)
2012-07-23 18:46 PDT, Adam [:hobophobe]
no flags Details | Diff | Splinter Review
Supersimplified version (2.16 KB, patch)
2012-07-24 13:50 PDT, Adam [:hobophobe]
bugs: review+
jaws: checkin+
Details | Diff | Splinter Review

Description Adam [:hobophobe] 2012-06-29 13:30:49 PDT
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.
Comment 1 Adam [:hobophobe] 2012-06-29 13:32:33 PDT
Created attachment 637993 [details] [diff] [review]
Implementation of the optimization
Comment 2 Olli Pettay [:smaug] (vacation Aug 25-28) 2012-06-29 13:43:36 PDT
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.
Comment 3 Adam [:hobophobe] 2012-06-29 14:12:34 PDT
Created attachment 638010 [details] [diff] [review]
Fix bracing of if/else
Comment 4 Olli Pettay [:smaug] (vacation Aug 25-28) 2012-07-03 14:45:44 PDT
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.
Comment 5 Adam [:hobophobe] 2012-07-03 16:29:00 PDT
Created attachment 638910 [details] [diff] [review]
Remove unreachable code.

Thanks, smaug!
Comment 6 Olli Pettay [:smaug] (vacation Aug 25-28) 2012-07-03 16:31:28 PDT
Have you pushed the patch to try?
Comment 7 Olli Pettay [:smaug] (vacation Aug 25-28) 2012-07-03 16:33:38 PDT
https://tbpl.mozilla.org/?tree=Try&rev=0442e3bf8b80
Comment 8 Ryan VanderMeulen [:RyanVM] 2012-07-03 19:12:34 PDT
https://hg.mozilla.org/integration/mozilla-inbound/rev/ea9410c65673
Comment 9 Phil Ringnalda (:philor) 2012-07-03 21:41:15 PDT
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.
Comment 10 Adam [:hobophobe] 2012-07-04 16:41:23 PDT
Created attachment 639198 [details] [diff] [review]
Explicitly check and set end of range

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.
Comment 11 Jared Wein [:jaws] (please needinfo? me) 2012-07-23 13:58:53 PDT
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.
Comment 12 Adam [:hobophobe] 2012-07-23 14:02:31 PDT
Created attachment 645059 [details] [diff] [review]
Unbitrotted
Comment 13 Adam [:hobophobe] 2012-07-23 14:30:41 PDT
Created attachment 645079 [details] [diff] [review]
Reunbitrot (correctly, this time :)
Comment 14 Jared Wein [:jaws] (please needinfo? me) 2012-07-23 15:43:33 PDT
Repushed to tryserver:
https://tbpl.mozilla.org/?tree=Try&rev=4cf718a62563
Comment 15 Olli Pettay [:smaug] (vacation Aug 25-28) 2012-07-23 16:33:50 PDT
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
Comment 16 Adam [:hobophobe] 2012-07-23 18:46:07 PDT
Created attachment 645167 [details] [diff] [review]
Move optimization to FindInsertionPoint

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.
Comment 17 Olli Pettay [:smaug] (vacation Aug 25-28) 2012-07-24 03:04:49 PDT
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);
  }
Comment 18 Adam [:hobophobe] 2012-07-24 13:50:59 PDT
Created attachment 645480 [details] [diff] [review]
Supersimplified version

That's so simple it almost hurts.  Great work!
Comment 19 Olli Pettay [:smaug] (vacation Aug 25-28) 2012-07-24 14:02:07 PDT
Comment on attachment 645480 [details] [diff] [review]
Supersimplified version

Pushed to try https://tbpl.mozilla.org/?tree=Try&rev=731b34130f80
Comment 20 Olli Pettay [:smaug] (vacation Aug 25-28) 2012-07-25 01:42:37 PDT
Comment on attachment 645480 [details] [diff] [review]
Supersimplified version

Looks like the patch passed the tests on try.
Comment 21 Adam [:hobophobe] 2012-08-03 14:19:28 PDT
The checkin? flag apparently didn't get noticed, so adding keywords.
Comment 22 Jared Wein [:jaws] (please needinfo? me) 2012-08-03 18:52:05 PDT
Pushed to inbound:
https://hg.mozilla.org/integration/mozilla-inbound/rev/0a329df2f15e
Comment 23 Ed Morley [:emorley] 2012-08-04 11:17:43 PDT
https://hg.mozilla.org/mozilla-central/rev/0a329df2f15e

Note You need to log in before you can comment on or make changes to this bug.