Remove I64x2/F64x2 instructions

[binji]

We discussed this at the 2019 CG meeting and decided to remove the i64x2/f64x2 instructions until there is performance data to justify their inclusion.

See https://github.com/WebAssembly/meetings/blob/master/2019/CG-06.md#simd--1-hr.

[mratsim]

What kind of performance data would be needed?

I64x2 SIMDs operations would be very useful for hash functions and cryptography in general.

[arunetm]

Typically any real world workload (crypto kernel) implemented using the 64x2 types showing performance benefits compared to an implementation without these types will help.

[AndrewScheidecker]

I don’t have an i32-only baseline, but here’s a Blake2b implementation for WASM SIMD that uses i64x2.add and i64x2.shr_u heavily: https://github.com/WAVM/WAVM/blob/master/Examples/blake2b.wast

Blake2b is specifically designed for efficient implementation using i64x2 SIMD, so I expect that emulating the i64x2 operations with i32x4 operations would be much slower.

[ngzhian]

@mratsim @arunetm do you have specific libraries/benchmarks in mind? I am prototyping 64x2 instructions and having specific tests to run will be helpful.

[gnzlbg]

Computing the mandelbrot set is one of the benchmarks used in the Dart Javascript SIMD paper that uses 64x2 instructions.

[ngzhian]

Are you referring to:

McCutchan, John, et al. "A SIMD programming model for Dart, JavaScript, and other dynamically typed scripting languages." Proceedings of the 2014 Workshop on Programming models for SIMD/Vector processing. ACM, 2014. ?

I check out the linked codebase (https://github.com/tc39/ecmascript_simd/tree/master/src/benchmarks) and it doesn't look like the benchmarks use 64x2 instructions.

[gnzlbg]

Yes, that's the paper. They did not add a 64x2 vector type, so Dart cannot use it. Here is the performance of Dart at a Mandelbrot implementation that uses 64-bit values compared against that of many other programming languages: https://benchmarksgame-team.pages.debian.net/benchmarksgame/performance/mandelbrot.html .

IIRC the machine where those benchmarks run is a core2, and most of the results that are < 2.0x slower than the fastest generate machine code that use 64x2 vector instructions.

[lemaitre]

I am very doubtful about this benchmark when I see Fortran 4.5 times slower than C. They probably messed their implementation up.

Concerning i64x2, it's not that algorithms need to process 64 bit integers and they need to process them fast.
Because that is very rare.
However, processing 64 bit floats is much more common (for instance Mandelbrot).

When you deal with SIMD, you should try to have all your data type of the same size in order to avoid resizing your data over and over again.
Resizing means internally shuffling your vector, and shuffling is surprisingly slow.
On x86, you can do a single shuffle operation per cycle (in comparison, you can do 3 to 4 bitwise operation per cycle).
Please note that widening and narrowing instructions require to shuffle and are bound to a throughput of 1 instruction per cycle (shared with other shuffling instructions).

If you don't have i64x2, you will have no choice but shuffling your data each and every time you need to process both integers and floats.

This is the reason why we need to have i64x2, even if only very few algorithms need integers that wide.
Have you ever wondered why PowerPC and Arm added i64x2 when they added f64x2? Now, you know!

EDIT: Mea culpa. I forgot that the topic was about removing not only i64x2 but also f64x2...

[gnzlbg]

I am very doubtful about this benchmark when I see Fortran 4.5 times slower than C. They probably messed their implementation up.

Clicking on a benchmark reveals its source code, the compiler options used to compile it, etc. so could you be a bit more precise on which part of the Fortran implementation is "messed up"?

The C programs are explicitly using the SSE instructions that the WASM opcodes being considered for removal would lower to, and most of them are also parallelized. The Fortran benchmarks do not use explicit SSE instructions because Fortran does not have intrinsics for them.

[lemaitre]

I don't write Fortran myself, but I know that optimizing Fortran compilers are more effective than optimizing C compilers because of the rules of Fortran (mainly aliasing rules). So I would expect at least similar performance between fully optimized C and fully optimized Fortran.
There might not be any SIMD intrinsics in Fortan, but this cannot explain a factor 4.5 between the C and Fortran with SSE (maximum expected speedup x2), and Fortran is usually well vectorized.
Plus, Mandelbrot is not that easy for SIMD and it is very hard to get perfect speed up on it (because of the divergence of the control flow).
So where is the x2.5 factor missing in Fortran?

That's what I mean when I say there is something weird with this benchmark.

[gnzlbg]

So where is the x2.5 factor missing in Fortran?

Probably a combination of vectorization, parallelization, and memory layout, all of which differ between the Fortran benchmark and the C benchmarks.

maximum expected speedup x2)

I don't think this is correct. If you go from scalar code with a data-dependency, to SIMD code without data-dependencies, you can increase throughput by N * M where N is the number of vector landes and M is the number of SIMD instructions that can be scheduled in parallel (i.e. the number of ports that support each instruction).

Plus, Mandelbrot is not that easy for SIMD and it is very hard to get perfect speed up on it (because of the divergence of the control flow).

On a similar machine and using the same techniques as the C code we do reproduce their results, getting a ~4x speedup with respect to scalar code with both Rust std::simd and ISPC (e.g. see here).

[lemaitre]

Probably a combination of vectorization, parallelization, and memory layout, all of which differ between the Fortran benchmark and the C benchmarks.

Fortran compilers vectorize in the same way as c compilers do, and they use the same multithread library (OpenMP). The default memory layouts are different, sure (and Fortran has usually a better default than C concerning vectorization).
In both languages, you can force other memory layouts. So when your goal is to compare what is the fastest, you should consider these kind of transformations.

I don't think this is correct. If you go from scalar code with a data-dependency, to SIMD code without data-dependencies, you can increase throughput by N * M where N is the number of vector landes and M is the number of SIMD instructions that can be scheduled in parallel (i.e. the number of ports that support each instruction).

If your scalar code has data-dependency where your SIMD one doesn't, then why can't you write scalar without data-dependencies? SIMD only cannot give higher speedups than the cardinal of the SIMD. If you gain more, then you have applied other transformations that could have been applied to the scalar code as well.

On a similar machine and using the same techniques as the C code we do reproduce their results, getting a ~4x speedup with respect to scalar code with both Rust std::simd and ISPC

A x4 speedup can also be explained by using AVX. But if that's the case, then it is not really relevant to the current discussion.

Another thing weird with those benchmarks: the C++ code is faster than the C while no C++ feature has been used. Should not C be as fast as the C++ if the code is C in both cases?
If the C++ version has not been compiled in C while it is already C, then the benchmark is fishy.

A last thing, the best C++ code has intrinsics for SSE, AVX and AVX512, while the command line is -march=native -msse3: is it really SSE? I checked that last point on my machine, and if you have -march=native while you also have -msse, you compile for the union of your machine and SSE, not the intersection nor the last. So how can I be sure their benchmark was only SSE? In fact, seeing this, I'm now pretty sure it wasn't. The second fastest is C, and looking at the code, this one has __m128d hardcoded, so is SSE only.

Is it a fair comparison? I don't know, and I have no way to know. So it's at the very least questionable.
Do I trust this benchmark? No, because of the previous reasons: it is far too questionable and fishy to merit my trust. And I want you to understand these problems with this benchmark and suggest not to rely on it.

[gnzlbg]

Is it a fair comparison? I don't know, and I have no way to know.

Of course you have a way to know. You could actually click the links, read them, google what you don't understand or ask, c&p the assembly in godbolt and clarify your own questions (https://godbolt.org/z/mDEt68).

Instead, you just claim that Fortran is faster than C and therefore those results are incorrect, and then go completely offtopic about which vector instructions C or Fortran might be using even though both are compiled with -march=native on the same host and therefore are allowed to use the exact same set of instructions.

I still claim that:

most of the results that are < 2.0x slower than the fastest generate machine code that use 64x2 vector instructions.

and I think this disproves the claim that 64x2 instructions are useless.

[penzn]

"Benchmakring game" seems to be a set of unrelated implementations, by lots of different people. I don't think it is practical to compare those to each other (other than for fun); for example, there is this single-threaded scalar C implementation that does very poorly. The top ones use SIMD and threads, bottom ones are completely sequential; even if they produce the same result, they get to it in dramatically different ways from performance point of view.

If you are interested in using SIMD semi-directly in Fortran, there are OpenMP SIMD directives, let me know if you want to submit an implementation, I could probably help :)

Back to the topic, I personally see value in 64-bit ops: double precision floats are important, and it makes sense to include them for at least for compatibility reasons in SIMD operations, with a similar argument for int64. I also agree that they should be faster than scalar, we just don't know by how much. I know there was a group vote to exclude them from spec, so if we want them in, we might need to provide justification. Let me see if I can pull up any compute code, but if you have any (or can think of any), let's take a look at that as well.

[lemaitre]

Of course you have a way to know. You could actually click the links, read them, google what you don't understand or ask, c&p the assembly in godbolt and clarify your own questions (https://godbolt.org/z/mDEt68).

I don't have time to put that much time in the process, and I guess I'm far from being the only one in that case. My point is, this benchmark is not reliable. If you want to prove anything, either you create your own unbiased benchmark, or you find a well crafted benchmark that expose the results.

Instead, you just claim that Fortran is faster than C and therefore those results are incorrect

I've never said the results were incorrect, I just said that is highly surprinsing to see Fortran x4.5 slower despite being usually at least as good as C (and is not explained just by the absence of SIMD intrinsics). And that encourages suspicion, like the other points I made.

then go completely offtopic about which vector instructions C or Fortran might be using even though both are compiled with -march=native on the same host and therefore are allowed to use the exact same set of instructions.

You misunderstood my last point: I just wanted to show the possible biases that this benchmark has, and why you probably don't want to rely on it. It was not about Fortran.

I think this disproves the claim that 64x2 instructions are useless.

That is exactly my point: by using questionable benchmarks, you disprove nothing. This creates an hint, not a proof.

Don't get me wrong, I also want to keep v64x2 operations avialable and I also think they have good performance impact when an algorithm need them. But if you want to convince people, I think you need better benchmarks.
Maybe that is only a concern for a scientist like me and most people don't care, but you wouldn't convince me with this very benchmark (even though I'm already convince of the usefulness ov v64x2).