我正在努力提高我的互相关算法的性能速度。我能做些什么来让我的C代码运行得更快？

Question

我创建了一个互相关算法，我正试图通过减少运行时间来最大化它的性能。首先，我减少了"crossCorrelationV2“函数中的函数调用次数。其次，我在程序的顶部为常量创建了几个宏。第三，我减少了"crossCorrelationV2“函数中的循环数量。您看到的代码是我拥有的最新代码。

有没有其他方法可以尝试减少代码的处理时间？

假设我只关注函数"crossCorrelationV2“和"createAnalyzingWave”。

我很高兴得到任何建议，无论是关于编程的一般建议还是关于这两个特定函数的建议；我是一个初学者。谢谢。

#include <stdio.h>
#include <stdlib.h>

#define ARRAYSIZE 4096
#define PULSESNUMBER 16
#define DATAFREQ 1300

// Print the contents of the array onto the console.
void printArray(double array[], int size){
    int k;
    for (k = 0; k < size; k++){
        printf("%lf ", array[k]);
    }
    printf("\n");
}

// Creates analyzing square wave. This square wave has unity (1) magnitude.
// The number of high values in each period is determined by high values = (analyzingT/2) / time increment
void createAnalyzingWave(double analyzingFreq, double wave[]){
    int highValues = (1 / analyzingFreq) * 0.5 / ((PULSESNUMBER * (1 / DATAFREQ) / ARRAYSIZE));
    int counter = 0;
    int p;

    for(p = 1; p <= ARRAYSIZE; p++){
        if ((counter % 2) == 0){
            wave[p - 1] = 1;
        } else{
            wave[p - 1] = 0;
        }
        if (p % highValues == 0){
            counter++;
        }
    }
}

// Creates data square wave (for testing purposes, for the real implementation actual ADC data will be used). This
// square wave has unity magnitude.
// The number of high values in each period is determined by high values = array size / (2 * number of pulses)
void createDataWave(double wave[]){
    int highValues = ARRAYSIZE / (2 * PULSESNUMBER);
    int counter = 0;
    int p;
    for(p = 0; p < ARRAYSIZE; p++){
        if ((counter % 2) == 0){
            wave[p] = 1;
        } else{
            wave[p] = 0;
        }
        if ((p + 1) % highValues == 0){
            counter++;
        }
    }
}

// Finds the average of all the values inside an array
double arrayAverage(double array[], int size){
    int i;
    double sum = 0;
    // Same thing as for(i = 0; i < arraySize; i++)
    for(i = size; i--; ){
        sum = array[i] + sum;
    }
    return sum / size;
}
// Cross-Correlation algorithm
double crossCorrelationV2(double dataWave[], double analyzingWave[]){
    int bigArraySize = (2 * ARRAYSIZE) - 1;
    // Expand analyzing array into array of size 2arraySize-1
    int lastArrayIndex = ARRAYSIZE - 1;
    int lastBigArrayIndex = 2 * ARRAYSIZE - 2; //bigArraySize - 1; //2 * arraySize - 2;

    double bigAnalyzingArray[bigArraySize];

    int i;
    int b;
    // Set first few elements of the array equal to analyzingWave
    // Set remainder of big analyzing array to 0
    for(i = 0; i < ARRAYSIZE; i++){
        bigAnalyzingArray[i] = analyzingWave[i];
        bigAnalyzingArray[i + ARRAYSIZE] = 0;
    }
    double maxCorrelationValue = 0;
    double currentCorrelationValue;


    // "Beginning" of correlation algorithm proper
    for(i = 0; i < bigArraySize; i++){

        currentCorrelationValue = 0;
        for(b = lastBigArrayIndex; b > 0; b--){

            if (b >= lastArrayIndex){
                currentCorrelationValue = dataWave[b - lastBigArrayIndex / 2] * bigAnalyzingArray[b] + currentCorrelationValue;
            }

            bigAnalyzingArray[b] = bigAnalyzingArray[b - 1];
        }

        bigAnalyzingArray[0] = 0;
        if (currentCorrelationValue > maxCorrelationValue){
            maxCorrelationValue = currentCorrelationValue;
        }
    }

    return maxCorrelationValue;
}
int main(){
    int samplesNumber = 25;
    double analyzingFreq = 1300;


    double analyzingWave[ARRAYSIZE];
    double dataWave[ARRAYSIZE];

    createAnalyzingWave(analyzingFreq, analyzingWave);
    //createDataWave(arraySize, pulsesNumber, dataWave);

    double maximumCorrelationArray[samplesNumber];

    int i;
    for(i = 0; i < samplesNumber; i++){
        createDataWave(dataWave);
        maximumCorrelationArray[i] = crossCorrelationV2(dataWave, analyzingWave);
    }
    printf("Average of the array values: %lf\n", arrayAverage(maximumCorrelationArray, samplesNumber));

    return 0;
}

Answer 1

第一点是您显式地移动了analizingData数组，这样您需要两倍的内存，并且移动这些项大约占您时间的50%。在这里的测试中，使用crossCorrelationV2需要4.1秒，而实现crossCorrelationV3只需要大约2.0秒。

接下来的事情是，你在填充的数组上花费时间乘以0，去掉它，也去掉了填充，并简化了我们以crossCorrelationV4结束的索引，使程序在大约1.0秒内运行。

// Cross-Correlation algorithm
double crossCorrelationV3(double dataWave[], double analyzingWave[]){
    int bigArraySize = (2 * ARRAYSIZE) - 1;
    // Expand analyzing array into array of size 2arraySize-1
    int lastArrayIndex = ARRAYSIZE - 1;
    int lastBigArrayIndex = 2 * ARRAYSIZE - 2; //bigArraySize - 1; //2 * arraySize - 2;

    double bigAnalyzingArray[bigArraySize];

    int i;
    int b;
    // Set first few elements of the array equal to analyzingWave
    // Set remainder of big analyzing array to 0
    for(i = 0; i < ARRAYSIZE; i++){
        bigAnalyzingArray[i] = analyzingWave[i];
        bigAnalyzingArray[i + ARRAYSIZE] = 0;
    }
    double maxCorrelationValue = 0;
    double currentCorrelationValue;


    // "Beginning" of correlation algorithm proper
    for(i = 0; i < bigArraySize; i++){

        currentCorrelationValue = 0;

        // Instead of checking if b >= lastArrayIndex inside the loop I use it as
        // a stopping condition.
        for(b = lastBigArrayIndex; b >= lastArrayIndex; b--){
            // instead of shifting bitAnalizing[b] = bigAnalyzingArray[b-1] every iteration
            // I simply use bigAnalizingArray[b-i]
            currentCorrelationValue = dataWave[b - lastBigArrayIndex / 2] * bigAnalyzingArray[b - i] + currentCorrelationValue;
        }

        bigAnalyzingArray[0] = 0;
        if (currentCorrelationValue > maxCorrelationValue){
            maxCorrelationValue = currentCorrelationValue;
        }
    }

    return maxCorrelationValue;
}

// Cross-Correlation algorithm
double crossCorrelationV4(double dataWave[], double analyzingWave[]){
    int bigArraySize = (2 * ARRAYSIZE) - 1;
    // Expand analyzing array into array of size 2arraySize-1
    int lastArrayIndex = ARRAYSIZE - 1;
    int lastBigArrayIndex = 2 * ARRAYSIZE - 2; //bigArraySize - 1; //2 * arraySize - 2;

    // I will not allocate the bigAnalizingArray here
    // double bigAnalyzingArray[bigArraySize];

    int i;
    int b;
    // I will not copy the analizingWave to bigAnalyzingArray
    // for(i = 0; i < ARRAYSIZE; i++){
    //     bigAnalyzingArray[i] = analyzingWave[i];
    //     bigAnalyzingArray[i + ARRAYSIZE] = 0;
    // }
    double maxCorrelationValue = 0;
    double currentCorrelationValue;


    // Compute the correlation by symmetric paris 
    // the idea here is to simplify the indices of the inner loops since
    // they are computed more times.
    for(i = 0; i < lastArrayIndex; i++){

        currentCorrelationValue = 0;

        for(b = lastArrayIndex - i; b >= 0; b--){
            // instead of shifting bitAnalizing[b] = bigAnalyzingArray[b-1] every iteration
            // I simply use bigAnalizingArray[b-i]
            currentCorrelationValue += dataWave[b] * analyzingWave[b + i];
        }
        
        if (currentCorrelationValue > maxCorrelationValue){
            maxCorrelationValue = currentCorrelationValue;
        }
        if(i != 0){
            currentCorrelationValue = 0;
            // Correlate shifting to the other side
            for(b = lastArrayIndex - i; b >= 0; b--){
                // instead of shifting bitAnalizing[b] = bigAnalyzingArray[b-1] every iteration
                // I simply use bigAnalizingArray[b-i]
                currentCorrelationValue += dataWave[b + i] * analyzingWave[b];
            }
            
            if (currentCorrelationValue > maxCorrelationValue){
                maxCorrelationValue = currentCorrelationValue;
            }
        }
        
    }

    return maxCorrelationValue;
}

如果你想要更多的优化，你可以展开循环的一些迭代，并启用一些编译器优化，比如向量扩展。