Associative Iteration - Shaping Ancient Mathematical Knowledge Into Powerful Bit-fiddling Techniques
Talkat CppCon 2024 · on Monday, 2024-09-16· at 16:45· Cottonwood 8/9, 6700 North Gaylord Rockies Boulevard·
summary
Claims associative repetition reduces certain monoid loops from O(log(N)) vs O(N) by using bit-count-driven composition, provides a templated function that instantiates lanewise operations for the SW library and implements elementwise parallel multiplication for arbitrary widths, and demonstrates the compiler emitting compact LEA/addition-chain assembly rather than naive loops. The technique uses the most significant bit regressive wave and lane masks, shows concrete asm and performance wins, and the implementation works as advertised.
AI-written summary · about
chapters (12)
- 0:00Welcome
- 1:07Associative iteration
- 6:09Associativity in algorithms
- 8:58Egyptian multiplication
- 13:00Generalizing to monoids
- 17:57SAR SIMD library
- 20:50Parallel multiplication
- 23:18Parallel exponentiation
- 26:41Compiler optimizations
- 29:55Performance benefits
- 31:20Future applications
- 32:23Q&A
related talks
52mAdvanced SIMD Algorithms in Pictures
05mSigned Integers: Faster and Corrector
45mFreaking computers, how do they work?
48m[a bit noisy] Optimizing Generic Algorithms
08mOn "simple" Optimizations
38mEngineering Software Integral Types
42mFaster programs with your compilers autovectorization feature
01h 00mJust-in-Time Compilation