Finding min value of an array using SIMD

Question

I have the following code to find the minimum sbyte value in an array. It is using System.Runtime.Intrinsics to perform a SIMD min on chunks of the array, and then loops over the resulting vector to find the true minimum.

public static sbyte Min( sbyte[] array )
{
  if( array.Length <= 0 )
    return 0;

  var length = array.Length;
  var stepSize = Vector128<sbyte>.Count;

  fixed ( sbyte* pStep = &array[ 0 ] )
  {
    var i = stepSize;
    var minVector = Avx.LoadVector128( pStep );
    for( ; i <= length - stepSize; i += stepSize )
      minVector = Avx.Min( minVector, Avx.LoadVector128( pStep + i ) );

    var _ = stackalloc sbyte[ stepSize ];
    Avx.Store( _, minVector );

    // Find min of minVector
    var min = sbyte.MaxValue;
    for( var j = 0; j < stepSize; j++ )
      if( min > _[ j ] )
        min = _[ j ];

    // Evaluate remaining elements
    if( i < length )
      while( i < length )
      {
        if( min > pStep[ i ] )
          min = pStep[ i ];
        i++;
      }

    return min;
  }
}

I feel like this is a slightly excessive amount of code, but seeing how this function is meant to handle arrays with lengths that can't be equally partitioned into a 128-bit register, I'm not sure if there's any cleaner way to do this.

I do intend to implement this method for all supported primitive types, but it seems like most of the code will just be duplicated.

Answer 1

Correctness

  if( array.Length <= 0 )
    return 0;

This piece of code is suspicious. Maybe you should return sbyte.MaxValue, maybe null, or maybe throw ArgumentException. (I can imagine that there were a Max method, both, together is used to find the range of values, then maybe 0 is a valid return value.) This is one of the rare times I'd appreciate a comment to explain such extrinsic information.

Useless Code

 if( i < length )
      while( i < length )

Lose the if.

Excessive code

When you are operating on fixed size chunks, - pad the input with some appropriate value (sbyte.MaxValue) - handle the last fixed size chunk of the input separately.

The last suggestion should read something like this, (which means I don't even guarantee that it will compile):

if (length < stepSize)
    throw new ArgumentException($"this method cannot be used for arrays shorter than {stepSize}") 

Vector128<sbyte> minVector;
SetAllVector128(minVector, sbyte.MaxValue);
for (var i = 0; i < length - stepSize; i += stepSize)
    minVector = Avx.Min(minVector, Avx.LoadVector128(pStep + i));

minVector = Avx.Min(minVector, Avx.LoadVector128(pStep + length - stepSize));

Then you can use the last loop altogether;

Answer 2

As mentioned by others it's a problem when the size of the input array is lesser than Vector128<sbyte>.Count. You can handle it by taking the min of the two as stepSize:

int stepSize = Math.Min(Vector128<sbyte>.Count, array.Length);

This is safe because the first for-loop will only run if stepSize > vector size and the first while-loop will only iterate the actual number of elements in array.

---

Alternatively you can make some proper input checks like:

  if (array == null) throw new ArgumentNullException(nameof(array));
  if (array.Length == 0) throw new InvalidOperationException("Input must contains data.");

  if (array.Length < Vector128<sbyte>.Count)
    return array.Min();

You should do the first two checks anyway...