Compute efficiently Max and Min on data stream

user_9593060 0
Viewed 592

I'm working in C with a stream of data. Basically I receive a column array of 6 elements every n milliseconds. I would like to compute the max value for each row of data.

To make this clear this is how my data looks like (this is a toy example, actually I'll have thousand of columns acquired):

[6] [-10] [5]
[1] [5]   [3]
[5] [30]  [10]
[2] [-10] [0]
[-2][5]   [10]
[-5][0]   [1]

So basically (as I said) I receive a column of data every n milliseconds, and I want to compute the max and min value row-wise. So in my previous example my result would be:

max_values=[6,5,30,2,10,1]
min_values=[-10,1,5,-10,-2,-5]

I want to point out that I have no access to the full matrix, I can only work over single columns of 6 elements that I receive every n milliseconds.

This is my simple code algorithm so far (I'm omitting the whole code since it's part of a bigger project):

 for(int i=0;i<6;i++){
        if(input[i]>temp_max[i]){
            temp_max[i]=input[i];
        }
        if(input[i]<temp_min[i]){
            temp_min[i]=input[i];
        }

    }

Where input, temp_max and temp_min are all float arrays of dimension 6. Basically my code executes this piece of code everytime a new input array is available and updates the maximum and minimum accordingly.

Since I'm interested in performance (this is going to run on an embedded system), is there any way to improve this part of the code? Calling a comparison for each single element of the 2 arrays doesn't seem the most smart idea.

optimization c algorithm performance
5 Answers

With random input data (i.e. unordered data), it'll be pretty hard (aka impossible) to find min/max without a comparison per element.

You may get some minor improvement from something like:

temp_max[0]=input[0];
temp_min[0]=input[0];
for(int i=1;i<6;i++){             // Only 1..6
    if(input[i]>temp_max[i]){
        temp_max[i]=input[i];
    }
    else  // If current element was larger than max, you don't need to check min
    {
        if(input[i]<temp_min[i]){
            temp_min[i]=input[i];
        }
    }
}

but I doubt this will be a significant improvement.

user_43864270

Branching is slow, especially on embedded systems. Scalar computation too. Hopefully, your targeted processor seems to be an ARM-based processor supporting the NEON SIMD instruction set (apparently one based on a 64-bits ARM-V8 A53 architecture). NEON can compute 4 32-bits floating-point operations in a row. This should be much faster than the current code (which compilers apparently fail to vectorize).

Here is an example code (untested):

void minmax_optim(float temp_min[6], float temp_max[6], float input[6]) {
    /* Compute the first 4 floats */

    float32x4_t vInput = vld1q_f32(input);
    float32x4_t vMin = vld1q_f32(temp_min);
    float32x4_t vMax = vld1q_f32(temp_max);

    vMin = vminq_f32(vInput, vMin);
    vMax = vmaxq_f32(vInput, vMax);
    vst1q_f32(temp_min, vMin);
    vst1q_f32(temp_max, vMax);

    /* Remainder 2 floats */

    float32x2_t vLastInput = vld1_f32(input+4);
    float32x2_t vLastMin = vld1_f32(temp_min+4);
    float32x2_t vLastMax = vld1_f32(temp_max+4);

    vLastMin = vmin_f32(vLastInput, vLastMin);
    vLastMax = vmax_f32(vLastInput, vLastMax);
    vst1_f32(temp_min+4, vLastMin);
    vst1_f32(temp_max+4, vLastMax);
}

The resulting code should be much faster. One can see on goldbolt that the number of instructions of this vectorized implementation is drastically smaller than the reference implementation without any conditional jump instructions.

user_129395570

You nailed it -- you have to keep a temporary max and min arrays. Unfortunately, if we're talking strictly C, it seems to be the single possible and thus most performant algorithm possible.

Since you've mentioned it's going to run on embedded system (but omitted which), please make sure you have hardware floating point support. If there isn't, that's going to be high performance penality. If you have high-end hardware, you can look for availability of vector instructions, but then that's platform-specific, possibly by use of assembly.

user_23932630

To my impression the approach as such cannot be substantially improved, as the input is not available as a whole. That being said, the inner comparisons can be compacted. The assignemnts

if(input[i]>temp_max[i]){
    temp_max[i]=input[i];
}
if(input[i]<temp_min[i]){
    temp_min[i]=input[i];
}

can be improved to

if(input[i]>temp_max[i]){
    temp_max[i]=input[i];
}
else if(input[i]<temp_min[i]){
    temp_min[i]=input[i];
}

because if the current value replaces the temporary maximum, it cannot also replace the temporary minimum (assuming some sensible initialization).

user_33554760

Only for max but it is easy to expand

#define MAX(a,b,c) (a) > (b) ? ((b) > (c) ? (b) : (a) > (c) ? (a) : (c) ) : (b) > (c) ? (b) : (c) 


void rowmax(int *a, int *b, int *c, int *result, size_t size)
{
    for(size_t index = 0; index < size; index++)
    {
        result[index] = MAX(a[index], b[index], c[index]);
    }
}
user_61100940
Related