如何用多进程/线程加速C++程序？特定计算场景优化问询

我有如下func函数：

int func(int n){
    counter = 0;
    for (int i = 0; i < n; i++){
        if(check(i)){
            counter++;
        }
    }
}

其中check是某一函数。我需要在4000000 < n < 4100000范围内，找出所有使func(n)恰好等于1000000的n值。目前单个n的检查耗时约3秒，检查100000个n耗时过长。我的计算机有6核，认为多进程可大幅提速，但我缺乏多进程经验，C++水平有限，同时求相关优质指南。

编辑补充：check函数本质是检查三角平面中点(0,0)与(i, n-i)之间的距离。检查顺序无关，这是IBM某谜题的解决方案，其中func(n)用于统计n到n+1之间的距离半径数量。我知道嵌套while循环看似会造成延迟，但确定时间复杂度约为O(n)。

补充的func实现代码：

typedef long long ll;
ll rad2(ll horizontal, ll vertical){
    return horizontal * horizontal + vertical * vertical + horizontal * vertical;
}
int func(ll m){
    ll horizontal = m + 1;
    ll vertical = 1;
    ska::flat_hash_set<ll> rads;
    while (vertical < (m + 1) && horizontal >= 0){
        while (m * m < rad2(horizontal, vertical)){
            if (rad2(horizontal, vertical) < (m + 1) * (m + 1)) {
                rads.insert(rad2(horizontal, vertical));
            }
            horizontal--;
        }
        vertical++;
    }
    return rads.size();
}

一、先优化单线程性能 #

在启动多进程/线程前，先优化单线程代码的效率，能大幅减少整体耗时：

• 避免重复计算：rad2在循环内被调用两次，可将计算结果存入临时变量，减少重复运算：

  ll current_rad2 = rad2(horizontal, vertical);
  while (m * m < current_rad2){
      if (current_rad2 < (m + 1) * (m + 1)) {
          rads.insert(current_rad2);
      }
      horizontal--;
      if (horizontal < 0) break;
      current_rad2 = rad2(horizontal, vertical);
  }
  

• 预计算固定值：m*m和(m+1)*(m+1)在func调用期间是固定值，提前计算并存储，避免循环内重复计算：

  ll m_sq = m * m;
  ll m1_sq = (m + 1) * (m + 1);
  

• 哈希集合预分配空间：因为目标结果是1000000，提前给rads预留足够空间，减少哈希表扩容开销：

  rads.reserve(1000000);
  

二、C++多线程实现（适配6核） #

推荐用std::thread实现多线程（跨平台、易上手），核心思路是将目标区间拆分为6份，每个线程负责一份区间的计算，最后汇总结果。

完整示例代码 #

#include <iostream>
#include <vector>
#include <thread>
#include <mutex>
#include <ska/flat_hash_set.hpp>

typedef long long ll;

ll rad2(ll horizontal, ll vertical) {
    return horizontal * horizontal + vertical * vertical + horizontal * vertical;
}

int func(ll m) {
    ll m_sq = m * m;
    ll m1_sq = (m + 1) * (m + 1);
    ll horizontal = m + 1;
    ll vertical = 1;
    ska::flat_hash_set<ll> rads;
    rads.reserve(1000000); // 预分配空间

    while (vertical < (m + 1) && horizontal >= 0) {
        ll current_rad2 = rad2(horizontal, vertical);
        while (m_sq < current_rad2) {
            if (current_rad2 < m1_sq) {
                rads.insert(current_rad2);
            }
            horizontal--;
            if (horizontal < 0) break;
            current_rad2 = rad2(horizontal, vertical);
        }
        vertical++;
    }
    return rads.size();
}

// 存储结果的全局向量，用互斥锁保证线程安全
std::vector<ll> valid_ns;
std::mutex result_mutex;

// 线程任务：检查[start, end)区间内的n值
void process_range(ll start, ll end) {
    for (ll n = start; n < end; ++n) {
        int count = func(n);
        if (count == 1000000) {
            std::lock_guard<std::mutex> lock(result_mutex);
            valid_ns.push_back(n);
        }
    }
}

int main() {
    const ll lower_bound = 4000001;
    const ll upper_bound = 4100000;
    const int thread_count = 6; // 对应6核
    ll total_range = upper_bound - lower_bound;
    ll range_per_thread = total_range / thread_count;

    std::vector<std::thread> threads;

    // 创建线程分配任务
    for (int i = 0; i < thread_count; ++i) {
        ll start = lower_bound + i * range_per_thread;
        // 最后一个线程处理剩余所有区间
        ll end = (i == thread_count - 1) ? upper_bound : start + range_per_thread;
        threads.emplace_back(process_range, start, end);
    }

    // 等待所有线程完成
    for (auto& t : threads) {
        t.join();
    }

    // 输出结果
    std::cout << "符合条件的n值：" << std::endl;
    for (ll n : valid_ns) {
        std::cout << n << std::endl;
    }

    return 0;
}

编译与运行注意事项 #

• 编译时需添加线程支持参数，GCC/Clang使用-pthread：

  g++ -std=c++17 -pthread your_code.cpp -o find_valid_n
  

• 内存占用：每个线程会创建一个哈希集合，若单个集合占用约500MB，6个线程共需约3GB内存，内存不足时可改为计算一个输出一个，无需存储到全局向量。
• 异常处理：可在process_range函数中添加try-catch块，避免单个线程崩溃导致整个程序终止。

三、C++并发编程学习资源 #

• 权威文档：CppReference的C++并发专题，涵盖std::thread、std::mutex等所有并发API的详细说明与示例。
• 经典书籍：
  • 《C并发编程实战》：系统讲解C多线程编程的基础、进阶技巧与最佳实践。
  • 《Effective Modern C++》：包含并发编程相关的条款，讲解现代C++并发的正确用法。
• 在线教程：各大编程平台的C++并发入门教程，比如菜鸟教程、CppGuide的并发章节，适合快速上手。

内容的提问来源于stack exchange，提问作者PotatoBrain