Re: [PATCH] Faster text rendering by optimizing font glyph lookup

[Felix Zielcke]

Am Freitag, den 24.07.2009, 23:17 +0200 schrieb Felix Zielcke:
> Am Donnerstag, den 11.06.2009, 23:31 +0200 schrieb Vladimir 'phcoder'
> Serbinenko:
> > On Thu, Jun 11, 2009 at 12:28 PM, Felix Zielcke<address@hidden> wrote:
> > > Am Montag, den 09.02.2009, 08:24 -0800 schrieb Colin D Bennett:
> > >> On Mon, 9 Feb 2009 15:11:16 +0100
> > >> Robert Millan <address@hidden> wrote:
> > >>
> > >> > On Sun, Feb 08, 2009 at 01:49:53PM -0800, Colin D Bennett wrote:
> > >> > > This patch greatly—*tremendously*, even, if higher-numbered Unicode
> > >> > > characters are used—speeds up retrieving a glyph for a particular
> > >> > > Unicode character.  This makes text rendering in general much faster.
> > >> > >
> > >> > > My text benchmark shows the new text rendering speed is somewhere 
> > >> > > from
> > >> > > 2.6x to 31x of the previous speed.  Basically, PFF2 font files are 
> > >> > > now
> > >> > > required to have the character index ordered in ascending order of 
> > >> > > code
> > >> > > point.
> > >> > >
> > >> > > Fonts created by 'grub-mkfont' already satisfy this requirement.  
> > >> > > Fonts
> > >> > > created by my old Java 'fonttool' do not, and cannot be used any 
> > >> > > longer.
> > >> > >
> > >> > > The font loader verifies that fonts fulfill the character ordering
> > >> > > requirement, refusing to load invalid fonts, but the primary change 
> > >> > > is
> > >> > > in the 'find_glyph()' function, which now uses a binary search rather
> > >> > > than a linear search to find the glyph.
> > >> >
> > >> > Very nice!
> > >> >
> > >> > With this patch, how does retrieving glyphs from the complete unicode 
> > >> > font
> > >> > compare to retrieving glyphs (without the patch) from the ascii ascii 
> > >> > one?
> > >>
> > >> Here is the result of my benchmark with two kinds of text:
> > >> (1) 104 characters of ASCII English text, and
> > >> (2) 104 Unicode characters randomly selected from the characters in
> > >>     unifont, uniformly distributed over all 61050 characters in the
> > >>     font.
> > >>
> > >> Also, I ran the tests with both the 'ascii.pf2' and 'unicode.pf2' font
> > >> files generated by GRUB's Makefile.  Here are the results:
> > >>
> > >> ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
> > >> 9 February 2009 videotest bench, text rendering
> > >> benchmark 640x480 resolution
> > >>                               ASCII Text  Unicode Text
> > >> Algorithm       Unifont used   (Chars/s)   (Chars/s)
> > >> --------------- ------------- ----------  ------------
> > >> Linear search   ASCII Font      255113       12098 [1]
> > >> Linear search   Unicode Font    250874       23068 [2]
> > >> Binary search   ASCII Font      255746       96231 [1]
> > >> Binary search   Unicode Font    255113      194741 [2]
> > >>
> > >> [1] Note that using the ASCII font for Unicode text results in a
> > >>     performance hit because the grub_font_draw_string() function will
> > >>     use font fallback to search for the missing glyphs in another
> > >>     font.  I had other fonts loaded while running the benchmark, so
> > >>     GRUB had to scan them for the missing characters.
> > >>
> > >> [2] These numbers, for full Unicode text with the full unifont, show
> > >>     the improvement in worst-case performance when using the binary
> > >>     search versus linear search.
> > >> ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
> > >>
> > >> Note that most of the time is now spent actually rendering the bitmaps
> > >> on screen (instead of retrieving glyphs from the font), which actually
> > >> takes longer for the Unicode text because many of the glyphs are wider
> > >> than the English ASCII characters.
> > >>
> > >> (BTW, is there any way to run GRUB in a profiler?  I'd like to know
> > >> where the graphics performance bottlenecks are.)
> > >>
> > >> > Can we make unicode font the default now?
> > >>
> > >> I think so.  Using the full Unicode font does not seem to have a
> > >> significant effect on rendering speed now.  I will commit the patch if
> > >> it looks OK to you.
> > >>
> > >
> > > Now that Vladimir finally commited this, should we make it now the
> > > default or not?
> > I think we can make unicode fonts default now. Don't get too
> > overexcited though: we still lack ligatures. I don't know if composing
> > accents work and no bidi.But this subset is already enough to support
> > all European languages, Chinese, Korean and Japanese as long
> > characters are precomposed
> 
> So if there still won't come up objections against this, then I'll do
> the change, then at least an Ubuntu bug report can be closed.
> 
Ah just read now the comment in grub-mkconfig_lib.in, which complains
about loading speed not rendering.
In qemu there's a very small delay in loading unicode.pf2
ascii.pf2 loads instantly.
But I think that's acceptable or not?

-- 
Felix Zielcke
Proud Debian Maintainer