C++ 原子素数筛中缺少小素数

Question

我尝试使用 C++ 原子开发并发素筛实现。但是，当 core_count 增加时，输出中会丢失越来越多的小素数。

我的猜测是生产者线程在被消费者读取之前会覆盖彼此的结果。即使构造应该通过使用幻数 0 来表明它已准备好接受下一个素数来防止它。在这种情况下，compare_exchange_weak 似乎不是真正的原子。

我尝试过的事情：

将 compare_exchange_weak 替换为 compare_exchange_strong
将 memory_order 更改为其他任何内容。
交换 'crossing-out' 和写入。

我已经用 Microsoft Visual Studio 2019、Clang 12.0.1 和 GCC 11.1.0 对其进行了测试，但无济于事。

欢迎就此提出任何想法，包括我可能错过的一些最佳实践。

#include <algorithm>
#include <atomic>
#include <future>
#include <iostream>
#include <iterator>
#include <thread>
#include <vector>

int main() {
  using namespace std;

  constexpr memory_order order = memory_order_relaxed;
  atomic<int> output{0};
  vector<atomic_bool> sieve(10000);
  for (auto& each : sieve) atomic_init(&each, false);
  atomic<unsigned> finished_worker_count{0};

  auto const worker = [&output, &sieve, &finished_worker_count]() {
    for (auto current = next(sieve.begin(), 2); current != sieve.end();) {
      current = find_if(current, sieve.end(), [](atomic_bool& value) {
        bool untrue = false;
        return value.compare_exchange_strong(untrue, true, order);
      });
      if (current == sieve.end()) break;
      int const claimed = static_cast<int>(distance(sieve.begin(), current));
      int zero = 0;
      while (!output.compare_exchange_weak(zero, claimed, order))
        ;
      for (auto product = 2 * claimed; product < static_cast<int>(sieve.size());
           product += claimed)
        sieve[product].store(true, order);
    }
    finished_worker_count.fetch_add(1, order);
  };

  const auto core_count = thread::hardware_concurrency();
  vector<future<void>> futures;
  futures.reserve(core_count);
  generate_n(back_inserter(futures), core_count,
             [&worker]() { return async(worker); });
  vector<int> result;
  while (finished_worker_count < core_count) {
    auto current = output.exchange(0, order);
    if (current > 0) result.push_back(current);
  }
  sort(result.begin(), result.end());
  for (auto each : result) cout << each << " ";
  cout << '\n';
  return 0;
}

Answer 1

如果无法进行更新，

compare_exchange_weak 将更新（更改）“预期”值（局部变量 zero）。如果主线程不能快速处理第一个素数，这将允许用另一个素数覆盖一个素数。

您需要在重新检查之前将 zero 重置为零：

while (!output.compare_exchange_weak(zero, claimed, order))
   zero = 0;

C++ 原子素数筛中缺少小素数

Missing small primes in C++ atomic prime sieve

c++

atomic