Reciprocal pre-compute operations for fast wide divisions

[MaxGraey]

I know the specification already rejects div/rem operations which is perfectly makes sense.

However, I'd like to discuss the possibility of adding not the high-level division operations themselves, but rather some of the underlying building blocks, specifically reciprocal_2by1 and possibly reciprocal_3by2.

The idea is similar to SSE's RCPSS/RCPPS, but targeted at wide integer arithmetic. Division by inversion is already used in a number of libraries that provide efficient division algorithms, and it was described in the following paper:
https://gmplib.org/~tege/division-paper.pdf

And how reciprocal_2by1 and reciprocal_3by2 looks like on practive.

btw not sure about Clang but GCC do this for loop inv divisors during compile time

reciprocal_2by1 is more important because it requires a lookup table, which costs size and performance on wasm side.

Furthermore, the reciprocal precomputation has optimization opportunities of its own. If the divisor is loop-invariant, the reciprocal step can be hoisted by LICM. Likewise, if multiple expressions use the same divisor, apply CSE. In that sense, representing the reciprocal explicitly as an IR-level or specific wasm op seems genuinely useful

WDYT?

[alexcrichton]

Would you be able to test out the performance of those function compiled as-is with wide arithmetic? Nothing in there looks obvious to me in terms of "native has an edge wasm doesn't". The main operator, umul, should already be satisfied by wide-arithmetic as-is today.

Could you benchmark, though, that C++ code compiled to native and that C++ code compiled to wasm? That would be telling if there's still a large gap in performance there.

[MaxGraey]

Could you benchmark, though, that C++ code compiled to native and that C++ code compiled to wasm? That would be telling if there's still a large gap in performance there.

Sure,

I probably will do this in Rust since it appears that neither Clang nor LLVM does the same thing as GCC so div as LI routine required manual code in any way.

[MaxGraey]

I created a repository with a small benchmark comparing compiler_rt div routines against a reciprocal-division approach across native and wasm targets. Wasm is tested on the latest Node.js (v26.0.0) and the latest Wasmtime (45.0.1).

The code is structured so it should be easy to later extract two or three operations, such as i64.recip128 and i64.divrem_recip128 / i64.divrem_recip128_{u|s}.

The reciprocal approach can likely be made even faster. Right now it uses a generalized div/rem form, so specialized versions may provide a larger speedup due to smaller code size and fewer branches. Limbs are also used throughout the code to ensure consistent behavior between native and wasm. Using u128/i128 for wide mul can provide an even bigger performance boost for recip version compare to builtin. Even in this form, the native reciprocal-div version clearly beats the standard implementation.

On WebAssembly, however, the result is accurately the opposite! The reciprocal version is significantly slower (execpt divrem_loop_invariant case). To me, this is a clear signal that adding two or three new div/recip operations is worth considering.

Please try running the benchmark on your machine. I am especially interested in results from aarch64/arm systems.

Repo:
https://github.com/MaxGraey/wasm-i128-div-bench

Report result for x86:
https://github.com/MaxGraey/wasm-i128-div-bench/blob/main/report/RESULTS-b7f9c68a.md

Native

bench	builtin	reciprocal	rel
udivrem128	28.54 ns	27.04 ns	-5.3%
udiv128	28.41 ns	26.47 ns	-6.8%
urem128	29.06 ns	26.74 ns	-8.0%
sdivrem128	34.48 ns	31.18 ns	-9.6%
sdiv128	32.97 ns	31.54 ns	-4.3%
srem128	32.86 ns	29.13 ns	-11.3%
divrem_loop_invariant	136.99 µs	40.55 µs	-70.4%

Node (V8)

bench	builtin	reciprocal	rel
udivrem128	34.84 ns	39.77 ns	+14.1%
udiv128	30.03 ns	38.33 ns	+27.6%
urem128	30.36 ns	38.24 ns	+25.9%
sdivrem128	36.93 ns	42.96 ns	+16.3%
sdiv128	32.72 ns	40.87 ns	+24.9%
srem128	32.78 ns	40.70 ns	+24.2%
divrem_loop_invariant	63.04 µs	46.56 µs	-26.1%

wasmtime (Cranelift)

bench	builtin	reciprocal	rel
udivrem128	38.76 ns	44.77 ns	+15.5%
udiv128	32.04 ns	44.51 ns	+38.9%
urem128	32.45 ns	43.42 ns	+33.8%
sdivrem128	40.83 ns	47.47 ns	+16.3%
sdiv128	35.33 ns	45.85 ns	+29.8%
srem128	36.21 ns	44.94 ns	+24.1%
divrem_loop_invariant	80.33 µs	57.66 µs	-28.2%

Cross-runtime: wasm cost vs native

% = (runtime - native) / native for the same implementation; positive means
slower than running native.

bench	recip: node	recip: wasmtime	builtin: node	builtin: wasmtime
udivrem128	+47.1%	+65.6%	+22.1%	+35.8%
udiv128	+44.8%	+68.1%	+5.7%	+12.8%
urem128	+43.0%	+62.4%	+4.5%	+11.7%
sdivrem128	+37.8%	+52.2%	+7.1%	+18.4%
sdiv128	+29.6%	+45.4%	-0.8%	+7.1%
srem128	+39.7%	+54.3%	-0.2%	+10.2%
divrem_loop_invariant	+14.8%	+42.2%	-54.0%	-41.4%

[jakobkummerow]

The key ingredient to expressing the algorithms from https://gmplib.org/~tege/division-paper.pdf in Wasm is the i64.mul_wide_u instruction, which is already part of this proposal (but not used by that microbenchmark AFAICS).

I don't see why creation or application of the reciprocal would need to be represented as a Wasm instruction. LICM'ing the computation of the reciprocal should be done by Wasm-producing toolchains. Performance of computing the reciprocal is largely irrelevant, because it's computed once and then used many times; if it was used only once then regular division would be faster. I'm not sure what that benchmark is supposed to be measuring, but it doesn't look like it's producing data points that support the idea that this proposal would benefit from any additional instructions.

(The fact that repeated divisions by the same divisor can be made faster by computing that divisor's multiplicative inverse is well known and does not need proving. The question is whether this proposal already supports that technique well enough.)

[MaxGraey]

LICM'ing the computation of the reciprocal should be done by Wasm-producing toolchains.

This cannot be done with __udivti3 / __umodti3 and neither LLVM nor the runtimes do this. You can literally see this on divrem_loop_invariant bench results.

i64.mul_wide_u

it's mul128. But I don't use wide arithm proposal for wasm. multiply is not a bottleneck here anyway. Also note that mul128 is intentionally used in native target as well, so it's a tie.

The fact that repeated divisions by the same divisor can be made faster by computing that divisor's multiplicative inverse is well known and does not need proving. The question is whether this proposal already supports that technique well enough.

Exactly, but LLVM, and most likely other runtimes & compilers, such as the JVM, do not do this. Currently only GCC and some of AP int libraries use this approach.

My proposal is to make it the standard lowering strategy for everyone. That way, we would not be relying on a particular toolchain, compiler, or runtime implementation. Everyone would get the same deterministic and optimal performance.

[MaxGraey]

Ok, I added native wide multiplication via feature:

#[cfg(feature = "native-wide-mul")]
#[inline(always)]
fn mul128(a: u64, b: u64) -> (u64, u64) {
    split((a as u128) * (b as u128))
}

and this changes native results for reciprocal are dramatically getting better:

Full Report Results with Native Wide Multiply

Native

bench	builtin	reciprocal	rel
udivrem128	27.55 ns	19.61 ns	-28.8%
udiv128	26.36 ns	19.48 ns	-26.1%
urem128	26.99 ns	18.99 ns	-29.7%
sdivrem128	32.65 ns	22.02 ns	-32.6%
sdiv128	31.06 ns	21.77 ns	-29.9%
srem128	33.44 ns	21.57 ns	-35.5%
divrem_loop_invariant	133.38 µs	4.22 µs	-96.8%

Node (V8)

bench	builtin	reciprocal	rel
udivrem128	34.84 ns	39.77 ns	+14.1%
udiv128	30.03 ns	38.33 ns	+27.6%
urem128	30.36 ns	38.24 ns	+25.9%
sdivrem128	36.93 ns	42.96 ns	+16.3%
sdiv128	32.72 ns	40.87 ns	+24.9%
srem128	32.78 ns	40.70 ns	+24.2%
divrem_loop_invariant	63.04 µs	46.56 µs	-26.1%

wasmtime (Cranelift)

bench	builtin	reciprocal	rel
udivrem128	38.34 ns	53.66 ns	+39.9%
udiv128	32.19 ns	48.62 ns	+51.0%
urem128	33.04 ns	48.90 ns	+48.0%
sdivrem128	41.52 ns	51.49 ns	+24.0%
sdiv128	35.87 ns	50.48 ns	+40.7%
srem128	34.92 ns	50.93 ns	+45.9%
divrem_loop_invariant	77.85 µs	65.15 µs	-16.3%

Cross-runtime: wasm cost vs native

% = (runtime - native) / native for the same implementation; positive means
slower than running native.

bench	recip: node	recip: wasmtime	builtin: node	builtin: wasmtime
udivrem128	+102.8%	+173.6%	+26.5%	+39.2%
udiv128	+96.7%	+149.5%	+14.0%	+22.1%
urem128	+101.4%	+157.5%	+12.5%	+22.4%
sdivrem128	+95.1%	+133.9%	+13.1%	+27.2%
sdiv128	+87.7%	+131.9%	+5.3%	+15.5%
srem128	+88.7%	+136.2%	-2.0%	+4.4%
divrem_loop_invariant	+1003.1%	+1443.5%	-52.7%	-41.6%

[alexcrichton]

Procedurally this proposal is currently pretty far along and one I'd like to move to stage 4 (stabilize) in the near future as well. In that sense the bar for adding something new or changing things is pretty high at this point, so @MaxGraey I'm going to be leaning on you to do a lot of the leg work here to prove out this new hypothetical instruction. I'm not currently convinced about adding these instructions, but I want to ask some questions of you which may involve collecting more numbers/etc to figure out what's going on.

• First is that I don't see -Wwide-arithmetic, enabling this proposal, in your scripts. I also don't see -Ctarget-feature=+wide-arithmetic when compiling wasm in your repository. I also don't see -Zbuild-std to rebuild compiler-builtins, which defines __udivti3 for example, with wide-arithmetic. This means that, I think, all of your benchmarks are comparing wasm as-is today without wide-arithmetic to native. I wouldn't consider this a useful comparison because as @jakobkummerow mentioned it's expected that 128-bit division can be accelerated with a "wide multiply" used internally. Benchmarks and comparisons should all enable this proposal to be used.
• I previously measured bignum division to be 36-39% slower than native with wide-arithmetic enabled. This looks pretty similar to your "builtin" column. My conclusion at the time was that the remaining overhead was unrelated to the division operation itself and was probably just "general overhead" spread throughout the rest of the system. Do you have a reason to suspect otherwise? How are you certain that the division operation itself is the slow part here?
• For the most egregious number, the divrem_loop_invariant benchmark with the "recip" algorithm, do you know why wasm is so much slower? Can you do performance analysis to figure out what's so different on native vs on wasm? Is this just a case of some compiler heuristic needing tweaking on wasm? A missing entire class of instructions? Something related?

I can at least start there, but I want to make sure to set expectations in the sense that I don't plan on proactively investigating a lot of this myself. I consider that at this stage of development the burden is on you @MaxGraey to show the use case for a new instruction, what it would be, why it's needed, how it would be implemented, and the performance impact. When I first developed this it involved me having a local fork of wasm-tools/wasmtime/LLVM/rust/etc all in-sync to experiment with different variations of instructions and such. This is likely what's going to be required to answer all of these questions fully.

[MaxGraey]

For the most egregious number, the divrem_loop_invariant benchmark with the "recip" algorithm, do you know why wasm is so much slower? Can you do performance analysis to figure out what's so different on native vs on wasm? Is this just a case of some compiler heuristic needing tweaking on wasm? A missing entire class of instructions? Something related?

I think it's notive vs soft wide mul. For soft-version reciprocal (native) 40.55 µs vs (v8) 46.56 µs so mostly the same. But with hardware wide mul, we have dramatically bigger gap between them for divrem_loop_invariant.

So you're right. I need to add support for wide arithmetic for all toolchain so that wasm benches have the same level of parity.

I'll try adding all the flags and testing them on the Node.js nightly build.

I also measured the distribution of the composite operation across its parts by time:

udivrem128 53 ns:

• reciprocal part 29 ns - ~55%
• divrem part 24 ns - ~45%

And it is the reciprocal part (i64.recip128) that accounts for the majority of wide multiplications

[MaxGraey]

Algiht, I updated benchmark. wide-arithmetic is enabled for rust and all runtimes. Also, I simplified recip code a little for avoid limbs for add, sub and mul. See changes here. @alexcrichton let me know if I need to add or change something.

Full report

v8 adds +20-45% and wasmtime adds +50-70% (+20-42% after param order opt) overhead for wasm if we ignore divrem_loop_invariant bench case.

Updated results:

UPDATE: use -C cpu=native + xorshift128++ rand for all targets

Native

bench	builtin	reciprocal	rel
udivrem128	27.86 ns	17.18 ns	-38.3%
udiv128	26.73 ns	16.95 ns	-36.6%
urem128	27.11 ns	17.10 ns	-36.9%
sdivrem128	30.50 ns	21.52 ns	-29.4%
sdiv128	28.76 ns	20.57 ns	-28.5%
srem128	28.98 ns	19.61 ns	-32.3%
divrem_loop_invariant	134.44 µs	9.73 µs	-92.8%

V8 (d8)

bench	builtin	reciprocal	rel
udivrem128	18.27 ns	24.38 ns	+33.4%
udiv128	19.57 ns	24.17 ns	+23.5%
urem128	19.47 ns	24.58 ns	+26.3%
sdivrem128	21.21 ns	25.36 ns	+19.6%
sdiv128	20.21 ns	24.72 ns	+22.3%
srem128	20.41 ns	24.82 ns	+21.6%
divrem_loop_invariant	29.67 µs	18.24 µs	-38.5%

wasmtime (Cranelift)

bench	builtin	reciprocal	rel
udivrem128	22.34 ns	22.39 ns	+0.2%
udiv128	20.49 ns	22.22 ns	+8.4%
urem128	20.42 ns	22.52 ns	+10.3%
sdivrem128	25.32 ns	25.15 ns	-0.7%
sdiv128	23.53 ns	24.14 ns	+2.6%
srem128	23.21 ns	23.60 ns	+1.7%
divrem_loop_invariant	52.51 µs	13.97 µs	-73.4%

Cross-runtime: wasm cost vs native

bench	recip: d8	recip: wasmtime	builtin: d8	builtin: wasmtime
udivrem128	+41.9%	+30.4%	-34.4%	-19.8%
udiv128	+42.6%	+31.1%	-26.8%	-23.3%
urem128	+43.7%	+31.6%	-28.2%	-24.7%
sdivrem128	+17.9%	+16.9%	-30.5%	-17.0%
sdiv128	+20.2%	+17.4%	-29.7%	-18.2%
srem128	+26.5%	+20.4%	-29.6%	-19.9%
divrem_loop_invariant	+87.5%	+43.7%	-77.9%	-60.9%

[alexcrichton]

That matches my intution in the sense that a / b for 128-bit types is on-par with native (although faster than native is a bit surprising...). It seems like the remaining piece here is the "recip" algorithm has more overhead on wasm than (I assume) expected. You'll need to dig in to understand why that is. For example is it a missing instruction? Is it a missing compiler flag? Is it different defaults for wasm-vs-native? I'm not sure what the answer is, but just saying wasm is slower isn't the full story, there needs to be a more complete explanation as to why wasm is slower for justifying something like a new instruction.

[MaxGraey]

It seems like the remaining piece here is the "recip" algorithm has more overhead on wasm than (I assume) expected

Actually, this is what I expected, since recip uses a lookup table and performs table lookups.

But I'll try to dig deeper into it tomorrow.

[MaxGraey]

Another interesting observation is that builtin divisions run faster in wasm runtimes than in native code. And because of that, it introduces an accumulating diff effect.

[MaxGraey]

Another interesting observation is that builtin divisions run faster in wasm runtimes than in native code.

I found out that Rust uses different division algorithms for different targets:

https://github.com/rust-lang/rust/tree/main/library/compiler-builtins/compiler-builtins/src/int/specialized_div_rem

• wasm uses specialized trifecta div algo

• x86 uses specialized asymmetric div algo. Asymmetric utilized hardware's divq and, at first glance, should be more efficient, but inside the loops, it's much worse than soft compound div algos due to invariant parts which can be optimized by JIT & LICM (but that's just my assumption) or divq is much slower on my Coffee Lake cpu than soft trifecta

@alexcrichton
that explains a lot. It appears that relying on Rust's native divs isn't really a good idea for comparison between native vs. wasm. And only my implementation of reciprocal div is truly platform/target deterministic.

UPDATE

Also this might be interesting to you and the Wasmtime team.

It looks like there's a missed optimization and a perf gap between V8 and Wasmtime related to sensitivity to the ordering of function arguments and return values. In this commit I rearranged input/output params into a more stack-friendly order so that there were no temp local vars between two wasm operations, and that resulted in 20-25% perf boost for wasmtime while v8 stayed immune to such reordering in term of perf.

[MaxGraey]

Friendly ping. As shown above all Rust's division benches on native vs wasm are not an apples-to-apples comparison since the Rust compiler applies different lowering strategies for 128-bit divisions for these targets.

If there is any additional proofs, benchmarks or validation needed from my side please let me know.