使用OMP parallel与critical实现的计数函数是否与串行版本功能一致？

结论 #

分两种情况判断：

1. 满足以下两个前提时，结果和串行版本完全一致：
   • 代码笔误已修正：函数参数传入的n和循环条件里的N是同一个变量
   • 调用的randomVal()是线程安全的，且多线程场景下生成的N个随机值的集合，和串行场景下循环N次生成的随机值集合完全相同
2. 若randomVal()不是线程安全的（绝大多数语言/系统默认的随机数生成器都属于这类），则结果和串行版本不一致，甚至会出现未定义行为。

具体原因分析 #

• 你添加的#pragma omp critical确实保证了对共享数组list1的写入操作是互斥执行的，不会出现多个线程同时修改同一块内存导致的计数丢失，只要输入的随机值集合和串行版本相同，最终计数结果就会完全一致。
• 但默认的随机数生成器通常内部持有全局状态，多线程同时调用时会出现状态竞争，不仅会导致生成的随机序列和串行版本不同，还可能触发未定义行为，最终计数自然和串行版本不一样。

额外优化建议 #

你当前的实现因为critical的调用频率极高，锁的开销会非常大，大概率性能比串行版本还差。更优的实现方式是用OpenMP数组归约，不用加锁也能保证线程安全：

std::vector<int> randValueCounter3(int n, int listSize) {
   std::vector<int> list1(listSize, 0);
   // OpenMP 4.5+ 版本支持直接对数组段做归约
   #pragma omp parallel for reduction(+:list1[:listSize])
   for (int i = 0; i < n; ++i) {
     int rand = randomVal();
     // 注意原代码边界判断有问题，rand等于listSize时会访问越界，数组下标最大为listSize-1
     if(rand >=0 && rand < listSize){
        ++list1[rand];
     }
   }
   return list1;
}

内容的提问来源于stack exchange，提问作者Polynomial length of study