"Magic" algorithms / Low-level optimizations
Posted: Mon Apr 13, 2009 3:22 pm
aggregate.org/MAGIC is highly recommended reading (from my professor's supercomputer group).
Index of AlgorithmsThere are lots of people and places that create and collect algorithms of all types. Unfortunately, in building systems hardware and software, we in The Aggregate often have found it necessary to do relatively obscure low-level things very efficiently. Many of the tricks we've devised or collected either require assembly language coding or are not entirely portable when coded in HLLs like C, but these techniques are still valuable because they can yield significant performance improvements over the more obvious ways of doing things.
- Absolute Value of a Float
- Alignment of Pointers
- Average of Integers
- Bit Reversal
- Comparison of Float Values
- Comparison to Mask Conversion
- Divide Rounding
- Dual-Linked List with One Pointer Field
- GPU Any
- Gray Code Conversion
- Integer Constant Multiply
- Integer Minimum or Maximum
- Integer Power
- Integer Selection
- Is Power of 2
- Leading Zero Count
- Least Significant 1 Bit
- Log2 of an Integer
- Next Largest Power of 2
- Most Significant 1 Bit
- Natural Data Type Precision Conversions
- Polynomials
- Population Count (Ones Count)
- Shift-and-Add Optimization
- Sign Extension
- Swap Values Without a Temporary
- SIMD Within A Register (SWAR) Operations
- Trailing Zero Count
