我在网上和书里都查找过，但好像无法解决这个问题。我被要求对程序的一小部分进行优化，即使用vi和gcc在短时间内添加数组的内容，而不使用内置优化器。我尝试了循环展开和其他一些针对乘积的优化方法。你能帮忙吗？
int length = ARRAY_SIZE;
int limit = length-4;
for (j=0; j < limit; j+=5) {
sum += array[j] + array[j+1] + array[j+2] + array[j+3] + array[j+4];
}
for(; j < length; j++){
sum += array[j];
}
int，并且所有值都已经初始化。for (j=0; j < limit; j+=4) {
sum1 += array[j];
sum2 += array[j+1];
sum3 += array[j+2];
sum4 += array[j+3];
}
sum = sum1 + sum2 + sum3 + sum4;
这样可以避免一些写后读依赖，也就是说，在每次循环迭代中计算sum2不需要等待sum1的结果才能执行，处理器可以同时安排循环中的这两行代码。
使用 SSE/MMX 指令集：
__m128i sum;
for (j=0; j < limit; j+=4) {
sum = _mm_add_epi32(sum, array+j);
}
目前循环已经展开了5次。
由于您禁用了优化器，所有这些索引操作都会增加成本。
第一个循环可以被替换为：
int* p = array;
for (j = 0; j < ARRAY_SIZE - 4; j += 5, p += 5){
sum += p[0] + p[1] + p[2] + p[3] + p[4];
}
所以它不进行任何索引（将 j 乘以 sizeof(int) 并将其加到地址上）。
补充：当然，由于数组大小 ARRAY_SIZE 可能是已知常量，因此这可能是最快的代码，但您可能需要编写代码生成器（或聪明的宏）来实现它：
sum += array[0];
sum += array[1];
...
sum += array[ARRAY_SIZE - 1];
#define FOO64(i) FOO32(i); FOO32((i)+32)
#define FOO32(i) FOO16(i); FOO16((i)+16)
#define FOO16(i) FOO8(i); FOO8((i)+8)
#define FOO8(i) FOO4(i); FOO4((i)+4)
#define FOO4(i) FOO2(i); FOO2((i)+2)
#define FOO2(i) FOO1(i); FOO1((i)+1)
#define FOO1(i) sum += array[i]
FOO64(0);
您可以将相同的思路应用于其他幂，例如10。
我不确定为什么你不能使用优化器，因为根据我的经验，它通常会生成比大多数“自称”手动优化者更快的代码 :-) 另外，你应该确保这段代码实际上是一个问题区域 - 优化已经接近最大速度的代码没有意义，也不应该关注占用时间0.01%的代码，可能有其他代码占用了20%的时间。
优化应该有针对性，否则就是浪费努力。
除了天真的“只需将数字相加”的解决方案之外，大多数情况下都需要使用目标CPU的特殊功能。
如果你愿意在每次数组更新时承受一点小的损失（鉴于你的“所有值都已初始化”的评论，这可能不是一个选项），你可以非常快地得到总和。使用一个“类”来同时维护数组和总和。伪代码如下：
def initArray (sz):
allocate data as sz+1 integers
foreach i 0 thru sz:
set data[i] to 0
def killArray(data):
free data
def getArray (data,indx):
return data[indx+1]
def setArray (data,indx,val):
data[0] = data[0] - data[indx] + val
data[indx+1] = val
def sumArray(data):
return data[0]
应该可以解决问题。
#include <stdio.h>
#include <stdlib.h>
static int *initArray (int sz) {
int i;
int *ret = malloc (sizeof (int) * (sz + 1));
for (i = 0; i <= sz; i++)
ret[i] = 0;
return ret;
}
static void killArray(int *data) {
free (data);
}
static int getArray (int *data, int indx) {
return data[indx+1];
}
static void setArray (int *data, int indx, int val) {
data[0] = data[0] - data[indx] + val;
data[indx+1] = val;
}
static int sumArray (int *data) {
return data[0];
}
int main (void) {
int i;
int *mydata = initArray (10);
if (mydata != NULL) {
setArray (mydata, 5, 27);
setArray (mydata, 9, -7);
setArray (mydata, 7, 42);
for (i = 0; i < 10; i++)
printf ("Element %d is %3d\n", i, getArray (mydata, i));
printf ("Sum is %3d\n", sumArray (mydata));
}
killArray (mydata);
return 0;
}
这个的输出是：
Element 0 is 0
Element 1 is 0
Element 2 is 0
Element 3 is 0
Element 4 is 0
Element 5 is 27
Element 6 is 0
Element 7 is 42
Element 8 is 0
Element 9 is -7
Sum is 62
就像我所说的，这可能不是一个选择，但如果你能做到的话，你很难找到比单个数组索引提取更快的方法来获取总和。
而且，只要你正在实现一个类来完成这个任务，你也可以使用前两个元素进行一些管理工作，一个用于当前总和，另一个用于最大索引，这样你就可以通过检查indx是否超出最大值来避免越界错误。
在循环内部预取数据，您可以获得更好的性能。
我会在Drew的答案上进行补充：
register int value1, value2, value3, value4;
or (j=0; j < limit; j+=4)
{
// Prefetch the data
value1 = array[j];
value2 = array[j + 1];
value3 = array[j + 2];
value4 = array[j + 4];
// Use the prefetched data
sum1 += value1;
sum2 += value2;
sum3 += value3;
sum4 += value4;
}
sum = sum1 + sum2 + sum3 + sum4;
volatile来实现。我不知道volatile是否可以与register结合使用。由于样本中似乎每次需要进行五个加法，因此我在这里也这样做。通常情况下，您可以像Drew Hoskins建议的那样使用2的幂次方。 通过在开始时正确地获取模数并向另一个方向步进，可能需要更少的值。 以不同的顺序计算在科学计算中经常是有利的，而不仅仅是用于索引。 要确定优化是否有效，测试是必不可少的。
int sum1, sum2, sum3, sum4;
for(j = ARRAY_SIZE; j%5; j--){
sum += array[j];
}
sum1 = sum2 = sum3 = sum4 = 0;
for (; j; j-=5) {
sum += array[j-1];
sum1 += array[j-2];
sum2 += array[j-3];
sum3 += array[j-4];
sum4 += array[j-5];
}
sum += sum1+sum2+sum3+sum4;
fork吗？ - sje397-msse4选项。 - Anycorn