Inefficient x64 codegen for 8x16 shifts

[abrown]

While attempting to lower shl and shr (https://github.com/WebAssembly/simd/blob/master/proposals/simd/SIMD.md#bit-shifts) in cranelift, I observed that following instructions would involve a non-optimal lowering to x86:

• i8x16.shl
• i8x16.shr_s
• i8x16.shr_u
• i64x2.shr_s

I see that, e.g., v8 lowers i8x16.shl to 10 instructions (https://github.com/v8/v8/blob/5097dcb706b4438cf2ba3da5dfacfbc36643759c/src/compiler/backend/x64/code-generator-x64.cc#L3358-L3398) and am concerned that unsuspecting users may be hit with performance cliffs on x86. Are there better ideas out there on how to lower this? Are there workloads out there that would use these instructions?

[tlively]

See some recent discussion of shift semantics in #100.

[dtig]

The shifts were included as these are useful operations, narrow shifts in the initial version for codecs, and 64x2 shifts with benchmarking results from @ngzhian. The codegen on Intel hardware is suboptimal, though I'm not sure that it introduces a performance cliff as mostly SIMD instructions are used. The rationale for some of these commonly used instructions is that these are useful operations to have, and expensive to emulate in the absence of operations that directly lower to codegen.

[abrown]

@dtig, we captured in the notes that there are some uses of 8x16 shifts in vp8 code. Looking at https://github.com/webmproject/libvpx, I see some uses of 8x16 shifts in the ARM tree (e.g. https://github.com/webmproject/libvpx/tree/master/vpx_dsp/arm/loopfilter_4_neon.asm) but obviously not in the x86 tree (e.g. https://github.com/webmproject/libvpx/blob/master/vpx_dsp/x86/loopfilter_avx2.c). Is this the use you were referring to?

It is unclear to me, unfamiliar with the code, if using a more granular 8x16 shift is an advantage for performance reasons or simply for convenience reasons like you describe above ("useful operations"). If the reason is convenience only, there is likely a case to be made for dropping these 8x16 shifts to avoid penalizing x86 since in that case there is an alternate, performance-equivalent, code sequence (along the lines of whatever x86 has to do). If the reason is performance, that is a different story. Is there any way to understand which of these reasons, performance or convenience, weighs heavier in this instruction selection? I'm thinking of some form of benchmark or some explanation why the 8-bit lanes are preferable to 16-bit lanes.

You mentioned there were other benchmarks making use of the 8x16 shift; can you link to them?

[nfrechette]

Shifts are commonly used with fixed point arithmetic but it isn't as common on 8 bit values (16/32/64 bit being the most common). I also imagine that it might be even less common for the type of code that will target wasm.

[dtig]

@dtig, we captured in the notes that there are some uses of 8x16 shifts in vp8 code. Looking at https://github.com/webmproject/libvpx, I see some uses of 8x16 shifts in the ARM tree (e.g. https://github.com/webmproject/libvpx/tree/master/vpx_dsp/arm/loopfilter_4_neon.asm) but obviously not in the x86 tree (e.g. https://github.com/webmproject/libvpx/blob/master/vpx_dsp/x86/loopfilter_avx2.c). Is this the use you were referring to?

These are some examples, there should be more, but from the feedback we've gotten anything in the dsp directories is on the critical path for performance.

It is unclear to me, unfamiliar with the code, if using a more granular 8x16 shift is an advantage for performance reasons or simply for convenience reasons like you describe above ("useful operations"). If the reason is convenience only, there is likely a case to be made for dropping these 8x16 shifts to avoid penalizing x86 since in that case there is an alternate, performance-equivalent, code sequence (along the lines of whatever x86 has to do). If the reason is performance, that is a different story. Is there any way to understand which of these reasons, performance or convenience, weighs heavier in this instruction selection? I'm thinking of some form of benchmark or some explanation why the 8-bit lanes are preferable to 16-bit lanes.

From what I understand, what you are recommending here is to get rid of the 8x16 shift, and document an accepted code pattern for applications that use these shifts. This is something we've strongly avoided, because this is a way applications can encode performance cliffs. Can you add specific details about alternate, performance-equivalent code sequences on relevant architectures? (At least Neon, ARMv7 are required, and any others are optional, but useful to have). The performance definitely weighs higher IMO, though other opinions here are useful as well. The convenience reason here is that the x86 instruction set is asymmetrical in many different ways, but where possible it would be nice to not bias, or encode the same inconsistencies in a portable-SIMD proposal. Most of the operations that are harder to emulate on x86 aren't included in this proposal except for basic operations, emulating Shifts without documenting accepted patterns is very slow on ARM, and developers that are aware of those patterns can use them without compromising any existing performance on x86.

You mentioned there were other benchmarks making use of the 8x16 shift; can you link to them?

[abrown]

what you are recommending here is to get rid of the 8x16 shift, and document an accepted code pattern for applications that use these shifts

I don't think I am, but let me explain. I am recommending that we do get rid of the 8x16 shift if adding the instruction is only for convenience; if there is a performance-critical reason to keep those shifts then I would change my tune, but that is why I am 1) asking for feedback about the effect of 8x16 shifts (vs 16x8 shift) on libvpx performance and 2) asking for other workloads that might use these instructions in a performance-critical way.

emulating Shifts without documenting accepted patterns is very slow on ARM

The way I see it, looking at libvpx, there is an ARM implementation of the DSP using 8x16 shifts and an x86 implementation of the DSP using 16x8 shifts (e.g., PSRAW in x86 SSE2). If we were to drop the 8x16 shifts, the libvpx team could still compile the x86 version with its 16x8 shifts to Wasm and Wasm runtimes could still lower to ARM NEON in a single 16x8 VSHR. But if we retain the 8x16 shifts and an unsuspecting developer compiled the ARM version of the DSP to Wasm, Wasm runtimes would encounter a ~10 instruction penalty on x86 architectures. Why encode a penalty to an architecture into the spec? Right now I'm arguing we should avoid this, but I could be convinced this would an OK trade-off if the 8x16 approach had a performance advantage over the 16x8 approach over several workloads--hence my questions about other uses of the 8x16 shifts.

it would be nice to not bias, or encode the same inconsistencies in a portable-SIMD proposal

I agree. It would be nicer and more symmetrical if x86 had 8x16 shifts but, as @nfrechette mentions, perhaps their use is uncommon (understanding that that could be reinforced by the instructions just not being present in x86 😄). I'll set up a meeting to discuss further but hopefully this gives some perspective on where I'm coming from.

[abrown]

@arunetm mentioned that it might be a good idea to get a sense from the community how 8x16 shift instructions would be used. For context, I'm creating a poll within this issue; could you respond using the emoji reactions to this comment and tag other developers with opinions on 8x16 shift inclusion in Wasm SIMD? cc: @dtig, @Maratyszcza, @tlively, @penzn, @nfrechette, @zeux

• If you consider 8x16 shifts to be uncommon instructions (e.g. absent in real-world applications, easily emulated by 16x8 shifts, etc.), vote with a 👀.
• If you consider 8x16 shifts to be nice-to-have instructions (e.g. for symmetry between ISAs, ease-of-use when doing SIMD programming), vote with a 🎉.
• If you consider 8x16 shifts to be performance-critical instructions (e.g. necessary for performance speed-ups in real-world applications), vote with a 🚀.

(I think it makes sense to be able to vote for multiple of these so feel free to react with multiple emojis).

[abrown]

To circle back to the "performance cliff" argument, here are some measurements: I created x86 assembly code for the v8 implementation of i8x16.shl (an 11 instruction lowering) and, having no x86 encoding for i8x16.shl, created x86 assembly code for i16x8.shl (a 1 instruction lowering). The entire gist of the code is available here.

On my machine, the emulated v8 implementation took ~0.112s to complete 10M iterations and the 16x8 implementation took ~0.023s, roughly a 5x speed-up. I am comparing an emulated 8x16 shift to a native 16x8 shift to make this point: a developer using 16x8 shifts would assume that in changing their code to use 8x16 shifts they would be sacrificing lane-width in order to gain more lanes, but unwittingly they would incurring this 5x slow-down in some form. If we include 8x16 shifts in the spec we hide this slow-down until it negatively affects runtimes on certain machines--this is what I meant by creating a "performance cliff" when adding instructions for ease-of-use.

[arunetm]

Thanks, @abrown for the numbers. Quick question, Is vp9 using i16x8.shl in the IA version of their kernel and i8x16.shl on ARM?

[zeux]

I feel like in almost all cases the shift amount is going to be a constant in practice. For that, the v8 lowering is much less efficient compared to the optimum lowering available for SSE - shifting right by 2 for example is:

.LCPI0_0:
        .zero   16,63
shr2(long long __vector(2)):                           # @shr2(long long __vector(2))
        psrlw   xmm0, 2
        pand    xmm0, xmmword ptr [rip + .LCPI0_0]
        ret

(I believe v8 has some issues with constant loads but TBH I think this is a large limitation that will have to be lifted for efficient SIMD codegen of many instructions, including but not limited to v128.const and dynamic shuffle)

So I'm not sure that the performance cliff has to be quite as steep.

[dtig]

Thanks @abrown for initiating offline conversations and adding numbers. @zeux makes a good point that the performance cliff in practice is not expected to be this large. I've mentioned this here, and in other issues - the current V8 implementation is a prototype implementation that is behind a flag for experimentation, and is in some cases not the most optimal codegen for every opcode. We don't have a nice way to load a constant for when the codegen is more complex, and have to emulate that, using immediate optimizations for constant shifts, using correct AVX codegen, avoiding the SSE-AVX performance cliff etc. These are all on our radar and will be fixed in the future, but our highest priority at this stage is to make sure that all operations have a prototype implementation to test with. Which is why it's great to have multiple independent implementations as all the engines don't have the same limitations.

[zeux]

These are all on our radar and will be fixed in the future, but our highest priority at this stage is to make sure that all operations have a prototype implementation to test with.

Yeah I fully understand that (although we're going to start hitting impedance mismatch pretty soon - I've encountered this with v128.const where llvm is very eager to use v128.const; Chrome doesn't support it atm at all but if it does using the currently available means, LLVM will assume that replacing code with v128.const is a great idea for performance and Chrome will use inefficient codegen).

My point was that while the general 8-bit shift by a variable is a bit painful to implement, for the common case (shift by a constant) it's just one extra instruction for x64. So it seems perfectly reasonable to include this instruction into the baseline instruction set - emulating this instruction in "userspace" requires replicating the code above (with 16-bit shift and a constant mask) which is going to be same speed for x64 and worse for ARM.

In fact, if v8 wanted to fix the performance even for variable shifts, it would have been enough to have a 128-byte lookup table with 8 masks, and the code becomes something like

and     edi, 7
movd    xmm1, edi
psrlw   xmm0, xmm1
shl     rdi, 4
pand    xmm0, xmmword ptr [rdi + masks]

Still not great, but ~2x shorter than the currently emitted sequence (not sure what the perf characteristics are).

[arunetm]

Agree that we have a great case for keeping byte shifts if these are useful and const shifts make the common case.
@zeux do you know of any workload that relies on byte shifts for performance? They are very helpful in understanding and optimizing for performance and for considerations relating to future hw arch changes.

[zeux]

@arunetm I don't have great examples where byte shifts are critical - this is why I voted 👀 . But I also voted 🎉 because I think orthogonality and symmetry in a SIMD instruction set are important, and I don't see the codegen here as being particularly problematic.

FWIW my geometry decompression code (used in meshoptimizer) that tends to be somewhat unusual in the SIMD facilities it uses does use byte-shift on ARM and word-shift on Intel instead; my current WASM port only uses word-shift because it was ported from the Intel version. I don't think it would matter too much whether I used byte shift or not one way or the other if the codegen was perfect for constants as I suggested.