你会如何优化这个功能？

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

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() 对数字的所有位都没有高质量的随机性，但现在已修复。如果你在意高质量的随机性，请关注这里。

如果随机性的质量不是特别重要，您可能还会寻找更快的随机生成器（它们存在）。

Answer 3

很难提供完整的答案。

（评论）我假设 rand 只是外部 50/50 决定的占位符，也不是用于生产用途？

否则，请注意 rand() 很糟糕。这对于匆忙中使数字看起来随机的白痴很有用。避免浮点除法。 rand()%2 通常比 rand()>RAND_MAX/2 差一点，但这种差异无关紧要。

（注解）你假设sizeof(int)==4。不太好。
是否有理由不复制整个缓冲区？

单个大副本可能比许多小副本更快，即使它涉及双倍的数据。

即如果不使用未复制的元素，则原始数据是否在其中并不重要。 OTOH，如果不能覆盖未复制的元素，则不适用。

用 3 个整数赋值替换 memcpy。

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

这允许三个分配并行使用每个核心的多个单元。

并行化（但缓存）的巨大优化潜力

如果您可以使随机数生成不连续 - 例如通过使用 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" 的赋值，这不是什么好事。但是，您可能知道/可以构造一些技巧来使该赋值无分支）

你会如何优化这个功能？

how would you optimize this function?

c

c++

optimization

branch-prediction