251862 - Find Toolbar Highlight is unresponsive when there are too many matches

Status: RESOLVED DUPLICATE of bug 429732

(Toolkit :: Find Toolbar, defect)

Description

[Nickolay_Ponomarev]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7) Gecko/20040715 Firefox/0.9.1+ (best browser EVAR1!!)
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7) Gecko/20040715 Firefox/0.9.1+

Find Toolbar Highlight is unresponsive when there are too many matches. See
steps to reproduce.

Reproducible: Always
Steps to Reproduce:
1. Go to
http://lxr.mozilla.org/mozilla/source/toolkit/components/history/src/nsGlobalHistory.cpp
2. Search for "ns"
3. Click Highlight
Actual Results:  
The whole Firefox is freezed for several seconds on a 2Ghz machine.

Expected Results:  
Firefox is responsive, user can cancel the action or switch to another tab

The obvious workaround is not to use Highlight when you suspect the page
contains many entries of the string searched. Thus minor.

Comment 1

[José Jeria]

Seing this as well on a 3,2 ghz computer, firefox freezes for a second or two.
Confirming. 

Comment 2

[tve]

Freezed for 30 seconds on a P3 550Mhz running Linux. System load was at 100%
during that time.

Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.3) Gecko/20040902 Firefox/1.0 PR
(NOT FINAL)

Comment 3

[Doug]

Works for me:
2.66 GHz machine,
Mozilla/5.0 (Windows; U; Windows NT 5.0; rv:1.7.3) Gecko/20040913 Firefox/0.10

Comment 4

[Ryan Polk (Quark)]

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

Comment 5

[Udo Richter]

I would recommend increasing this to severity:normal or major.

Alternate test case to the first one:

1. Go to above link:
http://lxr.mozilla.org/mozilla/source/toolkit/components/history/src/nsGlobalHistory.cpp
2. Search anything using find toolbar
3. Enable highlighting
3. Close the find toolbar
4. Type "e"
5. (Optionally) Go get some coffee.

On above link, the highlighting of all e letters took 80 seconds on my 2.4GHz
machine, and FF is totally frozen the whole time. 
Searching "e" isnt that unusual either, if you just wanted to search for a word
starting with e you'll get stuck after the first letter.

Possible solutions:
-Stop highlighting after # hits
-Stop highlighting after # seconds
-Highlight in background leaving FF responsible
-Only highlight what's currently on screen

Comment 6

[Kevin R. Gallagher]

I would recommend increasing this to severity:major or even critical.

Alternate test case to the one in comment 5:

1. Go to above link:
http://lxr.mozilla.org/mozilla/source/toolkit/components/history/src/nsGlobalHistory.cpp
2. Search anything using find toolbar
3. Enable highlighting
3. Highlight your "Find:" string
4. Push "Delete" or "Backspace"
5. Kill Browser

Comment 7

[bulk]

And here I thought I found something new.., I have a bit more extreme case for
this issue... 
 ftp://weather.noaa.gov/data/observations/metar/cycles/
then pick a file that has some size to it, they are typically about 800K or more
in size

if you simply enter a "k" while the highlight button is active, or backspace
over other letters until there is only a "k" ( example, I was changing from
"krdm" to "kbok" and got stuck in this ) the wait time is not in seconds, but in
minutes. You could select other letters or numbers as well, but "K" is very
common on these text pages.

We tested this with both Windows XP and with Mac OSX, and the release version of
Firefox 1.0.6. XP Home, Athlon XP 2600+, 480MB of RAM, and on OSX a Minimac with
1GB of RAM... both machines took about 20 minutes to complete the highlight
operation. When I tested unhighlighting, I actually had a script warning that
interrupted the process, and asked if I would like to stop the script as it was
taking a long time and could cause the computer to become unresponsive, this at
about 30 minutes into the unhighlight. 

Due to the warning about a script issue, I suspect this is a scripting issue,
which I am not seeing mentioned in this bug anywhere. Since I don't know where
to begin digging in the source to find the cause, I can only come up with this,
I believe that the Highlighting actually adds tags into the body of the page and
 then removes them you unhighlight, the unhighlight seems to take about 50
percent longer. The biggest problem I see here, is that there is typically NO
option to halt this script, so you are stuck waiting, or you have to kill the
broswer.

Comment 8

[Adam Guthrie]

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

Comment 9

[Adam Guthrie]

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

Comment 10

[Adam Guthrie]

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

Comment 11

[Tae Kim]

For anybody interested in tackling this bug, you can find the relevant code in the highlightDoc function at the following:
http://lxr.mozilla.org/mozilla/source/toolkit/components/typeaheadfind/content/findBar.js#215

Have no idea how it works, but it looks like a recursive function? Could explain why it's so slow.

Comment 12

[Ginn Chen]

I opened a 2000 lines source file in LXR, enter "s" in Find bar, and press "Highlight all".
After waiting about 3 minutes, I got a dialog saying
"A script on this page may be busy, or it may have stopped responding, You can stop the script now, or you can continue to see if the script will complete.
Script: chrome://global/content/bindings/finderbar.xml:587"

I don't know why this dialog comes out so late.

Comment 13

[Graeme McCutcheon [:graememcc]]

There's a fuller discussion of this in bug 429732

Comment 14

[(no longer active)]

Should this be a dupe of bug 429732 or vice versa? (I think the former is the better, given the thorough analysis of the problem given in that bug)

Comment 15

[Nickolay_Ponomarev]

Since the discussion in that bug is about the more general problem, I think I'll mark this one dependent on 429732 for now.

Comment 16

[Henrik Skupin [:whimboo][⌚️UTC+1]]

Nickolay, can you still reproduce this issue while highlighting a lot of matches? It looks much better now. In my opinion we should dupe this one and do all of the discussion in one bug. Sorry, that I haven't found your one.

Comment 17

[Adam]

Attachment: WIP v1: Optimization: Skip useless binsearches

When we're adding matches to the array of selection ranges so they can be highlighted, there are two possibilities:

1. The new match begins at the end of the last range.
2. The new match begins after the end of the last range.

Cheap as binsearch is, it's adding a lot of useless work for this case.

Finding the letter 'f' on https://mxr.mozilla.org/mozilla-central/source/testing/marionette/atoms/atoms.js has over 3600 matches.

I tested this patch there and got a couple of rough averages for |findbar.xml|'s |_highlightDoc|:

Without this patch: 14.1 seconds
With the patch: 7.9 seconds

This should give us a nice speedup for cases where there are many matches to highlight.

Need to look at the patch a bit more to be sure it plays nice with the rest of |GetIndicesForInterval| and consumers.