Optimized table read and offset traversal

[dfrg]

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<H> 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:

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:

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.

[rsheeter]

Sounds worth pursuing at least to the measurement of perf step.

I'm curious, how would one verify the continued branchless nature? Do people do things like compile and check assembly in tests?

[dfrg]

I'm curious, how would one verify the continued branchless nature? Do people do things like compile and check assembly in tests?

We could include these example functions and check the assembly in CI. Of course, we can’t guarantee what the optimizer will do when this code is inlined into larger contexts. The better (additional?) option is to start tracking performance by running some benches in CI.

[wmedrano]

For CI

Criterion

We have some criterion tests and can just run the relevant ones in CI and compare.

For flakiness, https://github.com/jbreitbart/criterion-perf-events or similar could be more deterministic. We could set up a script to make sure the diff isn't unintentionally large. Some things I found:

• Annoying to interpret. 165,772,057,534 is hard to read compared to 23.8s
• Criterion only supports one measurement per benchmark, maybe I didn't look hard enough though.

Custom

The perf counters are pretty nice if we want to go custom harness. Specifically, I think this change is meant to improve cycles and insn per cycle

$ perf stat .....
....
....
    42,572,279,673      task-clock                       #    1.787 CPUs utilized
            26,334      context-switches                 #  618.572 /sec
             1,377      cpu-migrations                   #   32.345 /sec
           113,898      page-faults                      #    2.675 K/sec
   289,836,632,674      instructions                     #    1.75  insn per cycle
                                                  #    0.06  stalled cycles per insn
   165,772,057,534      cycles                           #    3.894 GHz
    18,202,410,183      stalled-cycles-frontend          #   10.98% frontend cycles idle
    47,351,056,137      branches                         #    1.112 G/sec
       820,227,069      branch-misses                    #    1.73% of all branches

      23.829190330 seconds time elapsed

      40.836457000 seconds user
       1.876145000 seconds sys

[dfrg]

The branch and branch miss counts in the perf stats are particularly interesting for this experiment. I’d love to see some tracking of these for various workloads.