|
64dbeaf0
|
2025-02-28T00:54:39
|
|
[glyf] Mover decycler to the scratch pad
|
|
|
d59d435e
|
2025-02-27T22:41:03
|
|
[decycler] Comments
|
|
|
c84e9b95
|
2025-02-17T15:08:03
|
|
[decycler] Change value type from unsigned to uintptr_t
Since the node struct is gonna be 3*sizeof(void*) bytes anyway,
change value type to use the full space available.
|
|
|
1c18646d
|
2025-02-17T15:06:27
|
|
[decycler] Reduce stack use, kinda
Move the bool to the decycler from the node. The value can now become
a full pointer size (next commit).
|
|
|
fb0e181a
|
2025-02-17T14:57:20
|
|
[decycler] Reduce stack use further
Down to three pointers. Exercise for the reader to prove this is
optimal.
|
|
|
646da80c
|
2025-02-17T14:49:06
|
|
[decycler] Reduce stack use
Down from 5 pointers to 4.
|
|
|
5aea89b5
|
2025-02-17T14:32:23
|
|
[decycler] Don't leave a dangling pointer around
Even if it was never accessed.
|
|
|
bedc8d93
|
2025-02-16T12:30:18
|
|
[decycler] Document algorithm
|
|
|
3cb49717
|
2025-02-16T10:54:11
|
|
[decycler] Add some documentation
|
|
|
a0f83e78
|
2025-02-16T09:55:12
|
|
[decycler] Reduce stack use
48bytes -> 40bytes per node.
|
|
|
0aa400b1
|
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.
|