Finding min value of an array using SIMD

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.

• var _ - what an unconventional variable name is this? o_O I'm also giving you a -1 for that because it's just impolite to use names like this one and expect people to understand your code. – t3chb0t May 3 at 7:07
• While I don't share t3ch0t's sentiment completely, _ is a terrible variable name, and is now used as a discard, which may create confusion. – VisualMelon May 3 at 8:15

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;

• +1; I don't think there is any need to do the 'padding'; you can just load the first/final vector before the loop, and it will be fine. I think you can put a +1 in the loop condition so that it doesn't run the final block twice if length % stepSize == 0 – VisualMelon May 3 at 7:53

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...

• You still need to explicitly avoid any calls to LoadVector128 (e.g. the first in the OP, the last in abuzittin gillifirca's answer). I'm assuming that it could seg-fault (at some level), but even if it doesn't blow up it is not polite to read memory you can't control. I also think an explicit check (like abuzittin gillifirca's, though it needn't throw) would be better because it makes the intention clear, whereas setting up loops so that they implicitly don't run is a bit cryptic. – VisualMelon May 3 at 8:19
• @VisualMelon: I don't see your point. The minimum stepSize prevents effectively reading uncontrolled memory. – Henrik Hansen May 3 at 8:31
• I mean - for example in the OP's code - that even if the for loop cycles, that var minVector = Avx.LoadVector128( pStep ); will. It's not impossible I'm completely confused. – VisualMelon May 3 at 8:43
• @VisualMelon: OK, but if array.Length < Vector128<sbyte>.Count, the result is a vector padded with `0´ (defaults). Is seems safe to use by me :-) – Henrik Hansen May 3 at 8:48
• I don't know, it just feels wrong to me ;) It necessarily involves reading beyond the length of the array, and you can't make assumptions about whether you own that memory or not (maybe the structure of the HEAP in the CLR means it's safe enough, but that's an implementation detail). Your second piece of code would make me much happier indeed! – VisualMelon May 3 at 8:57