Implement SIMD where applicable

[olback]

What got me looking into this was the somewhat slow key generation and the related issue #29. A solution or rather, improvement would be to implement SIMD, Single Instruction Multiple Data. I found a paper by freescale semiconductor on this topic here: http://application-notes.digchip.com/314/314-66328.pdf.

Since all processors do not support the AVX/SSE/SIMD family of instructions, this would have to be implemented under a feature flag or as in the case of aes_gcm, the feature is enabled when the compiler is passed these flags:

RUSTFLAGS="-Ctarget-cpu=sandybridge -Ctarget-feature=+aes,+sse2,+sse4.1,+ssse3"

Update: What takes time during key generation is finding big primes, and that is done here: https://github.com/dignifiedquire/num-bigint/blob/master/src/bigrand.rs#L324-L371

I might take a deeper look at this when my exams are over.

[zicklag]

I would suggest looking/asking around about the best ways to support SIMD in Rust, too, because I think there are crates that allow for determining whether or not to use SIMD at runtime based on CPU features and such.

[tarcieri]

Yes, there's a stable std::is_x86_feature_detected macro as well as the cpuid-bool cpufeatures crate. There's also a nightly-only std::is_arm_feature_detected macro. But these are only helpful after you have a SIMD backend in the first place.

Another crate to look at is packed_simd, which is an implementation of the std::simd proposal. Unfortunately, it's also nightly-only.

[burdges]

Any idea what is optimal here? We'd first want some fixed size bigint crate that avoids the Vec used by num-bigint? We'd then do SIMD support only for that crate? Or something more bespoke?

[tarcieri]

We'd first want some fixed size bigint crate that avoids the Vec used by num-bigint?

This is what we wrote crypto-bigint for: https://github.com/rustcrypto/crypto-bigint

Should have another release soon, although it doesn't yet have any SIMD features.

One thing I can try to do prior to the next release is add support for loading certain sizes of big ints (it's using const generics internally, but still allows specialization around size) into SIMD registers, which will at least leave the door open for SIMD optimizations.