Skip to contentSkip to conversation

Faster text rendering by optimizing font glyph lookup

PATCH In review Colin D Bennett 5 participants 15 messages Feb 8, 2009 – Jul 26, 2009

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Faster text rendering by optimizing font glyph lookup

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.

Regards,
Colin

=== modified file 'ChangeLog'

ChangeLog +11 -0
@@ -1,3 +1,14 @@
+2009-02-08  Colin D Bennett  <[email protected]>
+
+	Optimized font character lookup using binary search instead of linear
+	search.  Fonts now are required to have the character index ordered by
+	code point.
+
+	* font/font.c (load_font_index): Verify that fonts have ordered
+	character indices.
+	(find_glyph): Use binary search instead of linear search to find a
+	character in a font.
+
 2009-02-04  Felix Zielcke  <[email protected]>
 
 	util/getroot.c (grub_util_get_grub_dev): Add support for /dev/mdNpN and

=== modified file 'font/font.c'

font.c +32 -8
@@ -249,6 +249,7 @@
                  grub_font *font)
 {
   unsigned i;
+  grub_uint32_t last_code;
 
 #if FONT_DEBUG >= 2
   grub_printf("load_font_index(sect_length=%d)\n", sect_length);
@@ -277,6 +278,8 @@
   grub_printf("num_chars=%d)\n", font->num_chars);
 #endif
 
+  last_code = 0;
+
   /* Load the character index data from the file.  */
   for (i = 0; i < font->num_chars; i++)
     {
@@ -287,6 +290,17 @@
         return 1;
       entry->code = grub_be_to_cpu32 (entry->code);
 
+      /* Verify that characters are in ascending order.  */
+      if (i != 0 && entry->code <= last_code)
+        {
+          grub_error (GRUB_ERR_BAD_FONT,
+                      "Font characters not in ascending order: %u <= %u",
+                      entry->code, last_code);
+          return 1;
+        }
+
+      last_code = entry->code;
+
       /* Read storage flags byte.  */
       if (grub_file_read (file, (char *) &entry->storage_flags, 1) != 1)
         return 1;
@@ -583,15 +597,25 @@
 static struct char_index_entry *
 find_glyph (const grub_font_t font, grub_uint32_t code)
 {
-  grub_uint32_t i;
-  grub_uint32_t len = font->num_chars;
-  struct char_index_entry *table = font->char_index;
-
-  /* Do a linear search.  */
-  for (i = 0; i < len; i++)
+  struct char_index_entry *table;
+  grub_size_t lo;
+  grub_size_t hi;
+  grub_size_t mid;
+
+  /* Do a binary search in `char_index', which is ordered by code point.  */
+  table = font->char_index;
+  lo = 0;
+  hi = font->num_chars - 1;
+
+  while (lo <= hi)
     {
-      if (table[i].code == code)
-        return &table[i];
+      mid = lo + (hi - lo) / 2;
+      if (code < table[mid].code)
+        hi = mid - 1;
+      else if (code > table[mid].code)
+        lo = mid + 1;
+      else
+        return &table[mid];
     }
 
   return 0;
#1 lore raw
Quoted 9 lines · Colin D Bennett

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.

Quoted 7 lines

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?

Can we make unicode font the default now?

Signature · 5 lines
Robert Millan

  The DRM opt-in fallacy: "Your data belongs to us. We will decide when (and
  how) you may access your data; but nobody's threatening your freedom: we
  still allow you to remove your data and not access it at all."
#2 lore raw
Quoted 18 lines · On Mon, 9 Feb 2009 15:11:16 +0100 Robert Millan <[email protected]> wrote:
Quoted 9 lines · Colin D Bennett

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.

Quoted 7 lines

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.

Quoted 4 lines

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

Quoted 1 line

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

#3 lore raw

Am Montag, den 09.02.2009, 08:24 -0800 schrieb Colin D Bennett:

Quoted 62 lines
Quoted 18 lines · On Mon, 9 Feb 2009 15:11:16 +0100 Robert Millan <[email protected]> wrote:
Quoted 9 lines · Colin D Bennett

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.

Quoted 7 lines

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.

Quoted 4 lines

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.

Quoted 9 lines

(BTW, is there any way to run GRUB in a profiler? I'd like to know where the graphics performance bottlenecks are.)

Quoted 1 line

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?

Signature · 1 line
Felix Zielcke
#4 lore raw
Quoted 68 lines · Felix Zielcke

Am Montag, den 09.02.2009, 08:24 -0800 schrieb Colin D Bennett:

Quoted 67 lines
Quoted 18 lines · On Mon, 9 Feb 2009 15:11:16 +0100 Robert Millan <[email protected]> wrote:
Quoted 9 lines · Colin D Bennett

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.

Quoted 7 lines

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.

Quoted 4 lines

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

Quoted 1 line

Can we make unicode font the default now?

Quoted 7 lines
Quoted 4 lines

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

Quoted 10 lines

--
Felix Zielcke

_______________________________________________
Grub-devel mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/grub-devel

Signature · 2 lines
Regards
Vladimir 'phcoder' Serbinenko
#5 lore raw

Am Donnerstag, den 11.06.2009, 23:31 +0200 schrieb Vladimir 'phcoder' Serbinenko:

Quoted 74 lines · Felix Zielcke
Quoted 73 lines

Am Montag, den 09.02.2009, 08:24 -0800 schrieb Colin D Bennett:

Quoted 71 lines
Quoted 18 lines · On Mon, 9 Feb 2009 15:11:16 +0100 Robert Millan <[email protected]> wrote:
Quoted 9 lines · Colin D Bennett

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.

Quoted 7 lines

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.

Quoted 4 lines

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

Quoted 1 line

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.

Quoted 7 lines
Quoted 2 lines

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.

Signature · 1 line
Felix Zielcke
#6 lore raw
Quoted 3 lines · Felix Zielcke

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.

I think it's fine, but is this an upstream change or a debian change? IIRC the default font selection is in grub-mkconfig.

Signature · 5 lines
Robert Millan

  The DRM opt-in fallacy: "Your data belongs to us. We will decide when (and
  how) you may access your data; but nobody's threatening your freedom: we
  still allow you to remove your data and not access it at all."
#7 lore raw

Am Samstag, den 25.07.2009, 18:04 +0200 schrieb Robert Millan:

Quoted 8 lines · Felix Zielcke
Quoted 3 lines

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.

I think it's fine, but is this an upstream change or a debian change? IIRC the default font selection is in grub-mkconfig.

Upstream. There you changed the default from unicode.pff to ascii.pff.

Signature · 2 lines
Felix Zielcke
Proud Debian Maintainer
#8 lore raw
Quoted 7 lines · Felix Zielcke

Am Samstag, den 25.07.2009, 18:04 +0200 schrieb Robert Millan:

Quoted 5 lines · Felix Zielcke
Quoted 3 lines

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.

Quoted 7 lines
Quoted 3 lines

I think it's fine, but is this an upstream change or a debian change? IIRC the default font selection is in grub-mkconfig.

Upstream. There you changed the default from unicode.pff to ascii.pff.

The default font for generating a rescue floppy image should be ascii because the unicode font won't fit.

However, I could not find any font at all on the floppy, and it is probably not required in any environment that supports floppy booting so I am not sure if there is any reason for including it except for easy testing of graphics.

Thanks

Michal

#9 lore raw

Am Sonntag, den 26.07.2009, 10:38 +0200 schrieb Michal Suchanek:

Quoted 13 lines · Felix Zielcke
Quoted 12 lines

Am Samstag, den 25.07.2009, 18:04 +0200 schrieb Robert Millan:

Quoted 8 lines · Felix Zielcke
Quoted 3 lines

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.

I think it's fine, but is this an upstream change or a debian change? IIRC the default font selection is in grub-mkconfig.

Quoted 5 lines
Quoted 2 lines

Upstream. There you changed the default from unicode.pff to ascii.pff.

The default font for generating a rescue floppy image should be ascii because the unicode font won't fit.

The change is just for grub-mkconfig, which isn't at all used by grub-mkrescue.
It would still use ascii.pf2 if there's no unicode.pf2

Quoted 8 lines

However, I could not find any font at all on the floppy, and it is probably not required in any environment that supports floppy booting so I am not sure if there is any reason for including it except for easy testing of graphics.

Thanks

Michal

If anyone wants to have gfxterm on a floppy, he/she could just use grub-mkrescue with --overlay
A custom grub.cfg would be good anyway in that case and then you could just copy ascii.pf2 there too.

Signature · 2 lines
Felix Zielcke
Proud Debian Maintainer
#10 lore raw
In reply to Felix Zielcke

Am Freitag, den 24.07.2009, 23:17 +0200 schrieb Felix Zielcke:

Quoted 78 lines

Am Donnerstag, den 11.06.2009, 23:31 +0200 schrieb Vladimir 'phcoder' Serbinenko:

Quoted 76 lines · Felix Zielcke
Quoted 75 lines

Am Montag, den 09.02.2009, 08:24 -0800 schrieb Colin D Bennett:

Quoted 62 lines
Quoted 18 lines · On Mon, 9 Feb 2009 15:11:16 +0100 Robert Millan <[email protected]> wrote:
Quoted 9 lines · Colin D Bennett

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.

Quoted 7 lines

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.

Quoted 4 lines

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.

Quoted 9 lines

(BTW, is there any way to run GRUB in a profiler? I'd like to know where the graphics performance bottlenecks are.)

Quoted 1 line

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?

Quoted 9 lines
Quoted 5 lines

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?

Signature · 2 lines
Felix Zielcke
Proud Debian Maintainer
#11 lore raw
In reply to Colin D Bennett

Any reason not to merge this patch?

Quoted 27 lines · Colin D Bennett

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.

Regards,
Colin

------------------------------------------------------------------------

_______________________________________________
Grub-devel mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/grub-devel

Signature · 2 lines
Regards
Vladimir 'phcoder' Serbinenko
#12 lore raw
Quoted 1 line · phcoder

Any reason not to merge this patch?

Probably not. Btw does Colin need/have an account?

Signature · 5 lines
Robert Millan

  The DRM opt-in fallacy: "Your data belongs to us. We will decide when (and
  how) you may access your data; but nobody's threatening your freedom: we
  still allow you to remove your data and not access it at all."
#13 lore raw

Am Montag, den 13.04.2009, 15:57 +0200 schrieb Robert Millan:

Quoted 4 lines · phcoder
Quoted 1 line

Any reason not to merge this patch?

Probably not. Btw does Colin need/have an account?

Colin has an account and already commit access.

Signature · 1 line
Felix Zielcke
#14 lore raw
In reply to Colin D Bennett
Quoted 9 lines · Colin D Bennett

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.

Quoted 7 lines

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.

There were no oppositions to this patch and it still applies cleanly (except Changelog). If it's ok with you I'll commit this patch

Quoted 11 lines

Regards,
Colin

_______________________________________________
Grub-devel mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/grub-devel

Signature · 2 lines
Regards
Vladimir 'phcoder' Serbinenko