在c++中使用OpenMP和Timsort算法

Question

我一直在寻找一种方法来实现多线程的c++ Timsort(在Github上找到的实现)，我已经尝试在这个过程中使用。我确信我使用了正确的编译器标志，但是每当我尝试使用Timsort时，就像我下面所做的那样:

#pragma omp parallel shared(DataVector)
{
     gfx::timsort(DataVector.begin(), DataVector.end(), comp_1);
}

注意:排序的数据是一个包含单个单词字符串的向量，我使用自己的比较器。

它似乎在不使用OpenMP的情况下运行所需的时间相同。使用适当的包括计时等，我计时的值平均在0.01秒内，在我的排序中徘徊在1.24秒左右。

是否有理由线程似乎不与我的排序方法工作，或者它是一个问题与我实现OpenMP的方式?

注意:我一直在使用__gnu_parallel::sort以及更好的结果，但我希望在实践中自己比较这些方法。

Answer 1

omp parallel需要看到它将要并行化的循环。按照您声明的方式，omp将并行化一段代码，这不会带来任何好处。

检查你的文档关于omp parallel的使用。

要执行for循环，您需要使用omp parallel for和下面的for语句。你现在拥有它的方式，它将在你拥有的每个核心上运行你的时间排序。

Answer 2

认为openMP不够聪明…如果你想对gfx::timsort做一个平行，你不能从外面做…您应该将此代码添加到函数gfx::timsort

中

#pragma omp parallel for
for(int i=0;i<num;i++)
...

此外，shared是一个关键字，指示变量您不希望它被并行编辑