AVX IFMA Accelerated `split_mul`

[kayabaNerve]

I prototyped a portable split_mul implementation premised on using the AVX IFMA instructions to accelerate itself. I believe I optimized it decently, the code is well-documented, the benchmark is easy to run, and the README explains the challenges moving forward. Unfortunately, despite observing a 20-40% improvement when compiled exclusively for the native CPU, I was unable to see any real-world performance benefit when I patched my crypto-bigint dependency to a fork which used this split_mul implementation when reasonable.

https://github.com/kayabaNerve/avx-ifma-mul

I'd love to see further discussion and potential upstreaming (again, as explained in the README). I would have entirely made this an issue if I did not want to provide the implementation + benchmark as an artifact (hence the repository).

[kayabaNerve]

Relevance #572.

Also, the obvious performance benefit is by introducing a Uintx4<N> type which provides four individual Uint values for which identical operations are simultaneously applied. I also have some code for that, yet replicating the entire Uint API over Uintx4 and having users figure out where that fits into their flow is a much more difficult task than accelerating the existing Uint type (which everyone immediately benefits from, ideally).

Funnily enough, I can't immediately think of why you couldn't implement the Integer trait for a Uintx4...

EDIT: AsRef<[Limb]>, BitOps, Ord, is_odd and is_even returning a Choice instead of a Choicex4...

[kayabaNerve]

The AVX-512 intrinsics are available via the latest stable.

With some further poking, I've written some derivative code which is able to do reduction (a scalar operation of notable cost, https://github.com/kayabaNerve/avx-ifma-mul/blob/1ff8d47759a967e68290b7a516327d2702e0cea1/src/lib.rs#L374-L385) as a vector operation with a non-uniform result. This causes the final to_bytes (https://github.com/kayabaNerve/avx-ifma-mul/blob/1ff8d47759a967e68290b7a516327d2702e0cea1/src/lib.rs#L387-L408, itself a scalar operation) to be the only code which has to do a scalar reduction. While this doesn't benefit the linked artifact, premising on re-formatting for mul, doing a single mul, and reformatting back, it benefits doing repeated operations within the 52-bit-word space.

A distinct optimization would be to make to_bytes non-scalar. lcm(52, 64) = 832, meaning that each [u52x4; 4] corresponds to a perfectly aligned set of 13 u64s. This allows to_bytes to loop through each [u52x4; 4] chunk and use handwritten parallel code within the loop body, due to the very specific input parameters/expected output. I don't believe it'd be feasible to have an algorithm which automatically finds a parallel conversion methodology for any about of 52-bit words in.

I believe a lot of the slowdown when the portable code is used may be due to LLVM not inlining as aggressively (and Rust's refusal to allow inline(always) on any function which requires target_feature). That aspect may be resolvable via replacing the low-level functions with macros, such that they inline the Rust code itself.