Nap*_*eis 7 c++ linear-algebra openmp compiler-optimization
我正在寻找OpenMP,部分原因是我的程序需要添加非常大的向量(数百万个元素).但是,如果我使用std :: vector或raw数组,我会看到相当大的差异.我无法解释.我坚持认为差异只在于循环,而不是当然的初始化.
我所指的时间差异,只是添加的时间,特别是不考虑矢量,数组等之间的任何初始化差异.我实际上只是谈论总和部分.在编译时不知道向量的大小.我g++在Ubuntu 16.04上使用5.x.
编辑:我测试了什么@Shadow说,它让我思考,是否有一些优化正在进行？如果我编译-O2,然后,使用初始化的原始数组,我回来进行循环缩放与线程数.但是使用-O3或者-funroll-loops,就好像编译器在早期启动并在看到编译指示之前进行优化.
我想出了以下简单测试:
#define SIZE 10000000
#define TRIES 200
int main(){
std::vector<double> a,b,c;
a.resize(SIZE);
b.resize(SIZE);
c.resize(SIZE);
double start = omp_get_wtime();
unsigned long int i,t;
#pragma omp parallel shared(a,b,c) private(i,t)
{
for( t = 0; t< TRIES; t++){
#pragma omp for
for( i = 0; i< SIZE; i++){
c[i] = a[i] + b[i];
}
}
}
std::cout << "finished in " << omp_get_wtime() - start << std::endl;
return 0;
}
我编译
g++ -O3 -fopenmp -std=c++11 main.cpp
获得一个线程
>time ./a.out
finished in 2.5638
./a.out 2.58s user 0.04s system 99% cpu 2.619 total.
对于两个线程,循环需要1.2s,总共1.23.
现在,如果我使用原始数组:
int main(){
double *a, *b, *c;
a = new double[SIZE];
b = new double[SIZE];
c = new double[SIZE];
double start = omp_get_wtime();
unsigned long int i,t;
#pragma omp parallel shared(a,b,c) private(i,t)
{
for( t = 0; t< TRIES; t++)
{
#pragma omp for
for( i = 0; i< SIZE; i++)
{
c[i] = a[i] + b[i];
}
}
}
std::cout << "finished in " << omp_get_wtime() - start << std::endl;
delete[] a;
delete[] b;
delete[] c;
return 0;
}
我得到(1线程):
>time ./a.out
finished in 1.92901
./a.out 1.92s user 0.01s system 99% cpu 1.939 total
std::vector 慢了33%!
对于两个线程:
>time ./a.out
finished in 1.20061
./a.out 2.39s user 0.02s system 198% cpu 1.208 total
作为比较,使用Eigen或Armadillo进行完全相同的操作(使用c = a + b带矢量对象的重载),我得到总实时~2.8s.它们不是用于向量添加的多线程.
现在,我认为std::vector几乎没有开销？这里发生了什么？我想使用漂亮的标准库对象.
在这样一个简单的例子中,我找不到任何参考.
Xirema的答案已经详细概述了代码中的差异。std::vector::reserve 将数据初始化为零，new double[size]但不初始化为零。请注意，您可以使用new double[size]()强制初始化。
但是，您的测量不包括初始化，并且重复次数非常高，即使在Xirema的示例中，循环成本也应超过小的初始化。那么，为什么在循环中完全相同的指令会因为初始化数据而花费更多时间呢？
让我们用一个可以动态确定内存是否已初始化的代码（基于Xirema的代码，但仅对循环本身进行计时）来挖掘其核心。
#include <vector>
#include <chrono>
#include <iostream>
#include <memory>
#include <iomanip>
#include <cstring>
#include <string>
#include <sys/types.h>
#include <unistd.h>
constexpr size_t size = 10'000'000;
auto time_pointer(size_t reps, bool initialize, double init_value) {
double * a = new double[size];
double * b = new double[size];
double * c = new double[size];
if (initialize) {
for (size_t i = 0; i < size; i++) {
a[i] = b[i] = c[i] = init_value;
}
}
auto start = std::chrono::steady_clock::now();
for (size_t t = 0; t < reps; t++) {
for (size_t i = 0; i < size; i++) {
c[i] = a[i] + b[i];
}
}
auto end = std::chrono::steady_clock::now();
delete[] a;
delete[] b;
delete[] c;
return end - start;
}
int main(int argc, char* argv[]) {
bool initialize = (argc == 3);
double init_value = 0;
if (initialize) {
init_value = std::stod(argv[2]);
}
auto reps = std::stoll(argv[1]);
std::cout << "pid: " << getpid() << "\n";
auto t = time_pointer(reps, initialize, init_value);
std::cout << std::setw(12) << std::chrono::duration_cast<std::chrono::milliseconds>(t).count() << "ms" << std::endl;
return 0;
}
结果是一致的：
./a.out 50 # no initialization
657ms
./a.out 50 0. # with initialization
1005ms
使用出色的Linux perf工具：
$ perf stat -e LLC-loads -e dTLB-misses ./a.out 50
pid: 12481
626ms
Performance counter stats for './a.out 50':
101.589.231 LLC-loads
105.415 dTLB-misses
0,629369979 seconds time elapsed
$ perf stat -e LLC-loads -e dTLB-misses ./a.out 50 0.
pid: 12499
1008ms
Performance counter stats for './a.out 50 0.':
145.218.903 LLC-loads
1.889.286 dTLB-misses
1,096923077 seconds time elapsed
随着重复次数的增加，线性缩放也告诉我们，差异来自循环内部。但是，为什么初始化内存会导致更多的最后一级缓存负载和数据TLB丢失？
要了解这一点，我们需要了解如何分配内存。仅仅因为malloc/ new返回指向虚拟内存的一些指针，并不意味着它背后有物理内存。虚拟内存可以位于没有物理内存支持的页面中，并且仅在第一页故障时才分配物理内存。现在在这里page-types（从linux/tools/vm-和我们在输出中显示的pid派上用场了。在长时间执行我们的小基准测试期间，查看页面统计信息：
flags page-count MB symbolic-flags long-symbolic-flags
0x0000000000000804 1 0 __R________M______________________________ referenced,mmap
0x000000000004082c 392 1 __RU_l_____M______u_______________________ referenced,uptodate,lru,mmap,unevictable
0x000000000000086c 335 1 __RU_lA____M______________________________ referenced,uptodate,lru,active,mmap
0x0000000000401800 56721 221 ___________Ma_________t___________________ mmap,anonymous,thp
0x0000000000005868 1807 7 ___U_lA____Ma_b___________________________ uptodate,lru,active,mmap,anonymous,swapbacked
0x0000000000405868 111 0 ___U_lA____Ma_b_______t___________________ uptodate,lru,active,mmap,anonymous,swapbacked,thp
0x000000000000586c 1 0 __RU_lA____Ma_b___________________________ referenced,uptodate,lru,active,mmap,anonymous,swapbacked
total 59368 231
大多数虚拟内存都位于正常mmap,anonymous区域中-映射到物理地址。
flags page-count MB symbolic-flags long-symbolic-flags
0x0000000001000000 1174 4 ________________________z_________________ zero_page
0x0000000001400000 37888 148 ______________________t_z_________________ thp,zero_page
0x0000000000000800 1 0 ___________M______________________________ mmap
0x000000000004082c 388 1 __RU_l_____M______u_______________________ referenced,uptodate,lru,mmap,unevictable
0x000000000000086c 347 1 __RU_lA____M______________________________ referenced,uptodate,lru,active,mmap
0x0000000000401800 18907 73 ___________Ma_________t___________________ mmap,anonymous,thp
0x0000000000005868 633 2 ___U_lA____Ma_b___________________________ uptodate,lru,active,mmap,anonymous,swapbacked
0x0000000000405868 37 0 ___U_lA____Ma_b_______t___________________ uptodate,lru,active,mmap,anonymous,swapbacked,thp
0x000000000000586c 1 0 __RU_lA____Ma_b___________________________ referenced,uptodate,lru,active,mmap,anonymous,swapbacked
total 59376 231
现在，在这里，只有1/3的内存由专用物理内存支持，而2/3映射到零页。a和后面的数据b全部由一个填充有零的只读4kiB页作为后备。c（和a，b在另一个测试中）已经被写入，因此它必须拥有自己的内存。
现在看起来很奇怪：这里的一切都为零1-为什么变为零很重要？不管你memset(0)，a[i] = 0.或者std::vector::reserve-一切导致明确写入到内存中，因此，如果你这样做零页面上的页面错误。我认为您此时不能/应该阻止物理页面分配。你可以在做的唯一事情memset/ reserve是使用calloc明确要求zero'd内存，这可能是一个支持zero_page，但我怀疑它完成（或使得很多的意义上）。请记住，new double[size];或malloc有不能保证一种记忆你会得到什么，但包括零内存的可能性。
1：请记住，双精度数0.0的所有位均设置为零。
最后，性能差异实际上仅来自循环，而是由初始化引起的。std::vector携带无开销的循环。在基准代码中，原始数组仅受益于优化未初始化数据的异常情况。
我对其进行了测试并发现以下结果： 该vector案例的运行时间大约是原始数组案例的 1.8 倍。但这只是当我没有初始化原始数组时的情况。在时间测量之前添加一个简单的循环以使用0.0原始数组初始化所有条目后，case 花费的时间与 case 一样长vector。
它仔细观察并执行了以下操作：我没有像这样初始化原始数组
for (size_t i{0}; i < SIZE; ++i)
a[i] = 0.0;
但这样做是这样的：
for (size_t i{0}; i < SIZE; ++i)
if (a[i] != 0.0)
{
std::cout << "a was set at position " << i << std::endl;
a[i] = 0.0;
}
（其他数组也相应）。
结果是我在初始化数组时没有得到任何控制台输出，并且它再次与根本没有初始化一样快，比 s 快大约 1.8 vector。
例如，当我使用a该子句初始化“正常”向量和其他两个向量时，我测量了运行时与使用该子句“假初始化”的所有数组的运行时if之间的时间。vectorif
呃……这很奇怪……
现在，我认为 std::vector 几乎没有开销？这里发生了什么事？我想使用漂亮的 STL 对象......
虽然我无法向您解释这种行为，但我可以告诉您，如果您“正常”使用它，实际上并没有真正的开销std::vector。这只是一个非常人为的案例。
编辑：
正如qPCR4vir和 OP Napseis指出的那样，这可能与优化有关。一旦我打开优化，“真正的初始化”情况就会比前面提到的慢 1.8 倍。但如果没有它，速度仍然慢约 1.1 倍。
所以我查看了汇编代码，但我没有看到“for”循环有任何区别......
| 归档时间： |
|
| 查看次数： |
235 次 |
| 最近记录： |