HarfBuzz Study: hb-decycler
behdad
February 28, 2025

Introduction

In many places in HarfBuzz we traverse a directed graph in a DFS manner. It is important to detect any possible (directed) cycles in this traversal and break out of them. Legitimate fonts do not contain such cycles. So it is desirable to do this work in a way that is primarily efficient for the non-cyclical case.

The classic way to do this is to maintain a set of currently visited vertices in the path from the root node to the current node. Unfortunately, common implementations of this method, for an arbitrarily sized graph, require at least one heap memory allocation, which can be costly. The hb-decycler is a facility (data-structure + algorithm) I designed to address this problem.

The design is heavily influenced by, and uses, Floyd’s tortoise & hare linked-list cycle detection algorithm. In the rest of this paper I describe the algorithm and analyze its properties. I have not found something like this explored before, hence writing this down.

Problem Statement

We have a directed graph that we like to traverse from a root node. We cannot modify the graph itself (eg. adding a color or visited member to the vertex storage). The goal is a full traversal, which can legitimately take exponential time in the size of the graph itself. The full traversal is desirable, and as such, the size of the traversed tree is the baseline for any running time assessment for the cycle-detection algorithm.

We would like to avoid any heap allocation in the algorithm, run-time be linear, and with minimal global and stack-frame allocations.
​

The rest of this writeup assumes a recursive DFS implementation, although the technique is applicable to loop-based DFS traversals as well.

Main idea

Since we are interested in detecting only directed cycles in the DFS traversal, if such a cycle exists, there will be a time in the traversal where the same graph node appears at least twice from the traversal path from the root to the current node. This path, essentially, is a linked-list, and we can apply Floyd’s tortoise & hare algorithm progressively to this path, to detect cycles and break out of them.

Implementation

Familiarity with Floyd’s tortoise & hare algorithm is assumed in this section.

The implementation is done using two small objects:

• hb_decycler_t is the main object, the size of three pointers, and is once allocated on the stack per traversal work.

• hb_decycler_node_t is also the size of three pointers, and is allocated on the stack once for each level of descent.

The object declarations are very short (slightly simplified):

struct hb_decycler_t

{

friend struct hb_decycler_node_t;

private:

bool tortoise_awake = false;

hb_decycler_node_t *tortoise = nullptr;

hb_decycler_node_t *hare = nullptr;

};

struct hb_decycler_node_t

{

hb_decycler_node_t (hb_decycler_t &decycler);

~hb_decycler_node_t ();

bool visit (uintptr_t value_);

private:

union {

hb_decycler_t *decycler;

hb_decycler_node_t *next;

} u = {nullptr};

hb_decycler_node_t *prev = nullptr;

uintptr_t value = 0;

};

The actual code is in the constructor, destructor, and visit method of the hb_decycler_node_t. They are inlined, but removed here for brevity. The full code is in hb-decycler.hh. The code also has its own description of the algorithm in slightly more detail.

The hb_decycler_t object simply contains two pointers to the tortoise and hare nodes in the current traversal path, plus a boolean to keep the waking state of the tortoise.

The hb_decycler_node_t contains previous/next links to maintain the linked-list, as well as a value corresponding to the graph vertex this traversal node refers to. The constructor basically inserts the node at the end of the linked-list from the root to the current end node and advances the decylcler’s hare member to point to this new end node. It also advances the decylcer’s tortoise member if the tortoise is awake, and also flips the tortoise’s awake state.

The destructor simply undoes what the constructor did, removing the node from the linked list and restoring the decycler to its previous state.

The visit method is where the cycle-detection happens. It involves checking whether the graph vertex we are trying to visit is the same vertex that the decycler’s tortoise node points to. If this happens, we have a cycle.

For sample use see test-decycler.cc.

Analysis

From a memory consumption point of view, I believe three pointers for both the decycler and the decycler-node objects to be optimal. Proof is left to the reader.

For the running time, each method runs in O(1) time, and at most two methods are called per DFS edge traversal: node constructor & the visit method. This can be further optimized by reusing the same node for all outgoing edges from a vertex during the traversal. As such, if there exist no loops, the running time of the algorithm is linear in the running time of the DFS itself.

If there are loops in the DFS traversal, this algorithm does not detect them at the first sight necessarily. This is exactly the same property as Floyd’s algorithm. So the loop detector is eventual, not immediate. This penalizes the bad cases in our workloads, so it is not a problem per se.

Conclusion

Loop detection during graph traversal in HarfBuzz is a problem that was previously solved by maintaining an integer-set or hashmap-set of the currently visited nodes. This involved heap memory allocation which proved to take significant time of the traversal: around 10 to 20 percent. By porting the traversals to use this new algorithm, the memory allocation and the time it took was completely wiped off the profile. In fact, we cannot measure any meaningful speed difference in the new code compared to code with no cycle-detection at all.

In closing, I should note that in HarfBuzz, for all graph traversals, we also enforce a maximum stack depth and edge traversal budget. So, even without a cycle detector, we will not loop infinitely. However, this cycle detector is a nice way to break out of simple cycles earlier which would be faster and reduce rendering artifacts.