Help me optimize this snippet.

Question

Is it possible to speed up this snippet?

firstSample and lastSample is the part of the array I'm interested in this iteration. It's when this interval reaches > 3000 that I get a noticeable slowdown. The _average array can contain 6-60 million int values.

minY and maxY is the result I use after this calculation is completed.

int minY = Int32.MaxValue;
int maxY = Int32.MinValue;
int Y = 0;
int sample = firstSample + 1;

while (sample <= lastSample)
{
       Y = _average[sample];
       minY = Math.Min(Y, minY);
       maxY = Math.Max(Y, maxY);
       sample++;
}

Answer 1

You can use FOR is more speedy than while or use Parallel if you have 3.5+ framework

Answer 2

I'm going to stick my neck out and say No, I don't think there's any way to make that significantly faster (unless inlining the calls to Min and Max would help, but I expect the optimiser will take care of that).

But that said, if you're doing this multiple times on the same data, sorting the data (or the chunks of data you're dealing with each time) might make the whole process quicker.

It's slower to sort than to the find the minimum, but it's quicker to sort once than to find the minimum a thousand times.

(Forgive me if I'm teaching you to suck eggs here. 8-)

Answer 3

For one thing, I'd rewrite it as a simple for loop and avoid using a Pascal-cased local variable, including one with more scope than it needs:

int minY = int.MaxValue;
int maxY = int.MinValue;

for (int sample = firstSample + 1; sample <= lastSample; sample++)
{
    int y = _average[sample];
    minY = Math.Min(y, minY);
    maxY = Math.Max(y, maxY);
}

That's just to make it more familiar and conventional. The JIT knows about looping over arrays in certain situations, but I don't know whether it will help in this case - it could just check firstSample >= -1 && lastSample < _average.length and then eliminate bounds checks, but I don't know if it does. Now, samples which are already in the current min/max range don't need any side effects, so let's get rid of the assignments in that case:

for (int sample = firstSample + 1; sample <= lastSample; sample++)
{
    int y = _average[sample];
    if (y < minY)
    {
        minY = y;
    }
    if (y > maxY)
    {
        maxY = y;
    }
}

I don't know whether or not that will help - and I suspect it won't, but it may be worth a try...

(As another answer said, this is a very easy operation to parallelise - it should improve the speed nearly linearly with CPU count, i.e. 2 processors ~= twice as fast etc, apart from the cache misses etc.)

Answer 4

The _average[sample] expression is a huge bottleneck, since it contains an implicit bounds check on each iteration. Use a pointer to the "_average" array (and the unsafe keyword). Then avoid calling any functions, so get rid of the Math.Min/Max calls and do that checks yourself.

Without any compiler at my hands right now, I think this is how it should look:

unsafe
{
 fixed ( int* paverage = _average )   
 {
  int* p = paverage + firstSample + 1;
  for ( int sample = firstSample+1 ; sample <= lastSample ; sample++ )   
  {
   if ( *p < minY )
    minY = *p;
   if ( *p > maxY )
    maxY = *p;
   p++;
  }
 }   
}

Then finally, since "sample" is not actually used in the loop, you can change it to a loop variable that counts down to zero, so that the loop termination check is done against a constant (zero) instead of a variable.

Answer 5

You might try the for loop as others have suggested.

It'll need profiling, but you could also try eliminating method invocations and branching:

   Y = _average[sample];
   minY = minY + ((Y-minY) & (Y-minY)>>31);
   maxY = maxX - ((X-maxX) & (X-maxX)>>31);
   sample++;

Make these changes only if the performance gain is really critical for you, since the maintainability of the code degrades with similar constructs.

Answer 6

Unsafe code would allow you to use pointers to index the array, as the JIT compiler will be unable to remove the bounds check in this particular case. Look here on how to do that.

You might also try inlining the Min/Max calls yourself, but there's a good chance the JIT is already doing that for you.

Finally, it's fairly easy to parallelize this with the Parallel Extensions of .NET 4 (you can use the CTP for .NET 3.5). Just make sure you don't write to the min/max values from multiple threads at the same time. Don't lock on it either though, I would have a min/max value per thread and do a final compare between the min/max values of each thread/task when all threads are done.

Answer 7

Use a for loop as others have said, but set it up so the comparison is to zero. This is a faster comparison in most implementations.

Answer 8

You wrote the following in a comment:

I'm not sorting. Only finding the max and min of an interval. And the interval moves every 20ms

It seems that you actually want a moving minimum and moving maximum.

I believe that this can be done more efficiently than to re-search the entire interval each time, assuming that the interval moves only in one direction, and that there is significant overlap between subsequent intervals.

One way would be to keep a special queue, where every new element copies its value to every element in the queue that is bigger (for the moving minimum), e.g.:

(5 8 4 7 7 0 7 0 4 4 3 4 0 9 7 9 5 4 2 0)  ; this is the array
(4 4 4 4)  ; the interval is 4 elements long, and initialized to the minimum
           ; of the first 4 elements
  (4 4 4 7)  ; next step, note that the current minimum is always the first element
    (4 7 7 0)  ; now something happens, as 0 is smaller than the value before
    (4 7 0 0)  ; there are still smaller values ...
    (4 0 0 0)  ; and still ...
    (0 0 0 0)  ; done for this iteration
      (0 0 0 7)
        (0 0 0 0)  ; the 0 again overwrites the fatties before
          (0 0 0 4)
            (0 0 4 4)
              (0 3 3 3)  ; the 3 is smaller than the 4s before,
                         ; note that overwriting can be cut short as soon as a
                         ; value not bigger than the new is found
                (3 3 3 4)
                  (0 0 0 0)  ; and so on...

If you move by more than 1 element each time, you can first calculate the minimum of all new values and use that for the back-overwriting.

Worst case for this algorithm is when the array is sorted descendingly, then it is O(nm), where m is the interval length and n the array length. Best case is when it is sorted descendingly, then it's O(n). For the average case, I conject O(n log(m)).

Answer 9

You could get rid of duplicate comparisons in situations where you find a new min. If you set both your min/max to the first value, then if you find a new min, there is no reason to check if it is also a new max. This is basically @Skeet's code with initialization and an extra 'else' statement.

int firstIndex = firstSample + 1;
if (firstIndex <= lastSample)
{
    minY = _average[firstIndex];
    maxY = minY;

    for (int sample = firstIndex + 1; sample <= lastSample; sample++)
    {
        int y = _average[sample];
        if (y < minY)
        {
            minY = y;
        }
        else if (y > maxY)
        {
            maxY = y;
        }
    }
}