344895 - Spellchecker hangs Firefox when dealing with a largish textarea

Status: RESOLVED FIXED

(Core :: Spelling checker, defect)

Description

[Boris Zbarsky [:bzbarsky]]

STEPS TO REPRODUCE:

1)  Start Firefox
2)  Load https://bugzilla.mozilla.org/attachment.cgi?id=227870&action=edit
3)  Click "Edit Attachment As Comment"

EXPECTED RESULT: 2-3 seconds later, an editable attachment

ACTUAL RESULTS: Give up after 2-3 minutes and kill the browser.  Run the profiler the next time around.  Discover that:

Total hit count: 261221
  261221 under mozInlineSpellChecker::SpellCheckRange(nsIDOMRange*)

for the period while profiling.  Most of the time is spent calling IndexOf() in range code.  I'll attach the whole profile.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Attachment: Profile

Comment 2

[Ria Klaassen (not reading all bugmail)]

Isn't this the same as bug 340326?

Comment 3

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

It just so happens that i've started cleaning up our range code in a major way which should have a large impact on performance here. Unfortunately that's not something that we can fix for FF2 as it will depend on nsINode existing.

Maybe what we should do for the FF2 branch is to just reimplement nsRange::IsIncreasing to be saner and less wasteful.

Comment 4

[Boris Zbarsky [:bzbarsky]]

> Isn't this the same as bug 340326?

No idea.  I can't even get to the point of typing -- the initial spellchecker init completely hangs.  Since bug 340326 has no data on _what_ is slow, it's impossible to tell whether this is the same bug.

sicking, improving range perf won't help that much here, I suspect.  Looking at the spellcheck code, the algorithm looks like it's about the following (in DoSpellCheck):

for each word {
  Check whether the start node/offset is in the spell-check selection.
  If not, check whether the end node/offset is in the spell-check selection.
  Remove the relevant range, if any, from the spellcheck selection.
  Spell-check the word.
  If it's mis-spelled, add the range that contains that word to the spell-check 
    selection.
}

The problem here is that this is fundamentally O(M*N) where M is the number of mis-spelled words and N is the total number of words (assuming uniform distribution of mis-spelled words), since there will be one range in the selection for each mis-spelled word and we'll check every single word against it.

In general, this may be the best we can do unless we start storing the range array sorted in the selection or something.  But for this specific case (spellchecker init), we should be able to do a lot better.  For example, if I follow this code correctly we don't even need to do all those IsPointInSelection checks, since we know it can't be -- we had never spell-checked that part yet.

Comment 5

[Boris Zbarsky [:bzbarsky]]

Oh, in case anyone is interested my selection had about 200 ranges before I got bored with the whole thing and killed the debugger.  ;)

Comment 6

[Boris Zbarsky [:bzbarsky]]

So this does in fact look like the same basic problem as bug 340326.  Leaving separate for now in case we want to adopt different solutions for spellchecker init vs actual spellcheck-as-you-type.

Comment 7

[Ria Klaassen (not reading all bugmail)]

*** Bug 344839 has been marked as a duplicate of this bug. ***

Comment 8

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

bz: out of the 261197 Hits in mozInlineSpellChecker::DoSpellCheck 258613 Hits are in mozInlineSpellChecker::IsPointInSelection. Of those 162491 Hits are in nsGenericElement::IndexOf which are almost all compleatly unneccesary calls.

So just eliminating those should remove some 60% of all cycles (or just under given that not all indexOf calls are useless)

Comment 9

[Boris Zbarsky [:bzbarsky]]

Hey, if we can make it better, I'm all for it!

Comment 10

[Brett Wilson]

Sicking: I'm not sure what you're talking about. Can you make a patch that does this, or provide me detailed instructions? Does anybody else want to volunteer?

I've almost completed a patch that makes some things much faster by reducing the calls to IsPointInSelection. It makes the example in comment 1 run in about 5 seconds on my computer. But in many cases it is still needed, and the benefit will be noticeable.

Comment 11

[Brett Wilson]

Attachment: Init & Paste optimizations

This patch improves the time taken to spellcheck text in the window when it is initially loaded, and when pasting a lot of text. The example in comment 1 now takes 5 seconds on my computer (as opposed to several minutes--I gave up waiting for it so I don't know for sure).

Comment 12

[Brett Wilson]

*** Bug 340326 has been marked as a duplicate of this bug. ***

Comment 13

[Boris Zbarsky [:bzbarsky]]

Brett, is that patch against branch?  I can't seem to apply it on trunk...

I'd be happy to profile with a trunk patch again, if desired.

Comment 14

[Brett Wilson]

You need to be in extensions/spellcheck/src to apply it, sorry.

This was a branch patch, but the code for trunk/branch should be the same.

Comment 15

[Boris Zbarsky [:bzbarsky]]

I was in the right dir.   I get:

Hunk #2 FAILED at 261.
Hunk #3 FAILED at 370.
Hunk #4 FAILED at 406.

Comment 16

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: Patch to speed up nsRange::IsIncreasing

This should speed up the range code significantly. On trunk we can clean this up further, but I'll file a separate bug for that. For now lets land this on trunk and branch.

Comment 17

[Brett Wilson]

Attachment: Trunk patch for init & paste

Apparently the trunk is just slightly different. This is a trunk patch, but I didn't compile it yet so there may be a typo (I just started a new build since mine was messed up).

Comment 18

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Brett, it'd be great if you could check if my patch makes a difference once your patch is applied, or if we don't spend enough time in the range code for it to matter.

Comment 19

[Brett Wilson]

Jonas: I'm sure it will. My code only affects pasting and initialization. We call this code when you type as well. The faster we can make that the better.

Comment 20

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 229585 [details] [diff] [review]
Patch to speed up nsRange::IsIncreasing

Looks ok, but doesn't help "actual" perf on the testcase (at least it still runs for over 2 mins on my machine then I kill it).

Comment 21

[Brett Wilson]

I noticed some other important problems perhaps one of you might know more about:

1. Turning off spellchecking is very slow. The time is spent in nsISelection::RemoveAllRanges. I didn't profile it, but it looks like mose of the code is the pretty nasty function nsTypedSelection::selectFrames, which gets called for every range in the selection.

2. Scrolling seems slower when misspellings are highlighted. If you go to a large textarea as in comment 1, scrolling in the range of spellchecked items with the scroll thumb is kind of jerky. Scrolling in the later part where there are no misspellings marked (we hit the maximum) is much smoother. Turning off spellchecking makes it all smooth. I originally thought it was always slow when any selection was visible, but now I don't see that effect any more.

Comment 22

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Comment on attachment 229585 [details] [diff] [review]
Patch to speed up nsRange::IsIncreasing

Checked in this to trunk. I think we should take it on branch too given the performance problems.

Comment 23

[Boris Zbarsky [:bzbarsky]]

For what it's worth, with Brett's patch applied I get about the same performance with and without sicking's patch (to within measurement fluctuation -- both numbers seem to be about 13.7s +- 0.2s between when I press the button and when things are done reflowing, etc, but I only did three trials for each).  Profiling this, it looks like of the 188298 hits only 23778 are under mozInlineSpellChecker::SetEnableRealTimeSpell.  About half of these are under mozInlineSpellWordUtil::GetNextWord.  Most of _that_ is under mozInlineSpellWordUtil::MakeRange.  There's also some time spent in flushing out notifications to get the computed style, actually spell-checking the word, and destroying ranges (in that order).

So it does look like Brett's patch addresses the major issue I saw.

Brett, if you can file bugs about the remaining perf problems with steps to reproduce, I would be happy to profile what happens when those steps are performed.

Comment 24

[Brett Wilson]

I created bug 345048 for scrolling, and bug 435050 for the turning off spellcheck slowness.

bz: If you can think of how to profile scrolling, that would be great. I don't know where to look or what to do. The spellchecker doesn't do anythink on scrolling, so it may be a core problem with many selections visible.

Turning off spellchecking for a a field with many misspellings could also use profiling.

Comment 25

[Boris Zbarsky [:bzbarsky]]

You mean bug 345050 for turning off, right?

I'll post some profiles.

Comment 26

[Brett Wilson]

(In reply to comment #25)
> You mean bug 345050 for turning off, right?

Yes, sorry.

> I'll post some profiles.

Thanks!

Comment 27

[Dave Townsend [:mossop]]

*** Bug 345109 has been marked as a duplicate of this bug. ***

Comment 28

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Comment on attachment 229585 [details] [diff] [review]
Patch to speed up nsRange::IsIncreasing

removing request for approval since according to comment 23 it doesn't help perf here anyway.

Comment 29

[Brett Wilson]

(In reply to comment #28)
> removing request for approval since according to comment 23 it doesn't help
> perf here anyway.

Does it help without my patch? If so, it will definitely help cases that bz didn't measure. When you type, we do a lot of these operations as well.

Comment 30

[Boris Zbarsky [:bzbarsky]]

Given the number of places that hit nsRange::IsIncreasing in spellchecker code in general (see the profiles for scrolling, turning off spellcheck, etc), improvements in it are probably worth it even if they just reduce wall-clock times by a few percent (where we want to reduce them by orders of magnitude)...

Comment 31

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Comment on attachment 229585 [details] [diff] [review]
Patch to speed up nsRange::IsIncreasing

Ok, rerequestion approval then

Comment 32

[Robert O'Callahan (:roc) (email my personal email if necessary)]

+      if (createdRange)
+        createdRange->IsPointInRange(beginNode, beginOffset, &inCreatedRange);

What happens if we paste text "fi" before "sh"? Will the spellcheck selection be removed from "sh", or will this cause that to be bypassed?

Comment 33

[Brett Wilson]

(In reply to comment #32)
> +      if (createdRange)
> +        createdRange->IsPointInRange(beginNode, beginOffset, &inCreatedRange);
> 
> What happens if we paste text "fi" before "sh"? Will the spellcheck selection
> be removed from "sh", or will this cause that to be bypassed?

Hmm, that is a bug. Do you have any ideas? We could always check the beginning & end of the word to see if it is in the range, but these tests are relatively slow.

Comment 34

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 229538 [details] [diff] [review]
Init & Paste optimizations

Let's just check the end as well, for now. Comment that since both the start and end are in createdRange, the whole word must be in createdRange so you don't need to remove from the spellcheck selection. r+sr with that.

Comment 35

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Actually, is there a reason why we don't just call RemoveRange(aRange) on the spellcheck selection outside the word loop?

Comment 36

[Brett Wilson]

I think the bugs with this patch are better than the performance without it.

We don't know which range to remove outside the word loop. We need the word to see if it intersects a range.

Comment 37

[Robert O'Callahan (:roc) (email my personal email if necessary)]

How about RemoveRange(aRange) and then do the word removal for just the first and last words?

Comment 38

[Brett Wilson]

(In reply to comment #37)
> How about RemoveRange(aRange) and then do the word removal for just the first
> and last words?

I was thinking that, too. Does the word finder know when you've found the last word? My original design didn't. We can always save the previous range, though, and use it outside the loop.

Comment 39

[Boris Zbarsky [:bzbarsky]]

I was thinking... Could we possibly enforce in the selection that it consists of non-overlapping ranges (consolidating as needed when ranges are added)?  If we could, then a lot of these linear search/check algorithms could become binary searches/checks.

For the "misspelled stuff" selection, I think we _are_ pretty much guaranteed that it consists of non-overlapping ranges already, right?  I guess for normal selection (with ctrl-drag to get multiple ranges) we might not be able to enforce this, though...  But we could certainly have the selection notice when it ends up with overlapping ranges and set a flag that it and callers could check or something.

Comment 40

[Brett Wilson]

I'm doing an interval tree, (basically two trees, one sorted by range beginning, one by end). I don't think doing this will be much slower than if we only had one tree, and I'm afraid to change the semantics of the selection at this point. We can optimize it for the common case where they don't overlap.

Comment 41

[Boris Zbarsky [:bzbarsky]]

Ah, yeah.  An interval tree sounds great.

Comment 42

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to comment #38)
> (In reply to comment #37)
> > How about RemoveRange(aRange) and then do the word removal for just the first
> > and last words?
> 
> I was thinking that, too. Does the word finder know when you've found the last
> word? My original design didn't. We can always save the previous range, though,
> and use it outside the loop.

I was thinking of the latter approach.

Comment 43

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

What's been checked in to the trunk here (of the patches with approval requests)?  It's hard to tell, and when approving patches we generally like to take things that have already baked a little on the trunk.

Comment 44

[Brett Wilson]

Currently the IsIncreasing patch is on Trunk. I'm going to check Init&Paste in this afternoon. Anybody else can check it in sooner if they want.

Comment 45

[Martijn Wargers (dead)]

(In reply to comment #44)
> Currently the IsIncreasing patch is on Trunk. I'm going to check Init&Paste in
> this afternoon. Anybody else can check it in sooner if they want.

I've just checked in that patch on the trunk. 

Comment 46

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 229538 [details] [diff] [review]
Init & Paste optimizations

a=dbaron on behalf of drivers.  Please check in to MOZILLA_1_8_BRANCH and mark fixed1.8.1 once you have done so.

Comment 47

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 229585 [details] [diff] [review]
Patch to speed up nsRange::IsIncreasing

a=dbaron on behalf of drivers.  Please check in to MOZILLA_1_8_BRANCH and mark fixed1.8.1 once you have done so.

Comment 48

[Brett Wilson]

The init & paste optimizations are on the 1.8.1 branch now. It looks like we just need to get IsIncreasing on branch now?

Comment 49

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Landed the IsIncreasing patch on the 1.8 branch.

Comment 50

[Simon Fraser [no longer active]]

This may have caused a hang bug 345562.

Comment 51

[Brett Wilson]

This seems to be fixed everywhere now.

Comment 52

[Ryan Flint [:rflint] (ping via IRC for reviews)]

*** Bug 348491 has been marked as a duplicate of this bug. ***

Comment 53

[Carsten Book [:Tomcat]]

verified fixed 1.8.1.3 using Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.3) Gecko/20070326 Thunderbird/2.0.0.0 ID:2007032622 and also wfm Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9a4pre) Gecko/20070405 Minefield/3.0a4pre Mnenhy/0.7.4.666 ID:2007040504 [cairo] 

Using the steps to reproduce from comment 0 -> no hang - adding verified keyword