RustCrypto / RSA

RSA implementation in pure Rust
Apache License 2.0
550 stars 153 forks source link

Disable num-bigint-dig/u64_digit feature on wasm targets #252

Closed jameysharp closed 1 year ago

jameysharp commented 1 year ago

WebAssembly doesn't have 128-bit integers, so on wasm targets LLVM implements 128-bit multiplies with a libcall to __multi3. That's slower than just doing arithmetic on smaller units.

I patched the rsa crate to remove the u64_digit feature from the num-bigint-dig dependency, and tested the patched version with the blind-rsa-signatures crate. The toy demo app I tested ran 15% faster under Wasmtime with this patch.

It would be nice if either this crate or num-bigint-dig would automatically determine what limb size to use based on the build target. Barring that, perhaps this crate should expose its own u64_digit feature that forwards to num-bigint-dig.

tarcieri commented 1 year ago

FWIW I've been working on a crate for automatic limb size selection based on the target which we can reuse among the many crates within @RustCrypto:

tarcieri commented 1 year ago

@jameysharp curious what you use to benchmark WASM. It's something I've been wanting to figure out.

re: automatic limb size selection it seems like it will be tougher than I thought to pick good defaults for WASM. I have been leaning towards 64-bit though I wanted to check that via benchmarks.

Sidebar: crypto-bigint uses u128 in a few places where we want lowerings to adc/sbb on x86. Checking how that compiles on WASM in Godbolt, I don't see any use of __multi3:

https://godbolt.org/z/5b78hM1oz

tarcieri commented 1 year ago

Well, this isn't automatic, but it at least makes it possible to disable num-bigint-dig/u64_digit: #313