googlefonts / googlefonts/fontations

Optimized table read and offset traversal

Open
#1,971 4 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
826
Forks
75
Avg merge
22h 33m
Merged PRs (30d)
75

Description

I've been playing around with code patterns for improving our general table parsing performance without leaning (too heavily, see below) on unsafe.

What I've landed on is essentially equal in semantics to "minimal validate" in that table fields that are fixed size and at known offsets are checked ahead of time and the remainder of the fields use checked access but return default values on fail. I've primarily focused on improving code generation for the checked read part with particular interest on minimizing branching.

There's a gist at https://gist.github.com/dfrg/abeefb60984cf151ea6c01581c7a8a70 with the sample code. The two main ideas:

1. Each table has an associated struct containing the header prefix with fixed size fields at known offsets. The table data is fed into a `TableDataRef` object which validates header at construction time (using `bytemuck::try_from_bytes`) and then stores only the data slice. An unsafe `header()` method is provided that just performs a pointer cast, essentially becoming a nop. This means all field reads from the header portion essentially become a load + bswap, no branching at all. The unsafe code here is trivial to validate.
2. The `TableDataRef` constructors are carefully crafted to avoid branching. The `with_offset` function folds offset resolve and the NULL check into the constructor-- this allows reordering the operations in a way that allows the optimizer to avoid generating branches.

The branchless assembly for three constructors (`new`, `with_offset`, and `with_offset_or_default`) is shown below for x86_64 and ARM64. The `with_offset_or_default` method returns data backed by a zero filled static buffer just like our current impl in read-fonts.

x86_64:
```asm
read_my_table:
xor eax, eax
cmp rdx, 10
cmovae rax, rcx
ret

read_my_table_with_offset:
mov r9d, r8d
lea r10, [r9 + 10]
lea rax, [rcx + r9]
mov rcx, rdx
sub rcx, r9
xor r9d, r9d
test r8d, r8d
cmove rax, r9
cmp r10, rdx
cmova rax, r9
mov rdx, rcx
ret

read_my_table_with_offset_or_default:
mov eax, r8d
lea r9, [rax + 10]
cmp r9, rdx
seta r9b
add rcx, rax
sub rdx, rax
test r8d, r8d
sete al
or al, r9b
mov eax, 512
cmovne rdx, rax
lea rax, [rip + anon.df5b7af56b1c95466f7d6f02cae63787.0]
cmove rax, rcx
ret
```

and ARM64:
```asm
read_my_table:
cmp x1, #9
csel x0, x0, xzr, hi
ret

read_my_table_with_offset:
mov w9, w2
add x10, x9, #10
sub x8, x1, x9
cmp w2, #0
ccmp x10, x1, #2, ne
add x9, x0, x9
csel x0, xzr, x9, hi
mov x1, x8
ret

read_my_table_with_offset_or_default:
mov w8, w2
add x9, x8, #10
sub x10, x1, x8
cmp x9, x1
add x8, x0, x8
ccmp w2, #0, #4, ls
mov w9, #512
csel x1, x9, x10, eq
adrp x9, l_anon.8ad8465d1d151927df8569aa0705e208.0@PAGE
add x9, x9, l_anon.8ad8465d1d151927df8569aa0705e208.0@PAGEOFF
csel x0, x9, x8, eq
ret
```

I believe this is about as slim as you can get while still checking lengths and handling null offsets.

If this seems worth pursuing, I can cook up a fontations branch based on this and we can compare performance.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with the linked gist and the proposed TableDataRef design, focusing on the new, with_offset, and with_offset_or_default constructors and their validation semantics. Compare the generated x86_64 and ARM64 assembly and benchmark the approach against the current table-reading implementation; done means preserving minimal-validate behavior while demonstrating the claimed performance improvement.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
performance
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.