Should 128-bit comparison operators be added?

[alexcrichton]

This idea was raised at the last CG meeting and hasn't been investigated yet. Should 128-bit comparison operators (lt, gt, etc) be added to this proposal as well?

Performance and generated code should be evaluated for these operations today in comparison with what native platforms do. Ideally a benchmark or microbenchmark could be created to compare before/after performance of hypothetical operations.

[alexcrichton]

Some investigation about this. Here's an example of what native platforms generate for 128-bit comparisons across a few architectures. This is what LLVM generates WebAssembly-wise and what Wasmtime compiles to native platforms.

On x86_64 and aarch64 the generated code is significantly worse due to not being able to use sbb or sbcs that the native lowering uses. On riscv64 the generated code looks mostly similar to native and native profiling would be needed to show if it's measurably worse.

Without actually having a benchmark at this time to measure it appears that naively there's a lot of room to improve here and it might be worthwhile to add 128-bit comparison instructions.

[jameysharp]

I'm curious what wasm LLVM generates for comparisons when you enable any of the extensions you've already prototyped for this.

Integer comparison boils down to doing a subtraction and then checking how the result compares to zero. I predict that any extension supporting arbitrary-precision subtraction should get closer to native code for this case.

[alexcrichton]

I tried this out locally and LLVM's default lowerings didn't use i64.sub_overflow_u or i64.sub_with_carry_u for comparisons by default. Not to say they couldn't be used, only that it would require more custom code to generate such lowerings

[alexcrichton]

With some benchmarking at https://github.com/alexcrichton/wasm-benchmark-i128 I've collected these numbers. The benchmark here is to generate an array of 128-bit numbers and then sort it and time how long that takes. The assumption is that this includes a lot of compares so should be good at stressing this. Numbers are slowdowns relative to native, lower is better.

The x86_64 computer here is Intel(R) Core(TM) i9-14900K and the aarch64 computer is a macOS M2 Pro.

Engine	sort signed	sort unsigned
x86_64 Wasmtime 24.0.0	38%	36%
x86_64 Spidermonkey 130.0b6	59%	57%
x86_64 v8 13.0.3	47%	46%
x86_64 JSC 282428	88%	85%
aarch64 Wasmtime 24.0.0	55%	54%
aarch64 Spidermonkey 130.0b8	68%	69%
aarch64 v8 13.0.38	55%	54%
aarch64 JSC 282574	51%	49%

This shows to me that there's a large enough gap of performance that it's worth investigating prototyping these opcodes and seeing how they perform to see if the gap closes significantly.

[alexcrichton]

I've done a prototype of eight new opcodes i64.{l,g}{t,e}128_{u,s} in LLVM/wasmtime and am going to recollect results. In doing so I am using Rust's master branch which is a newer version than what I tested above (stable 1.80). There's a different sorting algorithm in the standard library now so I'm also going to recollect the number from above with existing engines as well. I've additionally enabled the +simd128 feature when compiling code since the native version uses this to move 128-bit values from place to place and helps close the gap to focus only on the comparisons here.

Same computer as before with Intel(R) Core(TM) i9-14900K and a macOS M2 Pro. Rust is roughly nightly-2024-08-22. Numbers are slowdown-relative-to-native, lower is better.

Engine	sort signed	sort unsigned
x86_64 Wasmtime 25ish	79%	95%
x86_64 Spidermonkey 130.0b6	99%	118%
x86_64 v8 13.0.3	68%	85%
x86_64 JSC 282428	66%	80%
aarch64 Wasmtime 25ish	76%	74%
aarch64 Spidermonkey 130.0b8	76%	74%
aarch64 v8 13.0.38	65%	63%
aarch64 JSC 282574	64%	64%

Next I compared before/after for these benchmarks with the 128-bit comparison opcodes. Note the inverted columns/rows a bit here.

arch / benchmark	before	after
x86_64 signed	79%	57%
x86_64 unsigned	95%	72%
aarch64 signed	76%	101%
aarch64 unsigned	74%	100%

Notably x86_64 did improve, but not by a huge amount (for Wasmtime at least). Additionally aarch64 got slower with the 128-bit comparisons. Investigating a bit it looks like 128-bit comparisons on aarch64 aren't as optimized as they are on x86_64 for Wasmtime which likely explains the slowdown.

---

Overall to me at least this isn't providing a compelling story to add comparison-related opcodes. It appears that the comparison-related bits on aarch64/x86_64 are relying on sbb and overflow-flag related primitives so it might be best to explore #6 for the purposes of closing the gap in performance on this benchmark. Notably that would require likely more clever management of the EFLAGS register and such.

In looking at the profile of x86_64 after the 128-bit comparisons were added it looks like "more clever management of EFLAGS" would also help improve performance for Wasmtime at least. Wasmtime is a bit too eager to rematerialize comparisons it seems as the Wasmtime-generated code is performing the comparison more than the x86_64 native code which relies on carrying EFLAGS across some instructions which don't modify flags.

[alexcrichton]

I'm curious what wasm LLVM generates for comparisons when you enable any of the extensions you've already prototyped for this.

I tried this out locally and LLVM's default lowerings didn't use i64.sub_overflow_u or i64.sub_with_carry_u for comparisons by default

I poked around at this some more and found that there's a SETCCCARRY opcode in LLVM's backend IR which corresponds to SETCC cc, lhs, (rhs+carry) but doesn't let rhs+carry overflow. This opcode wasn't implemented in my branch with *_carry and *_overflow ops which is why it didn't get used. That being said translating this to carry/overflow ops I personally found pretty difficult. If we went this route my guess is that we might need to go down the route of adding i64.{l,g}{e,t}_carry_u : [i64 i64 i32] -> [i32] to to make it possible to pattern match all the output. This would correspond more closely to what SETCCCARRY is.

[alexcrichton]

Further thinking on this is that it's actually relatively easy to pattern-match 64-bit comparisons used to compose a 128-bit comparison. I implemented that in bytecodealliance/wasmtime#9176 and received the same speedup as using the native wasm instructions.

Given that I'm personally continuing to lean in the direction of "no" for this extension.

[alexcrichton]

I've summarized much of the above into #14

[alexcrichton]

I'm going to close this as "no" with the summary here