[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: [e-mail]
        ReportedBy: [e-mail]
    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.

[Bug 30627] Appending text to a large richedit is very slow

http://bugs.winehq.org/show_bug.cgi?id=30627

Dan Kegel  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |performance, source

[Bug 30627] Appending text to a large richedit is very slow

http://bugs.winehq.org/show_bug.cgi?id=30627

--- Comment #1 from Dan Kegel  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

[Bug 30627] Appending text to a large richedit is very slow

http://bugs.winehq.org/show_bug.cgi?id=30627

--- Comment #2 from Dan Kegel  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.

[Bug 30627] Appending text to a large richedit is very slow

http://bugs.winehq.org/show_bug.cgi?id=30627

Dan Kegel  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #40101|0                           |1
        is obsolete|                            |

--- Comment #3 from Dan Kegel  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

[Bug 30627] Appending text to a large richedit is very slow

http://bugs.winehq.org/show_bug.cgi?id=30627

--- Comment #4 from Dan Kegel  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.

[Bug 30627] Appending text to a large richedit is very slow

http://bugs.winehq.org/show_bug.cgi?id=30627

Dan Kegel  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #40107|0                           |1
        is obsolete|                            |

--- Comment #5 from Dan Kegel  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

[Bug 30627] Appending text to a large richedit is very slow

http://bugs.winehq.org/show_bug.cgi?id=30627

--- Comment #6 from Dan Kegel  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.

[Bug 30627] Appending text to a large richedit is very slow

http://bugs.winehq.org/show_bug.cgi?id=30627

--- Comment #7 from Dan Kegel  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.

[Bug 30627] Common operations in richedit are O(N), should be O(log N) or so

http://bugs.winehq.org/show_bug.cgi?id=30627

Dan Kegel  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  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.

[Bug 30627] Common operations in richedit are O(N), should be O(log N) or so

http://bugs.winehq.org/show_bug.cgi?id=30627

Qian Hong  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |[e-mail]

[Bug 30627] Common operations in richedit are O(N), should be O(log N) or so

https://bugs.winehq.org/show_bug.cgi?id=30627

Jactry Zeng  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |[e-mail]

[Bug 30627] Common operations in richedit are O(N), should be O(log N) or so

https://bugs.winehq.org/show_bug.cgi?id=30627

Ken Sharp  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |download, testcase
           Severity|enhancement                 |trivial

[Bug 30627] Common operations in richedit are O(N), should be O(log N) or so

https://bugs.winehq.org/show_bug.cgi?id=30627

[e-mail] changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |[e-mail]

[Bug 30627] Common operations in richedit are O(N), should be O(log N) or so

https://bugs.winehq.org/show_bug.cgi?id=30627

--- Comment #9 from [e-mail] ---
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

[Bug 30627] Common operations in richedit are O(N), should be O(log N) or so

https://bugs.winehq.org/show_bug.cgi?id=30627

--- Comment #10 from Dan Kegel  ---
The patch wasn't sufficient anyway; the code would need refactoring to
remove linear scans.

[Bug 30627] Common operations in richedit are O(N), should be O(log N) or so

[WineHQ Bugzilla]

https://bugs.winehq.org/show_bug.cgi?id=30627

joaopa  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |[e-mail]

--- Comment #11 from joaopa  ---
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?

[Bug 30627] Common operations in richedit are O(N), should be O(log N) or so

[WineHQ Bugzilla]

https://bugs.winehq.org/show_bug.cgi?id=30627

--- Comment #12 from Dan Kegel  ---
5000 probably isn't enough lines to show the problem clearly.

Also, you'd want to compare against the time with native richedit...

[Bug 30627] Common operations in richedit are O(N), should be O(log N) or so

[WineHQ Bugzilla]

https://bugs.winehq.org/show_bug.cgi?id=30627

--- Comment #13 from joaopa  ---
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