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

[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.

Regards,
Colin

signature.asc
Description: PGP signature