[HarfBuzz] On optimizing HarfBuzz
Hi,
I happened to look into optimization opportunities in HarfBuzz and these are
my findings:
For very short strings, preparing the shape plan seems to take a significant
portion of the shape() call, so transparently caching the plan as Jonathan and
I agreed we should do, would address that. On the plus side, mutexes (as
would be required for that) seem to have negligible overhead.
For longer text, it's a different story. Seems like, contrary to my
expectation, all the passes we do in hb-ot-shape.cc (getting Unicode
properties, mirroring, cmap mapping, normalization, default positioning, etc)
have really insignificant overhead. This is great.
What *is* a big problem is the actual OpenType lookups themselves. And how
bad that is depends directly on the font. There are fonts with zero OpenType
lookups (eg. Droid Sans), and there are fonts that have over a 100 sublookups
for a simple shape plan (eg. Arabic Typesetting). Seems like, currently we
are being very inefficient for those larger fonts. But even for simpler fonts
with around 20 sublookups (eg. DejaVu Sans) we are doing an awful job. I
tried to understand this, and here are my findings. I think I have a good
grasp on what's causing the slowness. Less so on how to address it, but I
have ideas. Note that Uniscribe doesn't seem to be nearly as affected by the
number of lookups, so there ought to be ways to address this.
To understand, lets see what the main apply() loops for GSUB and GPOS
currently look like:
1 for each lookup {
2for each glyph in buffer {
3 for each sublookup of the lookup {
4switch on the lookup_type {
5 switch on the sublookup_type {
6if glyph in coverage of the sublookup {
7 do lots of work...
}
}
}
}
}
}
Now, *that*'s expensive! Note that the passthrough rate at 6 is very very
low. Ie. most glyphs don't pass the coverage check for most sublookups. But
we do a hell of a lot of work to get to that conclusion. In short, I think we
don't have to worry about speeding up the actual lookup processing. We need
to make to the "first glyph doesn't match" conclusion much much faster.
The actual coverage matching if constrained by the OpenType data-structures
(unless we want to do caching, etc, more on that below). However, for
example, we can get rid of the switching on lines 4 and 5 for most cases. The
way OpenType was originally designed, all sublookup types of all lookup types
had the coverage table offset in the same place. So we can move line 6 to
before line 4. Now, newer additions to the spec (Context subtype 3,
ChainContext subtype 3, and Extension subtype 1) don't have the coverage in
the same place. However, by rewriting the loop at line 2 to handle the 3
cases separately we can save lots of churning. I did an initial take of this
by adding "fast-path" to GSUB/GPOS, but didn't reorder the actual loops. Will
be doing that soon. Also, by simply looking up the coverage table before
looping over each glyph, we save a lot.
For fonts that were slow, I found that they have lots of ChainContext subtype
3. I understand why this is. Unlike the rest of the lookups, each Context
subtype 3 and ChainContext subtype 3 can only match a single sequence. So, if
you have 100 different contextual ligatures, you need 100 subtables... Now,
inspecting Arabic Typesetting, I also found that all the subtables in each
lookup reference the same Coverage table for the first character. (BTW, I
have a vague memory that OTS does not like this.) Currently, we ignore that
and check each glyph against each subtable. We can easily check whether the
Coverage table is the same and skip rechecking.
This much is the easy part. To significantly get faster, we need a way to
avoid the cartesian product of "all glyphs in the buffer" and "all subtables"
somehow. That's were caching comes in, and as one wise programmer once said,
"All programming is an exercise in caching." I have ideas around there too,
but I will harvest the low-hanging fruit before going there.
Hopefully the easy stuff gives us enough boost to let me go back and
concentrate on correctness before we need to optimize again.
Comments?
Cheers,
behdad
___
HarfBuzz mailing list
HarfBuzz@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/harfbuzz
[HarfBuzz] [PATCH] Enhancements for gobject introspection
From: "أحمد المحم�?= =?UTF-8?q?�دي (Ahmed El-Mahmoudy)" * Check for HB_GOBJECT_COMPILATION before failing on private headers * Use introspection autoconf/make stuff. --- configure.ac|2 ++ src/Makefile.am | 24 ++-- src/hb-blob.h |2 +- src/hb-buffer.h |2 +- src/hb-common.h |2 +- src/hb-font.h |2 +- src/hb-ot-layout.h |2 +- src/hb-ot-tag.h |2 +- src/hb-set.h|2 +- src/hb-shape.h |2 +- src/hb-unicode.h|2 +- src/hb-version.h.in |2 +- 12 files changed, 34 insertions(+), 12 deletions(-) diff --git a/configure.ac b/configure.ac index 2fb058f..784c8fe 100644 --- a/configure.ac +++ b/configure.ac @@ -194,6 +194,8 @@ fi dnl === +GOBJECT_INTROSPECTION_CHECK([0.6.7]) + AC_CONFIG_FILES([ Makefile harfbuzz.pc diff --git a/src/Makefile.am b/src/Makefile.am index 344cc57..3abd786 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -6,6 +6,7 @@ EXTRA_DIST = CLEANFILES = DISTCLEANFILES = MAINTAINERCLEANFILES = +DISTCHECK_CONFIGURE_FLAGS = --enable-introspection # The following warning options are useful for debugging: -Wpadded -Wcast-align #AM_CXXFLAGS = @@ -207,8 +208,27 @@ TESTS_ENVIRONMENT = \ HBHEADERS="$(HBHEADERS)" \ $(NULL) -scan: - g-ir-scanner $(HBCFLAGS) $(HBHEADERS) -n hb --strip-prefix=hb --library libharfbuzz.la +-include $(INTROSPECTION_MAKEFILE) +INTROSPECTION_GIRS = hb-1.0.gir +INTROSPECTION_SCANNER_ARGS = --add-include-path=$(srcdir) +INTROSPECTION_COMPILER_ARGS = --includedir=$(srcdir) +if HAVE_INTROSPECTION +introspection_sources = $(HBHEADERS) + +hb-1.0.gir: libharfbuzz.la +hb_1_0_gir_INCLUDES = GObject-2.0 +hb_1_0_gir_CFLAGS = $(INCLUDES) $(HBCFLAGS) -DHB_GOBJECT_COMPILATION +hb_1_0_gir_LIBS = libharfbuzz.la +hb_1_0_gir_FILES = $(introspection_sources) + +girdir = $(datadir)/gir-1.0 +gir_DATA = $(INTROSPECTION_GIRS) + +typelibdir = $(libdir)/girepository-1.0 +typelib_DATA = $(INTROSPECTION_GIRS:.gir=.typelib) + +CLEANFILES += $(gir_DATA) $(typelib_DATA) +endif -include $(top_srcdir)/git.mk diff --git a/src/hb-blob.h b/src/hb-blob.h index 360310b..c64e09b 100644 --- a/src/hb-blob.h +++ b/src/hb-blob.h @@ -24,7 +24,7 @@ * Red Hat Author(s): Behdad Esfahbod */ -#ifndef HB_H_IN +#if !defined(HB_H_IN) && !defined(HB_GOBJECT_COMPILATION) #error "Include instead." #endif diff --git a/src/hb-buffer.h b/src/hb-buffer.h index fe53197..6a5b110 100644 --- a/src/hb-buffer.h +++ b/src/hb-buffer.h @@ -27,7 +27,7 @@ * Google Author(s): Behdad Esfahbod */ -#ifndef HB_H_IN +#if !defined(HB_H_IN) && !defined(HB_GOBJECT_COMPILATION) #error "Include instead." #endif diff --git a/src/hb-common.h b/src/hb-common.h index 562b04c..7140396 100644 --- a/src/hb-common.h +++ b/src/hb-common.h @@ -26,7 +26,7 @@ * Google Author(s): Behdad Esfahbod */ -#ifndef HB_H_IN +#if !defined(HB_H_IN) && !defined(HB_GOBJECT_COMPILATION) #error "Include instead." #endif diff --git a/src/hb-font.h b/src/hb-font.h index b98759b..27239c4 100644 --- a/src/hb-font.h +++ b/src/hb-font.h @@ -24,7 +24,7 @@ * Red Hat Author(s): Behdad Esfahbod */ -#ifndef HB_H_IN +#if !defined(HB_H_IN) && !defined(HB_GOBJECT_COMPILATION) #error "Include instead." #endif diff --git a/src/hb-ot-layout.h b/src/hb-ot-layout.h index b8b5baf..42bd7ef 100644 --- a/src/hb-ot-layout.h +++ b/src/hb-ot-layout.h @@ -24,7 +24,7 @@ * Red Hat Author(s): Behdad Esfahbod */ -#ifndef HB_OT_H_IN +#if !defined(HB_OT_H_IN) && !defined(HB_GOBJECT_COMPILATION) #error "Include instead." #endif diff --git a/src/hb-ot-tag.h b/src/hb-ot-tag.h index 1bf12ab..94f7c59 100644 --- a/src/hb-ot-tag.h +++ b/src/hb-ot-tag.h @@ -24,7 +24,7 @@ * Red Hat Author(s): Behdad Esfahbod */ -#ifndef HB_OT_H_IN +#if !defined(HB_OT_H_IN) && !defined(HB_GOBJECT_COMPILATION) #error "Include instead." #endif diff --git a/src/hb-set.h b/src/hb-set.h index 9f849cf..69367bf 100644 --- a/src/hb-set.h +++ b/src/hb-set.h @@ -24,7 +24,7 @@ * Google Author(s): Behdad Esfahbod */ -#ifndef HB_H_IN +#if !defined(HB_H_IN) && !defined(HB_GOBJECT_COMPILATION) #error "Include instead." #endif diff --git a/src/hb-shape.h b/src/hb-shape.h index 1a0d6cf..89b4922 100644 --- a/src/hb-shape.h +++ b/src/hb-shape.h @@ -24,7 +24,7 @@ * Red Hat Author(s): Behdad Esfahbod */ -#ifndef HB_H_IN +#if !defined(HB_H_IN) && !defined(HB_GOBJECT_COMPILATION) #error "Include instead." #endif diff --git a/src/hb-unicode.h b/src/hb-unicode.h index 205e4c7..e8893ac 100644 --- a/src/hb-unicode.h +++ b/src/hb-unicode.h @@ -28,7 +28,7 @@ * Google Author(s): Behdad Esfahbod */ -#ifndef HB_H_IN +#if !defined(HB_H_IN) && !defined(HB_GOBJECT_COMPILATION) #error "Include instead." #endif diff --git a/src/hb-version.h.in b/src/hb-version.h.in index 43634f9..38185b2 100644 --- a/src/hb-version.h.in +++ b/src/hb-version.h.in
[HarfBuzz] harfbuzz-ng: Branch 'master'
util/shape-consumer.hh |2 --
1 file changed, 2 deletions(-)
New commits:
commit 6a5661f1e69c937083e8d976cb12429b99180d54
Author: Behdad Esfahbod
Date: Sat Jun 9 03:26:16 2012 -0400
Ugh
diff --git a/util/shape-consumer.hh b/util/shape-consumer.hh
index 11e4cc3..220daa4 100644
--- a/util/shape-consumer.hh
+++ b/util/shape-consumer.hh
@@ -49,7 +49,6 @@ struct shape_consumer_t
{
output.new_line ();
-for (unsigned int i = 0; i < 1; i++) {
shaper.populate_buffer (buffer, text, text_len);
output.consume_text (buffer, text, text_len, shaper.utf8_clusters);
@@ -59,7 +58,6 @@ struct shape_consumer_t
output.shape_failed (buffer, text, text_len, shaper.utf8_clusters);
return;
}
-}
output.consume_glyphs (buffer, text, text_len, shaper.utf8_clusters);
}
___
HarfBuzz mailing list
HarfBuzz@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/harfbuzz
[HarfBuzz] harfbuzz-ng: Branch 'master' - 17 commits
src/hb-cache-private.hh |2 +
src/hb-open-type-private.hh | 21 +-
src/hb-ot-layout-common-private.hh | 26 +-
src/hb-ot-layout-gpos-table.hh | 28 +--
src/hb-ot-layout-gsub-table.hh | 28 ++-
src/hb-ot-layout-gsubgpos-private.hh | 15 +-
src/hb-ot-layout-private.hh |4 --
src/hb-ot-layout.cc | 50 +--
src/hb-set-private.hh|5 +++
util/shape-consumer.hh |2 +
10 files changed, 137 insertions(+), 44 deletions(-)
New commits:
commit f211d5c291b4c947cfd732e873627567173057e4
Author: Behdad Esfahbod
Date: Sat Jun 9 03:11:22 2012 -0400
More Oops! Fix fast-path with sub-type==0
diff --git a/src/hb-ot-layout-gpos-table.hh b/src/hb-ot-layout-gpos-table.hh
index 48f0a9d..c8020d8 100644
--- a/src/hb-ot-layout-gpos-table.hh
+++ b/src/hb-ot-layout-gpos-table.hh
@@ -1311,7 +1311,7 @@ struct PosLookupSubTable
inline bool can_use_fast_path (unsigned int lookup_type) const
{
/* Fast path, for those that have coverage in the same place. */
-return likely (lookup_type < Context) ||
+return likely (lookup_type && lookup_type < Context) ||
(hb_in_range (lookup_type, Context, ChainContext) &&
hb_in_range (u.header.sub_format, 1, 2));
}
diff --git a/src/hb-ot-layout-gsub-table.hh b/src/hb-ot-layout-gsub-table.hh
index e62be98..f5f38cc 100644
--- a/src/hb-ot-layout-gsub-table.hh
+++ b/src/hb-ot-layout-gsub-table.hh
@@ -970,7 +970,7 @@ struct SubstLookupSubTable
/* Fast path, for those that have coverage in the same place.
* Note that ReverseChainSingle can also go through this but
* it's not worth the effort. */
-return likely (lookup_type < Context) ||
+return likely (lookup_type && lookup_type < Context) ||
(hb_in_range (lookup_type, Context, ChainContext) &&
hb_in_range (u.header.sub_format, 1, 2));
}
diff --git a/util/shape-consumer.hh b/util/shape-consumer.hh
index 220daa4..11e4cc3 100644
--- a/util/shape-consumer.hh
+++ b/util/shape-consumer.hh
@@ -49,6 +49,7 @@ struct shape_consumer_t
{
output.new_line ();
+for (unsigned int i = 0; i < 1; i++) {
shaper.populate_buffer (buffer, text, text_len);
output.consume_text (buffer, text, text_len, shaper.utf8_clusters);
@@ -58,6 +59,7 @@ struct shape_consumer_t
output.shape_failed (buffer, text, text_len, shaper.utf8_clusters);
return;
}
+}
output.consume_glyphs (buffer, text, text_len, shaper.utf8_clusters);
}
commit b1de6aa1f33b228afe231c8209aef90a5fa1ee5d
Author: Behdad Esfahbod
Date: Sat Jun 9 03:07:59 2012 -0400
Oops!
diff --git a/src/hb-ot-layout-gpos-table.hh b/src/hb-ot-layout-gpos-table.hh
index ad403d5..48f0a9d 100644
--- a/src/hb-ot-layout-gpos-table.hh
+++ b/src/hb-ot-layout-gpos-table.hh
@@ -1343,7 +1343,7 @@ struct PosLookupSubTable
inline bool sanitize (hb_sanitize_context_t *c, unsigned int lookup_type) {
TRACE_SANITIZE ();
if (!u.header.sub_format.sanitize (c) ||
- (can_use_fast_path (lookup_type)) && !u.header.coverage.sanitize (c,
this))
+ (can_use_fast_path (lookup_type) && !u.header.coverage.sanitize (c,
this)))
return TRACE_RETURN (false);
switch (lookup_type) {
case Single: return TRACE_RETURN (u.single.sanitize (c));
diff --git a/src/hb-ot-layout-gsub-table.hh b/src/hb-ot-layout-gsub-table.hh
index 75e38b9..e62be98 100644
--- a/src/hb-ot-layout-gsub-table.hh
+++ b/src/hb-ot-layout-gsub-table.hh
@@ -1000,7 +1000,7 @@ struct SubstLookupSubTable
inline bool sanitize (hb_sanitize_context_t *c, unsigned int lookup_type) {
TRACE_SANITIZE ();
if (!u.header.sub_format.sanitize (c) ||
- (can_use_fast_path (lookup_type)) && !u.header.coverage.sanitize (c,
this))
+ (can_use_fast_path (lookup_type) && !u.header.coverage.sanitize (c,
this)))
return TRACE_RETURN (false);
switch (lookup_type) {
case Single: return TRACE_RETURN (u.single.sanitize (c));
commit b12e2549cbcd4f1ef46e66c75533686ee560f59b
Author: Behdad Esfahbod
Date: Sat Jun 9 03:05:20 2012 -0400
Minor
diff --git a/src/hb-ot-layout-gsubgpos-private.hh
b/src/hb-ot-layout-gsubgpos-private.hh
index 4ac724c..98d4e0a 100644
--- a/src/hb-ot-layout-gsubgpos-private.hh
+++ b/src/hb-ot-layout-gsubgpos-private.hh
@@ -144,7 +144,7 @@ struct hb_apply_context_t
{
return unlikely (num_items && idx + num_items >= end);
}
-inline bool reject (void)
+inline void reject (void)
{
num_items++;
}
@@ -193,7 +193,7 @@ struct hb_apply_context_t
{
return unlikely (idx < num_items);
}
-inline bool reject (void)
+inline void reject (void)
{
num_items++;
}
commit faf0f20253d954cc4cfa4c967ece7573a5ddae3b
Author: Behdad Esfahbod
Date: Sat Ju
