Open Bug 289644 Opened 20 years ago Updated 3 years ago

"Reply" or "reply all" is slow for large messages - O(n^2) performance

Categories

(Thunderbird :: Message Compose Window, defect)

Product:
Thunderbird
Component:
Message Compose Window
Type:
defect
Priority:
Not set
Severity:
major

Tracking

(Not tracked)

People

(Reporter: marcia, Unassigned)

References

Details

(Keywords: perf, Whiteboard: [see comment 20, 23])

Seen using today's trunk build, version (20050408). Using IMAP. STR: 1. Reply or Reply all to any message 2. TB seems abnormally slow to load Clicking on a message doesn't seem slow, just noticed it when I reply or reply all to any message.
IMAP or POP3? Does bringing up a new compose window for the first time seem slow? (we load the spell-checker and dictionary then, which is slow the first time)
David: IMAP. Compose window comes up fine - no noticeable difference there. I only notice the latency in replying to mail
message display is extremely slow on today's mac build let alone message reply. Something weird is going on we we try to fetch a message.
shaver said there's some problem with the mac text library, ATSUI, which generates lots of warning with trunk builds...though if that's the problem here, it would also affect local messages.
every time I display a message I get the following warnings in the console which seem very scary since we don't have plugin support for thunderbird: /builds/mscott/tbirddbg/mozilla/dist/ThunderbirdDebug.app/Contents/MacOS/thunderbird-bin: can't map file: /builds/mscott/tbirddbg/mozilla/dist/ThunderbirdDebug.app/Contents/MacOS/plugins/Default Plugin.plugin ((os/kern) invalid argument) [loaded plugin /builds/mscott/tbirddbg/mozilla/dist/ThunderbirdDebug.app/Contents/MacOS/plugins/Default Plugin.plugin] /builds/mscott/tbirddbg/mozilla/dist/ThunderbirdDebug.app/Contents/MacOS/thunderbird-bin: can't map file: /Library/Internet Plug-Ins/DRM Plugin.bundle ((os/kern) invalid argument) [loaded plugin /Library/Internet Plug-Ins/DRM Plugin.bundle] /builds/mscott/tbirddbg/mozilla/dist/ThunderbirdDebug.app/Contents/MacOS/thunderbird-bin: can't map file: /Library/Internet Plug-Ins/Windows Media Plugin ((os/kern) invalid argument) [loaded plugin /Library/Internet Plug-Ins/Windows Media Plugin] /builds/mscott/tbirddbg/mozilla/dist/ThunderbirdDebug.app/Contents/MacOS/thunderbird-bin: can't map file: /Library/Internet Plug-Ins/QuickTime Plugin.plugin ((os/kern) invalid argument) [loaded plugin /Library/Internet Plug-Ins/QuickTime Plugin.plugin] [loaded plugin /Library/Internet Plug-Ins/Java Applet Plugin Enabler] /builds/mscott/tbirddbg/mozilla/dist/ThunderbirdDebug.app/Contents/MacOS/thunderbird-bin: can't map file: /Library/Internet Plug-Ins/Java Applet.plugin ((os/kern) invalid argument) [loaded plugin /Library/Internet Plug-Ins/Java Applet.plugin]
the only other thing I see on the console when displaying a message is: ###!!! ASSERTION: : 'Error', file xptiInterfaceInfoManager.cpp, line 956 Break: at file xptiInterfaceInfoManager.cpp, line 956
local messages are just as slow to both display and reply to as imap by the way. at least for me.
this message display issue could be a separate bug. I click a message, selection changes, then there's a long pause and then the throbber starts to spin, the status bar says Loading Message. It's that pause before the status bar text changes that seems abnormal.
Keywords: perf
I am still seeing this on today's Thunderbird Trunk build - version 1.0+ (20050421). Asa is seeing this too in Windows. I am going to try to hunt down a regression window. Also, I see a number of errors in my JS console too - different than the ones Scott is seeing, thought i would put them in this bug: Error: redeclaration of const imgICache Source File: chrome://communicator/content/contentAreaUtils.js Line: 230 Error: Unrecognized at-rule or error parsing at-rule '@font-face'. Source File: imap://knous@mail.meer.net:143/fetch%3EUID%3E/INBOX%3E17434 Line: 32 Error: Unknown property 'mso-margin-top-alt'. Declaration dropped. Source File: imap://knous@mail.meer.net:143/fetch%3EUID%3E/INBOX%3E17434 Line: 49
Hardware: Macintosh → All
windows is still working great for me using todays build.
Is spell as you type enabled and delay go away if disabled? Same results with foward as inline?
I believe I've figured out the cause of this problem. My IMAP provider is meer.net which can be flakey at times. When I'm replying to an IMAP mail and the server can't be reached, it just hangs with a blank reply window until it manages to make the connection to the server - then it populates the reply compose addresses and content. I've tested this by simply unplugging my network cable and can reproduce reliably. If there is no network connection, then the reply compose window does not populate, it just hangs. It feels like a performance problem, and not a hang, when the connection is just bad -- that's why we thought it was a performance problem. Why are we blocking the populating of the reply compose window for a server connection. That seems bad. That hasn't always been the case, has it?
OS: MacOS X → All
because we're quoting the message. That apparently is blocking the UI. The weird thing is that quoting should be getting the message from the memory cache, so we should require a network connection.
This is definitely a performance problem and unrelated to the network. I tested this with TB 1.5 (20051201) on Win XP, AMD Athlon 64, 2200 MHz (11 x 200) 3500+, 1GB RAM. I have a multipart/mixed message in my IMAP inbox. It has two parts, both text/plain. Content-Type: Multipart/Mixed; Boundary="==JBEAAAAAAMQ2CQAAYQABSOwLQb5U==" --==JBEAAAAAAMQ2CQAAYQABSOwLQb5U== Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: Quoted-Printable This part is about 40 lines long. The second part headers are --==JBEAAAAAAMQ2CQAAYQABSOwLQb5U== Content-Type: text/plain; charset=iso-8859-1; name="steve.log" Content-Disposition: attachment Content-Description: "Text Document (ISO Latin 1 (Western))" Content-Transfer-Encoding: Quoted-Printable and this is close to 3MB. The message is loaded from the IMAP mailbox in a few seconds and the "steve.log" is shown in the attachment bar. If I copy that mail to a local folder, it copies in under a second. If I make a reply to that message, either from the version in the IMAP inbox OR from the local folder version, an empty compose window is shown and the CPU runs at 100% for 4 minutes and 50 seconds before finally the text is displayed!! However, it displays the text from BOTH body parts, even though the second body part has a Content-Disposition header of attachment. Why is this. Anyway, there's some seriously poor code :) that handles the quoting algorithm. How anything can take that long to process 3MB of text on that sort of machine. Just as an comparison, I can cat a 1.6GB file in 30 seconds with very little CPU load.
(In reply to comment #14) > This is definitely a performance problem and unrelated to the network. I > tested this with TB 1.5 (20051201) on Win XP, AMD Athlon 64, 2200 MHz (11 x > 200) 3500+, 1GB RAM. Antony please try trunk build and report back. perhaps you were affected by Bug 324521. (In reply to David Bienvenu comment #13) > ... quoting should be getting the message from the memory cache, so > we should require a network connection. David, should, or should not?
(In reply to comment #15) > Antony > please try trunk build and report back. > perhaps you were affected by Bug 324521. Re: 324521, I disabled inline spellchecking and it made no differece when attempting a reply to a 5.7MB mail item. It took 10 minutes, 9 seconds. FYI: There were 2 distinct phases during that time. Phase 1. Window appears blank, CPU 100%. After 6 minutes, 5 seconds, the text is painted in black. Phase 2. CPU continues at 100%. After a further 4 minutes, 4 seconds, text turns blue and CPU drops to normal. Does this give any clues? BTW, why does it do this for text _attachments_ that are specifically marked with Content-Disposition: attachment, NOT inline? As for the trunk build - does that mean the latest nightly build, 3.0a1? Can I install alongside my existing 1.5 version?
(In reply to comment #16) > Re: 324521, I disabled inline spellchecking and it made no differece when Just to clarify, this test was still done using 20051201. I'll try with the trunk and report later. Antony
I'm also seeing the "slow" behavior - but my messages are only 35-50k of plain text. I compose in plain text as well. Thunderbird CPU utilization goes to 99% for 30 seconds to 5 minutes! Once recovered, it is also very slow to delete some of the quoted lines. And if I wish to abort the message, even closing the window takes 10-20 seconds. Windows 2000, 1 GB memory. Occurs with v1.5 and 1.5.0.2 (20060308).
Hmm, I thought I tried this earlier, but turning off "Enable spell as you type" seems to make a differece. I just tried copying the text of the message (ctrl-A, ctrl-C) and composed a new message. I pasted the 30k into the body - and even with "Spell as you type" turned on, performance wasn't affected. I noticed that the spell-check wasn't performed on the text that was pasted in - but it was performed on the text that was quoted when I "replied"... And why would _closing_ a window take up to 30 seconds for a 30k message?? Spellcheck shouldn't be working overtime then???
(In reply to comment #14) > Anyway, there's some seriously poor code :) that handles the quoting algorithm. > How anything can take that long to process 3MB of text on that sort of > machine. The problem is that a lot of the code used takes a time proportional to the *square* of the message size. So each time the message size doubles, the time taken multiplies by 4. Here are some examples of O(n^2) code. These 3 examples all happen in thunderbird 1.5.0.2 when I reply to a plain text message with a plain text attachment, using the plain text editor: ------ 1 ------ nsMsgCompose::ConvertAndLoadComposeWindow calls nsHTMLEditRules::WillInsertText which loops over each line of the message. for each line, nsHTMLEditRules::WillInsertText calls both nsHTMLEditor::CreateBRImpl and nsEditor::InsertTextImpl, and both of those end up calling nsFrameList::LastChild, which loops over all the lines processed so far. Perhaps if nsFrameList::LastChild was able to find what it was looking for in O(1) time, by keeping a pointer to the last child, this could be sped up. ------ 2 ------ Another instance of O(n^2) code used when quoting a message to reply to is when nsMsgCompose::ConvertAndLoadComposeWindow calls nsHTMLEditor::InsertAsQuotation which calls nsHTMLEditor::InsertAsPlaintextQuotation which calls ~nsAutoRules, which ends up calling nsHTMLEditor::CollapseAdjacentTextNodes, which loops over all the lines of the message which was quoted For each of those lines, it ends up calling nsCSSFrameConstructor::FindFrameWithContent, which again is O(n). ------ 3 ------ Finally, a 3rd place with O(n^2) code: nsMsgCompose::ConvertAndLoadComposeWindow calls nsEditor::EndTransaction nsHTMLEditor::EndUpdateViewBatch nsEditor::EndUpdateViewBatch PresShell::EndReflowBatching PresShell::FlushPendingNotifications ... [ some omitted - I have the full list if anyone's interested ] nsBlockFrame::ReflowLine, which loops a lot, and each time through the loop, nsFrameList::CheckForLoops gets called, which also loops a lot ------ I've just tried similar tests on thunderbird-3.0a1.en-US.linux-i686.tar.bz2 found it to have similar behaviour... It took 35 seconds to reply to a 10,000 line message, and 2 minutes to reply to a 20,000 line message; double the message length, quadruple the reply time.
QA Contact: message-compose
Marcia, Chris, does this still happen for you with current trunk or alpha 1? ftp://ftp.mozilla.org/pub/thunderbird/nightly/3.0a1-candidates/build1/
Assignee: mscott → nobody
Short answer: it's worse now than it was before. 10k lines = 16s 20k lines = 80s Long answer: I just downloaded and installed this: http://download.mozilla.org/?product=thunderbird-3.0b1&os=win&lang=en-US I made a text file with 10,000 lines, each containing a single '.' character. That was a 30,000 byte file with all the \r and \n characters. I run Thunderbird, added my Gmail account using the "Gmail IMAP" setting which was nice - it filled in everything for me automatically other than the username. It then automatically downloaded thousands of message headers, the process size blew up to 150MB and the computer hung. After killing and restarting Thunderbird it started behaving again. I hadn't let it save my password, so I guess it wasn't able to download any more messages to hang itself again. I set the account not use the HTML editor, and composed a message to myself, attaching the text file. I sent it, retrieved it, and Thunderbird hung again. I'd had to supply my password to retrieve the mail I had sent, and Thunderbird used this to start retrieving headers for all the 'labels' I use in Gmail. Killing and restarting again, I found that I was able to reply to the message instantly. The previous O(n^2) behaviour was gone. But that's because the text file attachment wasn't being quoted. Seems that in the 2.5 years since I reported the bug, the feature of quoting text attachments has been removed. I composed a new message, still using plain text, and copy/pasted the 10,000 lines into the message editor. I sent the message to myself and retrieved it. (I'll omit the details of having to restart each time I tell Thunderbird my password). When I tried to reply to the message, it took 16 seconds for the 10,000 quoted dots to appear. I tried again with 20,000 lines instead, and it took 80 seconds. 5 times longer than for the 10,000 line message. This is worse than O(n^2). Bear in mind that previously I was testing a different version of Thunderbird, using a text attachment rather than inline text, on a slower older computer, and on Linux rather than Windows. But given all that, the relative performance has got a bit worse, not better. This should be easy enough for anyone to reproduce.
Summary: "Reply" or "reply all" seems slow → "Reply" or "reply all" is slow for large messages - O(n^2) performance
Whiteboard: [see comment 20, 23]
I ran into the same thing with Thunderbird 3.1.9 on a message with 713 lines (16K in size) and 13 recipients.
I encounter this problem on Thunderbird 11.0.1 on Archlinux x64, but only if i have the option to create messages in html-format UNCHECKED in my account settings. If the option is set, when i click on reply of a large text-message (100KB+) i can immediately write my answer. If unchecked Thunderbird hangs for a short time (30s and up) and then, after the hang i can write my answer.
I believe I encounter this issue whenever I reply to a long message in plaintext mode, which is my default. I am presently running Thunderbird 24.6.0. Steps to reproduce: 1. Select an e-mail from a long thread that has not been trimmed, by which I mean it includes all previous text as quotes. I don't think any particular type of HTML markup in the thread is a deciding factor. 2. Reply in plaintext mode. The initial delay for the composition window to be ready for input is fairly short, on the order of a few seconds. However, typing within the editor is frustratingly unresponsive, with the user interface reduced to processing keyboard input roughly once every second. When in this state, typing causes Thunderbird to totally consume one CPU core. If all quoted lines are deleted, the editor will become responsive, as it is with a fresh e-mail composition window. When typing a plaintext reply at the top of a long e-mail thread, it's as if the editor is doing repeated computation with respect to the quoted text. For the time being, I will be using the HTML mode to reply to long messages even though my preference is plaintext.

I can replicate this issue by hitting "reply" to a message in a local folder. The message contains lots of broken-up quotes, like so:

...
> a quoted line
..blank...
> another quoted line
... etc etc...

The slowdown occurs when the message I'm replying to is being inserted into the HTML editor DOM, using HTMLEditor::InsertAsCitedQuotation().
It quickly creates a documentFragment with the HTML elements it wants to insert, then loops through, adding them into the DOM.
It's inserting elements into the DOM which seems to be slow. My test message takes 10 mins or so.

The test email I'm using is a pretty awful one, but it's a form you'd often find out in the wild - a long thread with lots of top-posting, and all the quoted lines interleaved with blank lines somewhere along the way by some . It comes out as about 80000 HTML elements (Mostly <pre> and <blockquote> elements I think).
There's a similar story with plain-text composition - it still generates HTML elements in a similar way for each bit of quoted content, so it's not just a matter of inserting one big element. You still end up with a comparable number of elements to insert.

You can see the elements being added with the log - MOZ_LOG="EditorTransaction:5"

Now. 80000 DOM nodes is a good number... but it still seems awfully slow to me. From what I can tell it's spending the bulk of it's time in
InsertNodeTransaction::DoTransaction(), which spends all it's time inside Selection::CollapseInLimiter(), which ends up dividing the time between nsINode::SetBoolFlag() and nsINode::ClearBoolFlag().

So, my guess is something selection-related slowing it down. I thought it might be registered Selection listeners causing trouble, but that doesn't seem to be the case (I commented out the notification call and it was still slow). I'm out of ideas for now.
Magnus: this would benefit from having some input from someone who knows about HTMLEditor - any thoughts who?

Flags: needinfo?(mkmelin+mozilla)

:masayuki is the editor expert.

Any suggestions?

Flags: needinfo?(mkmelin+mozilla) → needinfo?(masayuki)

I'd be nice if the profile is public and there is a testcase to reproduce it in mochitest. Anyway, editor creates transaction instances and modifies connected trees too many times. And also editor depends on selection, therefore, needs to update selection everywhere, that's also causes slowness because of Selection API cost.

So, bug 1555919 and bug 1624587 are the root cause, but perhaps, we can fix it with some simple patches if the bottlenecks are only a few places.

Flags: needinfo?(masayuki)
You need to log in before you can comment on or make changes to this bug.