About
Cyclic Redundancy Check (CRC) is a standardized way to implement a degree of data validation and is used in various over the wire protocols, data checksums, etc. Naive implementations are a bitwise loop over an input message and highly inefficient. Detection of a CRC loop and transformation into either a table lookup or a combination of clmul + shift operations can speed up such code by 2X or more. This would include the CRC loop in the Coremark benchmark – detecting and optimizing that idiom results in about a 10% improvement in Coremark scores.
The detection of a CRC loop is a complex optimization with elements of vectorization, feedback loops, pattern matching, etc. It is further complicated by function inlining. At this time we have patches for upstream GCC that can detect and generate code (either table lookup or clmul) for a variety of CRC implementations. An aggressive schedule would be integration in time for gcc-14, but more likely it will fall into gcc-15.
Stakeholders/Partners
RISE:
Ventana: 1 FTE Contractor, ~1yr. Mariam Harutyunyan from Center of Advanced Software Technologies), lead developer
Ventana: Jeff Law – oversight
External:
Significant design work and theoretical backgrouind provided by Philipp Tomsich and Henry Brausen of VRULL
Dependencies
Status
Updates
- Dependency on CRC code being a distinct self-contained function removed, this generalization was the last major implementation roadblock for the initial implementation
- Using ~25 CRC implementations from Fedora as general testcases. Converts about 50% of them right now.
- Expecting to start breaking out independent chunks of work in the coming weeks to start upstreaming (CRC builtin/IFN support with backend expansion for example)
- Project reported as a priority for 1H2024