News for hackers. Stuff that matters.
Re:SIMD Everywhere: 0.5.0 by Const-me on Tuesday August 04, 2020 @08:33AM (#24049284)
I sometimes write code portable across SSE4 and NEON, and I'm not sure this is going to work fast enough for that. There're important unique features.

SSE has shuffles, pack/unpack, movemask, 64-bit doubles, testzero, float rounds, blends, integer averages, float square roots and dot product.

NEON has interleaved RAM load/stores, vectors operators with scalar other argument, byte swap, rotate, bit scan and population count, and versions of all instructions processing 8-byte long vectors.

That's enough differences that I have to adjust both algorithms and data structures to be portable between them. I'm not convinced it's possible to do automatically.

Re:SIMD Everywhere: 0.5.0 by gioele on Tuesday August 04, 2020 @09:23AM (#24049674)
> I'm not sure this is going to work fast enough for that.

From reading the SIMD Everywhere description, it seems to me that SIMDe is a way to allow code that targets only a platform to work on other platforms as well. As a nice byproduct, you get _some_ speed up if architecture targeted by the code is similar to the architecture that will run the code.

Portability is the main focus, not speed.

Obviously, once you have a good emulation of an architecture the first question is going to be: can I make it faster?

Re:SIMD Everywhere: 0.5.0 by nemequ1729 on Tuesday August 04, 2020 @02:15PM (#24052855)
I'm the lead developer of SIMDe.

I wouldn't say that portability is the main focus. The first step is to get portable implementations up and running, but a huge number of functions have optimized implementations for NEON, AltiVec/VSX, and WASM SIMD 128, and we're working on adding more. We go to a lot of trouble to get good performance on multiple architectures, basically writing each implementation several times and using ifdefs to switch depending on what the fastest version available to a given architecture will be.

Even just for the portable implementations, we use a lot of hints to help the compiler auto-vectorize. Almost every portable implementation has a loop which uses a pragma to try to get the compiler do the right thing (OpenMP SIMD, clang loop-specific pragmas, GCC ivdep, etc.). On top of that we take advantage of lots of compiler-sepecific features to speed things up where possible, including GCC-style vector extensions, __builtin_shuffle/__builtin_shufflevector, and __builtin_convertvector.

SIMDe never going to be as fast as someone who knows what they're doing writing an optimized implementation for a given target. However, it should be as fast (or faster) than someone who is just trying to do a direct port where they just try to match the existing code as closely as possible.

Re:SIMD Everywhere: 0.5.0 by innocenat on Tuesday August 04, 2020 @04:08PM (#24053985)
I don't have experience with SIMD on platform other than x86/amd64, but a few of data-shuffling type functions [0] have SIMD version that is not that faster than scalar C implementation, and the overhead of translation might make then slower.

[0]: http://web.archive.org/web/20140807014206/http://x264dev.mul...

Re:SIMD Everywhere: 0.5.0 by nemequ1729 on Tuesday August 04, 2020 @07:05PM (#24055460)
I hadn't seen that post before, thanks.

This doesn't quite apply to SIMDe; the problem that post is talking about is really at a higher level… whether it is faster to do a bunch of shuffles or use some scalar code. Once SIMDe is called you've already made your decision, and at that level the hardware-based shuffles are much faster than scalar code. For example, see the decompression speed benchmarks for LZSSE-SIMDe (<https://github.com/nemequ/LZSSE-SIMDe>) (they're in the README).

It sounds like what that post really needs is a fast 16-bit gather operation. AVX2 has some 32-bit gather functions which you may be usable (2 gathers + a blend could emulate 16-bit gathers). For NEON, you could probably use one of the `vtbl` functions; they're all 8-bit, but that just means you have separate index entries for high and low bytes… it's a bit more code, but there shouldn't be any runtime overhead.

Re:SIMD Everywhere: 0.5.0 by souprock on Wednesday August 05, 2020 @01:54AM (#24057653)
That is a common problem. SIMD can be slower than non-SIMD. Consider this problem:

The goal was to emulate a 4-way PowerPC TLB on x86-64. Four uint32_t values had to be compared to find a match. The data structure was roughly "uint32_t array[512][4][4]", laid out so that the 4 uint32_t values would be adjacent.

It simply didn't perform OK. Getting the equality test results out of SIMD was lengthy, awkward, and slow.

That task was so perfect for SIMD, and yet SIMD failed at it. The data was the exactly correct size of an SSE XMM register. It was aligned. The task was a simple parallel operation.

Re:SIMD Everywhere: 0.5.0 by Const-me on Wednesday August 05, 2020 @09:44AM (#24060659)
Based on your description, here’s what you should do to vectorize that code.

1. If you don’t have AVX, a good way to broadcast integer from scalar register to vector is _mm_cvtsi32_si128 followed by _mm_shuffle_epi32( v, 0 )

2. To compare them for equality, _mm_cmpeq_epi32

3. Getting index of the first match is 2 instructions, MOVMSKPS and BSF.

Getting compiler to emit them is a bit awkward, though. You first need _mm_castsi128_ps to be able to call _mm_movemask_ps. Test the integer for 0 afterwards, if zero, none of the 4 lanes were equal.

The portable way to emit BSF is only introduced in C++/20. In the current version of the language you have to use preprocessor to detect compiler, use _BitScanForward for msvc, __builtin_ctz for gcc/clang.

If you want count of matches, replace BSF with POPCNT. Again, in current version of the language it’s compiler specific, __popcnt for msvc, __builtin_popcount for gcc/clang.

P.S. If you only need a single boolean saying if none of the 4 lanes matched / any of the lanes matched, use _mm_test_all_zeros / _mm_test_mix_ones_zeros instead of _mm_movemask_ps. Or if you want to test more than 1 cache entry, leave the comparison result in a vector register, compare more entries, combine results with bitwise instructions.

Update: If you don’t need index or count of matches but want to individually test all 4 matches with scalar code, on old CPUs _mm_movemask_epi8 is slightly faster because cross-domain latency, test the result for bits 1, 0x10, 0x100, 0x1000.

Re:SIMD Everywhere: 0.5.0 by BeeOnRope on Wednesday August 05, 2020 @11:31AM (#24061928)
I wouldn't characterize this as "perfect" for SIMD!

Perfect for SIMD usually means a significant amount of calculation that can be done vector-wise (you could include contiguous data movement in that definition).

Here, you are doing exactly one (cheap) calculation: the compare, and one vectorized load, and you want to feed the results to a branch, presumably.

You are only saving a few instructions versus scalar and pay a vector to GP penalty.

Re:SIMD Everywhere: 0.5.0 by Const-me on Wednesday August 05, 2020 @12:33PM (#24062677)
The penalty is quite small, 1-3 cycles each direction. RAM latency is 1-2 orders of magnitude more than that, even L1D level of cache is many cycles away. Replacing multiple scalar RAM loads with 1 vector load is usually a good idea performance wise. This is true even if you’ll then use extract instructions to access the lanes. Extract latency is 2-3 cycles, much faster than RAM.

I think what might have happened, GP tried to use SSE for dealing with individual lanes. Better approach for that use case is moving the comparison results to scalar register with a single movmskps, pmovmskb, or ptest instruction, just once for the complete vector.

Re:SIMD Everywhere: 0.5.0 by BeeOnRope on Wednesday August 05, 2020 @05:21PM (#24065744)
Yes, the penalty is small, but the total amount of vectorized work is also very small!

L1D is not many cycles away: it is 4 or 5 for scalar loads, 6 or 7 for xmm or ymm loads. If the load misses, it doesn't much matter if it's a scalar or vector load: the time to fetch the cache line is the same.

So a scalar load of 5 cycles looks much better, latency-wise, than a vector load of 6 cycles, plus an extract of 1-3 cycles.

Of course, you need only 1 vector load vs 4 GP loads, but the latencies are overlapped.

Furthermore, the extracts can happen on a single port: so even though you have 512 bits/cycle of "contiguous" vector load bandwidth, you then suck those loads though a 32 bits/cycle extract straw [1]? 32-bit GP loads have 64 bits/cycle bandwidth and the value goes directly to the GP register, or even micro-fused with the ALU op.

So no, it is not an obvious win to load 4x32-bit values with a vector load and then bring them over to GP registers. Even if it might sometimes be slightly better, this is hardly "perfect" for vectorization, rather I'd say it is "quite poor candidate for vectorization".

Also, if the goal is to set a flag and jump on it, you'll still end up needing a scalar comparison anyway, so actually for the computation part there is no savings.

Don't forget the thing you are comparing to: presumably it starts in a GP register, so you need some kind of GP->SIMD move and then a broadcast to prepare the comparison.

> I think what might have happened, GP tried to use SSE for dealing with individual lanes. Better approach for that use case is moving the comparison results to scalar register with a single movmskps, pmovmskb, or ptest instruction, just once for the complete vector.

Right, well who know what they tried to do or how the surrounding code works. I agree the approach you suggest sounds like it should be a slight win sometimes, but the key word is "slight". If the surrounding code is general purpose code and the inputs and outputs come from and go to GP registers, this is just "too small" to vectorize well. It's a common misconception that say comparing values is the bulk of the work, so of course vectorization will be a 4x win, but actually all the surrounding stuff takes most of the work, much more than a comparison which can execute 4 per cycle on the scalar side.

---

[1] You can try other tricks like extracting 64-bits and then messing around in the GP reg to split the halves, but it's basically a wash.

Re:SIMD Everywhere: 0.5.0 by mtgx on Tuesday August 04, 2020 @10:00AM (#24050012)
All other chip architectures should adopt Arm's SVE2 or something similar.

https://community.arm.com/developer/ip-products/processors/b...

Re:SIMD Everywhere: 0.5.0 by nemequ1729 on Tuesday August 04, 2020 @02:47PM (#24053205)
I'm not aware of anything in the works for Intel, but RISC-V seems to be going in that direction.

I'm hoping to start using SVE to implement AVX-512 and AVX in SIMDe soon.

Re:SIMD Everywhere: 0.5.0 by fao_ on Tuesday August 04, 2020 @01:11PM (#24052113)
Hi there! It looks like you've been shadowbanned, I vouched a few of your comments because they didn't seem terrible, but I didn't scroll very far. It might be worth sending a mail to dang to ask him to take a look at your account or something!
Re:SIMD Everywhere: 0.5.0 by chmod775 on Tuesday August 04, 2020 @02:11PM (#24052801)
That account has 33k karma and is 8 years old.

I just can't imagine a set of circumstances where a shadowban of all things could be justified if they transgressed in some way.

It's probably a mistake?

Re:SIMD Everywhere: 0.5.0 by fao_ on Tuesday August 04, 2020 @03:16PM (#24053467)
or they said something ridiculously heinous
Re:SIMD Everywhere: 0.5.0 by chmod775 on Wednesday August 05, 2020 @01:04AM (#24057424)
In that case one should point that out to them and warn them.

Shadowbans are quite a heinous punishment in themselves, and better used to prevent spammers etc. from creating new accounts.

But people who make thousands upon thousands of comments are bound to make an emotional comment or an error of judgment at some point.

Re:SIMD Everywhere: 0.5.0 by saagarjha on Tuesday August 04, 2020 @01:38PM (#24052444)
It'd be nice, but they won't :( I'm not even sure if any consumer ARM chips ship with SVE2 at the moment.
Re:SIMD Everywhere: 0.5.0 by nemequ1729 on Tuesday August 04, 2020 @02:29PM (#24053018)
(Lead developer of SIMDe here.)

It sounds like you actually know what you're doing, so in this case you're probably right, at least if all you do is compile your x86 code with SIMDe.

That said, SIMDe also provides support for other architectures, notably WASM SIMD 128 and AltiVec/VSX, as well as portable implementations which work everywhere, including on CPUs I'd never heard of until people told me SIMDe was working well on them (I'm thinking of Kalray, which supports vectors but doesn't have an API and instead relies on compiler auto-vectorization support).

One use case for SIMDe which may be interesting for you is that you can freely mix calls to different APIs. Say, for example, that you already have a bunch of x86 code written and want a NEON port. You can add SIMDe and you get a NEON port basically for free, then you can start adding some ifdefs to add optimizations for NEON without having to rewrite the whole thing. SIMDe doesn't in any way prevent you from optimizing your NEON (or whatever) port.

The way I tend to look at it is that SIMDe never makes your code slower, only more portable.

Re:SIMD Everywhere: 0.5.0 by Const-me on Tuesday August 04, 2020 @04:50PM (#24054357)
I might give it a try next time I’ll need to do something for AMD64 + NEON. Not going to rewrite code I have already written, debugged and shipped.

Also, about this

> we have an extensive test suite to verify our implementations

Don’t forget about MXCSR register in that suite, esp. the rounding bits of that. I avoid changing it as much as possible ‘coz the state is preserved across context switches and causes funny things in OpenMP and other thread pools, but not all people are aware of that. Also, there’s non-trivial amount of code written for SSE < 4.1 (the 4.1 introduced proper rounding instruction, roundps) where you sometimes forced to mess with MXCSR rounding bits because the alternatives are much slower.

Re:SIMD Everywhere: 0.5.0 by nemequ1729 on Tuesday August 04, 2020 @06:54PM (#24055377)
> Not going to rewrite code I have already written, debugged and shipped.

I wouldn't, either. At least unless you want a WASM/AltiVec/etc. version. But if you already have good implementations SIMDe probably won't help.

OTOH, if all you have is a x86 implementation and a portable fallback, the SIMDe version of the x86 implementation will probably be faster than your portable version. That's what happened with MMseqs2 (<https://github.com/soedinglab/MMseqs2>).

> Don’t forget about MXCSR register in that suite

Yeah, rounding is definitely PITA. It's actually something I completely screwed up on in the beginning of the project and had to go back and correct :(. We do have some tests now which fiddle with the rounding mode to verify correctness, but could definitely use more, and obviously we can't always set a dedicated register to control behavior, so on some platforms `_mm_getcsr`/`_mm_setcsr`/`_MM_GET_ROUNDING_MODE`/`_MM_SET_ROUNDING_MODE` becomes `fegetround`/`fesetround`, which probably won't be a problem but still makes me uncomfortable.

The other area where we could really use more tests is replicating behavior for NaNs. By default we try to replicate the behavior of the function we're trying to emulate, but we currently only test NaN handling on a few functions :(. If you use -ffast-math or -ffinite-math-only we disable that code (compilers define __FINITE_MATH_ONLY__), though, and just use the fastest implementation we can.

Re:SIMD Everywhere: 0.5.0 by dragontamer on Tuesday August 04, 2020 @09:16AM (#24049612)
Shuffle, pack/unpack, movemask, blends (SSE/AVX) and interleaved load/stores, byte swap (NEON) are "just" data-movement instructions.

All of them can be implemented (with obvious slowdowns) with a conditional write to memory, then a conditional read from memory. Yeah, its inefficient to do it like this, but this "write then read" pattern really gives us an idea of what's really going on between the registers in a pack/pshufb/whatever instruction.

On AMD GPUs, there's a fully arbitrary crossbar between SIMD-lanes allowing for arbitrary movement. The two instructions are just "permute" and "b-permute" (backwards permute), roughly correlating to gather and scatter respectively.

On NVidia GPUs, perm and bperm are both implemented in PTX, but instead read/write to L1 or __shared__ memory. NVidia GPUs likely have a crossbar to L1 memory to make this instruction very fast.

---------

The solution is to implement perm and bperm on AVX. Its already half-implemented: pshufb is equivalent to GPU-permute. CPUs are just missing the backwards permute.

I'm pretty confident that pack/unpack, blends, interleaved load/stores, and more could all be implemented as pshufb and a hypothetical "backwards pshufb". Version 1.0 could be an NVidia-like "write to L1 cache" sort of implementation too, if full crossbars are too expensive at the hardware layer.

-----------

So the question is: how should we write code today? CPUs of today do not implement this feature, but CPUs of the future might. I think specifying the memory-moves explicitly, and then working on a "pshufb compiler/optimizer" of sorts is what we need.

Re:SIMD Everywhere: 0.5.0 by Const-me on Tuesday August 04, 2020 @09:50AM (#24049914)
> the question is: how should we write code today?

The only thing that matters today is how fast the code works on today’s hardware. To illustrate, see how I have emulated neon’s vst3q_s16 with SSE: https://github.com/Const-me/DtsDecoder/blob/master/Utils/sto... However, not all of them can be emulated in a fast enough manner.

> specifying the memory-moves explicitly, and then working on a "pshufb compiler/optimizer" of sorts is what we need.

I’ll consider that approach when I’ll see that compiler/optimizer working, and producing output comparable to manually-written code. Until then I think that’s a “sufficiently smart compiler” class of problems. These are rarely ever solved, IMO. For example, we don’t have generally useful auto-vectorizers in C compilers despite two decades of R&D, even the best of them (clang, intel) are still very limited.

Re:SIMD Everywhere: 0.5.0 by floatboth on Tuesday August 04, 2020 @09:51AM (#24049928)
> how should we write code today?

Write in a GPU-style "compute shader" language and let the compiler pick the fastest ways of doing things on each ISA?

https://github.com/ispc/ispc

Re:SIMD Everywhere: 0.5.0 by dragontamer on Tuesday August 04, 2020 @10:36AM (#24050400)
Well, such a feature doesn't exist in ispc. I guess I'm proposing a hypothetical feature that doesn't exist yet in any compiler. But it'd be nice if it existed...

For it to exist, we need a combination of new assembly instructions as well as a smart enough compiler.

Re:SIMD Everywhere: 0.5.0 by gameswithgo on Tuesday August 04, 2020 @10:09AM (#24050112)
>I'm not convinced it's possible to do automatically.

It isn't always, but sometimes it is.

Re:SIMD Everywhere: 0.5.0 by Rebelgecko on Tuesday August 04, 2020 @12:29PM (#24051562)
Are compilers smart enough to interleave load/stores? I've noticed when using NEON intrinsics that GCC occasionally did clever things (and of course sometimes I got huge speed improvements by making small changes, like adding a PLD a few instructions before a hunk of memory is used)