c++ - 多线程时如何避免堆栈空间不足？

Question

我已经用 C++ 实现了一个有效的多线程合并排序，但我遇到了困难。

在我的实现中，我递归地将一个输入 vector 分成两部分，然后对这两部分进行线程化处理:

void MergeSort(vector<int> *in)
{
if(in->size() < 2)
    return;

vector<int>::iterator ite = in->begin();
vector<int> left = vector<int> (ite, ite + in->size()/2);
vector<int> right = vector<int> (ite + in->size()/2, in->end() );

//current thread spawns 2 threads HERE
thread t1 = thread(MergeSort, &left);
thread t2 = thread(MergeSort, &right);

t1.join();
t2.join();

vector<int> ret;
ret.reserve(in->size() );

ret = MergeSortMerge(left, right);

in->clear();
in->insert(in->begin(), ret.begin(), ret.end() );

return;
}

代码看起来很漂亮，但它是我写过的最恶毒的代码之一。尝试对超过 1000 个 int 值的数组进行排序会导致产生如此多的线程，以至于我用完了堆栈空间，并且我的计算机出现蓝屏死机 :( 始终如一。

我很清楚这段代码产生这么多线程的原因，这不是很好，但从技术上(如果不是理论上)，这不是一个正确的实现吗？

基于一些谷歌搜索，我似乎发现了对线程池的需求。使用线程池是否可以解决我遇到的根本问题，即我试图生成太多线程这一事实？如果是这样，您对图书馆有什么建议吗？

感谢您的建议和帮助!

Answer 1

正如 zdan 所解释的，您应该限制线程的数量。确定限制是什么需要考虑两件事，

1. CPU 核心数。在 C++11 中，您可以使用 std::thread::hardware_concurrency() 来确定硬件内核。但是，此函数可能会返回 0，这意味着程序不知道有多少个内核，在这种情况下，您可以假设此值为 2 或 4。

2. 受要处理的数据数量限制。您可以将要处理的数据划分为每个线程 1 个数据，但仅 1 个数据的成本太高，并且不符合成本效益。比如你大概可以说，当数据个数小于50的时候，你就不想再划分了。因此，您可以根据 total_data_number/50 + 1 之类的内容确定所需的最大线程数。

然后，您选择情况 1 和情况 2 之间的最小数量来确定限制。

在您的情况下，因为您是通过递归生成线程，所以您可以尝试以类似的方式确定递归深度。