Re: Analysis of redisplay performance on Windows

Re: Analysis of redisplay performance on Windows

[Chong Yidong]

Jason Rumney <jasonr@gnu.org> writes:

> The redisplay performance problems on Windows seem to be mostly caused
> by the left_overwriting and right_overwriting functions. These functions
> analyse all glyphs, one by one, before and after (respectively) the
> current glyph string on the same row to see if the glyphs overlap the
> current glyph string.
>
> To determine the overlap for each glyph, it is necessary to encode it
> into a glyph code point in the font used to display it, then measure its
> text extents.  Even with caching of the text extents, the Windows code
> is still especially slow here because of the encoding to glyph code points.
>
> Currently we cache glyph code points at the glyph_string level. Perhaps
> caching them at the glyph row level would help, as we could then reuse
> them after we have finished with the glyph string. Alternatively we
> could keep all the glyph strings for the row until we are finished so we
> could use glyph code points and other information from there. This might
> reduce the number of iterations we need to find the left and right
> overwriting glyphs, since we can check the glyph strings for overlaps
> first, and only check the glyphs inside glyph strings that overlap.
>
> There may also be a problem with the setting of
> row->contains_overlapping_glyphs_p on Windows. The above functions
> should only be called when that is set, but after inserting debugging
> code I can see them being called frequently even when using fonts that
> contain no overlapping glyphs (confirmed by further debugging code in
> w32font_text_metrics).

Thanks for looking into this, Jason.

But I don't understand why the problem of left_overwriting and
right_overwriting, if that's indeed the culprit, would be specific to
Windows.  These functions are called in the platform-independent
redisplay code.  Or is it much more expensive to look up glyph code
points in fonts on Windows, compared to GNU/Linux?

Re: Analysis of redisplay performance on Windows

[Jason Rumney]

Chong Yidong wrote:

>> There may also be a problem with the setting of
>> row->contains_overlapping_glyphs_p on Windows. The above functions
>> should only be called when that is set, but after inserting debugging
>> code I can see them being called frequently even when using fonts that
>> contain no overlapping glyphs (confirmed by further debugging code in
>> w32font_text_metrics).

> 
> But I don't understand why the problem of left_overwriting and
> right_overwriting, if that's indeed the culprit, would be specific to
> Windows.

That is why I suspect there may be a problem with the setting of
row->contains_overlapping_glyphs_p on Windows. We avoid calling those
functions if that variable is not set. It may also be much more
expensive to look up the glyph index points in Windows, that is the case
for obtaining text extents, so it wouldn't surprise me.

Another factor is that we do this all one character at a time, and each
time on Windows we select the font into the current GC, then reselect
the previously set font. This operation is also expensive, so it would
help to have functions in the font backend interface for selecting and
deselecting fonts. I already tried using prepare_face and done_face for
this, but the calls overlap - ie we prepare a second face without
calling done_face for the first.

Re: Analysis of redisplay performance on Windows

[Chong Yidong]

Jason Rumney <jasonr@gnu.org> writes:

> That is why I suspect there may be a problem with the setting of
> row->contains_overlapping_glyphs_p on Windows. We avoid calling those
> functions if that variable is not set. It may also be much more
> expensive to look up the glyph index points in Windows, that is the case
> for obtaining text extents, so it wouldn't surprise me.
>
> Another factor is that we do this all one character at a time, and each
> time on Windows we select the font into the current GC, then reselect
> the previously set font. This operation is also expensive, so it would
> help to have functions in the font backend interface for selecting and
> deselecting fonts. I already tried using prepare_face and done_face for
> this, but the calls overlap - ie we prepare a second face without
> calling done_face for the first.

Could you verify that setting the overlaps argument unconditionally to 1
in draw_glyphs indeed removes the performance problem?  If so, we can
work around this.

Re: Analysis of redisplay performance on Windows

[Jason Rumney]

Chong Yidong wrote:

> Could you verify that setting the overlaps argument unconditionally to 1
> in draw_glyphs indeed removes the performance problem?  If so, we can
> work around this.

Doing this results in a blank frame.  #if 0 around the block that calls
left_overwritten and right_overwritten does not solve the performance
problems completely (redisplay can still not keep up with scrolling,
whereas Emacs 22 can on the same PC), and without that code, the display
becomes garbaged, so I don't think it is worth pursuing this workaround.

Re: Analysis of redisplay performance on Windows

[Chong Yidong]

Jason Rumney <jasonr@gnu.org> writes:

> Chong Yidong wrote:
>
>> Could you verify that setting the overlaps argument unconditionally to 1
>> in draw_glyphs indeed removes the performance problem?  If so, we can
>> work around this.
>
> Doing this results in a blank frame.  #if 0 around the block that calls
> left_overwritten and right_overwritten does not solve the performance
> problems completely (redisplay can still not keep up with scrolling,
> whereas Emacs 22 can on the same PC), and without that code, the display
> becomes garbaged, so I don't think it is worth pursuing this workaround.

I wasn't suggesting this as a final solution, just as a starting point
to look for the solution.

What you wrote seems to imply that left_overwritten and
right_overwritten aren't really the problem; they have a performance
impact simply because they cause more glyphs to be drawn (i.e., for
redrawing overwritten glyphs).  But the ultimate problem is that drawing
glyphs is a much slower operation, compared to GNU/Linux.  The question
is, what's the reason for this slowness, and can we fix it?

Re: Analysis of redisplay performance on Windows

[Jason Rumney]

Chong Yidong wrote:
> Jason Rumney <jasonr@gnu.org> writes:

> What you wrote seems to imply that left_overwritten and
> right_overwritten aren't really the problem; they have a performance
> impact simply because they cause more glyphs to be drawn (i.e., for
> redrawing overwritten glyphs).  But the ultimate problem is that drawing
> glyphs is a much slower operation, compared to GNU/Linux.  The question
> is, what's the reason for this slowness, and can we fix it?

One difference between Emacs 22 and 23 is that we compute glyph indexes
properly in Emacs 23, while on 22 we use unicode code points. Since we
call font->encode_char once per character rather than for a whole run,
the overhead of selecting fonts into the GC is multiplied. As I
suggested in my earlier email, new functions in the font backend
interface to select a font for working with and releasing it when done,
would help, as we could then skip doing this in functions like
encode_char and text_extents.

Re: Analysis of redisplay performance on Windows

[Chong Yidong]

Jason Rumney <jasonr@gnu.org> writes:

> One difference between Emacs 22 and 23 is that we compute glyph
> indexes properly in Emacs 23, while on 22 we use unicode code
> points. Since we call font->encode_char once per character rather than
> for a whole run, the overhead of selecting fonts into the GC is
> multiplied. As I suggested in my earlier email, new functions in the
> font backend interface to select a font for working with and releasing
> it when done, would help, as we could then skip doing this in
> functions like encode_char and text_extents.

Could you suggest precisely what interface we need?  I.e., could you
suggest function names and rought docstrings?

Re: Analysis of redisplay performance on Windows

[Kevin Yu]

[-- Attachment #1: Type: text/plain, Size: 2333 bytes --]

Hi,

On Mon, Jul 28, 2008 at 5:53 AM, Jason Rumney <jasonr@gnu.org> wrote:

> Chong Yidong wrote:
> > Jason Rumney <jasonr@gnu.org> writes:
>
> > What you wrote seems to imply that left_overwritten and
> > right_overwritten aren't really the problem; they have a performance
> > impact simply because they cause more glyphs to be drawn (i.e., for
> > redrawing overwritten glyphs).  But the ultimate problem is that drawing
> > glyphs is a much slower operation, compared to GNU/Linux.  The question
> > is, what's the reason for this slowness, and can we fix it?
>
> One difference between Emacs 22 and 23 is that we compute glyph indexes
> properly in Emacs 23, while on 22 we use unicode code points. Since we
> call font->encode_char once per character rather than for a whole run,
> the overhead of selecting fonts into the GC is multiplied. As I
> suggested in my earlier email, new functions in the font backend
> interface to select a font for working with and releasing it when done,
> would help, as we could then skip doing this in functions like
> encode_char and text_extents.


I have tried to comment out the font selecting and restoring code in
w32font_encode_char(so using the default font), but the issue still exists.

Here's my analysis, anyway it may be wrong.

When you hold down "C-n" at the bottom line of window you will notice that
half of the screen is updated and half of it left blank. The rest will be
updated when you release the key. It seems like at that time emacs is busy
with handling user input other than redisplay after scrolling. In other
words Emacs hangs the redisplay routine between scrolling and updating other
parts. It's unacceptable. I have trace the code and find that
scrolling_window in the function update_window almost never returns 1, so
emacs have the chance to process user input when redisplay.

But the scrolling job is done by scrolling_window when it returns 1. It
confuses me a lot. At last I found that the x_scroll_run function is also
called by some subroutine of function internal_condition_case_1 in file
xdisp.c line 11895. This function scrolls part of the window back, and then
emacs get the chance to handle user input in update_window? Is that true?

Anyway, all the above should be the same on all platform why it lags on
windows? I haven't traced it on Linux.

[-- Attachment #2: Type: text/html, Size: 2842 bytes --]

Re: Analysis of redisplay performance on Windows

[Adrian Robert]

Chong Yidong <cyd <at> stupidchicken.com> writes:

> 
> Jason Rumney <jasonr <at> gnu.org> writes:
> 
> > As I suggested in my earlier email, new functions in the
> > font backend interface to select a font for working with and releasing
> > it when done, would help, as we could then skip doing this in
> > functions like encode_char and text_extents.

In the NS font driver (nsfont.m) these two functions cache info
for each font by block of 256 (stored in nsfont_info -- nsterm.h).
This made a significant different in rendering speed when I
implemented it, and the memory cost is not high unless lots of different
char ranges are being rendered in lots of different fonts.  Moving this code
up to font.c would be another option to consider.

Re: Analysis of redisplay performance on Windows

[YAMAMOTO Mitsuharu]

>>>>> On Sun, 27 Jul 2008 22:53:47 +0100, Jason Rumney <jasonr@gnu.org> said:

> One difference between Emacs 22 and 23 is that we compute glyph
> indexes properly in Emacs 23, while on 22 we use unicode code
> points. Since we call font->encode_char once per character rather
> than for a whole run, the overhead of selecting fonts into the GC is
> multiplied.

According to the document below, Uniscribe seems to provide some
mechanism to defer heavy operations such as get_frame_dc and
SelectObject.

  http://www.microsoft.com/typography/developers/uniscribe/uniscribe.htm#SCRIPT_CACHE

I'm not sure if this retrying with E_PENDING solves the performance
problem on Windows with Uniscribe.  But I think it's worth trying
before resorting to platform-independent changes because the
performance problem is not found so far in other platforms including
my local Core Text font-backend driver mentioned in
http://lists.gnu.org/archive/html/emacs-devel/2008-02/msg02186.html.

				     YAMAMOTO Mitsuharu
				mituharu@math.s.chiba-u.ac.jp

Re: Analysis of redisplay performance on Windows

[Chong Yidong]

Adrian Robert <Adrian.B.Robert@gmail.com> writes:

> In the NS font driver (nsfont.m) these two functions cache info for
> each font by block of 256 (stored in nsfont_info -- nsterm.h).  This
> made a significant different in rendering speed when I implemented it,
> and the memory cost is not high unless lots of different char ranges
> are being rendered in lots of different fonts.  Moving this code up to
> font.c would be another option to consider.

If we go this route, it's probably faster to reimplement this cache
separately for w32, using the NS code as a guide and keeping it as close
as possible.  Working with the platform-independent code, you'd have to
worry about screwing things up on other platforms.  We can always
consolidate/refactor the code in the next development cycle.

Handa, do you have any comments about the nsfont_info mechanism that
Adrian pointed to?

Re: Analysis of redisplay performance on Windows

[Jason Rumney]

Chong Yidong wrote:
> Jason Rumney <jasonr@gnu.org> writes:
> 
>> As I suggested in my earlier email, new functions in the
>> font backend interface to select a font for working with and releasing
>> it when done, would help, as we could then skip doing this in
>> functions like encode_char and text_extents.
> 
> Could you suggest precisely what interface we need?  I.e., could you
> suggest function names and rough docstrings?

/* Optional.
   Begin using a font exclusively.
   Backends may setup the FONT for use on frame F here so that it
   does not need setting up in every call to the encode_char,
   text_metrics or draw functions.  The font remains current
   until done_font is called.  */
   functions.
void (*use_font) P_ ((FRAME_PTR f, struct font *font));

/* Optional.
   Finish using a font exclusively.
   Backends may undo the actions of use_font here.  */
void (*done_font) P_ ((FRAME_PTR f, struct font *font));

Re: Analysis of redisplay performance on Windows

[YAMAMOTO Mitsuharu]

>>>>> On Mon, 28 Jul 2008 13:24:47 +0900, YAMAMOTO Mitsuharu <mituharu@math.s.chiba-u.ac.jp> said:

>>>>> On Sun, 27 Jul 2008 22:53:47 +0100, Jason Rumney <jasonr@gnu.org> said:
>> One difference between Emacs 22 and 23 is that we compute glyph
>> indexes properly in Emacs 23, while on 22 we use unicode code
>> points. Since we call font->encode_char once per character rather
>> than for a whole run, the overhead of selecting fonts into the GC
>> is multiplied.

> According to the document below, Uniscribe seems to provide some
> mechanism to defer heavy operations such as get_frame_dc and
> SelectObject.

>   http://www.microsoft.com/typography/developers/uniscribe/uniscribe.htm#SCRIPT_CACHE

The following document might be better.

  http://msdn.microsoft.com/en-us/library/ms776490.aspx

  Caching

  Uniscribe saves Unicode-to-glyph (cmap) mappings, glyph widths, and
  OpenType script shaping tables. A handle to the tables for a
  particular font of a particular size is called a "script
  cache". Many Uniscribe functions call for both an device context
  handle parameter and a SCRIPT_CACHE parameter. These functions look
  first for information through the script cache, using the device
  context only when required tables are not already cached.
  (snip)

  For ScriptShape and ScriptPlace, it is valid for the application to
  pass a null device context. Most often the call will succeed, as
  required tables are already cached. If the shaping or placement
  requires access to a device context, ScriptShape or ScriptPlace
  returns immediately with the E_PENDING error code. Then the
  application must select the font in the device context. For most
  applications, this helps performance by avoiding repeated
  preparation of a device context handle with calls to SelectObject.

				     YAMAMOTO Mitsuharu
				mituharu@math.s.chiba-u.ac.jp

Re: Analysis of redisplay performance on Windows

[Jason Rumney]

YAMAMOTO Mitsuharu wrote:

>> According to the document below, Uniscribe seems to provide some
>> mechanism to defer heavy operations such as get_frame_dc and
>> SelectObject.

Yes, that seems to work if we switch to using uniscribe for encoding
characters. Since the gdi backend is only used for bitmap fonts and
older versions of Windows, I've switched off glyph indexing there for a
similar performance improvement. It hasn't had as bad an effect as I
expected with false positives when detecting support for a character.