When Greedy Algorithms Can Be Faster [C++]
5 comments
·January 28, 2025nxobject
hinkley
Very early games had lookup tables for trig functions. The cpu instructions were too slow or missing. The tables were either generated at run time or statically defined in the code.
I think that’s one of those things Jai and Zig agree on - compile time functions have a place in preventing magic numbers that cannot be debugged.
cozzyd
I suspect if you started using SIMD instructions, the analytical case would get better again (since it's branchless).
nxobject
Apropos of SIMD – I'm also surprised that the inner loop of the rejection-based algorithm optimized to MMX, but not the analytic algorithm!
I would like to think the rejection algorithm after -O3 is benefiting from branch prediction and all sorts of modern speculation optimizations. But I imagine the real test of that would be running these benchmarks would be running these benchmarks on a 5-10ish year old uarch.
Sesse__
Ten years ago, you already have Skylake with pretty good indirect branch predictors...
I don't know how numerics in hardware works, but would the use of functions like sin, cos, sqrt incur a penalty as well, even if only a slight one?
It's really fascinating to think about how all of this would work.