Runtime: Add Conversions methods to Vector<T>

[CarolEidt]

It would be useful to support conversions between different types of Vector. The API and usage model is pretty straightforward for same-size types, e.g. Double and Int64, so I would suggest that we start by exposing that, and consider mixed-size converts as usage demands (we have had customer requests for at least the same-size convert). A possible instance method on Vector might look like this:
public Vector ToVectorDouble();
and it would throw arg exception for non-64-bit vectors (or, alternatively, it could be defined as an extension method on the static Vector class for only those instantiations that are supported).

I propose the following:

• Vector<Double> <=> Vector<Int64>
• Vector<Double> <=> Vector<UInt64>
• Vector<Single> <=> Vector<Int32>
• Vector<Single> <=> Vector<UInt32>

[CarolEidt]

@mellinoe - what do you think?

[mburbea]

Aren't these already supported?
AsVectorByte
AsVectorSbyte
AsVectorUInt16
AsVectorInt16
etc.

[svick]

@CarolEidt It looks like your generics got lost. For the record, it seems it should have been:

• Vector<Double> <=> Vector<Int64>
• Vector<Double> <=> Vector<UInt64>
• Vector<Single> <=> Vector<Int32>
• Vector<Single> <=> Vector<UInt32>

[mellinoe]

Aren't these already supported?
AsVectorByte
AsVectorSbyte
AsVectorUInt16
AsVectorInt16
etc.

These methods function as a sort of "re-interpret cast", so no actual conversion of bits is performed. What we would like is methods that perform actual conversion from one type to another (hopefully in a hardware-accelerated fashion).

[mburbea]

Oh yes, then this makes sense to me. A VectorConverter class of methods.

[CarolEidt]

@svick - thanks for catching that. I would be interested in any thoughts on how the API would look.

[goldshtn]

I actually need a short-to-float vector conversion for a current project, where I need a dot product of a short vector times a float vector. Of course, only half the shorts are converted to floats at each conversion. With native intrinsics, this can be expressed as:

float vectorized_native(unsigned __int16* a, float* b, int length)
{
    float aux = 0.0f;
    for (int i = 0; i < length; i += 8)
    {
        __m128i ia = _mm_loadu_si128((__m128i*)&a[i]);          
        __m128i lo = _mm_unpacklo_epi16(ia, _mm_set1_epi16(0)); 
        __m128i hi = _mm_unpackhi_epi16(ia, _mm_set1_epi16(0)); 
        __m128 flo = _mm_cvtepi32_ps(lo);                       
        __m128 fhi = _mm_cvtepi32_ps(hi);                       
        __m128 blo = _mm_loadu_ps(&b[i]);                       
        __m128 bhi = _mm_loadu_ps(&b[i + 4]);                   
        __m128 dp = _mm_dp_ps(flo, blo, 0xF1);
        aux += dp.m128_f32[0];
        dp = _mm_dp_ps(fhi, bhi, 0xF1);
        aux += dp.m128_f32[0];
    }
    return aux;
}

[mellinoe]

For mis-matched type sizes, we can do something like this, similar to what you mentioned above regarding extension methods

public static class VectorConversions
{
    public static void ConvertToSingle(
        this Vector<Byte> source,
        out Vector<Single> dest0,
        out Vector<Single> dest1,
        out Vector<Single> dest2,
        out Vector<Single> dest3)
    {
        ...
    }
}

It would be a lot of overloads, but Intellisense would sort them pretty cleanly.

[benaadams]

unpacklo and unpackhi for example converting byte ascii to c# utf-16 string (8 bit to 16 bit widening)

Few others if you want to do utf8 e.g. https://woboq.com/blog/utf-8-processing-using-simd.html

going from @mellinoe last comment that would be something like

public static void ConvertToUShort(
        this Vector<byte> source,
        out Vector<ushort> dest0,
        out Vector<ushort> dest1)
    {
        ...
    }

[nietras]

For image processing, machine learning we often use conversions so adding these would be a great addition. However, we really need all possible conversion and not a subset.

Example, often in image processing source data is in byte (unsigned 8-bit) and many operations (e.g. addition, subtraction, kernels, etc.) then need to convert this to short (signed 16-bit) before doing these operations to avoid overflow or similar. For high perf in these cases unpacklo/unpackhi are pretty essential. A simple example is given below:

    const __m128i zeros = _mm_setzero_si128();

    // In a loop (handling 16 bytes at a time)
    __m128i left = _mm_loadu_si128((__m128i*)leftPtr);
    __m128i right = _mm_loadu_si128((__m128i*)rightPtr);

    __m128i leftLow = _mm_unpacklo_epi8(left, zeros);
    __m128i rightLow = _mm_unpacklo_epi8(right, zeros);
    __m128i diffLow = _mm_subs_epi16(leftLow, rightLow);

    __m128i leftHigh = _mm_unpackhi_epi8(left, zeros);
    __m128i rightHigh = _mm_unpackhi_epi8(right, zeros);
    __m128i diffHigh = _mm_subs_epi16(leftHigh, rightHigh);

    _mm_storeu_si128((__m128i*)outputPtr, diffLow);
    _mm_storeu_si128((__m128i*)(outputPtr + ColStepSize / 2), diffHigh);

Hoping that JIT code-gen can actually output something as tight as the above.

However, conversions are often needed to all the other types as well e.g. int, float, double, ushort, uint etc. Additionally, often shuffling, shifting and other "manipulation" intrinsics are used. Note that many of these have other application areas such as SIMD sorting etc.

One issue with the conversion operations is that they are not generic so full generic programming is not possible with this e.g. cant write Vector<T>.UpConvert<R>(...) or similar. Not that I have any idea how that could be done in a generic way, but signed/unsigned "2x" up/down convert could be a pattern. Besides floating-pointing/integer conversions.

[nietras]

One extra thing, I do not like that you are always forced to get _both_ hi and lo, there are cases where we only need one or the other. And for some conversions it is just too expensive to do both. So I would at least split them so you actually have something like:

public static void ConvertLowToUShort(
        this Vector<byte> source,
        out Vector<ushort> dest)
    {
        ...
    }
public static void ConvertHighToUShort(
        this Vector<byte> source,
        out Vector<ushort> dest)
    {
        ...
    }

Basically, as thin and direct calls as possible to the underlying instructions.

Regarding a generic solution, It should be possible to do something like:

public static void ConvertHigh<T, R>(Vector<T> source, out Vector<R> dest)
{
     // Do simple type checks like otherwise seen in vector code 
     // and where the JIT can remove the checks at compile time e.g.
     if (typeof(T) == typeof(byte) && typeof(R) == typeof(short)
     {
           // Do unpackhi for byte to short
     }
     // Etc.
     // All possible combinations
     else
     {
           // Throw exception
     }
}

And then also a ConvertLow<T, R>(Vector<T> source, out Vector<R> dest). Of course, this means there are plenty of combinations that will throw but that is fine in my view.

[mellinoe]

This is still an important missing piece in our story for Vector<T>. We should try to come up with a minimal proposal and push it through a design review. Can anyone come up with a minimal set of API's that could cover the use cases described here?

[CarolEidt]

@benaadams posted a request for Vector<ushort> to Vector<byte> conversion at https://github.com/dotnet/coreclr/issues/7421. @terrajobst @mellinoe @sivarv what is the best way to move forward?

[benaadams]

What about something like?

enum Keep
{
    Low,
    High
}

Vector<byte> Narrow(Vector<ushort> value, Keep keep)

void Narrow(Vector<ushort> value, out Vector<byte> low, out Vector<byte> high)

Vector<ushort> Widen(Vector<byte> value)

[mellinoe]

@benaadams Could you clarify the behavior of the above? The way I am reading it and interpreting how it's supposed to work, it seems like some of the types are reversed. For example, if I was narrowing UInt16's into UInt8's, then I need twice as many Vector<UInt16>'s, not the other way around. Maybe I'm getting hung up on the naming.

[benaadams]

@mellinoe ah good point; it was late at night :)

[mellinoe]

Here's another straw-man proposal. How about directly exposing UnpackHigh and UnpackLow? Does this make sense from our abstraction level?

public static Vector<T> UnpackLow(Vector<T> first, Vector<T> second);
public static Vector<T> UnpackHigh(Vector<T> first, Vector<T> second);

If we want to maintain a higher abstraction level, we could have just Widen (a specialization of UnpackHigh and UnpackLow):

public static void Widen(Vector<4> source, out Vector<2> dest1, out Vector<2> dest2)
{
    Vector<4> low = UnpackLow(source, Vector<4>.Zero);
    Vector<4> high = UnpackHigh(source, Vector<4>.Zero);
    dest1 = Vector.AsVector<2>(low);
    dest2 = Vector.AsVector<2>(high);
}

(Pretend that Vector<4> and Vector<2> map to abstract 4- and 2-length vector types)

To address @nietras 's concerns above about only needing the low or high elements:

public static Vector<2> WidenLow(Vector<4> source)
{
    Vector<4> low = UnpackLow(source, Vector<4>.Zero);
    return Vector.AsVector<2>(low);
}
public static Vector<2> WidenHigh(Vector<4> source);

Those could also directly be intrinsics.

Integer-to-floating-point conversions:

public static Vector<float> Convert(Vector<int> source);
public static Vector<float> Convert(Vector<uint> source);
public static Vector<double> Convert(Vector<long> source);
public static Vector<double> Convert(Vector<ulong> source);

Size-changing Convert (this could also be an intrinsic, depending on where we land):

public static void Convert(Vector<ushort> source, out Vector<float> dest1, out Vector<float> dest2)
{
    Vector<uint> l1, l2;
    Widen(source, out l1, out l2);
    dest1 = Convert(l1);
    dest2 = Convert(l2);
}

[benaadams]

With UnpackLow and UnpackHigh Widen in the example above could just be an extension method? (assuming it jitted well for registers)

How would narrow work? Use cases

1. Ascii -> UTF16 (byte -> ushort) : Widen
2. UTF16 -> Ascii (ushort-low x 2 -> byte) : Narrow
3. UTF16 validate ascii

3 could be lots of ways; a contrived one for narrow

if (!V.Equals(
   ((V<ushort>-low x 2 -> V<byte>) & (V<byte>(0x70)) 
      | (V<ushort>-high x 2 -> V<byte>)
   ), V<byte>.Zero)
{
    throw;
}

[mellinoe]

With UnpackLow and UnpackHigh Widen in the example above could just be an extension method? (assuming it jitted well for registers)

Right; it _could_ be, since Widen as described above is essentially just two calls to UnpackLow/High with the second parameter as Zero. Then again, maybe we want it as a direct intrinsic since it could be very common.

How would narrow work?

It seems like the API for it could be as straightforward as this:

public static Vector<int> Narrow(Vector<long> first, Vector<long> second);

@CarolEidt What are your thoughts?

[nietras]

@mellinoe having direct access to UnpackLow/UnpackHigh sounds good, but would this work for 16-bit to 32-bit signed integer conversion with SSE 4.1 instructions such as:

__m128i c = _mm_maddubs_epi16(u, s); // SSSE3 
// unpack the 4 lowest 16-bit integers into 32 bits.
__m128i lo = _mm_cvtepi16_epi32(c)
// Unpack the 4 highest 16-bit integers into 32 bits.
__m128i hi = _mm_cvtepi16_epi32(_mm_shuffle_epi32(c, 0x4e)));
// Add them to the 4 32-bit integer accumulators.
sum = _mm_add_epi32(_mm_add_epi32(lo, hi), sum);

Or should there be UnpackLow/High overloads without the second parameter that can either revert to calling with zeros or use a optimized path for this case when available? That is also add the following:

public static Vector<T> UnpackLow(Vector<T> v);
public static Vector<T> UnpackHigh(Vector<T> v);

For the interested this is used in optimized neural nets as detailed in Improving the speed of neural networks on CPUs where the above could also be done like (which matches the UnpackLow/UnpackHigh but requires an extra shift:

__m128i c = _mm_maddubs_epi16(u, s); // SSSE3 
// unpack the 4 lowest 16-bit integers into 32 bits.
__m128i lo = _mm_srai_epi32(_mm_unpacklo_epi16(c, c), 16);
// Unpack the 4 highest 16-bit integers into 32 bits.
__m128i hi = _mm_srai_epi32(_mm_unpackhi_epi16(c, c), 16);
// Add them to the 4 32-bit integer accumulators.
sum = _mm_add_epi32(_mm_add_epi32(lo, hi), sum);

Regarding Narrow, how would this work for say 16-bit signed integer to 8-bit unsigned integers? or 32-bit signed integer to 8-bit unsigned integer, just as a thought experiment?

Update: For reference there is this cheat sheet for x86 intrinsics http://db.in.tum.de/~finis/x86%20intrinsics%20cheat%20sheet%20v1.0.pdf

And another question would be what about _mm_cvtepu8_epi32? This does not match the UnpackLow/UnpackHigh as far as I can tell.

[CarolEidt]

@mellinoe - sorry for the delay in response. I like the direction.
@nietras - I love the cheat sheet, thanks!
I think the right places to start, as @mellinoe proposes, is with Widen and Narrow between types where one is half the size of the other, and conversions to and from same-sized integer and float.
For narrowing conversions, I think we should attempt to follow the CLI (C#) semantics, which do the sign or zero-extension based on the target type (since the evaluation stack is effectively sign-less).
For conversions other than doubling or halving the size, I think we should consider whether the best approach is additional intrinsics versus relying on the JIT to perform peephole pattern matches of sequential calls.

[jackmott]

I was asked to chime in here, and just wanted to say I absolutely would love to see the conversion methods added. As well I would like every single SIMD intrinsic that intel and ARM support added to the api. The whole list here: https://software.intel.com/sites/landingpage/IntrinsicsGuide/

.NET makes writing SIMD very nice since it can adapt at JIT-time to the architecture, if you can achieve complete instruction coverage it makes an extremely compelling platform compared to all other managed environments.

[danmosemsft]

Anyone willing to write up a formal api proposal ?

[mellinoe]

I've made a proposal here: dotnet/corefx#15957

[mellinoe]

We've implemented some API's which should cover a good chunk of the scenarios here. If there's still things that could be optimally solved with different intrinsics, we can open a further discussion.