如何优化这个函数

Question

#include <stdlib.h> 
#include <cstring.h>
#include <time.h>
int cp[1000000][3];
int p[1000000][3];//assume this array to be populated
void  main(){
srand(time(NULL));
for(n; n < 1000000; n++){
    if (rand()%2)
        memcpy(cp[n], p[n], 12);
    }
}
}

这是我正在使用的实际代码的一个简化版本。这段代码占据了我的过程的一个重要部分，我想知道我是否可以用一些聪明的技巧来优化它。我以前使用过指针来避免分支，但我不知道如何在这里应用它。

Answer 1

去掉浮点数是您应该做的一个明显的改进。这部分看起来很可疑，我猜你想要50%的概率代码会复制数据?

分支本身可以通过一些愚蠢的技巧被删除，比如:

int do_copy = rand() % 2;
memcpy(cp[n], p[n], 12*do_copy);

但是，如果不首先查看优化后的代码的反汇编，我是不会编写这样的代码的。

Answer 2

很难给出一个完整的答案。

1. (评论)我认为rand只是外部50/50决策的占位符，而不是用于生产用途?

否则，请注意rand()很糟糕。对于一个赶时间的白痴来说，它可以让数字看起来是随机的。避免浮点除法。rand()%2通常比rand()>RAND_MAX/2差一点，但这种差异很少影响。

(注释)你假设sizeof(int)==4。不是很好。

是否有理由不复制整个缓冲区?

单个大拷贝可能比许多小拷贝快，即使它涉及两倍的数据。

。如果不打算使用未复制的元素，那么原始数据是否在那里就无关紧要了。如果不能覆盖未复制的元素，则不适用

。

用3个整数赋值替换内存。

好的编译器应该能够在大多数情况下做到这一点，就像你现在的情况一样，但是内存可能会变得有点复杂。(它需要检查奇数长度，可能需要检查未对齐的读取，等等)

这允许三个赋值并行地使用每个内核的多个单元。

并行化(缓存除外)的巨大优化潜力

如果您可以使随机数生成非顺序的-例如通过使用4个独立的生成器-可以将负载分配到多个线程，每个线程处理一个数据块。

可以通过复制到一个虚拟缓冲区来避免该分支

这是一个有趣的想法，但我不确定它是否能让你付出太多。

int dummyBuffer[3];
for(...)
{
  int * target = (rand() % 2) ? dummyBuffer : cp+n;
  //  <-- replace with arithmetic trickery to avoid the branch
  target[0] = p[n][0];
  target[1] = p[n][1];
  target[2] = p[n][2];
}

(如上所述，分支将被移动到"target"的赋值处，这并不算赢。但是，您可能知道/可以构造一些技巧来使这个赋值不受分支限制)

Answer 3

rand()很可能是这段代码的瓶颈。因为你只需要一个二进制决策，考虑使用单个随机数的所有比特来平摊随机数生成的成本。

for(int n=0; n<1000000; n+=NUM_BITS){
    uint32_t rand_val = static_cast<uint32_t>(rand()); // Edited based on comments
    for(int j=0; j<NUM_BITS; j++) {
        if((rand_val >> j) % 2) {
            memcpy(cp[n+j], p[n+j], 12);
        }
    }
}

唯一的技巧是从RAND_MAX中找出NUM_BITS，并决定您想要的高质量和可移植性。选择NUM_BITS，使1<<NUM_BITS小于RAND_MAX。注意，这个版本假设NUM_BITS平分为样本总数。检查此限制或编写循环序言以容纳部分，则留给op作为练习。

我的Linux文档警告我，旧版本的rand()对数字的所有位都没有高质量的随机性，但现在已经修复了。如果你关心高质量的随机性，请注意这一点。

如果随机性的质量不是特别重要，你也可以寻找一个更快的随机生成器。