logo标签列表

为什么使用排序后的分组计算速度比未排序的分组慢？

c++performance
27

我有两列用制表符分隔的整数，第一列是随机整数，第二列是标识组的整数。可以使用这个程序(generate_groups.cc)生成。

#include <cstdlib>
#include <iostream>
#include <ctime>

int main(int argc, char* argv[]) {
  int num_values = atoi(argv[1]);
  int num_groups = atoi(argv[2]);

  int group_size = num_values / num_groups;
  int group = -1;

  std::srand(42);

  for (int i = 0; i < num_values; ++i) {
    if (i % group_size == 0) {
      ++group;
    }
    std::cout << std::rand() << '\t' << group << '\n';
  }

  return 0;
}

我会使用第二个程序 (sum_groups.cc) 计算每个组的总和。
#include <iostream>
#include <chrono>
#include <vector>

// This is the function whose performance I am interested in
void grouped_sum(int* p_x, int *p_g, int n, int* p_out) {
  for (size_t i = 0; i < n; ++i) {
    p_out[p_g[i]] += p_x[i];
  }
}

int main() {
  std::vector<int> values;
  std::vector<int> groups;
  std::vector<int> sums;

  int n_groups = 0;

  // Read in the values and calculate the max number of groups
  while(std::cin) {
    int value, group;
    std::cin >> value >> group;
    values.push_back(value);
    groups.push_back(group);
    if (group > n_groups) {
      n_groups = group;
    }
  }
  sums.resize(n_groups);

  // Time grouped sums
  std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
  for (int i = 0; i < 10; ++i) {
    grouped_sum(values.data(), groups.data(), values.size(), sums.data());
  }
  std::chrono::system_clock::time_point end = std::chrono::system_clock::now();

  std::cout << (end - start).count() << std::endl;

  return 0;
}

如果我在给定大小的数据集上运行这些程序，然后对同一数据集的行进行洗牌，那么洗牌后的数据计算总和的速度比有序数据快大约2倍或更多。

g++ -O3 generate_groups.cc -o generate_groups
g++ -O3 sum_groups.cc -o sum_groups
generate_groups 1000000 100 > groups
shuf groups > groups2
sum_groups < groups
sum_groups < groups2
sum_groups < groups2
sum_groups < groups
20784
8854
8220
21006

我本以为按组排序的原始数据具有更好的数据局部性和更快的速度，但是我观察到相反的情况。我想知道是否有人能够假设原因？

1
我不清楚，但是你正在写入超出sums向量范围的元素 - 如果你做正常的事情，传递向量的引用而不是指向数据元素的指针，然后使用.at()或调试模式的 operator[]进行边界检查，你会看到。 - Shawn
2
程序的行为未定义，因为您从未调整sum的大小。您必须调用sums.resize(n_groups);而不是sums.reserve(n_groups); - 这就是@Shawn所提示的。 - Eugene
好的，我已将示例更改为使用 resize()，但行为仍然相同。顺便提一下，这是一个 C++ 的玩具示例，旨在演示行为，因为在 C++ 中很容易快速创建可重现的示例。我在实际情况中看到了相同的行为，实际情况是一个 C 程序，因此在 grouped_sum() 中使用了指针。 - Jim
1
请注意（例如在这里或这里），使用一对向量而不是两个向量（值和组）可以正常运行。 - Bob__
1
你按值对数据进行了排序，对吧？但这也会对分组进行排序，并且对表达式 p_out[p_g[i]] += p_x[i]; 产生影响。也许在原始的混乱顺序中，这些组实际上在访问 p_out 数组方面展现出良好的聚类。按值排序可能会导致对 p_out 的差劲的组索引访问模式。 - Kaz
显示剩余2条评论
2个回答
33

设置/使其变慢

首先，该程序运行时间大致相同:

sumspeed$ time ./sum_groups < groups_shuffled 
11558358

real    0m0.705s
user    0m0.692s
sys 0m0.013s

sumspeed$ time ./sum_groups < groups_sorted
24986825

real    0m0.722s
user    0m0.711s
sys 0m0.012s

大部分时间都花费在输入循环中。但是由于我们对grouped_sum()感兴趣，让我们忽略它。

将基准循环从10个迭代更改为1000个迭代，grouped_sum()开始主导运行时间：

sumspeed$ time ./sum_groups < groups_shuffled 
1131838420

real    0m1.828s
user    0m1.811s
sys 0m0.016s

sumspeed$ time ./sum_groups < groups_sorted
2494032110

real    0m3.189s
user    0m3.169s
sys 0m0.016s

性能差异

现在我们可以使用perf来找到程序中最热门的部分。

sumspeed$ perf record ./sum_groups < groups_shuffled
1166805982
[ perf record: Woken up 1 times to write data ]
[kernel.kallsyms] with build id 3a2171019937a2070663f3b6419330223bd64e96 not found, continuing without symbols
Warning:
Processed 4636 samples and lost 6.95% samples!

[ perf record: Captured and wrote 0.176 MB perf.data (4314 samples) ]

sumspeed$ perf record ./sum_groups < groups_sorted
2571547832
[ perf record: Woken up 2 times to write data ]
[kernel.kallsyms] with build id 3a2171019937a2070663f3b6419330223bd64e96 not found, continuing without symbols
[ perf record: Captured and wrote 0.420 MB perf.data (10775 samples) ]

它们之间的区别是：

sumspeed$ perf diff
[...]
# Event 'cycles:uppp'
#
# Baseline  Delta Abs  Shared Object        Symbol                                                                  
# ........  .........  ...................  ........................................................................
#
    57.99%    +26.33%  sum_groups           [.] main
    12.10%     -7.41%  libc-2.23.so         [.] _IO_getc
     9.82%     -6.40%  libstdc++.so.6.0.21  [.] std::num_get<char, std::istreambuf_iterator<char, std::char_traits<c
     6.45%     -4.00%  libc-2.23.so         [.] _IO_ungetc
     2.40%     -1.32%  libc-2.23.so         [.] _IO_sputbackc
     1.65%     -1.21%  libstdc++.so.6.0.21  [.] 0x00000000000dc4a4
     1.57%     -1.20%  libc-2.23.so         [.] _IO_fflush
     1.71%     -1.07%  libstdc++.so.6.0.21  [.] std::istream::sentry::sentry
     1.22%     -0.77%  libstdc++.so.6.0.21  [.] std::istream::operator>>
     0.79%     -0.47%  libstdc++.so.6.0.21  [.] __gnu_cxx::stdio_sync_filebuf<char, std::char_traits<char> >::uflow
[...]

更多时间在main()函数中，可能已经将grouped_sum()内联。太好了，非常感谢性能优化。

perf annotate

main()函数内部花费时间的位置是否有差异？

已洗牌：

sumspeed$ perf annotate -i perf.data.old
[...]
       │     // This is the function whose performance I am interested in
       │     void grouped_sum(int* p_x, int *p_g, int n, int* p_out) {
       │       for (size_t i = 0; i < n; ++i) {
       │180:   xor    %eax,%eax
       │       test   %rdi,%rdi
       │     ↓ je     1a4
       │       nop
       │         p_out[p_g[i]] += p_x[i];
  6,88 │190:   movslq (%r9,%rax,4),%rdx
 58,54 │       mov    (%r8,%rax,4),%esi
       │     #include <chrono>
       │     #include <vector>
       │
       │     // This is the function whose performance I am interested in
       │     void grouped_sum(int* p_x, int *p_g, int n, int* p_out) {
       │       for (size_t i = 0; i < n; ++i) {
  3,86 │       add    $0x1,%rax
       │         p_out[p_g[i]] += p_x[i];
 29,61 │       add    %esi,(%rcx,%rdx,4)
[...]

已排序：

sumspeed$ perf annotate -i perf.data
[...]
       │     // This is the function whose performance I am interested in
       │     void grouped_sum(int* p_x, int *p_g, int n, int* p_out) {
       │       for (size_t i = 0; i < n; ++i) {
       │180:   xor    %eax,%eax
       │       test   %rdi,%rdi
       │     ↓ je     1a4
       │       nop
       │         p_out[p_g[i]] += p_x[i];
  1,00 │190:   movslq (%r9,%rax,4),%rdx
 55,12 │       mov    (%r8,%rax,4),%esi
       │     #include <chrono>
       │     #include <vector>
       │
       │     // This is the function whose performance I am interested in
       │     void grouped_sum(int* p_x, int *p_g, int n, int* p_out) {
       │       for (size_t i = 0; i < n; ++i) {
  0,07 │       add    $0x1,%rax
       │         p_out[p_g[i]] += p_x[i];
 43,28 │       add    %esi,(%rcx,%rdx,4)
[...]

不，它是相同的两个指令占据主导地位。因此，在这两种情况下都需要很长时间，但当数据排序时情况会更糟。

perf stat

好的。但我们应该运行相同次数的操作，所以每个指令之所以变慢，肯定有某些原因。让我们看看perf stat说了什么。
sumspeed$ perf stat ./sum_groups < groups_shuffled 
1138880176

 Performance counter stats for './sum_groups':

       1826,232278      task-clock (msec)         #    0,999 CPUs utilized          
                72      context-switches          #    0,039 K/sec                  
                 1      cpu-migrations            #    0,001 K/sec                  
             4 076      page-faults               #    0,002 M/sec                  
     5 403 949 695      cycles                    #    2,959 GHz                    
       930 473 671      stalled-cycles-frontend   #   17,22% frontend cycles idle   
     9 827 685 690      instructions              #    1,82  insn per cycle         
                                                  #    0,09  stalled cycles per insn
     2 086 725 079      branches                  # 1142,639 M/sec                  
         2 069 655      branch-misses             #    0,10% of all branches        

       1,828334373 seconds time elapsed

sumspeed$ perf stat ./sum_groups < groups_sorted
2496546045

 Performance counter stats for './sum_groups':

       3186,100661      task-clock (msec)         #    1,000 CPUs utilized          
                 5      context-switches          #    0,002 K/sec                  
                 0      cpu-migrations            #    0,000 K/sec                  
             4 079      page-faults               #    0,001 M/sec                  
     9 424 565 623      cycles                    #    2,958 GHz                    
     4 955 937 177      stalled-cycles-frontend   #   52,59% frontend cycles idle   
     9 829 009 511      instructions              #    1,04  insn per cycle         
                                                  #    0,50  stalled cycles per insn
     2 086 942 109      branches                  #  655,014 M/sec                  
         2 078 204      branch-misses             #    0,10% of all branches        

       3,186768174 seconds time elapsed

只有一件事引人注目：stalled-cycles-frontend。

好的，指令流水线正在停滞。在前端。确切地说，它的含义可能因微体系结构而异。

不过我有一个猜想。如果你慷慨的话，甚至可以称之为假设。

假设

通过对输入进行排序，您可以增加写操作的局部性。实际上，它们将非常局部；您所做的几乎所有加法都将写入与上一个相同的位置。

这对缓存来说很好，但对管道来说不太好。您正在引入数据依赖关系，阻止下一个加法指令继续执行，直到前一个加法完成（或者以其他方式使结果可用于后续指令）

那就是你的问题。

我想。

修复它

多个求和向量

实际上，让我们试一试。如果我们使用多个求和向量，在每次加法之间切换，然后最后将它们加起来呢？它会牺牲一些局部性，但应该可以消除数据依赖性。

（代码不太好看; 不要评判我，互联网！！）

#include <iostream>
#include <chrono>
#include <vector>

#ifndef NSUMS
#define NSUMS (4) // must be power of 2 (for masking to work)
#endif

// This is the function whose performance I am interested in
void grouped_sum(int* p_x, int *p_g, int n, int** p_out) {
  for (size_t i = 0; i < n; ++i) {
    p_out[i & (NSUMS-1)][p_g[i]] += p_x[i];
  }
}

int main() {
  std::vector<int> values;
  std::vector<int> groups;
  std::vector<int> sums[NSUMS];

  int n_groups = 0;

  // Read in the values and calculate the max number of groups
  while(std::cin) {
    int value, group;
    std::cin >> value >> group;
    values.push_back(value);
    groups.push_back(group);
    if (group >= n_groups) {
      n_groups = group+1;
    }
  }
  for (int i=0; i<NSUMS; ++i) {
    sums[i].resize(n_groups);
  }

  // Time grouped sums
  std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
  int* sumdata[NSUMS];
  for (int i = 0; i < NSUMS; ++i) {
    sumdata[i] = sums[i].data();
  }
  for (int i = 0; i < 1000; ++i) {
    grouped_sum(values.data(), groups.data(), values.size(), sumdata);
  }
  for (int i = 1; i < NSUMS; ++i) {
    for (int j = 0; j < n_groups; ++j) {
      sumdata[0][j] += sumdata[i][j];
    }
  }
  std::chrono::system_clock::time_point end = std::chrono::system_clock::now();

  std::cout << (end - start).count() << " with NSUMS=" << NSUMS << std::endl;

  return 0;
}

（哦，我还修复了n_groups的计算;它错了一个）

结果

在将-DNSUMS=...参数添加到编译器的makefile进行配置后，我可以这样做：

sumspeed$ for n in 1 2 4 8 128; do make -s clean && make -s NSUMS=$n && (perf stat ./sum_groups < groups_shuffled && perf stat ./sum_groups < groups_sorted)  2>&1 | egrep '^[0-9]|frontend'; done
1134557008 with NSUMS=1
       924 611 882      stalled-cycles-frontend   #   17,13% frontend cycles idle   
2513696351 with NSUMS=1
     4 998 203 130      stalled-cycles-frontend   #   52,79% frontend cycles idle   
1116188582 with NSUMS=2
       899 339 154      stalled-cycles-frontend   #   16,83% frontend cycles idle   
1365673326 with NSUMS=2
     1 845 914 269      stalled-cycles-frontend   #   29,97% frontend cycles idle   
1127172852 with NSUMS=4
       902 964 410      stalled-cycles-frontend   #   16,79% frontend cycles idle   
1171849032 with NSUMS=4
     1 007 807 580      stalled-cycles-frontend   #   18,29% frontend cycles idle   
1118732934 with NSUMS=8
       881 371 176      stalled-cycles-frontend   #   16,46% frontend cycles idle   
1129842892 with NSUMS=8
       905 473 182      stalled-cycles-frontend   #   16,80% frontend cycles idle   
1497803734 with NSUMS=128
     1 982 652 954      stalled-cycles-frontend   #   30,63% frontend cycles idle   
1180742299 with NSUMS=128
     1 075 507 514      stalled-cycles-frontend   #   19,39% frontend cycles idle

最佳求和向量数量可能取决于您的CPU流水线深度。我的7年老超极本CPU可能比新的高端台式机CPU需要更少的向量来达到流水线的最大利用率。

显然，更多不一定更好；当我使用128个求和向量时，我们开始遭受更多的缓存未命中 - 正如您最初预期的那样，洗牌输入变得比排序后的输入慢。我们已经走了个圆！:)

在寄存器中按组求和

（这是在编辑中添加的）

啊，被技术细节钻牛角尖！如果您知道您的输入将会被排序并且正在寻找更高的性能，则以下函数重写（没有额外的求和数组）甚至在我的计算机上更快。

// This is the function whose performance I am interested in
void grouped_sum(int* p_x, int *p_g, int n, int* p_out) {
  int i = n-1;
  while (i >= 0) {
    int g = p_g[i];
    int gsum = 0;
    do {
      gsum += p_x[i--];
    } while (i >= 0 && p_g[i] == g);
    p_out[g] += gsum;
  }
}

这个技巧的关键在于它允许编译器将组的总和变量gsum保留在寄存器中。我猜测（但可能非常错误）这样做更快，因为管道中的反馈循环可以更短，或者内存访问更少。一个良好的分支预测器将使得检查组相等的额外开销很小。

结果

对于随机输入来说效果很差...
sumspeed$ time ./sum_groups < groups_shuffled
2236354315

real    0m2.932s
user    0m2.923s
sys 0m0.009s

但是它比我的“许多求和”解决方案快约40％，针对的是排序后的输入。

sumspeed$ time ./sum_groups < groups_sorted
809694018

real    0m1.501s
user    0m1.496s
sys 0m0.005s

许多小组会比少数大组更慢，因此这是否是更快的实现将取决于您的数据。并且像往常一样，也要考虑您的CPU型号。
使用偏移而不是位掩码的多个求和向量 Sopel 提出了四个展开的加法作为我的位掩码方法的替代方案。我已经实现了他们建议的通用版本，可以处理不同的 NSUMS。我指望编译器为我们展开内部循环（至少对于NSUMS=4）。
#include <iostream>
#include <chrono>
#include <vector>

#ifndef NSUMS
#define NSUMS (4) // must be power of 2 (for masking to work)
#endif

#ifndef INNER
#define INNER (0)
#endif
#if INNER
// This is the function whose performance I am interested in
void grouped_sum(int* p_x, int *p_g, int n, int** p_out) {
  size_t i = 0;
  int quadend = n & ~(NSUMS-1);
  for (; i < quadend; i += NSUMS) {
    for (int k=0; k<NSUMS; ++k) {
      p_out[k][p_g[i+k]] += p_x[i+k];
    }
  }
  for (; i < n; ++i) {
    p_out[0][p_g[i]] += p_x[i];
  }
}
#else
// This is the function whose performance I am interested in
void grouped_sum(int* p_x, int *p_g, int n, int** p_out) {
  for (size_t i = 0; i < n; ++i) {
    p_out[i & (NSUMS-1)][p_g[i]] += p_x[i];
  }
}
#endif


int main() {
  std::vector<int> values;
  std::vector<int> groups;
  std::vector<int> sums[NSUMS];

  int n_groups = 0;

  // Read in the values and calculate the max number of groups
  while(std::cin) {
    int value, group;
    std::cin >> value >> group;
    values.push_back(value);
    groups.push_back(group);
    if (group >= n_groups) {
      n_groups = group+1;
    }
  }
  for (int i=0; i<NSUMS; ++i) {
    sums[i].resize(n_groups);
  }

  // Time grouped sums
  std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
  int* sumdata[NSUMS];
  for (int i = 0; i < NSUMS; ++i) {
    sumdata[i] = sums[i].data();
  }
  for (int i = 0; i < 1000; ++i) {
    grouped_sum(values.data(), groups.data(), values.size(), sumdata);
  }
  for (int i = 1; i < NSUMS; ++i) {
    for (int j = 0; j < n_groups; ++j) {
      sumdata[0][j] += sumdata[i][j];
    }
  }
  std::chrono::system_clock::time_point end = std::chrono::system_clock::now();

  std::cout << (end - start).count() << " with NSUMS=" << NSUMS << ", INNER=" << INNER << std::endl;

  return 0;
}

结果

开始测量。请注意，由于昨天我是在/tmp目录下工作，所以我的输入数据并不完全相同。因此，这些结果不能直接与之前的结果进行比较（但可能非常接近）。

sumspeed$ for n in 2 4 8 16; do for inner in 0 1; do make -s clean && make -s NSUMS=$n INNER=$inner && (perf stat ./sum_groups < groups_shuffled && perf stat ./sum_groups < groups_sorted)  2>&1 | egrep '^[0-9]|frontend'; done; done1130558787 with NSUMS=2, INNER=0
       915 158 411      stalled-cycles-frontend   #   16,96% frontend cycles idle   
1351420957 with NSUMS=2, INNER=0
     1 589 408 901      stalled-cycles-frontend   #   26,21% frontend cycles idle   
840071512 with NSUMS=2, INNER=1
     1 053 982 259      stalled-cycles-frontend   #   23,26% frontend cycles idle   
1391591981 with NSUMS=2, INNER=1
     2 830 348 854      stalled-cycles-frontend   #   45,35% frontend cycles idle   
1110302654 with NSUMS=4, INNER=0
       890 869 892      stalled-cycles-frontend   #   16,68% frontend cycles idle   
1145175062 with NSUMS=4, INNER=0
       948 879 882      stalled-cycles-frontend   #   17,40% frontend cycles idle   
822954895 with NSUMS=4, INNER=1
     1 253 110 503      stalled-cycles-frontend   #   28,01% frontend cycles idle   
929548505 with NSUMS=4, INNER=1
     1 422 753 793      stalled-cycles-frontend   #   30,32% frontend cycles idle   
1128735412 with NSUMS=8, INNER=0
       921 158 397      stalled-cycles-frontend   #   17,13% frontend cycles idle   
1120606464 with NSUMS=8, INNER=0
       891 960 711      stalled-cycles-frontend   #   16,59% frontend cycles idle   
800789776 with NSUMS=8, INNER=1
     1 204 516 303      stalled-cycles-frontend   #   27,25% frontend cycles idle   
805223528 with NSUMS=8, INNER=1
     1 222 383 317      stalled-cycles-frontend   #   27,52% frontend cycles idle   
1121644613 with NSUMS=16, INNER=0
       886 781 824      stalled-cycles-frontend   #   16,54% frontend cycles idle   
1108977946 with NSUMS=16, INNER=0
       860 600 975      stalled-cycles-frontend   #   16,13% frontend cycles idle   
911365998 with NSUMS=16, INNER=1
     1 494 671 476      stalled-cycles-frontend   #   31,54% frontend cycles idle   
898729229 with NSUMS=16, INNER=1
     1 474 745 548      stalled-cycles-frontend   #   31,24% frontend cycles idle

是的，在我的电脑上，内部循环使用NSUMS=8是最快的。与我的“本地gsum”方法相比，它还具有不会因为混洗输入而变得可怕的额外好处。
有趣的是注意到：NSUMS=16比NSUMS=8更糟。这可能是因为我们开始看到更多的缓存未命中，或者因为我们没有足够的寄存器来正确展开内部循环。
5
很有趣。 :) - Snild Dolkow
3
太棒了！之前不知道 perf。 - Tanveer Badar
1
我想知道在你的第一种方法中，手动展开4x并使用4个不同的累加器是否会产生更好的性能。就像https://godbolt.org/z/S-PhFm中的那样。 - Sopel
谢谢您的建议。是的，那确实提高了性能，我已经将其添加到答案中。 - Snild Dolkow
谢谢！我曾考虑过这种可能性，但不知道如何确定，感谢您详细的回答！ - Jim
没问题！希望它会有用。 - Snild Dolkow
3
这里是为什么排序组比未排序组慢的原因：
首先，这里是求和循环的汇编代码：
008512C3  mov         ecx,dword ptr [eax+ebx]
008512C6  lea         eax,[eax+4]
008512C9  lea         edx,[esi+ecx*4] // &sums[groups[i]]
008512CC  mov         ecx,dword ptr [eax-4] // values[i]
008512CF  add         dword ptr [edx],ecx // sums[groups[i]]+=values[i]
008512D1  sub         edi,1
008512D4  jne         main+163h (08512C3h)

让我们看一下add（加法）指令，这是这个问题的主要原因；

008512CF  add         dword ptr [edx],ecx // sums[groups[i]]+=values[i]

当处理器执行此指令时，首先会向edx地址发出内存读取（加载）请求，然后加上ecx的值，然后再向同一地址发出写入（存储）请求。 处理器的一项特性被称为内存重排序。 为了允许指令执行的性能优化，IA-32架构允许从强序模型中偏离，称为Pentium 4、Intel Xeon和P6系列处理器中的处理器排序。这些处理器排序变化（在此称为内存排序模型）允许诸如允许读取超前缓冲写入等性能增强操作。任何这些变化的目标都是提高指令执行速度，同时保持内存一致性，即使在多处理器系统中也是如此。 另外还有一个规则：读取可以与较旧的写入到不同位置重新排序，但不能与较旧的写入到相同位置重新排序。 因此，如果下一次迭代在写入请求完成之前达到add指令，则如果edx地址与上一次不同，则不会等待并发出读取请求，并将其重新排序到较旧的写入请求和add指令继续进行。但如果地址相同，则add指令将等待旧写入完成。 请注意，循环很短，处理器可以比内存控制器更快地执行它。 因此，对于排序的分组，您将连续多次从同一地址读取和写入，因此它将失去使用内存重排序的性能增强功能。同时，如果使用随机分组，则每次迭代可能有不同的地址，因此读取将不会等待旧写入并重新排序；add指令将不会等待前一个指令完成。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接