HarfBuzz Study: OpenType Layout lookup caches
behdad
August 6, 2025
Lookups can have thousands of subtables
One subtable per lookup gets fast
ChainContext(Subst|Pos)Format2
One subtable per lookup gets FAT
Introduction
This document explains how caches involved in OpenType lookups (GSUB & GPOS) work in HarfBuzz, with the aim of facilitating their port to HarfRust.
For a review of the design patterns and data-structures used in the caches below, see HarfBuzz Study: Caching. For a dashboard of HarfRust performance compared to HarfBuzz, see this.
Refresher
Here is what you need to know to appreciate the design of the caches presented later.
The shaping buffer
HarfBuzz shaping works with an hb_buffer_t. The glyph information is held in buffer arrays of the following two types:
typedef struct hb_glyph_info_t {
hb_codepoint_t codepoint;
hb_mask_t mask;
uint32_t cluster;
/*< private >*/
hb_var_int_t var1;
hb_var_int_t var2;
} hb_glyph_info_t;
and:
typedef struct hb_glyph_position_t {
hb_position_t x_advance;
hb_position_t y_advance;
hb_position_t x_offset;
hb_position_t y_offset;
/*< private >*/
hb_var_int_t var;
} hb_glyph_position_t;
The hb_glyph_position_t is only available during positioning, whereas the hb_glyph_info_t is available during the entire shaping process.
The two free variables var1 and var2 are used during different phases to hold different auxiliary information. For example, Unicode properties, glyph properties, and ligature properties are generally held in some of the bytes in there during GSUB and GPOS application. Some shapers use a byte or two of that space for internal processing. For example, the Arabic shaper uses it to store Arabic joining classes. Or, Indic-only shapers stored character syllable category and positioning category in some of the bytes. Finally, for scripts where shaping works on a syllable at a time, a syllable() byte is allocated in those variables.
The buffer provides a mechanism to allocate certain bytes in the free variables, use them, and deallocate them. The allocation/deallocation used to only be used to make sure the same bytes are not used for different purposes accidentally. But later, a try_allocate method was also added, which only succeeds if the requested byte(s) are free, and will return false otherwise. This allows for opportunistic use of the free bytes by layout lookups as we will see later.
Main layout waterfall
The lookup application loops look like this:
for lookup in lookups:
for glyph in buffer:
for subtable in lookup:
if subtable.apply(glyph):
break
Lookups can have thousands of subtables
For reasons that stem from the design of (Chain)?Context(Subst|Pos)Format3 subtables, there are complex fonts in the wild that have a large number of subtables for some lookups. The reason being that the format3 coverage-based subtable covers only one contextual rule. So, if you have 3,800 rules to apply, you would need 3,800 subtables in the lookup (yes, real example from the Gulzar Arabic Nastaliq font).
The number of lookups, on the hand, is more tame, numbering in a few to a couple dozen in a variety of fonts.
Common workloads
Different scripts and font styles pressure different parts of the shaper, and as such, demand different optimizations and caches. Here is a high-level distinction:
Latin and other simple scripts: mostly pressure ligature-forming substitutions, and kerning & mark positioning. We benchmark shaping Roboto with ASCII text as a representative of this workload.
Cursive fonts, be it part of the inherent design of the script (eg. Nastaliq or Naskh styles of Arabic), or a font style, pressure the Context and ChainContext substitutions and positioning lookup types. We benchmark shaping NotoNastaliqUrdu with Persian text as a representative of this workload.
Indic-like scripts contain more custom shaper code than relying on heavy contextual rules in the GSUB/GPOS tables. We benchmark shaping NotoSansDevanagari with Hindi text as a representative of this workload.
Criteria
In HarfBuzz shaping, we are very strict about memory usage. We use the following guidelines:
The per-glyph memory is limited to the total 40 bytes that hb_buffer_t uses. No other allocation dependent on the length of the input is allowed,
No allocation is allowed that is linear or worse in the total number of glyphs in the font. Eg. no caching the coverage value of all glyphs for each subtable,
Any allocated cache must have a reasonably small, fixed, size. Per subtable, in the dozens of bytes range. Per lookup, 1024 bytes is deemed acceptable.
The caches
Dynamic dispatch
Remember the main loops:
for lookup in lookups:
for glyph in buffer:
for subtable in lookup:
if subtable.apply(glyph):
break
The innermost expression, subtable.apply(glyph), itself involves two switches:
switch (lookup_type)
{
case 1:
{
switch (subtable_format)
{
case 1: return lookuptype1format1_apply(glyph);
case 2: return lookuptype1format2_apply(glyph);
…
}
}
case 2:
{
…
}
…
}
The two switches are in tight loops and the conditionals involved break the instruction prefetching pipeline. In HarfBuzz, we use manual type-erasure to cache the subtable application function pointer, and call it directly, skipping the two switches completely.
This costs three pointers per subtable currently (for apply, apply_cached, and cache_func; more about those later), but can be reduced to one pointer if we use a vtable approach.
This might be doable in safe Rust using dynamic dispatch (dyn) as well, and might still be beneficial even if we have to get the dispatcher, uncached, for each lookup in every shape call.
Coverage set digests
Even hotter than the switches from the previous section, is the binary search that each of those inner-most, different, apply functions start with. We can avoid these super-hot loops by breaking out early if we have reason beyond doubt that the glyph is not covered by the coverage of the subtable involved. That is exactly what the hb_set_digest_t is about.
We cache the hb_set_digest_t for the coverage of each subtable, and also for the union of all of a lookup’s subtable coverages. We can then use these digests to reduce how much work we do, as elaborated here. The cache is allocated lazily and on-demand on a per-lookup granularity, which minimizes memory usage to only those lookups that are used. An hb_set_digest_t is a 24-byte structure, which we pay for per subtable.
This is already implemented in HarfRust.
One subtable per lookup gets fast
These caches significantly speed up the cursive-font workloads, like NotoNastaliqUrdu.
Since the buffer’s glyph-info array (hb_glyph_info_t) free variables might have a byte or two available during lookup application time, we can try to use this to cache results of a bsearch from a Coverage or ClassDef table.
For this to pay off, a subtable should try looking up the same glyph item in the Coverage or ClassDef table multiple times. Otherwise, there is no point in caching.
As it happens, there exist two such subtables, the workhorses of many complex / cursive fonts: the four subtable formats (Chain)?Context(Subst|Pos)Format2, which are class-based sets of rules, whereas the ruleset is chosen by the coverage index of the current glyph, and each rule in the rule set is tried, one after the other, against the glyph sequence, until one matches.
Each glyph is looked up in a ClassDef table. The Context(Subst|Pos)Format2 uses one ClassDef to match each glyph, whereas the ChainContext(Subst|Pos)Format2 use three distinct classes: BacktrackClassDef, InputClassDef, and LookaheadClassDef for matching different parts of the rule. By caching the class of a glyph in one of the relevant ClassDefs, we can reuse the value and avoid multiple binary search invocations.
Now, remember the main waterfall:
for lookup in lookups:
for glyph in buffer:
for subtable in lookup:
if subtable.apply(glyph):
break
Since all subtables are tried for each glyph before we move on to the same glyph, if we were to use a hb_glyph_info_t free byte for caching, we can only safely do so for one of the subtables. Otherwise, they will overwrite each others’ cached value or wrongly use it.
So, the subtables for a lookup bid to use the cache, with how much work they can save if they were given the cache spot. The number typically reflects the number of iterations of the binary search the subtable would have to otherwise perform uncached. The lookup performs this bidding dance once upon lookup accelerator initialization, and holds onto it. When invoking the subtable apply functions, it calls a different entry point, apply_cached, for the subtable that has won the cache. In the lookup accelerator, this is identified by unsigned subtable_cache_user_idx.
To allow the subtable to initialize the free byte, a cache-enter is performed before the lookup application is started, and a cache-leave is performed afterwards.
Since the free variable byte used to carry the syllabic information in the Indic-like shapers is free when other shapers operate, we decided to use this byte, called syllable().
Context(Subst|Pos)Format2
For the Context(Subst|Pos)Format2, the value cached is the class value of the hb_glyph_info_t’s codepoint in the input ClassDef. That is, to perform a match operation, instead of:
static inline bool match_class (hb_glyph_info_t &info, unsigned value, const void *data)
{
const ClassDef &class_def = *reinterpret_cast<const ClassDef *>(data);
return class_def.get_class (info.codepoint) == value;
}
we use a different match function:
static inline bool match_class_cached (hb_glyph_info_t &info, unsigned value, const void *data)
{
unsigned klass = info.syllable();
if (klass < 255)
return klass == value;
const ClassDef &class_def = *reinterpret_cast<const ClassDef *>(data);
klass = class_def.get_class (info.codepoint);
if (likely (klass < 255))
info.syllable() = klass;
return klass == value;
}
where the cache-enter call had initialized all syllable()s to 255 before, and again upon departure in cache-leave:
static void * cache_func (void *p, hb_ot_subtable_cache_op_t op)
{
switch (op)
{
…
case hb_ot_subtable_cache_op_t::ENTER:
{
hb_ot_apply_context_t *c = (hb_ot_apply_context_t *) p;
if (!HB_BUFFER_TRY_ALLOCATE_VAR (c->buffer, syllable))
return (void *) false;
auto &info = c->buffer->info;
unsigned count = c->buffer->len;
for (unsigned i = 0; i < count; i++)
info[i].syllable() = 255;
c->new_syllables = 255;
return (void *) true;
}
case hb_ot_subtable_cache_op_t::LEAVE:
{
hb_ot_apply_context_t *c = (hb_ot_apply_context_t *) p;
c->new_syllables = (unsigned) -1;
HB_BUFFER_DEALLOCATE_VAR (c->buffer, syllable);
return nullptr;
}
…
}
}
The various cache setup operations are implemented using the same function and an operation discriminant. This is to minimize the number of function thunks we need to cache per subtable, so we only have one cache_func to carry around, instead of many per subtable.
The cache cost function looks like:
unsigned cache_cost () const
{
unsigned c = (this+classDef).cost () * ruleSet.len;
return c >= 4 ? c : 0;
}
For small workloads, we sidestep the cache as per conditional.
ChainContext(Subst|Pos)Format2
The logic for chain contextuals is similar, except that we use the same one-byte syllable() to cache both InputClassDef result and LookaheadClassDef result, each using only four of the bits. That is, they can cache class values up to 15. This is still quite useful, as most fonts do not use that many classes.
The code is similar but more involved. It is all in hb-ot-layout-gsubgpos.hh; look for cache_cost and cache_func functions.
One subtable per lookup gets FAT
UPDATE: As of this PR, every subtable can request an externally-allocated cache. This is used sparingly.
That was effective for cursive-font workloads. The Latin & similar workload is heavy on the liga and kern tables. Since many start glyphs can participate in liga and kern (even in an extended-Latin font), the hb_set_digest_t structure gets flooded and lets every query in, so we get a lot of subtable.apply calls.
Here, using the hb_glyph_info_t free variables does not help for forming a cache, since each glyph is tried once as the start of a ligature / kerning-pair, so there is nothing useful to cache in the glyph slot itself.
However, this workload uses a small number of common glyphs (in the dozens) repeatedly (eg. the ASCII letters being the most common by far). So we can try a generic Coverage or ClassDef cache using the hb_cache_t data-structure. This needs to be heap-allocated, and as per criteria, we want to allow only one of these per lookup. So, the subtables, again, bid for using the cache using the same bidding mechanism introduced in the previous section. Whoever gets the cache, gets to create the cache and store it with the lookup, and destroy it at face destruction time. These are just two more operations for the cache_func. The allocated cache is stored in the lookup accelerator’s subtable_cache pointer.
LigatureSubstFormat1 Coverage cache
For ligature tables, we cache the coverage value of glyph indices. Such that, for example, seeing the e glyph again and again, we won’t do a binary search to get to its coverage value. The cache cost, setup, and destruction looks like this:
unsigned cache_cost () const
{
return (this+coverage).cost ();
}
static void * cache_func (void *p, hb_ot_subtable_cache_op_t op)
{
switch (op)
{
case hb_ot_subtable_cache_op_t::CREATE:
{
hb_ot_layout_mapping_cache_t *cache = (hb_ot_layout_mapping_cache_t *)
hb_malloc (sizeof (hb_ot_layout_mapping_cache_t));
if (likely (cache))
cache->clear ();
return cache;
}
…
case hb_ot_subtable_cache_op_t::DESTROY:
{
hb_ot_layout_mapping_cache_t *cache = (hb_ot_layout_mapping_cache_t *) p;
hb_free (cache);
return nullptr;
}
}
return nullptr;
}
Where:
using hb_ot_layout_mapping_cache_t = hb_cache_t<15, 8, 7>;
static_assert (sizeof (hb_ot_layout_mapping_cache_t) == 256, "");
This is a 256-byte cache that can accept keys (ie. glyph indices) up to 15bit wide, store values (ie. coverage index) up to 255 (8 bits), and store 128 (7 bits) key/value pairs.
PairPosFormat1 Coverage cache
The format1 kerning subtable is similar in nature to the ligature subtable above, so it uses the cache the same way.
PairPosFormat2 Coverage, ClassDef1, and ClassDef2 cache
The class-based kerning lookup is typically the heaviest part of shaping simple Latin text with common fonts like Roboto. We cache the Coverage, ClassDef1, and ClassDef2 values similarly, each in a 256-byte cache, for a total of 768 bytes per kern lookup. There is typically just one kern lookup in such fonts.
struct pair_pos_cache_t
{
hb_ot_layout_mapping_cache_t coverage;
hb_ot_layout_mapping_cache_t first;
hb_ot_layout_mapping_cache_t second;
};