HarfBuzz Study: Caching
behdad
April 2, 2025
Skipping work with hb_set_digest_t
(Chain)Contextual Substitution / Positioning class cache
Machine starter glyphs in morx and kerx
Kerning left and right glyph sets
The normalized variation coordinates cache
Unicode to glyph mapping cache
Introduction
This document enumerates various caching schemes used in HarfBuzz to speed up shaping text. Caches for other operations (drawing / painting) are briefly covered as well.
While some systems cache shaping results for entire words and try to reconstruct shaping of a paragraph from the word cache, those systems are fragile and break down if the font does shaping across the space character (which can be detected using HB API), memory hungry, and generally i as effective as Fast shaping on the general loading time of a full page of new text.
As such, the HarfBuzz approach is to make shaping as fast as possible, and expect clients to shape once and hold onto the results for as long as needed. However, over time, it became clear that some things can use a little memory for a good-sized speedup, so we have moved in that direction when the tradeoff made sense. After all, the existing HarfBuzz (codenamed harfbuzz-ng before) was super memory-efficient as previously shown in HarfBuzz Memoy Consumption back in 2012.
By cache, we specifically mean places where memory is allocated and used, to gain speed. These are typically per hb_face_t, but sometimes per hb_font_t.
The aim of this writeup is to identify caches that need to be ported to RustyBuzz / HarfRuzz to get close to matching HarfBuzz shaping performance across various font technologies, but I also cover caching applied to drawing and painting operations, which in Rust land, is the job of Fontation’s Skrifa crate.
We do not cover caching in the HarfBuzz subsetter library.
Update: for followups to this writing, see:
Design Patterns
The hb_cache_t objects
The hb_cache_t template implements a lockfree and thread-safe cache for int→int functions, using (optionally) relaxed atomic integer operations. The cache typically is configured with 256 32-bit integers, for a total size of 1kb of memory, although the parameters are configurable.
The cache is basically an LRU array keyed by the top bits of the key integer. It works mostly with key/value integer numbers with a combined number of bits of 40. For example, 21-bit key (Unicode codepoint) and 19-bit glyph index (supporting more than 64kb glyphs). If the key or value does not fit in the configured size, the cache is bypassed.
For a cache with 256 entries, looking up a set of local integers that span less than 256 from minimum to maximum, the cache will have 100% hit rate after the first insert of each value.
Here is, for example, how the cmap table uses the hb_cache_t template:
using cache_t = hb_cache_t<21, 19>;
static_assert (sizeof (cache_t) == 1024, "");
See the source documentation and code for details.
The hb_set_digest_t object
The hb_set_digest_t is a workhorse of the OpenType shaping performance.
The set-digest implements various filters that support approximate member query in sets of integer values. Conceptually these are like the Bloom filter and the Quotient filter, however, much smaller, faster, and designed to fit the requirements of our uses for glyph coverage queries. They digest is a small 32-byte object, typically embedded in other structs.
Our filters are highly accurate if the set covers a fairly small and local set of integers, but fully flooded and ineffective if the values in the set are all over the place.
The way the set-digest is used is that the filter is first populated by a set of integer (eg. the coverage of a lookup table), and then when we can query the filter whether a particular integer of interest may be in the set. If it is in the set, we return true surely. On the other hand, if the integer is not part of the set, we may return false or true (false positive). We can also match a digest against another digest to query whether the two sets might intersect. Both operations are very fast and involve just a few integer operations..
The set digest is quite effective (low false-positive rate) if the set cardinal (the number of integers in the set) is small and those numbers have locality (are nearby integers). As the set size increases, so does the false-positive rate, until the digest gets fully flooded and has a 100% false-positive rate. This is rare in most fonts.
Here is, for example, how we collect the set of all glyph indices in the shaping buffer into a set-digest:
hb_set_digest_t digest;
buffer->collect_codepoints (digest);
We can later call digest.may_have (codepoint) to gate-keep a slower, typically binary search, operation.
See the source documentation and code for details.
The hb_bit_set_t object
An hb_bit_set_t simply implements a set-of-integers data-structure. The set is stored sparse in a two-level tree, with leaf nodes each having a capacity of 512 bits, capable of storing 512 consecutive integers. Set membership operations and iteration consist of mainly two memory accesses, a small binary search, and a few integer operations. Set algebra (intersection, union, etc.) is supported. The set is optimized, such that looking up nearby integers bypasses the binary search.
The hb_bit_set_t is used instead of hb_set_digest_t where we can afford (theoretically unbounded) heap memory allocations, in exchange for zero false-positives.
See source code for details.
The table accelerators
An hb_face_t can be loosely thought of as a collection of known font table objects, loaded on demand upon first use. The lazy-loading is done using atomic pointer compare-and-exchange operations and is fully thread-safe without using a mutex. This scales very well to multi-threaded use.
Some font tables can be used efficiently with no extra information. Other tables, however, can use some pre-computation to make the later usage of the table data more efficient. In such cases, a per-table accelerator object is used, which holds onto the table itself but also stores extra information, all populated at the time of the lazy loading.
For example, the cmap table contains multiple subtables (format 4, format 12, format 14, etc). Which subtable is best to use can be pre-computed and cached in the cmap::accelerator_t structure, such that later queries to the cmap table have the best table readily available and not need to find it every time. Here is the abridged cmap accelerator structure:
struct cmap::accelerator_t
{
private:
hb_nonnull_ptr_t<const CmapSubtable> subtable;
hb_nonnull_ptr_t<const CmapSubtableFormat14> subtable_uvs;
hb_cmap_get_glyph_func_t get_glyph_funcZ;
const void *get_glyph_data;
CmapSubtableFormat4::accelerator_t format4_accel;
#ifndef HB_NO_OT_FONT_CMAP_CACHE
cache_t *cache;
#endif
public:
hb_blob_ptr_t<cmap> table;
};
The table scratchpads
Heap memory allocations (malloc / realloc) are fairly fast on Linux / glibc, but slower on some other platforms. Regardless, having heap allocations during operations like shaping text or drawing / painting glyphs typically has a measurable impact on the performance. Lots of small heap allocations and freeing operations also fragment the heap, which results in higher peak process memory use.
I got obsessed with allocation-free operations, so I took it upon myself to apply it to all major libharfbuzz operations: shaping, drawing, and painting, across a variety of different font technologies (TrueType, CFF, variable font, color font, etc).
Our shaping code paths were already allocation-free, except for the shaping buffer itself which will grow as needed by the shaping operations (eg. one-to-many glyph substitutions). Clients can reuse a hb_buffer_t to avoid reallocation on every shape call.
There are various places in glyph outline extraction (called drawing) where memory allocations are necessary. The HarfBuzz API for drawing, like many other libraries, simply issues move-to, line-to, quadratic-to, curve-to, and close-path operation call-backs to the client. This, by itself, requires no memory allocations. And indeed, for example, non-variable CFF fonts are designed to naturally fit this kind of API without any allocations. Variable TrueType (glyf/gvar) fonts on the other hand, require loading the entire glyph outline into memory, to apply variations to them, before issuing drawing commands can begin.
Painting was mostly allocation free after the hb-decycler integration. The exception was that the code to calculate the painting bounding-box has to maintain two vectors of data.
To address all of the remaining allocations, I improvised what I call the scratchpad pattern: the draw / paint operation will use a scratchpad for all its memory allocations. The scratchpad typically contains multiple vector members. Those vectors reallocate more memory as needed. Normally though, you would throw away the scratchpad after drawing / painting one glyph. But now instead, I hold onto the warmed-up scratchpad by attaching it to the hb_face_t font face object (via a table accelerator). The next draw / paint operation then, will borrow the scratchpad from the face if one is available / or create one, use it, and try returning it to the face.
In the off-chance that multiple threads need the same scratchpad (ie. same font table operation) at the same time, only one of them will be able to use the cached scratchpad, and others will allocate and free one as needed. All major HarfBuzz clients are single-threaded, so this is the perfect tradeoff.
For example, here is the glyf/gvar scratchpad structure:
struct hb_glyf_scratch_t
{
// glyf
contour_point_vector_t all_points;
contour_point_vector_t comp_points;
hb_decycler_t decycler;
// gvar
contour_point_vector_t orig_points;
hb_vector_t<int> x_deltas;
hb_vector_t<int> y_deltas;
contour_point_vector_t deltas;
hb_vector_t<unsigned int> shared_indices;
hb_vector_t<unsigned int> private_indices;
};
And here is how it is hooked up to the glyf accelerator:
struct glyf::accelerator_t
{
…
private:
bool short_offset;
unsigned int num_glyphs;
hb_blob_ptr_t<loca> loca_table;
hb_blob_ptr_t<glyf> glyf_table;
hb_atomic_t<hb_glyf_scratch_t *> cached_scratch;
};
The scratchpad is created lazily on-demand, borrowed, and returned, using atomic pointer compare-and-exchange operations as described before.
A minor downside of this approach is that the face will hold on to memory the size of the biggest operation performed. The face memory usage will not go back down after the big operation is finished. This, however, is not a major problem, since we are typically talking about a few kilobytes of memory or a few tens of. Unless you eg. throw 1 million characters of text in one piece at hb_shape(), and reuse the buffer for the future. In that case, yes, 40mb of memory would be allocated and held on to.
Caches on hb_face_t
Shape-plan cache
An hb_shape_plan_t object encompasses all pre-computed data necessary to shape text using a hb_face_t for a given combination of script, direction, and language. This includes which script shaper to use, and which lookups to apply to the glyph stream. Constructing the shape-plan upon each shape call is expensive and can dominate the run-time of the shape operation. As such, we cache all created shape-plans for the face, on the face itself. This is done using an atomically-updated lock-free singly-linked list.
This is one of the two places in HarfBuzz where memory allocations can grow unboundedly. The other being a similar linked-list of all created hb_language_t objects. In the twenty years of using HarfBuzz, this has not been shown as an obstacle, or abused.
If necessary, the per-face shape-plan cache can be converted to a size-bounded LRU cache using a mutex to ensure thread-safety.
OpenType shaping
Since all major HarfBuzz clients use it (only) for text shaping, the performance of OpenType shaping is of utmost importance.
Digression
Webkit, from which Chrome descended, used to have two code paths for shaping text. One for complex scripts, which would call HarfBuzz or another text shaper, and a fast-path for simple scripts like Latin. The fast-path did not apply font features like ligatures, kerning, or other advanced features. So they were not applied to Latin text! And to many other scripts. This was not ideal. So one of my aims was to make Chrome retire the fast-path, and always shape text with HarfBuzz.
Around 2012, engineers on the Chrome team produced a change-set to do exactly that. However, this change, always calling HarfBuzz for shaping text, would slow down shaping of simple Latin text like English. This was not acceptable by Chrome policy. So I had to make HarfBuzz fast enough for simple scripts to out-do the archaic fast-path. This was not going to be an easy feat. So I designed hb_set_digest_t to address that.
Skipping work with hb_set_digest_t
The main work of OpenType shaping after the initial character-to-glyph mapping involves applying the GSUB and then GPOS table lookups. Fonts can have as few as no lookup, up to dozens or even hundred. Each lookup includes one or more sublookups, which, again, can be as few as one or a few or up to dozens, in most fonts. But as observed in an extreme Urdu Nastaliq font (Gulzar), a positioning lookup exists with over 3,000 sublookups!
Applying each lookup involves a pass over the buffer contents. Each glyph in the buffer is then quaried against each of the lookup’s subtables’ coverage table until a match is found, in which case the sublookup is applied to the glyph. This process then is performed on the next glyph, and the next glyph, … The simplified pseudo-code for applying lookups looks like this:
for table in [‘GSUB’, ‘GPOS’]:
for lookup in table:
for glyph in buffer:
for sublookup in lookup:
if sublookup.coverage.has(glyph):
if sublookup.apply(glyph):
break
That is four nested for loops! The total work done is at least proportional to the number of glyphs in the buffer times the sum of the number of sublookups in all lookups!
The sublookup.coverage.has(glyph) itself performs a binary search on the glyphs (or ranges of glyphs) covered by the sublookup. In a font with tens or hundreds (or more!) glyphs all covered by a sublookup, this binary search cost will show prominently in the shaping time profiles.
To address this, I pre-compute an hb_set_digest_t for each subtable, as well as for the lookup as a whole (done lazily per lookup), and then check with the digest for possible coverage of the glyph, before calling into the sublookup.coverage.has() function. The updated code looks like this:
for table in [‘GSUB’, ‘GPOS’]:
for lookup in table:
for glyph in buffer:
if lookup.digest.may_have(glyph):
for sublookup in lookup:
if sublookup.digest.may_have(glyph):
if sublookup.coverage.has(glyph):
if sublookup.apply(glyph):
break
It is the same number of loops, but with two if conditions to avoid excess work. This change by itself made shaping of the mid-complexity Amiri Arabic font 3x faster.
More recently, we added another use of the lookup digests: We maintain a set-digest of all glyphs currently in the buffer, and check whether the buffer set digest intersects with the lookup set digest. If there is no intersection, this lookup cannot have any effect on the contents of the buffer, so we can simply skip it. This optimization gained another 10% speedup in shaping Roboto-Regular with English text. Mainly because, most English text has no mark glyphs, and because of this optimization, lookups for font features like mark-to-base, mark-to-ligature, and mark-to-mark positioning would be skipped completely, reducing the total amount of work performed. The updated code looks like this:
for table in [‘GSUB’, ‘GPOS’]:
for lookup in table:
if lookup.digest.intersects(buffer.digest):
for glyph in buffer:
if lookup.digest.may_have(glyph):
for sublookup in lookup:
if sublookup.digest.may_have(glyph):
if sublookup.coverage.has(glyph):
if sublookup.apply(glyph):
break
As noted before, checking two set digests for intersection is a fast operation, involving just a few integer operations.
Ligature coverage cache
Most fonts have a ligature lookup. In fonts for simple scripts, not many glyphs can initiate a ligature. In other, more complex, fonts though, there might be a large number of glyphs that initiate ligatures. To handle both cases, the hb_set_digest_t’s above are not effective, so an hb_cache_t totaling 256 bytes is allocated. This cache has only 128 entries of 16-bit numbers, capable of mapping 15bit glyph indices to 8-bit coverage index. Fonts having more than 32k glyphs typically have few ligatures, so the 15bit glyph indices do not pose a practical problem. Remember, if the integer doesn’t fit in the cache, the cache is simply bypassed. The code still performs correctly, just without any cache speedup.
PairPos coverage cache
There exist two formats of the pair positioning (aka. kerning) sublookup:
Format 1 subtables encode individual kern pairs, grouped by the first glyph in the pair. This table’s coverage is possibly cached similar to the ligature coverage cache above.
Format 2 subtables encode kerning as a matrix of first and second glyph classes. This table possibly caches the coverage as well as the class value for each glyph, for the first glyph class set and the second glyph class set, all using hb_cache_t of 256 bytes similar to the ligature coverage cache case above.
I said possibly cached, because the way the infrastructure is set up, and to minimize cache allocations, lookup can only have one of their sublookups use a cache. The subtable with heaviest coverage table is chosen as the cached sublookup.
(Chain)Contextual Substitution / Positioning class cache
Application of (Chain)Contextual substitution (GSUB) and positioning (GPOS) are heavier than other lookup types, as their application involves yet another loop on the glyphs adjacent to the current glyph, to match the input context, and possibly lookahead and backtrack in chase of the Chain version.
In one format of these subtables, glyphs are categorized into classes before they are matched to sublookup rules. Since these subtables are very expensive to apply, we optimize them by caching the class value for each glyph, in an hb_cache_t of 256bytes. The class value for each glyph is looked up in the cache, and furthermore, stored once in the buffer and reused when each rule examines the same glyph. The number of these rules can be quite high in complex fonts.
GDEF mark classes cache
TODO Update. both using bit-set instead of set-digest; AND caching whether it matched in glyph_props(), as well as caching glyph-props themselves.
Many complex Arabic fonts are designed to decompose each Arabic letter into its basic body and the dots as separate glyphs. In such a design, around 30% of the glyphs in the buffer might be of the mark glyph classification according to the GDEF glyph classes.
When processing a mark glyph, it might be necessary to look it up in one of the GDEF mark class coverage tables. Since coverage tables involve binary searching and are slow to process as established, we use a hb_set_digest_t for each GDEF mark class to speed up such lookups.
AAT shaping
AAT fonts are rare in the wild. Their natural habitat is Apple system fonts. Apple devices typically are less memory-pressured than other systems (eg. Android, ChromeOS) and as such we took the liberty of allocating larger caches for these fonts, eg. the exact hb_bit_set_t instead of the approximate hb_set_digest_t.
State-machine class cache
Both morx and kerx tables (and their predecessors) may contain subtables that encode a state-machine that needs to be fed the glyph stream, to produce results. For each glyph, a class value is looked up, and the machine action and next state are determined based on the current machine state and the glyph class. Looking up this class value, again, can involve a binary search and be slow. So we use an hb_cache_t of 256 bytes per state-machine to speed up this class value lookup.
Machine starter glyphs in morx and kerx
Both tables’ accelerators pre-compute a hb_bit_set_t of starter glyphs. These are glyphs that can move the state-machine from its initial, dormant, state to any other state, or to apply an action on the glyph from the initial state. This computation is a bit involved but not hard.
At shaping time, an hb_bit_set_t of all glyphs in the buffer is maintained, and if the two sets do not intersect, then the state-machine for this subtable is skipped and not tried, as it cannot have any effect on the glyph stream. Maintaining the hb_bit_set_t of the buffer is not allocation-free. As such, AAT shaping is not allocation-free in general.
Kerning left and right glyph sets
When performing non-state-machine-based kerning in the kerx table, or applying the OpenType legacy kern table, other than an hb_bit_set_t of all glyphs participating as the first glyph in a kern glyph pair, an hb_bit_set_t of the all second glyphs in all glyph pairs is also maintained. When looking up the kerning for a pair of glyphs, the first and second glyphs are checked for membership in the two hb_bit_set_t’s, and if at least one fails, a kerning value of 0 is reported. Otherwise, the actual, expensive, binary search lookup of the kerning pair happens:
struct accelerator_t
{
const KerxSubTableFormat0 &table;
hb_aat_apply_context_t *c;
accelerator_t (const KerxSubTableFormat0 &table_,
hb_aat_apply_context_t *c_) :
table (table_), c (c_) {}
int get_kerning (hb_codepoint_t left, hb_codepoint_t right) const
{
if (!c->left_set->has(left) || !c->right_set->has(right)) return 0;
return table.get_kerning (left, right, c);
}
};
Caches on hb_font_t
Most of these only apply to the HarfBuzz-internal font backend implementation, called ot. Other font backends typically do not do any caching as any caching is deemed the responsibility of the adjacent font platform, eg. hb-coretext, hb-directwrite, hb-fontations. The hb-ft backend does have an advance-width cache, because computing those for variable fonts are fairly expensive and FreeType has no cache for that.
The normalized variation coordinates cache
This one is obvious: when the user sets design variation coordinates on the font, we convert them to normalized coordinates (applying fvar, and avar if present) and cache the normalized coordinates. All the rest of the font tables work with the normalized coordinates only. We keep the original design coordinates as well, in case the user asks for them later.
We also cache whether all the normalized coordinates are 0, in which case variations will not be processed across various operations, resulting in a handsome speedup.
These are hooked to the hb_font_t object itself.
Unicode to glyph mapping cache
Mapping Unicode characters to nominal glyphs using the cmap table is one of the first steps of shaping. Every shaping operation has to go through this. Without a cache, each Unicode character has to be looked up in a cmap subtable, typically using a binary search operation. For fonts with thousands of glyphs, this can be slow. An hb_cache_t can solve the problem at a tiny cost of 1kb per face for a 256-entry cache. The cache is hooked to the cmap table accelerator.
Here is how the code to use the cache looks like:
inline bool _cached_get (hb_codepoint_t unicode,
hb_codepoint_t *glyph) const
{
#ifndef HB_NO_OT_FONT_CMAP_CACHE
// cache is always non-null if we have a get_glyph_funcZ
unsigned v;
if (cache->get (unicode, &v))
{
*glyph = v;
return true;
}
#endif
bool ret = this->get_glyph_funcZ (this->get_glyph_data,
unicode, glyph);
#ifndef HB_NO_OT_FONT_CMAP_CACHE
if (ret)
cache->set (unicode, *glyph);
#endif
}
Glyph advance width/height caches
TODO Update
For a non-variable font, the glyph advance width (for horizontal writing) / height (for vertical writing) are stored in a dense array in the hmtx / vmtx tables respectively. This is super fast to access as it is simply an array lookup indexed by the glyph index. In this case, no caching is necessary.
For variable fonts however, the glyph advance needs to be adjusted for the current variation settings of the font. This computation can be quite expensive. There are two cases, each with their own cost:
If the font has no HVAR / VVAR tables, then the phantom points from the glyph outline need to be constructed and the variations applied to them, to extract the advance width / height. This is particularly expensive as it involves gvar table processing of the glyph.
The HVAR / VVAR tables were added exactly to speed up the variable advance width / height calculation. They store the variations in an ItemVariationStore structure, which is in general much faster to compute with than the gvar table.
To remedy this, the ot font implementation maintains a 1kb hb_cache_t configured to fit glyph-index to unscaled-advance-width workload and hooked to the ot font private data (similar to scratchpads). So, this will be one per hb_font_t, and the cache is automatically (and thread-safely) invalidated if the font’s variation settings change. This cache is created lazily on-demand, such that shaping non-variable fonts, or variable fonts at their default design location, will not allocate the cache.
Since we have to process variations for each glyph in the shape result to calculate its advance width or height, assuming a well-built font means that the HVAR (and possibly VVAR) table is present. So we are in scenario number 2 above. With this assumption, if variations are set and the workload is big enough, we acquire an ItemVariationStore::cache_t, which is a tiny structure that only caches the calculated scalar value for each variation region (lazily). It does not cache the varied value of every item in the store, so it is very compact. The cache is hooked to the ot font in a scratchpad manner, so it is not reallocated each time.
ItemVariationStores come into play again during the GPOS table positioning phase of shaping. We allocate one lazily and hook it up to hb_font_t’s shaper data for the ot shaper.
TupleVariationStore cache
This cache involves drawing TrueType outlines of variable fonts. TupleVariationStore is where the variations for each glyph shape are stored, in the gvar table.
Variations for each glyph contain delta-sets for multiple regions. When processing variations, for each region we need to compute its contribution, also called its scalar. In a font with a large number of variation axes, this computation can be expensive, as for each region, each axis value should be examined. However, in any font with lots of variation axes, each region is activated by just a few axes, mostly one or two, though higher numbers are also possible (eg. corner masters with three or more non-zero axis values).
Each variation delta-set can specify its activation region, or refer to a table-wide shared-tuples list of regions. The latter is quite common, as most glyphs share the same design-space configuration. The cache here simply remembers the active (non-zero) axes of each shared variation region if there are only up to two axes active. (TODO: Update me; this changed.) This cache sped up axis-heavy fonts like RobotoFlex significantly.
See the code creating this cache in the accelerator, and its usage.
Conclusions
In this writeup I presented the various ways that HarfBuzz has over time grown data caches around hb_face_t and hb_font_t objects to speed up common operations. Even with the caches, because of the accelerator and scratchpad design patterns used, the total number of heap allocations HarfBuzz does per face is in the a-few-dozens range, regardless of how many operations you perform using it. That is to say, the number of allocations per face are capped for all but the most unusual workloads. Although, this number of allocations depends on the data in the font face tables. A “heavier” font would allocate more memory for caches.
The performance benefits of these caches are extremely high. Removing just the hb_set_digest_t usage from OpenType shaping can easily make complex Arabic fonts render many times slower. Even the Latin Roboto-Regular font, the default on most Android devices numbering in the billions of users, benefits from the caches to shape text at least 30% faster. When you are an operating system or a browser, such numbers matter.
The goal of this exercise was to make knowledge of HarfBuzz performance internals available for the Rust ports (RustyBuzz / HarfRuzz), but many of the ideas can be applied to any library implementing font shaping, drawing, or painting.
Further reading
Previously I performed a comparison of the ot, ft, and fontations font backends on speed and memory usage. Those validate the claims in this document.