Commit 0aa400b1d8d8bf933396e74af9a4248b6c92287b
2025-02-15T23:19:44
[decycler] Implement an efficient graph cycle detector This is an algorithm I came up with, based on the Floyd's Tortoise-Hare constant-memory linear-time linked-list cycle-detection algorithm. https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare It is linear-time and malloc-free. It *eventually* detects cycles, not immediately. The main different with Floyd's algorithm is that this algorithm detects cycles when one is traversing down a graph, not just a linked list. Our existing cycle-detection algorithms use a set-of-integers, either hb_set_t, or more efficient in this case, hb_map_t. Those include at least one malloc, and as such show up on profiles. Port hb-ot-font COLRv1 to use the decycler instead of previous hb_map_t usage for cycle detection. benchmark-font paint_glyph on NotoColorEmoji-Regular.ttf: Before: 8ms; After: 5.5ms. No cycle detection: 5.5ms. FT COLRv1 API is so slow (174ms) it's not worth porting to this. Other graphs (VARC, etc) to be ported. Test and documentation to be added.