优化技巧

Question

int *s;
allocate memory for s[100];
void func (int *a, int *b)
{
    int i;

    for (i = 0; i < 100; i++)
    {
        s[i] = a[i] ^ b[i];
    }
}

假设这段代码片段被调用了1000次，并且这是我代码中最耗时的操作。还要假设a和b的地址每次都会改变。's'是一个全局变量，它会被不同的a和b值更新。

就我所知，主要的性能瓶颈应该是内存访问，因为唯一的其他操作是XOR，这非常简单。

请问你能否建议如何以最佳方式优化我的代码？

我真正想要问的问题是，假设这个for循环包含10个XOR操作，循环次数为100，函数被调用1000次，关键点在于高内存访问。如果代码要在单核机器上执行，那么有哪些改进空间呢？

- anup

---

s是什么？为什么它是局部的？如果函数只是填充一个局部数组，那么它实际上并不会做任何事情，因此最好的优化方式就是完全删除它。如果函数没有返回任何东西，为什么你的函数要是int类型的？你用这个函数做什么？你需要给我们更多的信息。 - IVlad

这个函数很奇怪。它计算出了s，但立即将其丢弃并泄漏了分配的内存。因此，最好的优化可能是 int func(int *a, int *b) { (void)a; (void)b; }。 - lijie

你对你的应用程序和这段代码进行了剖析吗？在优化之前，始终进行剖析。其他一切都是虚构。 - RED SOFT ADAIR

@RED：OP确实说这是最耗时的操作了，你还想要什么？ - Cascabel

你必须提供更多有关调用函数的信息。一些a和b数组是重复的吗？当涉及到内存瓶颈时，你真的需要考虑整个访问模式，而不仅仅是一个小的100元素循环。在稍微高一级重新排列内存访问可能会对性能产生巨大影响，具体取决于正在进行的操作。 - phkahler

Answer 1

我已经测试了提出的两个解决方案和其他两个。我无法测试onemasse的建议，因为保存到s[]的结果不正确。我也无法修复它。我不得不对moonshadow的代码进行一些更改。测量单位是时钟周期，所以数值越低越好。

原始代码：

#define MAX 100
void inline STACKO ( struct timespec *ts, struct timespec *te ){

    int i, *s, *a, *b;

    for (i = 0; i < MAX; ++i){
        s = (int *) malloc (sizeof (int)); ++s;
        a = (int *) malloc (sizeof (int)); ++a;
        b = (int *) malloc (sizeof (int)); ++b;
    }

    srand ( 1024 );
    for (i = 0; i < MAX; ++i){
        a[i] = ( rand() % 2 );
        b[i] = ( rand() % 2 );
    }

    rdtscb_getticks ( ts ); /* start measurement */

    for (i = 0; i < MAX; i++)
        s[i] = a[i] ^ b[i];

    rdtscb_getticks ( te ); /* end measurement */

/*
    printf("\n");
    for (i = 0; i < MAX; ++i)
        printf("%d", s[i]);
    printf("\n");
*/
}

新提案1：注册int

来自：

int i, *s, *a, *b;

至：

register int i, *s, *a, *b;

新提案2：不使用数组表示法。

s_end = &s[MAX];
for (s_ptr = &s[0], a_ptr = &a[0], b_ptr = &b[0]; \
   s_ptr < s_end; \
   ++s_ptr, ++a_ptr, ++b_ptr){
    *s_ptr = *a_ptr ^ *b_ptr;
}

月影提出的优化建议：

s_ptr = &s[0];
a_ptr = &a[0];
b_ptr = &b[0];

for (i = 0; i < (MAX/4); i++){

    s_ptr[0] = a_ptr[0] ^ b_ptr[0];
    s_ptr[1] = a_ptr[1] ^ b_ptr[1];
    s_ptr[2] = a_ptr[2] ^ b_ptr[2];
    s_ptr[3] = a_ptr[3] ^ b_ptr[3];
    s_ptr+=4; a_ptr+=4; b_ptr+=4;
}

月影提出优化+寄存器int:

来自：

int i, *s, ...

至：

register int i, *s, ...

Christoffer提出了优化方案：

#pragma omp for
for (i = 0; i < MAX; i++)
{
    s[i] = a[i] ^ b[i];
}

结果：

Original Code   1036.727264
New Proposal 1  611.147928
New proposal 2  450.788845
moonshadow      713.3845
moonshadow2     452.481192
Christoffer     1054.321943

另外一种优化生成的二进制文件的简单方法是向 gcc 传递 -O2。这会告诉 gcc 你想要进行优化。如果想要了解 -O2 的具体作用，请参考 gcc 的 man 手册。

启用 -O2 后，如下图所示性能会得到提升：

Original Code   464.233031
New Proposal 1  452.620255
New proposal 2  454.519383
moonshadow      428.651083
moonshadow2     419.317444
Christoffer     452.079057

源代码可在以下网址获取：http://goo.gl/ud52m。

- Peter

Answer 2

不要使用循环变量进行索引。 展开循环。

for (i = 0; i < (100/4); i++)
{
  s[0] = a[0] ^ b[0];
  s[1] = a[1] ^ b[1];
  s[2] = a[2] ^ b[2];
  s[3] = a[3] ^ b[3];
  s+=4; a+=4; b+=4;
}

学习如何在你的平台上执行SIMD XOR。

将这些XOR作为显式步骤执行可能比将它们作为其他计算的一部分执行更加昂贵：你需要从a和b中读取并将结果存储在s中 - 如果为了进行更多的计算再次读取s，则通过在那里执行XOR可以每次迭代节省一次读取和写入，以及所有函数调用和循环开销；同样，如果a和b是某些其他函数的输出，则通过在其中一个函数结束时执行XOR可以更好地完成任务。

- moonshadow

---

你认为编译器不能自己做到这一点，考虑到常数的上限吗？它可以，并且会插入相应的SIMD指令（如果在这里有益的话，这很可能是情况）。 - Konrad Rudolph

@Konrad: 我一整天都在查看反汇编的编译器输出。很多时候，在我们支持的所有三个平台上，编译器无法很好地或根本不执行此类操作。我从未见过编译器在没有明确提示（即使用平台的SIMD类型和指令）的情况下产生合理的SIMD代码。 - moonshadow

@Konrad：哈哈。理论上，我们的一个平台甚至支持GCC自动向量化（http://gcc.gnu.org/projects/tree-ssa/vectorization.html）。实际上，我现在只有每个月提交一次编译器错误报告，所以我想事情正在稍微改善。八爪鱼编译器怎么了？ - moonshadow

自动向量化并不容易。编译器需要证明a、b和s能被16整除，如果不能则插入适当的填充，这会增加开销。这种开销可能会导致代码性能变差，我曾经通过使用-fno-tree-vectorize在某些关键循环中提高了性能。 - Gunther Piez

@Konrad：-O3 不够。例如，GCC 不会展开循环，除非您明确使用“-funroll-loops”，并且不会尝试使用 SIMD 指令，除非您使用“-march=$SOMETHING”来指定代码要在支持它们的处理器上运行。 - Porculus

Answer 3

int *s;
allocate memory for s[100];
void func (int *a, int *b)
{
    int i;

    #pragma omp for
    for (i = 0; i < 100; i++)
    {
        s[i] = a[i] ^ b[i];
    }
}

当然，对于只有一百个元素的情况下，您可能看不到任何特别的改进 :-)

- Christoffer

---

即使你忘记插入“parallel”，对于仅有100个数字来说，这实际上会慢得多。 - Konrad Rudolph

啊，Kondrad，你说得很对。我会删除之前的评论。 - Christoffer

在调用此函数1000次的下一个更高级别可能会更合适。 - phkahler

Answer 4

这只是一个猜测。如果这是缓存问题，您可以尝试以下操作：

int *s;
allocate memory for s[100];
void func (int *a, int *b)
{
    int i;

    memcpy( s, a, 100 );

    for (i = 0; i < 100; i++)
    {
        s[i] = s[i] ^ b[i];
    }
}

虽然memcpy是一个函数调用，但如果size参数是常数，则编译器通常会将其内联。循环展开在这里可能不起作用，因为它可以被编译器自动完成。但是你不应该只听我的话，在你的平台上进行验证。

- onemasse