代码之家 › 专栏 › 技术社区 › markzzz

如何同时迭代两个间距不等的数组?

branch-prediction optimization c++

-1

markzzz · 技术社区 · 6 年前

假设我要把两个数组相乘,比如 A[MAX_BUFFER] 和 B[MAX_BUFFER] (用) MAX_BUFFER = 256 )

出于某种原因,每个 B[最大缓冲区] 数值按固定控制率计算( 8 ,例如),因为每个值都将被重处理。

以后,我需要彼此相乘 C[MAX_BUFFER] ,考虑到(引入的)不同间距。所以用 A 在256个值上,我会得到一个 B 具有可变大小(本例中为32,因为控制率为8)。

这里有一个 example code :

#include <iostream>
#include <math.h>

#define MAX_BUFFER 256

double HeavyFunction(double value) {
    if (value == 0) return 0.0;

    return pow(10.0, value); // heavy operations on value...
}

int main()
{    
    int blockSize = 256;
    int controlRate = 8;

    double A[MAX_BUFFER];
    double B[MAX_BUFFER];
    double C[MAX_BUFFER];

    // fill A
    for (int sampleIndex = 0; sampleIndex < blockSize; sampleIndex++) {
        A[sampleIndex] = sampleIndex;
    }

    // fill B (control rated)
    int index = 0;
    for (int sampleIndex = 0; sampleIndex < blockSize; sampleIndex += controlRate, index++) {
        B[index] = HeavyFunction(index);
    }

    // calculate C
    for (int sampleIndex = 0; sampleIndex < blockSize; sampleIndex++) {     
        C[sampleIndex] = A[sampleIndex] + B[sampleIndex / 8];

        std::cout << C[sampleIndex] << std::endl;
    }
}

我需要性能,因为我将并行处理许多这些操作,在1秒内发送许多数据(例如44100个样本 blockSize & = MAX_BUFFER )

我想避开分支(即 if )和除法(如上例所示),它们不是类似cpu的操作(处理大量数据)。

在前面的例子中,这将介绍 sampleIndex / 8 * N “徒劳无功”的操作;如果我称之为百万样本的程序…

对于CPU,您将如何以一种奇特而轻松的方式重构此代码?

2 回复 | 直到 6 年前

1

0

Jarod42 6 年前

我认为Optimizer可以单独完成这项工作,但您可以展开循环以避免划分:

// calculate C
const max = blockSize / 8;
int j = 0;
for (int i = 0; i != max; ++i) {
    const auto b = B[i];
    C[j] = A[j] + b; std::cout << C[j] << std::endl; ++j;
    C[j] = A[j] + b; std::cout << C[j] << std::endl; ++j;
    C[j] = A[j] + b; std::cout << C[j] << std::endl; ++j;
    C[j] = A[j] + b; std::cout << C[j] << std::endl; ++j;
    C[j] = A[j] + b; std::cout << C[j] << std::endl; ++j;
    C[j] = A[j] + b; std::cout << C[j] << std::endl; ++j;
    C[j] = A[j] + b; std::cout << C[j] << std::endl; ++j;
    C[j] = A[j] + b; std::cout << C[j] << std::endl; ++j;
}

2

0

UmNyobe 6 年前

如何同时迭代两个间距不等的数组?

简而言之:专注于繁重的功能,避免在线程之间共享不必要的东西。

不幸的是你的例子不符合他的问题。数组

double A[MAX_BUFFER];
double B[MAX_BUFFER];
double C[MAX_BUFFER];

仅通过移动堆栈指针在堆栈上分配,因此可以说它们非常类似于一个连续数组。

即使不是它们,现代的缓存也非常复杂,通过尝试进行微观优化,最终可能会降低性能。

假设你有

BUFFER_SIZE = 1024 * 1024 * 1024;
std::vector<double> A(MAX_BUFFER);
std::vector<double> B(MAX_BUFFER);

好的改进是

std::vector<double> C{A};
for (int i = 0; i < blockSize/controlRate; i++) { 
     const double b = B[i];
     int indexStart = i*controlRate;
     for(int j = 0 ; j < controlRate; ++j){
        Cprime[indexStart+j] += b;
     }

}

你读A一次(分块),B一次(一次读两次),访问C的时间相同。