C++ 上的并行并不像 C# 那样快
Parallel on C++ isn't fast like C#
我在 C#
上有这样的代码
private static Random random = new Random();
public static string RandomString(int length)
{
const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
return new string(Enumerable.Repeat(chars, length)
.Select(s => s[random.Next(s.Length)]).ToArray());
}
Task.Factory.StartNew(() => {
System.Threading.Tasks.Parallel.For(0L, 10000000, new ParallelOptions { MaxDegreeOfParallelism = Environment.ProcessorCount * 10 }, n =>
{
Console.WirteLine(RandomString(12));
});
}
向其添加并行方法，它设法 运行 在不到 8 秒的时间内生成 1000 万个随机字符串并使用所有 CPU 能力
我尝试在 C++
中重做
string NonRepeatChar(int max_len)
{
std::string valid_chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(valid_chars.begin(), valid_chars.end(), g);
std::string rand_str(valid_chars.begin(), valid_chars.begin() + max_len);
return rand_str;
}
将代码应用于一些推荐的C++并行方法
void multiply()
{
for (size_t i = 0; i < 10; i++)
{
for (size_t j = 0; j < 10; j++)
{
for (int k = 0; k < 10; k++)
{
printf("%s\n",NonRepeatChar(10));
}
}
}
}
class Foo {
public:
Foo() : counter_(0) {}
std::pair<string, std::future<void>> a_function(std::future<void>& f) {
// Ensure that the background task from the previous iteration
// has completed
f.wait();
// Set the task for the next iteration
std::future<void> fut = std::async(std::launch::async, &Foo::background_task, this);
// Do some work
string value = NonRepeatChar(12);
// Return the result and the future for the next iteration
return std::make_pair(value.c_str(), std::move(fut));
}
void background_task() {
++counter_;
}
private:
std::atomic<int> counter_;
};
记录运行它
的时间
int main()
{
clock_t tStart = clock();
std::future<void> bleak = std::async(std::launch::deferred, []() {});
Foo foo;
for (size_t i = 0; i < 10000; ++i) {
// Call the function
std::pair<string, std::future<void>> result = foo.a_function(bleak);
bleak = std::move(result.second);
std::cout << result.first << "\n";
}
printf("Time taken: %.2fs\n", (double)(clock() - tStart) / CLOCKS_PER_SEC);
return 0;
}
这是我的结果：
10.98s//normal loop
8.76s//multiply
8.88s//Foo
显然代码与原始循环相比没有任何区别，仅生成 10000 行，而且它甚至没有像 C# 那样使用所有 CPU 的能力.并行方法有问题吗？我该如何优化它？
您的 C++ 代码与您的 C# 代码完全不同。
在 C# 端,
您正在使用来自 System.Threading.Tasks 命名空间的 Parallel.For。这是一个高级构造，允许循环迭代到 运行 并行，而不必以低级方式控制线程，因为任务是自动为您创建的，并以某种方式调度到您的处理器内核这对您的系统是最佳的。
对于您的特定代码，Parallel.For 配置为允许一次最多安排 Environment.ProcessorCount * 10 个工作线程。虽然不能保证（库的调度程序将拥有最终决定权），但这应该确保您的处理核心最佳地用于提交的工作负载，因为有足够的任务占用所有核心，并且有足够大的工作队列来确保核心没有因为没有提前安排的工作而挨饿。
在 C++ 方面、
您正在使用 async 和 future，它们是较低级别的构造，允许您 运行 后台任务，但您通过强制同步人为地限制了并行级别在每次迭代中：
// Ensure that the background task from the previous iteration
// has completed
f.wait();
在 C++ 中实现类似于 C# 代码的行为的最简单（但不可移植）的方法是使用 Microsoft 的 Parallel Patterns Library. This provides a functionality that is very similar to what System.Threading.Tasks.Parallel.For provides on the C# side, which is concurrency::parallel_for。
这是一个简单的单线程示例，说明可以使用混合 C/C++
方法。游戏开发者使用的方法是 "formal" C++ 代码的混合体
而且看起来不像 python。当然，像 Marmite 一样，您喜欢或讨厌它，但无论如何，结果不言而喻。
如果这比您想的要了解更多，我深表歉意。
这个特定示例在我的旧 AMD 机器上的单个线程上以 3.682 秒生成 10M 字符串。
您可以启动少量异步工作者 (< std::thread::hardware_concurrency()) 以将工作分成大约一百万个周期的块。然后，您的 I/O 会出现同步问题，因此请小心并避免互斥！
要更快，您需要手动展开循环，使用 SIMD 算法等。例如，这种情况适用于 SIMD 置换向量。
#include <stdint.h>
#include <stdio.h>
// This is typical of the random number generators used in professional games.
// It is less "correct" than mersenne twisters, for example, but much faster.
inline uint32_t fast_rand(int32_t &seed, uint32_t limit) {
// Prevent infinite loops.
//if (limit == 0) return 0;
// Make a mask that has all 1s in the bottom few bits.
// This reduces the number of iterations of the loop to ~1
int leading_zeros = __builtin_clz(limit);
int mask = 0xffffffff >> leading_zeros;
// Loop until our result is in range using rotate and xor.
do {
seed = (seed << 1) ^ ((seed >> 31) & 0xa53a9be9);
} while ((seed & mask) >= limit);
return seed & mask;
}
int main() {
// I'm using two seeds to prevent coupling.
// On their own, their quantiles are pretty flat, but
// in this example they couple, causing conditioning in the results.
int32_t length_seed = (int32_t)0x95abcfad;
int32_t swap_seed = (int32_t)0xba7235fab;
for (int i = 0; i != 10000000; ++i) {
// Note we don't use a std::string. These are very slow.
char chars[] =
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
auto num_chars = sizeof(chars) - 1;
auto length = fast_rand(length_seed, num_chars-1) + 1;
// Trim the string to the right length.
chars[length] = 0;
// Shuffle the characters.
for (int j = 0; j != length; ++j) {
int swapper = j + fast_rand(swap_seed, length - j);
auto tmp = chars[j];
chars[j] = chars[swapper];
chars[swapper] = tmp;
}
// Print with puts (not iostreams).
puts(chars);
}
}
对于 "hot loop" 这样的示例，您应该在 Godbolt 或类似软件上检查结果。
clang with -O3 -mlzcnt 给出了以下内部循环。
.LBB0_4: # Parent Loop BB0_1 Depth=1
mov rsi, rax
sub rsi, rdx
lzcnt ecx, esi
mov edi, -1
shr edi, cl
.LBB0_5: # Parent Loop BB0_1 Depth=1
lea ecx, [rbx + rbx]
sar ebx, 31
and ebx, -1522885655
xor ebx, ecx
mov ecx, ebx
and ecx, edi
cmp rsi, rcx
jbe .LBB0_5
add ecx, edx
mov sil, byte ptr [rsp + rdx]
movsxd rdi, ecx
mov cl, byte ptr [rsp + rdi]
mov byte ptr [rsp + rdx], cl
mov byte ptr [rsp + rdi], sil
add rdx, 1
cmp rdx, rax
jne .LBB0_4
我在 C#
上有这样的代码private static Random random = new Random();
public static string RandomString(int length)
{
const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
return new string(Enumerable.Repeat(chars, length)
.Select(s => s[random.Next(s.Length)]).ToArray());
}
Task.Factory.StartNew(() => {
System.Threading.Tasks.Parallel.For(0L, 10000000, new ParallelOptions { MaxDegreeOfParallelism = Environment.ProcessorCount * 10 }, n =>
{
Console.WirteLine(RandomString(12));
});
}
向其添加并行方法，它设法 运行 在不到 8 秒的时间内生成 1000 万个随机字符串并使用所有 CPU 能力
我尝试在 C++
中重做string NonRepeatChar(int max_len)
{
std::string valid_chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(valid_chars.begin(), valid_chars.end(), g);
std::string rand_str(valid_chars.begin(), valid_chars.begin() + max_len);
return rand_str;
}
将代码应用于一些推荐的C++并行方法
void multiply()
{
for (size_t i = 0; i < 10; i++)
{
for (size_t j = 0; j < 10; j++)
{
for (int k = 0; k < 10; k++)
{
printf("%s\n",NonRepeatChar(10));
}
}
}
}
class Foo {
public:
Foo() : counter_(0) {}
std::pair<string, std::future<void>> a_function(std::future<void>& f) {
// Ensure that the background task from the previous iteration
// has completed
f.wait();
// Set the task for the next iteration
std::future<void> fut = std::async(std::launch::async, &Foo::background_task, this);
// Do some work
string value = NonRepeatChar(12);
// Return the result and the future for the next iteration
return std::make_pair(value.c_str(), std::move(fut));
}
void background_task() {
++counter_;
}
private:
std::atomic<int> counter_;
};
记录运行它
的时间int main()
{
clock_t tStart = clock();
std::future<void> bleak = std::async(std::launch::deferred, []() {});
Foo foo;
for (size_t i = 0; i < 10000; ++i) {
// Call the function
std::pair<string, std::future<void>> result = foo.a_function(bleak);
bleak = std::move(result.second);
std::cout << result.first << "\n";
}
printf("Time taken: %.2fs\n", (double)(clock() - tStart) / CLOCKS_PER_SEC);
return 0;
}
这是我的结果：
10.98s//normal loop
8.76s//multiply
8.88s//Foo
显然代码与原始循环相比没有任何区别，仅生成 10000 行，而且它甚至没有像 C# 那样使用所有 CPU 的能力.并行方法有问题吗？我该如何优化它？
您的 C++ 代码与您的 C# 代码完全不同。
在 C# 端,
您正在使用来自 System.Threading.Tasks 命名空间的 Parallel.For。这是一个高级构造，允许循环迭代到 运行 并行，而不必以低级方式控制线程，因为任务是自动为您创建的，并以某种方式调度到您的处理器内核这对您的系统是最佳的。
对于您的特定代码，Parallel.For 配置为允许一次最多安排 Environment.ProcessorCount * 10 个工作线程。虽然不能保证（库的调度程序将拥有最终决定权），但这应该确保您的处理核心最佳地用于提交的工作负载，因为有足够的任务占用所有核心，并且有足够大的工作队列来确保核心没有因为没有提前安排的工作而挨饿。
在 C++ 方面、
您正在使用 async 和 future，它们是较低级别的构造，允许您 运行 后台任务，但您通过强制同步人为地限制了并行级别在每次迭代中：
// Ensure that the background task from the previous iteration
// has completed
f.wait();
在 C++ 中实现类似于 C# 代码的行为的最简单（但不可移植）的方法是使用 Microsoft 的 Parallel Patterns Library. This provides a functionality that is very similar to what System.Threading.Tasks.Parallel.For provides on the C# side, which is concurrency::parallel_for。
这是一个简单的单线程示例，说明可以使用混合 C/C++ 方法。游戏开发者使用的方法是 "formal" C++ 代码的混合体 而且看起来不像 python。当然，像 Marmite 一样，您喜欢或讨厌它，但无论如何，结果不言而喻。
如果这比您想的要了解更多，我深表歉意。
这个特定示例在我的旧 AMD 机器上的单个线程上以 3.682 秒生成 10M 字符串。 您可以启动少量异步工作者 (< std::thread::hardware_concurrency()) 以将工作分成大约一百万个周期的块。然后，您的 I/O 会出现同步问题，因此请小心并避免互斥！
要更快，您需要手动展开循环，使用 SIMD 算法等。例如，这种情况适用于 SIMD 置换向量。
#include <stdint.h>
#include <stdio.h>
// This is typical of the random number generators used in professional games.
// It is less "correct" than mersenne twisters, for example, but much faster.
inline uint32_t fast_rand(int32_t &seed, uint32_t limit) {
// Prevent infinite loops.
//if (limit == 0) return 0;
// Make a mask that has all 1s in the bottom few bits.
// This reduces the number of iterations of the loop to ~1
int leading_zeros = __builtin_clz(limit);
int mask = 0xffffffff >> leading_zeros;
// Loop until our result is in range using rotate and xor.
do {
seed = (seed << 1) ^ ((seed >> 31) & 0xa53a9be9);
} while ((seed & mask) >= limit);
return seed & mask;
}
int main() {
// I'm using two seeds to prevent coupling.
// On their own, their quantiles are pretty flat, but
// in this example they couple, causing conditioning in the results.
int32_t length_seed = (int32_t)0x95abcfad;
int32_t swap_seed = (int32_t)0xba7235fab;
for (int i = 0; i != 10000000; ++i) {
// Note we don't use a std::string. These are very slow.
char chars[] =
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
auto num_chars = sizeof(chars) - 1;
auto length = fast_rand(length_seed, num_chars-1) + 1;
// Trim the string to the right length.
chars[length] = 0;
// Shuffle the characters.
for (int j = 0; j != length; ++j) {
int swapper = j + fast_rand(swap_seed, length - j);
auto tmp = chars[j];
chars[j] = chars[swapper];
chars[swapper] = tmp;
}
// Print with puts (not iostreams).
puts(chars);
}
}
对于 "hot loop" 这样的示例，您应该在 Godbolt 或类似软件上检查结果。
clang with -O3 -mlzcnt 给出了以下内部循环。
.LBB0_4: # Parent Loop BB0_1 Depth=1
mov rsi, rax
sub rsi, rdx
lzcnt ecx, esi
mov edi, -1
shr edi, cl
.LBB0_5: # Parent Loop BB0_1 Depth=1
lea ecx, [rbx + rbx]
sar ebx, 31
and ebx, -1522885655
xor ebx, ecx
mov ecx, ebx
and ecx, edi
cmp rsi, rcx
jbe .LBB0_5
add ecx, edx
mov sil, byte ptr [rsp + rdx]
movsxd rdi, ecx
mov cl, byte ptr [rsp + rdi]
mov byte ptr [rsp + rdx], cl
mov byte ptr [rsp + rdi], sil
add rdx, 1
cmp rdx, rax
jne .LBB0_4