为什么多线程的 for 循环没有单线程的性能好?
Why will for-loop with multithreading not have as great performance as with single-thread?
我认为使用多线程处理简单而繁重的工作(例如矩阵计算)比使用单线程更好,所以我测试了以下代码:
int main()
{
constexpr int N = 100000;
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_real_distribution<double> ini(0.0, 10.0);
// single-thread
{
std::vector<int> vec(N);
for(int i = 0; i < N; ++i)
{
vec[i] = ini(mt);
}
auto start = std::chrono::system_clock::now();
for(int i = 0; i < N; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
auto end = std::chrono::system_clock::now();
auto dur = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
std::cout << "single : " << dur << " ms."<< std::endl;
}
// multi-threading (Th is the number of threads)
for(int Th : {1, 2, 4, 8, 16})
{
std::vector<int> vec(N);
for(int i = 0; i < N; ++i)
{
vec[i] = ini(mt);
}
auto start = std::chrono::system_clock::now();
std::vector<std::future<void>> fut(Th);
for(int t = 0; t < Th; ++t)
{
fut[t] = std::async(std::launch::async, [t, &vec, &N, &Th]{
for(int i = t*N / Th; i < (t + 1)*N / Th; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
});
}
for(int t = 0; t < Th; ++t)
{
fut[t].get();
}
auto end = std::chrono::system_clock::now();
auto dur = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
std::cout << "Th = " << Th << " : " << dur << " ms." << std::endl;
}
return 0;
}
执行环境:
OS : Windows 10 64-bit
Build-system : Visual Studio Community 2015
CPU : Core i5 4210U
在 Debug 模式下构建此程序时,结果如我所料:
single : 146 ms.
Th = 1 : 140 ms.
Th = 2 : 71 ms.
Th = 4 : 64 ms.
Th = 8 : 61 ms.
Th = 16 : 68 ms.
这表示不使用 std::async 的代码与使用单线程的代码具有相同的性能,当使用 4 或 8 线程时我可以获得很好的性能。
然而,当处于 Release 模式时,我得到了不同的结果 (N : 100000 -> 100000000) :
single : 54 ms.
Th = 1 : 443 ms.
Th = 2 : 285 ms.
Th = 4 : 205 ms.
Th = 8 : 206 ms.
Th = 16 : 221 ms.
我想知道这个结果。就后半段代码而言,多线程只是比单线程性能要好。但是最快的是前半码,不用std::async。我知道围绕多线程的优化和开销对性能有很大影响。然而,
- 这个过程只是vector的计算,那么多线程代码可以优化什么,单线程代码可以优化什么?
- 本程序不涉及互斥或原子等,不会发生数据冲突。我认为多线程的开销相对较小。
- CPU 在不使用 std::async 的代码中的利用率低于在多线程代码中的利用率。 CPU的大部分使用效率高吗?
Update :我试图研究矢量化。我启用了 /Qvec-report:1
选项并得到了事实:
//vectorized (when N is large)
for(int i = 0; i < N; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
//not vectorized
auto lambda = [&vec, &N]{
for(int i = 0; i < N; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
};
lambda();
//not vectorized
std::vector<std::future<void>> fut(Th);
for(int t = 0; t < Th; ++t)
{
fut[t] = std::async(std::launch::async, [t, &vec, &N, Th]{
for(int i = t*N / Th; i < (t + 1)*N / Th; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
});
}
和运行时间:
single (with vectorization) : 47 ms.
single (without vectorization) : 70 ms.
可以肯定的是,for-loop 在多线程版本中没有被向量化。但是,由于其他原因,版本需要很长时间。
更新 2:我重写了 lambda 中的 for 循环(类型 A 到类型 B):
//Type A (the previous one)
fut[t] = std::async(std::launch::async, [t, &vec, &N, Th]{
for(int i = t*N / Th; i < (t + 1)*N / Th; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
});
//Type B (the new one)
fut[t] = std::async(std::launch::async, [t, &vec, &N, Th]{
int nb = t * N / Th;
int ne = (t + 1) * N / Th;
for(int i = nb; i < ne; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
});
B 型效果很好。结果:
single (vectorized) : 44 ms.
single (invectorized) : 77 ms.
--
Th = 1 (Type A) : 435 ms.
Th = 2 (Type A) : 278 ms.
Th = 4 (Type A) : 219 ms.
Th = 8 (Type A) : 212 ms.
--
Th = 1 (Type B) : 112 ms.
Th = 2 (Type B) : 74 ms.
Th = 4 (Type B) : 60 ms.
Th = 8 (Type B) : 61 ms.
类型 B 的结果是可以理解的(多线程代码 运行 比单线程向量化代码快,但不如向量化代码快)。另一方面,Type A 似乎等同于 Type B(只是使用临时变量),但它们显示出不同的性能。这两种类型可以考虑生成不同的汇编代码。
更新 3:我可能会发现一个减慢多线程 for 循环的因素。是for
条件下的除法。这是单线程测试:
//ver 1 (ordinary)
fut[t] = std::async(std::launch::async, [&vec, &N]{
for(int i = 0; i < N; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
});
//ver 2 (introducing a futile variable Q)
int Q = 1;
fut[t] = std::async(std::launch::async, [&vec, &N, Q]{
for(int i = 0; i < N / Q; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
});
//ver 3 (using a temporary variable)
int Q = 1;
fut[t] = std::async(std::launch::async, [&vec, &N, Q]{
int end = N / Q;
for(int i = 0; i < end; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
});
//ver 4 (using a raw value)
fut[t] = std::async(std::launch::async, [&vec]{
for(int i = 0; i < 100000000; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
});
和运行宁时间:
ver 1 : 132 ms.
ver 2 : 391 ms.
ver 3 : 47 ms.
ver 4 : 43 ms.
ver 3 & 4 优化得很好,而 ver 1 没有那么多,因为我认为编译器无法捕获 N不变,尽管 N 是 constexpr
。我认为 ver 2 由于同样的原因非常慢。编译器不明白 N 和 Q 不会变化。所以条件 i < N / Q
需要大量的汇编代码,这会减慢 for 循环的速度。
当您 运行 单线程时,您的单线程在缓存中有 vec
,因为您刚刚从 mt 创建它。而且它会通过缓存保持良好的流式传输,因为它是所有缓存级别的唯一用户。
我认为这里没有进行太多矢量化,否则你会得到更短的时间。不过,我可能是错的,因为内存带宽是这里的关键。你看过asm了吗?
任何其他线程都必须获取 ram。在您的情况下,这本身并不是一个大问题,因为它是一个 cpu,所以 L3 是共享的,而且数据集无论如何都大于 L3。
但是,多个线程争夺 L3 是不好的。我认为这是这里的主要因素。
你运行线程太多了。您应该 运行 拥有多少内核就拥有多少线程,以减少上下文切换和缓存乱扔的费用。
当 2 个硬件线程在管道(这里不是这种情况)、BP(这里不是这种情况)和缓存利用率(这里是强情况 -> 参见 #1)中有足够的 "holes" 时,HT 是有益的。
我真的很惊讶 >2 个线程并没有降级更多 --- 现在 cpus 太棒了!
线程启动和术语时间低于预期。如果您想要更多的可预测性,运行 线程不断地使用一些廉价的信号来启动它们并通知它们已经完成。
编辑:特定问题的答案
The process is just calculation of the vector, so what can be optimized not in the multi-thread codes but in the single-thread codes?
这里没有多少代码可以优化....您可以分解长循环以启用循环展开:
C = 16; // try other C values?
for(int i=nb; i<ne; i+=C) {
for(int j=0; j<C; j++)
vec[i+j] = ...; // that's === vec[i] <<= 2;
}
// need to do the remainder....
如果编译器没有,您可以手动矢量化。先看组装。
This program contains nothing about mutex or atomic etc, and data conflict might not occur. I think overheads around multithreading would be relatively small.
没错。除了线程可能会在自己的时间启动。尤其是在 Windows 上,尤其是在有很多人的情况下。
CPU utilization in the codes not using std::async is smaller than in the multi-threading codes. Is it efficient to use the large part of CPU?
您总是希望在更短的时间内使用更多 cpu %。我不确定你在看什么,因为这里没有 IO。
我认为使用多线程处理简单而繁重的工作(例如矩阵计算)比使用单线程更好,所以我测试了以下代码:
int main()
{
constexpr int N = 100000;
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_real_distribution<double> ini(0.0, 10.0);
// single-thread
{
std::vector<int> vec(N);
for(int i = 0; i < N; ++i)
{
vec[i] = ini(mt);
}
auto start = std::chrono::system_clock::now();
for(int i = 0; i < N; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
auto end = std::chrono::system_clock::now();
auto dur = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
std::cout << "single : " << dur << " ms."<< std::endl;
}
// multi-threading (Th is the number of threads)
for(int Th : {1, 2, 4, 8, 16})
{
std::vector<int> vec(N);
for(int i = 0; i < N; ++i)
{
vec[i] = ini(mt);
}
auto start = std::chrono::system_clock::now();
std::vector<std::future<void>> fut(Th);
for(int t = 0; t < Th; ++t)
{
fut[t] = std::async(std::launch::async, [t, &vec, &N, &Th]{
for(int i = t*N / Th; i < (t + 1)*N / Th; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
});
}
for(int t = 0; t < Th; ++t)
{
fut[t].get();
}
auto end = std::chrono::system_clock::now();
auto dur = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
std::cout << "Th = " << Th << " : " << dur << " ms." << std::endl;
}
return 0;
}
执行环境:
OS : Windows 10 64-bit
Build-system : Visual Studio Community 2015
CPU : Core i5 4210U
在 Debug 模式下构建此程序时,结果如我所料:
single : 146 ms.
Th = 1 : 140 ms.
Th = 2 : 71 ms.
Th = 4 : 64 ms.
Th = 8 : 61 ms.
Th = 16 : 68 ms.
这表示不使用 std::async 的代码与使用单线程的代码具有相同的性能,当使用 4 或 8 线程时我可以获得很好的性能。
然而,当处于 Release 模式时,我得到了不同的结果 (N : 100000 -> 100000000) :
single : 54 ms.
Th = 1 : 443 ms.
Th = 2 : 285 ms.
Th = 4 : 205 ms.
Th = 8 : 206 ms.
Th = 16 : 221 ms.
我想知道这个结果。就后半段代码而言,多线程只是比单线程性能要好。但是最快的是前半码,不用std::async。我知道围绕多线程的优化和开销对性能有很大影响。然而,
- 这个过程只是vector的计算,那么多线程代码可以优化什么,单线程代码可以优化什么?
- 本程序不涉及互斥或原子等,不会发生数据冲突。我认为多线程的开销相对较小。
- CPU 在不使用 std::async 的代码中的利用率低于在多线程代码中的利用率。 CPU的大部分使用效率高吗?
Update :我试图研究矢量化。我启用了 /Qvec-report:1
选项并得到了事实:
//vectorized (when N is large)
for(int i = 0; i < N; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
//not vectorized
auto lambda = [&vec, &N]{
for(int i = 0; i < N; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
};
lambda();
//not vectorized
std::vector<std::future<void>> fut(Th);
for(int t = 0; t < Th; ++t)
{
fut[t] = std::async(std::launch::async, [t, &vec, &N, Th]{
for(int i = t*N / Th; i < (t + 1)*N / Th; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
});
}
和运行时间:
single (with vectorization) : 47 ms.
single (without vectorization) : 70 ms.
可以肯定的是,for-loop 在多线程版本中没有被向量化。但是,由于其他原因,版本需要很长时间。
更新 2:我重写了 lambda 中的 for 循环(类型 A 到类型 B):
//Type A (the previous one)
fut[t] = std::async(std::launch::async, [t, &vec, &N, Th]{
for(int i = t*N / Th; i < (t + 1)*N / Th; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
});
//Type B (the new one)
fut[t] = std::async(std::launch::async, [t, &vec, &N, Th]{
int nb = t * N / Th;
int ne = (t + 1) * N / Th;
for(int i = nb; i < ne; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
});
B 型效果很好。结果:
single (vectorized) : 44 ms.
single (invectorized) : 77 ms.
--
Th = 1 (Type A) : 435 ms.
Th = 2 (Type A) : 278 ms.
Th = 4 (Type A) : 219 ms.
Th = 8 (Type A) : 212 ms.
--
Th = 1 (Type B) : 112 ms.
Th = 2 (Type B) : 74 ms.
Th = 4 (Type B) : 60 ms.
Th = 8 (Type B) : 61 ms.
类型 B 的结果是可以理解的(多线程代码 运行 比单线程向量化代码快,但不如向量化代码快)。另一方面,Type A 似乎等同于 Type B(只是使用临时变量),但它们显示出不同的性能。这两种类型可以考虑生成不同的汇编代码。
更新 3:我可能会发现一个减慢多线程 for 循环的因素。是for
条件下的除法。这是单线程测试:
//ver 1 (ordinary)
fut[t] = std::async(std::launch::async, [&vec, &N]{
for(int i = 0; i < N; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
});
//ver 2 (introducing a futile variable Q)
int Q = 1;
fut[t] = std::async(std::launch::async, [&vec, &N, Q]{
for(int i = 0; i < N / Q; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
});
//ver 3 (using a temporary variable)
int Q = 1;
fut[t] = std::async(std::launch::async, [&vec, &N, Q]{
int end = N / Q;
for(int i = 0; i < end; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
});
//ver 4 (using a raw value)
fut[t] = std::async(std::launch::async, [&vec]{
for(int i = 0; i < 100000000; ++i)
{
vec[i] = 2 * vec[i] + 3 * vec[i] - vec[i];
}
});
和运行宁时间:
ver 1 : 132 ms.
ver 2 : 391 ms.
ver 3 : 47 ms.
ver 4 : 43 ms.
ver 3 & 4 优化得很好,而 ver 1 没有那么多,因为我认为编译器无法捕获 N不变,尽管 N 是 constexpr
。我认为 ver 2 由于同样的原因非常慢。编译器不明白 N 和 Q 不会变化。所以条件 i < N / Q
需要大量的汇编代码,这会减慢 for 循环的速度。
当您 运行 单线程时,您的单线程在缓存中有 vec
,因为您刚刚从 mt 创建它。而且它会通过缓存保持良好的流式传输,因为它是所有缓存级别的唯一用户。
我认为这里没有进行太多矢量化,否则你会得到更短的时间。不过,我可能是错的,因为内存带宽是这里的关键。你看过asm了吗?
任何其他线程都必须获取 ram。在您的情况下,这本身并不是一个大问题,因为它是一个 cpu,所以 L3 是共享的,而且数据集无论如何都大于 L3。
但是,多个线程争夺 L3 是不好的。我认为这是这里的主要因素。你运行线程太多了。您应该 运行 拥有多少内核就拥有多少线程,以减少上下文切换和缓存乱扔的费用。
当 2 个硬件线程在管道(这里不是这种情况)、BP(这里不是这种情况)和缓存利用率(这里是强情况 -> 参见 #1)中有足够的 "holes" 时,HT 是有益的。
我真的很惊讶 >2 个线程并没有降级更多 --- 现在 cpus 太棒了!线程启动和术语时间低于预期。如果您想要更多的可预测性,运行 线程不断地使用一些廉价的信号来启动它们并通知它们已经完成。
编辑:特定问题的答案
The process is just calculation of the vector, so what can be optimized not in the multi-thread codes but in the single-thread codes?
这里没有多少代码可以优化....您可以分解长循环以启用循环展开:
C = 16; // try other C values?
for(int i=nb; i<ne; i+=C) {
for(int j=0; j<C; j++)
vec[i+j] = ...; // that's === vec[i] <<= 2;
}
// need to do the remainder....
如果编译器没有,您可以手动矢量化。先看组装。
This program contains nothing about mutex or atomic etc, and data conflict might not occur. I think overheads around multithreading would be relatively small.
没错。除了线程可能会在自己的时间启动。尤其是在 Windows 上,尤其是在有很多人的情况下。
CPU utilization in the codes not using std::async is smaller than in the multi-threading codes. Is it efficient to use the large part of CPU?
您总是希望在更短的时间内使用更多 cpu %。我不确定你在看什么,因为这里没有 IO。