reducing equality tests in displaying text

reducing equality tests in displaying text

[YAMAMOTO Mitsuharu]

I experimented with some performance tool and noticed that there were
frequent equality tests in displaying text.  I think most of them can
safely be reduced.

1. Each call of assoc_no_quit (charset,_encoding_charset_alist) in
   fontset.c can be replaced with assq_no_quit because
   Vfont_encoding_charset_alist is a symbol-keyed alist.

2. Also in fontset.c:

   472	  if (c >= 0)
   473	    font_group = char_table_ref_and_range (base_fontset, c, &from, &to);
   474	  else
   475	    font_group = FONTSET_FALLBACK (base_fontset);
   476	  if (NILP (font_group))
   477	    return Qnil;

   If `font_group' becomes Qnil in line 473, `from' and `to' are not
   used at all.  So the most of the task of char_table_ref_and_range
   is wasted for this case.  Because font_group == Qnil case happens
   frequently, the char_table_ref_and_range call should be avoided for
   this case.

3. Despite its argument name, `has_char' functions in font backend
   drivers are mostly called for a font object instead of a font
   entity.  Some font backend drivers could make use of this fact:
   e.g., ftfont_has_char can avoid frequent assoc_no_quit calls if
   struct ft_font has a reference to fc_charset in ft_face_cache.

BTW, I suspect Ffontset_font is broken.  I couldn't get any meaningful
result from (fontset-font t ?a), for example.

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

Re: reducing equality tests in displaying text

[Kenichi Handa]

In article <wlmydihibf.wl%mituharu@math.s.chiba-u.ac.jp>, YAMAMOTO Mitsuharu <mituharu@math.s.chiba-u.ac.jp> writes:

> I experimented with some performance tool and noticed that there were
> frequent equality tests in displaying text.  I think most of them can
> safely be reduced.

Thank you for the report.

> 1. Each call of assoc_no_quit (charset,_encoding_charset_alist) in
>    fontset.c can be replaced with assq_no_quit because
>    Vfont_encoding_charset_alist is a symbol-keyed alist.

Yes, just fixed.

> 2. Also in fontset.c:

>    472	  if (c >= 0)
>    473	    font_group = char_table_ref_and_range (base_fontset, c, &from, &to);
>    474	  else
>    475	    font_group = FONTSET_FALLBACK (base_fontset);
>    476	  if (NILP (font_group))
>    477	    return Qnil;

>    If `font_group' becomes Qnil in line 473, `from' and `to' are not
>    used at all.  So the most of the task of char_table_ref_and_range
>    is wasted for this case.  Because font_group == Qnil case happens
>    frequently, the char_table_ref_and_range call should be avoided for
>    this case.

When font_group is Qnil, in most cases, SUB_CHAR_TABLE_P
(table) is zero.  Thus the calculation of FROM and TO must
not be that slow.  Did you really see the bottle-neck of the
performance here?

> 3. Despite its argument name, `has_char' functions in font backend
>    drivers are mostly called for a font object instead of a font
>    entity.  Some font backend drivers could make use of this fact:
>    e.g., ftfont_has_char can avoid frequent assoc_no_quit calls if
>    struct ft_font has a reference to fc_charset in ft_face_cache.

I've just fixed ftfont_has_char to use FT_Get_Char_Index
directly.

> BTW, I suspect Ffontset_font is broken.  I couldn't get any meaningful
> result from (fontset-font t ?a), for example.

I fixed it too.

---
Kenichi Handa
handa@m17n.org

Re: reducing equality tests in displaying text

[YAMAMOTO Mitsuharu]

>>>>> On Tue, 27 Jan 2009 14:26:42 +0900, Kenichi Handa <handa@m17n.org> said:

>> 1. Each call of assoc_no_quit (charset,_encoding_charset_alist) in
>> fontset.c can be replaced with assq_no_quit because
>> Vfont_encoding_charset_alist is a symbol-keyed alist.

> Yes, just fixed.

There's another occurrence in font_for_char.

>> 2. Also in fontset.c:

>> If `font_group' becomes Qnil in line 473, `from' and `to' are not
>> used at all.  So the most of the task of char_table_ref_and_range
>> is wasted for this case.  Because font_group == Qnil case happens
>> frequently, the char_table_ref_and_range call should be avoided for
>> this case.

> When font_group is Qnil, in most cases, SUB_CHAR_TABLE_P (table) is
> zero.  Thus the calculation of FROM and TO must not be that slow.
> Did you really see the bottle-neck of the performance here?

Below is a part of the result of an experiment (after your change)
with Shark.app on Mac OS X 10.5.6. I scrolled up and down the Japanese
tutorial.  Emacs is compiled with Xft support and the default CFLAGS
(-g -O2 -Wno-pointer-sign).

	957.8 ms	emacs	mark_object	
	194.3 ms	emacs	mark_vectorlike	
	147.9 ms	emacs	Fgarbage_collect	
	145.3 ms	libfreetype.6.dylib	tt_cmap4_char_map_binary	
	108.9 ms	emacs	char_table_ref_and_range	
	98.8 ms	emacs	sub_char_table_ref_and_range	
	53.5 ms	emacs	x_produce_glyphs	
	49.4 ms	emacs	fontset_find_font	
	36.3 ms	emacs	char_table_ref	
	31.3 ms	libXft.2.dylib	XftGlyphExtents	
	31.2 ms	emacs	get_next_display_element	
	29.2 ms	emacs	face_for_char	
	28.4 ms	emacs	display_count_lines	
	28.4 ms	mach_kernel	ml_set_interrupts_enabled	
	28.2 ms	emacs	hash_lookup	
	24.2 ms	emacs	assq_no_quit	
	24.2 ms	emacs	sub_char_table_ref	
	23.3 ms	emacs	validate_interval_range	
	23.2 ms	emacs	sort_overlays	
	22.3 ms	libXft.2.dylib	XftFontCheckGlyph	
	22.2 ms	emacs	move_it_in_display_line_to	
	21.3 ms	emacs	xftfont_text_extents	
	20.3 ms	libXft.2.dylib	XftCharIndex	

>> 3. Despite its argument name, `has_char' functions in font backend
>> drivers are mostly called for a font object instead of a font
>> entity.  Some font backend drivers could make use of this fact:
>> e.g., ftfont_has_char can avoid frequent assoc_no_quit calls if
>> struct ft_font has a reference to fc_charset in ft_face_cache.

> I've just fixed ftfont_has_char to use FT_Get_Char_Index directly.

But FT_Get_Char_Index is much slower than FcCharSetHasChar.
`tt_cmap4_char_map_binary' in the above table is called from
FT_Get_Char_Index.

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

Re: reducing equality tests in displaying text

[Kenichi Handa]

In article <wlpri8l24n.wl%mituharu@math.s.chiba-u.ac.jp>, YAMAMOTO Mitsuharu <mituharu@math.s.chiba-u.ac.jp> writes:

>>>>>> On Tue, 27 Jan 2009 14:26:42 +0900, Kenichi Handa <handa@m17n.org> said:
>>> 1. Each call of assoc_no_quit (charset,_encoding_charset_alist) in
>>> fontset.c can be replaced with assq_no_quit because
>>> Vfont_encoding_charset_alist is a symbol-keyed alist.

> > Yes, just fixed.

> There's another occurrence in font_for_char.

Oops, just fixed.

> > When font_group is Qnil, in most cases, SUB_CHAR_TABLE_P (table) is
> > zero.  Thus the calculation of FROM and TO must not be that slow.
> > Did you really see the bottle-neck of the performance here?

> Below is a part of the result of an experiment (after your change)
> with Shark.app on Mac OS X 10.5.6. I scrolled up and down the Japanese
> tutorial.  Emacs is compiled with Xft support and the default CFLAGS
> (-g -O2 -Wno-pointer-sign).

> 	957.8 ms	emacs	mark_object	
> 	194.3 ms	emacs	mark_vectorlike	
> 	147.9 ms	emacs	Fgarbage_collect	
> 	145.3 ms	libfreetype.6.dylib	tt_cmap4_char_map_binary	
> 	108.9 ms	emacs	char_table_ref_and_range	
> 	98.8 ms	emacs	sub_char_table_ref_and_range	

Are you sure that those calls mostly return nil?  Could you
please check if this patch surely improve the performance?

*** fontset.c.~1.154.~	2009-01-28 15:14:18.000000000 +0900
--- fontset.c	2009-01-28 15:50:37.000000000 +0900
***************
*** 470,476 ****
      return font_group;
    base_fontset = FONTSET_BASE (fontset);
    if (c >= 0)
!     font_group = char_table_ref_and_range (base_fontset, c, &from, &to);
    else
      font_group = FONTSET_FALLBACK (base_fontset);
    if (NILP (font_group))
--- 470,480 ----
      return font_group;
    base_fontset = FONTSET_BASE (fontset);
    if (c >= 0)
!     {
!       font_group = char_table_ref (base_fontset, c);
!       if (! NILP (font_group))
! 	font_group = char_table_ref_and_range (base_fontset, c, &from, &to);
!     }
    else
      font_group = FONTSET_FALLBACK (base_fontset);
    if (NILP (font_group))

>>> 3. Despite its argument name, `has_char' functions in font backend
>>> drivers are mostly called for a font object instead of a font
>>> entity.  Some font backend drivers could make use of this fact:
>>> e.g., ftfont_has_char can avoid frequent assoc_no_quit calls if
>>> struct ft_font has a reference to fc_charset in ft_face_cache.

> > I've just fixed ftfont_has_char to use FT_Get_Char_Index directly.

> But FT_Get_Char_Index is much slower than FcCharSetHasChar.
> `tt_cmap4_char_map_binary' in the above table is called from
> FT_Get_Char_Index.

Hmmm.  I've just found that Xft has the function
XftCharExists now.  I remember that it didn't exist in a
rather old vesion.  Does your Xft library have this
function?

---
Kenichi Handa
handa@m17n.org

Re: reducing equality tests in displaying text

[YAMAMOTO Mitsuharu]

>>>>> On Wed, 28 Jan 2009 16:03:01 +0900, Kenichi Handa <handa@m17n.org> said:

>> > When font_group is Qnil, in most cases, SUB_CHAR_TABLE_P (table) is
>> > zero.  Thus the calculation of FROM and TO must not be that slow.
>> > Did you really see the bottle-neck of the performance here?

>> Below is a part of the result of an experiment (after your change)
>> with Shark.app on Mac OS X 10.5.6. I scrolled up and down the Japanese
>> tutorial.  Emacs is compiled with Xft support and the default CFLAGS
>> (-g -O2 -Wno-pointer-sign).

>> 957.8 ms	emacs	mark_object	
>> 194.3 ms	emacs	mark_vectorlike	
>> 147.9 ms	emacs	Fgarbage_collect	
>> 145.3 ms	libfreetype.6.dylib	tt_cmap4_char_map_binary	
>> 108.9 ms	emacs	char_table_ref_and_range	
>> 98.8 ms	emacs	sub_char_table_ref_and_range	

> Are you sure that those calls mostly return nil?  Could you
> please check if this patch surely improve the performance?

Here is the result.

	750.9 ms	emacs	mark_object	
	153.4 ms	libfreetype.6.dylib	tt_cmap4_char_map_binary	
	126.7 ms	emacs	Fgarbage_collect	
	106.8 ms	emacs	mark_vectorlike	
	64.8 ms	emacs	x_produce_glyphs	
	61.5 ms	emacs	char_table_ref	
	47.5 ms	emacs	fontset_find_font	
	33.3 ms	emacs	get_next_display_element	
	30.3 ms	emacs	face_for_char	
	29.3 ms	libXft.2.dylib	XftGlyphExtents	
	29.3 ms	emacs	assq_no_quit	
	29.3 ms	emacs	find_interval	
	27.3 ms	emacs	hash_lookup	
	26.3 ms	emacs	make_uninit_multibyte_string	
	25.2 ms	emacs	sub_char_table_ref	
	24.4 ms	mach_kernel	ml_set_interrupts_enabled	
	23.2 ms	emacs	next_element_from_buffer	
	22.3 ms	emacs	display_count_lines	
	20.2 ms	emacs	Fcons	
	19.2 ms	libXft.2.dylib	XftCharIndex	

>>>> 3. Despite its argument name, `has_char' functions in font backend
>>>> drivers are mostly called for a font object instead of a font
>>>> entity.  Some font backend drivers could make use of this fact:
>>>> e.g., ftfont_has_char can avoid frequent assoc_no_quit calls if
>>>> struct ft_font has a reference to fc_charset in ft_face_cache.

>> > I've just fixed ftfont_has_char to use FT_Get_Char_Index directly.

>> But FT_Get_Char_Index is much slower than FcCharSetHasChar.
>> `tt_cmap4_char_map_binary' in the above table is called from
>> FT_Get_Char_Index.

> Hmmm.  I've just found that Xft has the function
> XftCharExists now.  I remember that it didn't exist in a
> rather old vesion.  Does your Xft library have this
> function?

It exists.  But it simply uses the `charset' member in struct _XftFont:

_X_EXPORT FcBool
XftCharExists (Display	    *dpy,
	       XftFont	    *pub,
	       FcChar32    ucs4)
{
    if (pub->charset)
	return FcCharSetHasChar (pub->charset, ucs4);
    return FcFalse;
}

Is there any reason you prefer an Xft-level routine to
fontconfig-level?  By adding some `FcCharSet *' member in struct
ftfont as I said, you don't need to "override" `has_char' function in
the xft driver, and the ftx driver can also benefit from it for free.

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

Re: reducing equality tests in displaying text

[Kenichi Handa]

In article <wl1vun23ss.wl%mituharu@math.s.chiba-u.ac.jp>, YAMAMOTO Mitsuharu <mituharu@math.s.chiba-u.ac.jp> writes:

> > Are you sure that those calls mostly return nil?  Could you
> > please check if this patch surely improve the performance?

> Here is the result.

> 	750.9 ms	emacs	mark_object	
> 	153.4 ms	libfreetype.6.dylib	tt_cmap4_char_map_binary	
> 	126.7 ms	emacs	Fgarbage_collect	
> 	106.8 ms	emacs	mark_vectorlike	
> 	64.8 ms	emacs	x_produce_glyphs	
> 	61.5 ms	emacs	char_table_ref	
> 	47.5 ms	emacs	fontset_find_font	
> 	33.3 ms	emacs	get_next_display_element	
> 	30.3 ms	emacs	face_for_char	
> 	29.3 ms	libXft.2.dylib	XftGlyphExtents	
> 	29.3 ms	emacs	assq_no_quit	
> 	29.3 ms	emacs	find_interval	
> 	27.3 ms	emacs	hash_lookup	
> 	26.3 ms	emacs	make_uninit_multibyte_string	
> 	25.2 ms	emacs	sub_char_table_ref	

Ummm, this result is surprising, but I found a bug in
fontset_get_font_group that is the culprit of so many calls
of char_table_ref_and_range.  I simply forgot to record the
result of previous call in the case of nil.  I should have
noticed it when you wrote that from and to were never used
in such a case.  :-(

Anyway, please try the new code.  I think that the calls of
char_rable_ref itself is reduced.

> > Hmmm.  I've just found that Xft has the function
> > XftCharExists now.  I remember that it didn't exist in a
> > rather old vesion.  Does your Xft library have this
> > function?

> It exists.  But it simply uses the `charset' member in struct _XftFont:

> _X_EXPORT FcBool
> XftCharExists (Display	    *dpy,
> 	       XftFont	    *pub,
> 	       FcChar32    ucs4)
> {
>     if (pub->charset)
> 	return FcCharSetHasChar (pub->charset, ucs4);
>     return FcFalse;
> }

> Is there any reason you prefer an Xft-level routine to
> fontconfig-level?  By adding some `FcCharSet *' member in struct
> ftfont as I said, you don't need to "override" `has_char' function in
> the xft driver, and the ftx driver can also benefit from it for free.

In ftfont.c, fontconfig is used only to list fonts.  The
other actual font driving is done directly by freetype.
Currently, the exception is ftfont_has_char, but I want to
find a way to avoid using fontconfig here too.

The reason why I want to keep this separation is that
listing fonts and using a font is different tasks, and, in
the future, I want to allow different combinations of them.

On the other hand, as Xft is so tightly combined with
fontconfig, and it already has `charset' member in XftFont
structure, it is nonsense not to utilize it.

---
Kenichi Handa
handa@m17n.org

Re: reducing equality tests in displaying text

[YAMAMOTO Mitsuharu]

>>>>> On Thu, 29 Jan 2009 09:37:19 +0900, Kenichi Handa <handa@m17n.org> said:

> Ummm, this result is surprising, but I found a bug in
> fontset_get_font_group that is the culprit of so many calls of
> char_table_ref_and_range.  I simply forgot to record the result of
> previous call in the case of nil.  I should have noticed it when you
> wrote that from and to were never used in such a case.  :-(

> Anyway, please try the new code.  I think that the calls of
> char_rable_ref itself is reduced.

Yes, it gives a good result.  Thanks.

	675.1 ms	emacs	mark_object	
	164.5 ms	libfreetype.6.dylib	tt_cmap4_char_map_binary	
	133.0 ms	emacs	mark_vectorlike	
	117.6 ms	emacs	Fgarbage_collect	
	41.5 ms	emacs	x_produce_glyphs	
	41.4 ms	emacs	char_table_ref	
	33.3 ms	emacs	fontset_find_font	
	32.3 ms	emacs	get_next_display_element	
	29.5 ms	emacs	display_count_lines	
	29.3 ms	emacs	assq_no_quit	
	28.3 ms	emacs	face_for_char	
	24.3 ms	mach_kernel	ml_set_interrupts_enabled	
	24.3 ms	libXft.2.dylib	XftCharIndex	
	24.3 ms	emacs	append_glyph	
	24.3 ms	libXft.2.dylib	XftGlyphExtents	
	24.2 ms	emacs	hash_lookup	
	23.2 ms	emacs	sub_char_table_ref	
	22.3 ms	emacs	find_interval	
	22.2 ms	emacs	Fcons	
	22.2 ms	emacs	sort_overlays	

>> Is there any reason you prefer an Xft-level routine to
>> fontconfig-level?  By adding some `FcCharSet *' member in struct
>> ftfont as I said, you don't need to "override" `has_char' function
>> in the xft driver, and the ftx driver can also benefit from it for
>> free.

> In ftfont.c, fontconfig is used only to list fonts.  The other
> actual font driving is done directly by freetype.  Currently, the
> exception is ftfont_has_char, but I want to find a way to avoid
> using fontconfig here too.

> The reason why I want to keep this separation is that listing fonts
> and using a font is different tasks, and, in the future, I want to
> allow different combinations of them.

I don't think it's unnatural for font listing layers to provide
`has_char' functionality, because that layer already involves
supported charset inclusion test in its core part.

> On the other hand, as Xft is so tightly combined with fontconfig,
> and it already has `charset' member in XftFont structure, it is
> nonsense not to utilize it.

Of course, it makes sense for font driving layers to provide
alternative implementations of `has_char', if it is more efficient
than the underlying counterpart in the font listing layer.

Another (maybe cleaner) design would be to separate the current
`has_char' function into that for font entities (font listing layer)
and that for font objects (font driving layer).

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

Re: reducing equality tests in displaying text

[Kenichi Handa]

In article <wleiymyjdd.wl%mituharu@math.s.chiba-u.ac.jp>, YAMAMOTO Mitsuharu <mituharu@math.s.chiba-u.ac.jp> writes:

> Another (maybe cleaner) design would be to separate the current
> `has_char' function into that for font entities (font listing layer)
> and that for font objects (font driving layer).

Ah, it seems that is a good idea.  I put that in my todo list.

---
Kenichi Handa
handa@m17n.org

Re: reducing equality tests in displaying text

[Jason Rumney]

Kenichi Handa wrote:
>> Another (maybe cleaner) design would be to separate the current
>> `has_char' function into that for font entities (font listing layer)
>> and that for font objects (font driving layer).
>>     
>
> Ah, it seems that is a good idea.  I put that in my todo list.
>   
Isn't encode_char sufficient for font_object use?  It will return 
FONT_INVALID_CODE if the font does not have that char.

Re: reducing equality tests in displaying text

[Kenichi Handa]

In article <49811688.4030309@gnu.org>, Jason Rumney <jasonr@gnu.org> writes:

> Kenichi Handa wrote:
>>> Another (maybe cleaner) design would be to separate the current
>>> `has_char' function into that for font entities (font listing layer)
>>> and that for font objects (font driving layer).
>>> 
> >
> > Ah, it seems that is a good idea.  I put that in my todo list.
> >   
> Isn't encode_char sufficient for font_object use?  It will return 
> FONT_INVALID_CODE if the font does not have that char.

It depends.  For instance, Xft has two separate functions
XftCharExists and XftCharIndex, and it seems that the former
is faster.

---
Kenichi Handa
handa@m17n.org

Re: reducing equality tests in displaying text

[YAMAMOTO Mitsuharu]

I found another scenario of excessive equality tests in displaying
text.  It can be observed with scrolling the Chinese-BIG5 tutorial: it
is much more sluggish than scrolling the Japanese tutorial, for
example.

I suspect something is wrong in the following part in fontset.c:

   581	      if (INTEGERP (RFONT_DEF_FACE (elt))
   582		  && XINT (AREF (elt, 1)) < 0)
   583		/* We couldn't open this font last time.  */
   584		continue;

where AREF (elt, 1) means RFONT_DEF_FONT_DEF (elt).

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

Re: reducing equality tests in displaying text

[Kenichi Handa]

In article <wl1vtscoft.wl%mituharu@math.s.chiba-u.ac.jp>, YAMAMOTO Mitsuharu <mituharu@math.s.chiba-u.ac.jp> writes:

> I suspect something is wrong in the following part in fontset.c:

>    581	      if (INTEGERP (RFONT_DEF_FACE (elt))
>    582		  && XINT (AREF (elt, 1)) < 0)
>    583		/* We couldn't open this font last time.  */
>    584		continue;

> where AREF (elt, 1) means RFONT_DEF_FONT_DEF (elt).

You are right.  I've just fixed it.

---
Kenichi Handa
handa@m17n.org