Vector.Narrow performance

[benaadams]

I was trying to work out why I wasn't getting the performance expected from Vector.Narrow

using System;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Text;

class Program
{
    static unsafe void Main(string[] args)
    {
        var charArray = Enumerable.Repeat('a', Vector<ushort>.Count * 2).ToArray();
        var byteArray = new byte[Vector<byte>.Count];

        fixed (char* pChar = charArray)
        fixed (byte* pByte = byteArray)
        {
            Narrow(pChar, pByte);
        }

        Console.WriteLine(Encoding.ASCII.GetString(byteArray));
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    private static unsafe void Narrow(char* input, byte* output)
    {
        var bytes = Vector.Narrow(
            Unsafe.AsRef<Vector<ushort>>(input), 
            Unsafe.AsRef<Vector<ushort>>(input + Vector<ushort>.Count));
        Unsafe.AsRef<Vector<byte>>(output) = bytes;
    }
}

Generates

; Assembly listing for method Program:Narrow(long,long)
; Emitting BLENDED_CODE for X64 CPU with AVX
; optimized code
; rsp based frame
; partially interruptible
; Final local variable assignments
;
;  V00 arg0         [V00,T00] (  4,  4   )    long  ->  rcx        
;  V01 arg1         [V01,T01] (  3,  3   )    long  ->  rdx        
;  V02 loc0         [V02,T07] (  2,  2   )  simd32  ->  mm0        
;  V03 tmp0         [V03,T02] (  2,  4   )  simd32  ->  mm0        
;* V04 tmp1         [V04,T08] (  0,  0   )   byref  ->  zero-ref   
;* V05 tmp2         [V05,T09] (  0,  0   )   byref  ->  zero-ref   
;  V06 tmp3         [V06,T03] (  2,  2   )   byref  ->  rax        
;* V07 tmp4         [V07    ] (  0,  0   )    long  ->  zero-ref   
;  V08 tmp5         [V08,T04] (  2,  2   )   byref  ->  rax        
;  V09 tmp6         [V09,T05] (  2,  2   )   byref  ->  rax        
;  V10 tmp7         [V10,T06] (  2,  2   )   byref  ->  rax        
;# V11 OutArgs      [V11    ] (  1,  1   )  lclBlk ( 0) [rsp+0x00]  
;
; Lcl frame size = 0

G_M2586_IG01:
       C5F877               vzeroupper 

G_M2586_IG02:
       C4E17D1001           vmovupd  ymm0, ymmword ptr[rcx]
       488D4120             lea      rax, [rcx+32]
       C4E17D1008           vmovupd  ymm1, ymmword ptr[rax]
       C4E37D46D920         vperm2i128 ymm3, ymm0, ymm1, 32
       C4E37D46D131         vperm2i128 ymm2, ymm0, ymm1, 49
       C4E16571F308         vpsllw   ymm3, 8
       C4E16571D308         vpsrlw   ymm3, 8
       C4E16D71F208         vpsllw   ymm2, 8
       C4E16D71D208         vpsrlw   ymm2, 8
       C4E16567C2           vpackuswb ymm0, ymm3, ymm2
       488BC2               mov      rax, rdx
       C4E17D1100           vmovupd  ymmword ptr[rax], ymm0

G_M2586_IG03:
       C5F877               vzeroupper 
       C3                   ret      

; Total bytes of code 70, prolog size 3 for method Program:Narrow(long,long)

Is this correct (performance wise)?

/cc @mikedn @CarolEidt

category:cq
theme:vector-codegen
skill-level:intermediate
cost:medium

[benaadams]

What I'm comparing the performance to does 128 bytes at a time as; so maybe its just close

const int Shift16Shift24 = (1 << 16) | (1 << 24);
const int Shift8Identity = (1 <<  8) | (1);
        
int ulongDoubleCount = (length - i) & ~0x7;
for (; i < ulongDoubleCount; i += 8)
{
    ulong inputUlong0 = *(ulong*)(input + i);
    ulong inputUlong1 = *(ulong*)(input + i + 4);
    // Pack 16 ASCII chars into 16 bytes
    *(uint*)(output + i) =
        ((uint)((inputUlong0 * Shift16Shift24) >> 24) & 0xffff) |
        ((uint)((inputUlong0 * Shift8Identity) >> 24) & 0xffff0000);
    *(uint*)(output + i + 4) =
        ((uint)((inputUlong1 * Shift16Shift24) >> 24) & 0xffff) |
        ((uint)((inputUlong1 * Shift8Identity) >> 24) & 0xffff0000);
}

[glenn-slayden]

I do not repro your emitted asm. For this code...

[MethodImpl(MethodImplOptions.NoInlining)]
static void narrow_simd(char* src, byte* dst, int c)
{
    Unsafe.AsRef<Vector<byte>>(dst) = 
        Vector.Narrow(Unsafe.AsRef<Vector<ushort>>(src + 0),
                      Unsafe.AsRef<Vector<ushort>>(src + 8));
}

...I currently get:

mov         rax,rdx
movups      xmm0,xmmword ptr [rcx]
lea         rdx,[rcx+10h]
movups      xmm1,xmmword ptr [rdx]
movaps      xmm0,xmm0
movaps      xmm2,xmm1
psllw       xmm0,8
psrlw       xmm0,8
psllw       xmm2,8
psrlw       xmm2,8
packuswb    xmm0,xmm2
movups      xmmword ptr [rax],xmm0
ret 

...which lacks the two vperm2i128 instructions you reported.

Could your result be an artifact of your test or debug apparatus? Or perhaps fallback code to preclude CPU incapabilities? For example your comment indicates that it is displaying the "blended code for AVX." I don't know what that means, but fwiw my output is directly from the vs2017 debugger metal on "Intel(R) Core(TM)2 Extreme CPU X9770." Otherwise, you may wish to re-test with the latest bits.
[edit: emitted based on different CPU capabilities; see below]

Having said that, there remains the PSRLW 8/PSLLW 8 sequence which will apparently be emitted for each-and-every vector that is used as an input to the PACKUSWB instruction. I was wondering what the deal was with this so I looked into it.

My conclusion on that front, unfortunately, is that the steps are indeed mandatory here, and are the result of a catastrophically misguided design choice regarding the PACKUSWB/PACKSSWB instructions. For details on this, read on...

On the design of PACKUSWB/PACKSSWB

The effect of the PSRLW 8/PSLLW 8 instruction sequence is to zero the high byte in each of a vector's eight char values. The requirement for this is mentioned here:

https://github.com/dotnet/coreclr/blob/eddc1a621b66d63ac9feda289f08fc0e9f67f850/src/jit/simdcodegenxarch.cpp#L507-L509

This code comment tersely summarizes a philosophical conundrum that arises with lossy instructions such as SSD PACKUSWB "Pack with unsigned saturation" and PACKSSWB "Pack with signed saturation." So what is this so-called "saturation," anyway? At issue here is what to do if there happen to be non-zero bits in any of the high bytes which are to be discarded:

1. One view would be that it is the caller's responsibility to know that narrowing operations are inherently lossy and use such instructions accordingly. To this thinking, it would be presumptous for these instructions to deem the presence of non-zero upper bytes an error condition. And it would be pointless too, since, absent further information about the caller's intention, it is unclear what might be done. So lest do further damage, the best action is to do nothing. In this school of thought, the upper bytes could simply be ignored in the first place, and altogether.

2. The alternative idea is that it is processor's responsibility--given its vast, omniscient view--to help as much as possible at all times. As such, the presence of non-zero bits in a discardable upper byte must most certainly represent an unintentional--and likely fatal--loss of data which must be signaled at all costs.

I tried to dial down the sarcasm, but I fear I may have betrayed my opinion. Unfortunately the design of the PACKUSWB/PACKSSWB opcodes hew to the latter ideology (2.), so apparently the meaning of "saturate" in the opcode descriptions is, "Be super-helpful by detecting an arbitrary condition that the user did, in fact, willfully submit, and then signal that condition by overwriting the data result in order to contaminate the mainline codepath!". Having worked in both industries, I suspect that that typically different worldviews of CPU firmware vs. software engineers might be contributing to the dissonance here: As you get closer to EE, every signal starts to look continuous. Seriously, though here are some excerpts from the (corrected) canonical descriptions:

PACKSSWB - Pack with Signed Saturation
If the signed doubleword [16-bit word integer] value is beyond the range of an unsigned word [signed byte integer] (i.e. greater than 007Fh or less than 0080h [negative]), the saturated signed byte integer value of 7Fh or 80h, respectively, is stored in the destination.

PACKUSWB - Pack with Unsigned Saturation
If a signed [16-bit] word integer value is beyond the range of an unsigned byte integer (that is, greater than 00FFh or less than 0000h [negative]), the saturated unsigned byte integer value of FFh or 00h, respectively, is stored in the destination.

Note that both instructions require that the source data values be under signed word interpretation. This, in turn entails that those 16-bit values represent scalar--as opposed to discrete--data. Now as far as I can tell, there are no unsigned-source equivalents for these instructions, so right off the bat we can note that discrete data uses, such truncating enumeration, bitmap/flag, or most importantly--and thus as we'll see, catastrophically--Unicode character data, are not a priority.

Scalar data values

So anyway, fine. If we assume a "scalar mentality," the most charitable view of saturation is as scalar clamping. This may indeed seem like a useful feature. Let's examine things a bit more closely. Because these narrowing instructions don't perform any actual scaling, they're essentially asserting that their 16-bit source vectors be already under byte interpretation. And the problem is, this directly contradicts the original assumption (previous paragraph) that the source values be interpreted as signed word values.

It's not hard to see how the SSE designers got here. While it's true that rudely truncating a signed 16-bit scalar to 8-bits is basically always nonsensical, that fact is slightly less true for the unsigned case. Whereas the low-order bits are garbage in the former case, in the latter they remain interpretable as the (e.g.) high-frequency components of the original time-series signal. So, one might conclude, "Great! We don't need to worry about unsigned variants for PACKUSWB/PACKSSWB!" Cross them off the list.

Well, perhaps. But the flaw in this analysis came earlier, when we assumed the "scalar mentality." Though that's understandably the default worldview for engineers seeped in the microcode of a CPU's vector unit, narrowing is a special case, since it ultimately effects an operation that's inherently non-scalar. There's nothing about bitwise summary-truncation that might remotely be considered an operation on continuous data. If the user wants clamping, let them explicitly apply it with full knowledge of the compression scenario.

Whether permanently attenuating a 16-bit source to 8-bit resolution by explicit (e.g.) linear scaling, or round-tripping an 8-bit source to 16-bit to minimize overflow losses during a close-ended sequence of 8-bit edits (example of a non-scaling use on scalar data), any/all logical re-scaling can really only meaningfully be applied prior to invoking PACKUSWB or PACKSSWB. By the time you issue PACKUSWB/PACKSSWB, it's too late to deal with scalar clamping, because you must already be dealing with (logical) 8-bit values--regardless of signed/unsigned--that happen to be stored as (physical) 16-bit words.

Piling on now, obviously you shouldn't need to clamp a scalar to 8-bits if it's already logically-8-bit, but in fact, you couldn't even if you wanted to, because as an "already-logically-8-bit" value, the overflow bits that would be needed to properly do so must be considered already lost. Despite the wishful designs of PACKUSWB/PACKSSWB, any bits in the upper-byte of the happenstance physical representation of a logically-8-bit value should never have been considered interpretable.

In short, any clamping must be explicitly coordinated with whatever preapplied logical scaling is applied, because once scaled, clamping a logically-same-sized value is (obviously) vacuous. It follows that the design of PACKUSWB/PACKSSWB did NOT need to assume that its source words were scalar. Rippling back now, since clamping can only be correctly performed in cahoots with some actual scaling operation (without which word-sized input values would be literal garbage), the _(ridiculous) special clamping behavior (a.k.a. "saturation") is therefore quite entirely useless. If useless, then any/all sign-meddling it inflicts on the result values is wholly unnecessary, or at least quite unhelpful. Add in the fact that the very notion of clamping is inherently antagonistic to non-scalar usage, plus that the behavior can't be turned off, and one can only conclude that the clamping behavior of the PACKUSWB/PACKSSWB is nothing short of detrimental.

Discrete data values

Enough of that; since the "scalar mentality" was a bust, let's put on our discrete hat now.

Suddenly, the behaviors quoted in the bulleted list above seem downright strange. From a non-scalar point of view, each instruction (PACKUSWB and PACKSSWB) has the audacity to pluck two values ({ 0x7F, 0x80 } and { 0xFF, 0x00 }, respectively), right out of our in-band data codomain to serve as special control/sentinel values. To us, because we have our discrete hat on, each of the four appropriated values, though surely fixed and well-known, are arbitrary. Obviously, each may conflate with--and thus may occlude--one of our perfectly legitimate runtime values.

Worse, with discrete data we're guaranteed by definition that the conditions signaled by these sentinels will be semantically meaningless, which further implies that such signals, if allowed to fire, will be random and thus indistinguishable from the true (discrete) values they conflate with, a scenario sometimes referred to as unmitigated data corruption. Specifically for us here, the only way to prevent the signalling of meaningless conditions from corrupting our output--which thus becomes mandatory practice--is to take explicit steps to preclude the meddlesome conditions from manifesting in the input values we submit.

The fact that discrete data apps are required to ensure that each-and-every input vector issued to PACKUSWB has its discard-destined bytes zeroed-out is an cruel irony at least, and persistent runtime penalty at worst. The annoying burden is made all the worse by the knowledge that, as I tried to establish in some detail above, there's really no realistic scenario--scalar or otherwise--that might tangibly benefit from the bankrupt design choice (a.k.a., clamping or "saturation") that necessitates the chore. Though cheerfully well-intentioned, this particular help is not just unhelpful; it's a scourge.

[mikedn]

For example your comment indicates that it is displaying the "blended code for AVX." I don't know what that means, but fwiw my output is directly from the vs2017 debugger metal on "Intel(R) Core(TM)2 Extreme CPU X9770."

That processor does not support AVX so there's no way you'll see vperm2i128 being generated.

[glenn-slayden]

@mikedn Oh, I'm starting to see that part. You're suggesting that maybe...

vmovupd  ymm0, ymmword ptr[rcx]
lea      rax, [rcx+32]
vmovupd  ymm1, ymmword ptr[rax]
vperm2i128 ymm3, ymm0, ymm1, 32
vperm2i128 ymm2, ymm0, ymm1, 49

is functionally the same as, but in in some ways perhaps an improvement over...

movups      xmm0,xmmword ptr [rcx]
lea         rdx,[rcx+10h]
movups      xmm1,xmmword ptr [rdx]
movaps      xmm0,xmm0
movaps      xmm2,xmm1

I remain a bit suspicious since while these exhibit the same number of fetches, the instruction stream for the latter, presumably "legacy", CPU (this wasn't news to me) likely has a tighter byte count (i.e. for keeping loops in-cache...)?

[mikedn]

You're suggesting that maybe is functionally the same as, but in in some ways perhaps an improvement over

I'm not suggesting anything, I'm simply saying that you're seeing different code because you're using a CPU with different capabilities.

I don't have time to investigate this issue in detail. The use of permute is very likely required due to the per-lane operation of AVX version of packuswb, not an "improvement".

Vector's Narrow is a high level operation that may work or not satisfactorily depending on whatever instructions the target architecture has. If that's not enough then the low level HW intrinsics should be used instead. In this particular case packuswb could likely be used without shifts as the code assumes that the text contains only ASCII characters.

[glenn-slayden]

Ok, thanks; I see that I'm in way over my head.

[glenn-slayden]

...if that's not enough then the low level HW intrinsics should be used...

@mikedn Is it actually possible to issue individual "low-level HW intrinsics" from managed IL somehow?

[tannergooding]

@glenn-slayden, it should be in netcoreapp3.0 (provided the feature gets completed/ships 😄).

You can browse most of the APIs here: https://source.dot.net/#System.Private.CoreLib/shared/System/Runtime/Intrinsics/X86/Sse.cs,a190e303dd574c72

[glenn-slayden]

Spectacular. Keep up the great work.

[saucecontrol]

I was just looking at this codegen a couple of weeks ago, in the context of SixLabors/ImageSharp#1143

The AVX2 implementation could be improved slightly by swapping out the two vperm2i128 at the beginning for a single vpermq at the end.

And it might be a little more efficient in the SSE2 implementation to construct a mask (mov + pshufd) and vpand to zero the upper bytes rather than the left and right shifts. However, that would likely not be better with AVX2 because a broadcast or permute would be needed to construct the mask.

In the end, it will always be inefficient because it attempts to preserve the truncating behavior of a scalar short->byte conversion, while the SIMD instructions narrow with saturation. (That is, BTW, not a design flaw in the SIMD instructions -- that behavior is extremely desirable in signal-processing applications).

Is this worth keeping open now that HWIntrinsics have landed?

[tannergooding]

And it might be a little more efficient in the SSE2 implementation to construct a mask (mov + pshufd) and vpand to zero the upper bytes rather than the left and right shifts. However, that would likely not be better with AVX2 because a broadcast or permute would be needed to construct the mask.

The mask is constant, so I don't think that would be a problem. I imagine that and + shuffle + combine would be more efficient and would break some dependencies that look to exist, but the only way to validate that would be to profile and test.

Is this worth keeping open now that HWIntrinsics have landed?

Yes. HWIntrinsics provide machine specific optimizations while Vector<T> provides platform independent optimizations. We still want to continue improving both where applicable/as-possible.

[saucecontrol]

Actually had a look at all the codegen for narrow, and some of it is quite poor. For example:

runtime/src/coreclr/src/jit/simdcodegenxarch.cpp

Lines 1696 to 1703 in 7d67d17

	GetEmitter()->emitIns_R_R_I(INS_vextracti128, EA_32BYTE, tmpReg, op1Reg, 0x01);
	GetEmitter()->emitIns_R_R_I(INS_vextracti128, EA_32BYTE, tmpReg2, op2Reg, 0x01);
	GetEmitter()->emitIns_R_R_I(INS_vinserti128, EA_32BYTE, tmpReg, tmpReg2, 0x01);
	inst_RV_RV(ins_Copy(simdType), tmpReg2, op1Reg, simdType, emitSize);
	GetEmitter()->emitIns_R_R_I(INS_vinserti128, EA_32BYTE, tmpReg2, op2Reg, 0x01);
	GetEmitter()->emitIns_R_R_I(INS_pshufd, emitSize, tmpReg, tmpReg, (int8_t)SHUFFLE_XXZX);
	GetEmitter()->emitIns_R_R_I(INS_pshufd, emitSize, targetReg, tmpReg2, (int8_t)SHUFFLE_XXZX);
	inst_RV_RV_RV(INS_punpcklqdq, targetReg, targetReg, tmpReg, emitSize);

That entire sequence of vextracti128 … vinserti128 could also be replaced with a single vpermq after the unpack. This seems like a prime case where we could get both a performance and maintenance cost win by re-implementing in managed code with HWIntrinsics. Are there still some roadblocks to starting that effort?