[Bug 30627] New: Appending text to a large richedit is very slow
http://bugs.winehq.org/show_bug.cgi?id=30627 Bug #: 30627 Summary: Appending text to a large richedit is very slow Product: Wine Version: 1.5.3 Platform: x86 OS/Version: Linux Status: NEW Severity: enhancement Priority: P2 Component: richedit AssignedTo: wine-bugs(a)winehq.org ReportedBy: dank(a)kegel.com Classification: Unclassified Although the pathological case reported in bug 30614 is now fixed, all is not yet well. When repeatedly appending lines, builtin riched20 starts out about 3x slower than native, and at 40k lines, is about 10x slower than native. This is painful for long-running apps that use richedit for verbose logs. (Measured with the attached program and today's git on my i5, appending 1000 lines to an empty richedit control takes builtin hidden: 907 ms builtin visible: 4862 ms native hidden: 368 ms native visible: 4530 ms Appending 1000 lines to a richedit control which already contains 40000 lines takes: builtin hidden: 22169 ms builtin visible: 33002 ms native hidden: 1750 ms native visible: 4807 ms ) Building wine's riched20 with -O1 -fno-inline and profiling with 'perf' shows 62.60% ME_WrapMarkedParagraphs 12.07% ME_PaintContent 9.99% ME_InvalidateMarkedParagraph at 50k lines. Initial inspection seems to show that most of the time in ME_WrapMarkedParagraphs is in the function itself, not in any called functions. Adding trace statements to all callers of ME_WrapMarkedParagraphs, I see one call during EM_EXSETSEL: ME_Repaint Calling ME_WrapMarkedParagraphs and four calls during EM_REPLACESEL: ME_UpdateRepaint Calling ME_WrapMarkedParagraphs ME_UpdateScrollBar Calling ME_WrapMarkedParagraphs ME_Repaint Calling ME_WrapMarkedParagraphs ME_UpdateScrollBar Calling ME_WrapMarkedParagraphs This is the case whether the window is hidden or not. Bug 13355 (which Dylan says is separate, since it's about richedit being slow on a single large call to WM_SETTEXT) suggests in comment 14 ways to remove some redundant calls to ME_WrapMarkedParagraphs, and to let one of them return early. In addition to those ideas, for this bug, it would be useful if ME_WrapMarkedParagraphs (and ME_InvalidateMarkedParagraph) could avoid making a linear scan across all paragraphs. -- Configure bugmail: http://bugs.winehq.org/userprefs.cgi?tab=email Do not reply to this email, post in Bugzilla using the above URL to reply. ------- You are receiving this mail because: ------- You are watching all bug changes.
http://bugs.winehq.org/show_bug.cgi?id=30627 Dan Kegel <dank(a)kegel.com> changed: What |Removed |Added ---------------------------------------------------------------------------- Keywords| |performance, source -- Configure bugmail: http://bugs.winehq.org/userprefs.cgi?tab=email Do not reply to this email, post in Bugzilla using the above URL to reply. ------- You are receiving this mail because: ------- You are watching all bug changes.
http://bugs.winehq.org/show_bug.cgi?id=30627 --- Comment #1 from Dan Kegel <dank(a)kegel.com> 2012-05-08 19:54:45 CDT --- Created attachment 40101 --> http://bugs.winehq.org/attachment.cgi?id=40101 Small program to measure how long it takes to append lines to a richedit -- Configure bugmail: http://bugs.winehq.org/userprefs.cgi?tab=email Do not reply to this email, post in Bugzilla using the above URL to reply. ------- You are receiving this mail because: ------- You are watching all bug changes.
http://bugs.winehq.org/show_bug.cgi?id=30627 --- Comment #2 from Dan Kegel <dank(a)kegel.com> 2012-05-09 16:43:57 CDT --- Time to insert 1000 lines into a richedit already containing 40k lines: Today's git without 1f8cbe164576ecab9d786903f64f76198e3e77f9: 35508 - 35607 ms Today's git: 32798 - 33007 ms That's about a 7% speedup; thanks, Dylan. -- Configure bugmail: http://bugs.winehq.org/userprefs.cgi?tab=email Do not reply to this email, post in Bugzilla using the above URL to reply. ------- You are receiving this mail because: ------- You are watching all bug changes.
http://bugs.winehq.org/show_bug.cgi?id=30627 Dan Kegel <dank(a)kegel.com> changed: What |Removed |Added ---------------------------------------------------------------------------- Attachment #40101|0 |1 is obsolete| | --- Comment #3 from Dan Kegel <dank(a)kegel.com> 2012-05-09 16:44:39 CDT --- Created attachment 40107 --> http://bugs.winehq.org/attachment.cgi?id=40107 Faster test program; builds base richedit all at once to save time -- Configure bugmail: http://bugs.winehq.org/userprefs.cgi?tab=email Do not reply to this email, post in Bugzilla using the above URL to reply. ------- You are receiving this mail because: ------- You are watching all bug changes.
http://bugs.winehq.org/show_bug.cgi?id=30627 --- Comment #4 from Dan Kegel <dank(a)kegel.com> 2012-05-09 16:57:49 CDT --- http://www.winehq.org/pipermail/wine-patches/2012-May/114044.html shaves another linear scan off. With that patch, 'append.exe 40000' takes 29895-29911 ms to append 1000 lines to a 40k line richedit. I think there are five linear scans left: four calls to ME_WrapMarkedParagraphs and one in ME_PaintContent. -- Configure bugmail: http://bugs.winehq.org/userprefs.cgi?tab=email Do not reply to this email, post in Bugzilla using the above URL to reply. ------- You are receiving this mail because: ------- You are watching all bug changes.
http://bugs.winehq.org/show_bug.cgi?id=30627 Dan Kegel <dank(a)kegel.com> changed: What |Removed |Added ---------------------------------------------------------------------------- Attachment #40107|0 |1 is obsolete| | --- Comment #5 from Dan Kegel <dank(a)kegel.com> 2012-05-10 14:07:21 CDT --- Created attachment 40111 --> http://bugs.winehq.org/attachment.cgi?id=40111 Faster test program; don't count lines, it messes with the timing -- Configure bugmail: http://bugs.winehq.org/userprefs.cgi?tab=email Do not reply to this email, post in Bugzilla using the above URL to reply. ------- You are receiving this mail because: ------- You are watching all bug changes.
http://bugs.winehq.org/show_bug.cgi?id=30627 --- Comment #6 from Dan Kegel <dank(a)kegel.com> 2012-05-10 14:08:11 CDT --- Ahem. The test program itself had a linear scan in it. That's gone now. Speeds things up noticably. -- Configure bugmail: http://bugs.winehq.org/userprefs.cgi?tab=email Do not reply to this email, post in Bugzilla using the above URL to reply. ------- You are receiving this mail because: ------- You are watching all bug changes.
http://bugs.winehq.org/show_bug.cgi?id=30627 --- Comment #7 from Dan Kegel <dank(a)kegel.com> 2012-05-10 14:19:44 CDT --- Created attachment 40112 --> http://bugs.winehq.org/attachment.cgi?id=40112 Kludge global flag optimization patch The attached kludge patch adds a global bNeedWrap flag sufficient to pass the test suite. With this and my previous patch, appending 1k lines at 40k now takes 14700 ms, only about 3x native. It's not enough at 400k, though; that's still 88800 ms, 11x slower than native. -- Configure bugmail: http://bugs.winehq.org/userprefs.cgi?tab=email Do not reply to this email, post in Bugzilla using the above URL to reply. ------- You are receiving this mail because: ------- You are watching all bug changes.
http://bugs.winehq.org/show_bug.cgi?id=30627 Dan Kegel <dank(a)kegel.com> changed: What |Removed |Added ---------------------------------------------------------------------------- Summary|Appending text to a large |Common operations in |richedit is very slow |richedit are O(N), should | |be O(log N) or so --- Comment #8 from Dan Kegel <dank(a)kegel.com> 2012-05-18 15:15:54 CDT --- In the real app, the global flag patch is not really enough; although it does speed things up a bunch, as more lines pile up in the richedit, having to pay an O(N) penalty on every insert, delete, and redraw soon swamps the patch's speedup. So the user perceives the speedup as letting him log 10k lines in the time it took to log 9k lines before. What we really need is to get rid of all linear scans for common operations like paint, insert, and delete. -- Configure bugmail: http://bugs.winehq.org/userprefs.cgi?tab=email Do not reply to this email, post in Bugzilla using the above URL to reply. ------- You are receiving this mail because: ------- You are watching all bug changes.
http://bugs.winehq.org/show_bug.cgi?id=30627 Qian Hong <fracting(a)gmail.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |fracting(a)gmail.com -- Configure bugmail: http://bugs.winehq.org/userprefs.cgi?tab=email Do not reply to this email, post in Bugzilla using the above URL to reply. ------- You are receiving this mail because: ------- You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=30627 Jactry Zeng <jactry92(a)gmail.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |jactry92(a)gmail.com -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=30627 Ken Sharp <imwellcushtymelike(a)gmail.com> changed: What |Removed |Added ---------------------------------------------------------------------------- Keywords| |download, testcase Severity|enhancement |trivial -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=30627 super_man(a)post.com changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |super_man(a)post.com -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=30627 --- Comment #9 from super_man(a)post.com --- patching file dlls/riched20/editor.c Hunk #1 succeeded at 2824 (offset 114 lines). patching file dlls/riched20/editstr.h Hunk #1 FAILED at 379. 1 out of 1 hunk FAILED -- saving rejects to file dlls/riched20/editstr.h.rej patching file dlls/riched20/paint.c Hunk #1 succeeded at 118 (offset -1 lines). patching file dlls/riched20/para.c Hunk #1 succeeded at 96 (offset 14 lines). patching file dlls/riched20/run.c Hunk #1 succeeded at 225 (offset 4 lines). Hunk #2 succeeded at 279 (offset -47 lines). Hunk #3 FAILED at 377. Hunk #4 FAILED at 768. Hunk #5 FAILED at 790. 3 out of 5 hunks FAILED -- saving rejects to file dlls/riched20/run.c.rej patching file dlls/riched20/wrap.c Hunk #1 succeeded at 948 (offset 348 lines). Hunk #2 FAILED at 744. 1 out of 2 hunks FAILED -- saving rejects to file dlls/riched20/wrap.c.rej against 1.9.8-git -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=30627 --- Comment #10 from Dan Kegel <dank(a)kegel.com> --- The patch wasn't sufficient anyway; the code would need refactoring to remove linear scans. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=30627 joaopa <jeremielapuree(a)yahoo.fr> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |jeremielapuree(a)yahoo.fr --- Comment #11 from joaopa <jeremielapuree(a)yahoo.fr> --- Created attachment 68774 --> https://bugs.winehq.org/attachment.cgi?id=68774 test binary Looks like the bug is fixed with wine-5.22 Tested on an old (2004) computer Lines 1...4000 took 576 ms to append all at once Lines 4000...5000 took 4186 ms to append Can an administrator close this bug as FIXED? -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=30627 --- Comment #12 from Dan Kegel <dank(a)kegel.com> --- 5000 probably isn't enough lines to show the problem clearly. Also, you'd want to compare against the time with native richedit... -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=30627 --- Comment #13 from joaopa <jeremielapuree(a)yahoo.fr> --- Looks like there are still noticeable differences between native and builtin: native: Lines 1...399000 took 28999 ms to append all at once Lines 399000...400000 took 9972 ms to append builtin: Lines 1...399000 took 35275 ms to append all at once Lines 399000...400000 took 63373 ms to append -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
participants (2)
-
wine-bugs@winehq.org -
WineHQ Bugzilla