3 ms·

The pervasive lack of frame pointers is the reason why we've developed a custom format derived from DWARF unwind information thanks to some insights: DWARF unwi

The pervasive lack of frame pointers is the reason why we've developed a custom format derived from DWARF unwind information thanks to some insights: DWARF unwind information is incredibly flexible, it supports many architecture and allows restoring any arbitrary register. But we only need 3: the frame pointer, the stack pointer, and in non-x86 the return address. While DWARF unwind info doesn't use that many bytes, but unfortunately reading and parsing that information is quite expensive. For that reason I've developed a new unwinder that uses custom unwind information derived from DWARF (https://www.polarsignals.com/blog/posts/2022/11/29/profiling-without-frame-pointers/ https://www.polarsignals.com/blog/posts/2022/11/29/profiling..., previously discussed in https://news.ycombinator.com/item?id=33788794 https://news.ycombinator.com/item?id=33788794) that runs in BPF. This new compact representation can be binary searched easily and each unwind row has a size of 16 bytes. I am currently working on reducing it down to ~10 bytes. All the code is fully OSS (Apache 2.0 for userspace and GPL for BPF), and part of the Parca project (https://github.com/parca-dev/parca-agent https://github.com/parca-dev/parca-agent). We've also given a talk this year in FOSDEM going deeper into how we made it scale for many big processes.

amluto 4y ago
Nice! One suggestion: binary search has extremely poor cache behavior, and early versions of the ORC in winder (IIRC) spent considerably more time binary searching the table than actually unwinding. There are many solutions to this. ORC (IIRC) uses a flat hint table mapping PC -> offset in the table. It’s sparse, so you look up hint[(ip-base) / divisor] and its successor to find a small range of the table to search. (Divisor is set to keep the hint table compact but still limit the main search to something small.). This gives essentially linear time lookups with simple code. You can also use a B-tree or a similar structure. B-trees are pretty straightforward if you don’t ever need to modify them. IIRC this gave a substantial speedup.
- javierhonduco 4y ago
  This is a very good point. Thanks for the context on how ORC does it, I was not familiar with how it evolved. In our case this is not an issue yet. We split up the unwind tables in chunks of up to ~1MB so we typically have in very few L2 cache misses. This has to be done once per frame so in my 4 year old i7 processor. There are roughly `2 L2 cache misses (+ few other misses from reading ancillary data structures) * frames`. We have more work to do regarding benchmarks but I collected some numbers the other day and 90 frames can be walked in less than 500ns (slide 50 https://fosdem.org/2023/schedule/event/walking_stack_without_frame_pointers/attachments/slides/5934/export/events/attachments/walking_stack_without_frame_pointers/slides/5934/FOSDEM_2023_kernel.pdf https://fosdem.org/2023/schedule/event/walking_stack_without...) There are more optimisations we have in the works to make our unwinder more efficient, mostly related to fitting more data in the CPU cache and reducing cache misses.

amluto 4y ago

Nice! One suggestion: binary search has extremely poor cache behavior, and early versions of the ORC in winder (IIRC) spent considerably more time binary searching the table than actually unwinding. There are many solutions to this. ORC (IIRC) uses a flat hint table mapping PC -> offset in the table. It’s sparse, so you look up hint[(ip-base) / divisor] and its successor to find a small range of the table to search. (Divisor is set to keep the hint table compact but still limit the main search to something small.). This gives essentially linear time lookups with simple code. You can also use a B-tree or a similar structure. B-trees are pretty straightforward if you don’t ever need to modify them. IIRC this gave a substantial speedup.

javierhonduco 4y ago
This is a very good point. Thanks for the context on how ORC does it, I was not familiar with how it evolved. In our case this is not an issue yet. We split up the unwind tables in chunks of up to ~1MB so we typically have in very few L2 cache misses. This has to be done once per frame so in my 4 year old i7 processor. There are roughly `2 L2 cache misses (+ few other misses from reading ancillary data structures) * frames`. We have more work to do regarding benchmarks but I collected some numbers the other day and 90 frames can be walked in less than 500ns (slide 50 https://fosdem.org/2023/schedule/event/walking_stack_without_frame_pointers/attachments/slides/5934/export/events/attachments/walking_stack_without_frame_pointers/slides/5934/FOSDEM_2023_kernel.pdf https://fosdem.org/2023/schedule/event/walking_stack_without...) There are more optimisations we have in the works to make our unwinder more efficient, mostly related to fitting more data in the CPU cache and reducing cache misses.