4 ms·
Nice! One suggestion: binary search has extremely poor cache behavior, and early versions of the ORC in winder (IIRC) spent considerably more time binary searc
by 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 agoThis 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.