c++ - 无锁多线程比单线程程序慢吗？

Question

我考虑过并行化程序，以便在第一阶段将项目按并行工作人员的数量为模分类到桶中，从而避免在第二阶段发生冲突。并行程序的每个线程使用std::atomic::fetch_add在输出数组中保留一个位置，然后使用std::atomic::compare_exchange_weak更新当前桶头指针。所以它是无锁的。但是，我对多个线程争夺单个原子的性能表示怀疑(我们做的那个fetch_add，因为桶头数等于线程数，因此平均来说没有多少争用)，所以我决定对此进行衡量。这是代码:

#include <atomic>
#include <chrono>
#include <cstdio>
#include <string>
#include <thread>
#include <vector>

std::atomic<int64_t> gCounter(0);
const int64_t gnAtomicIterations = 10 * 1000 * 1000;

void CountingThread() {
  for (int64_t i = 0; i < gnAtomicIterations; i++) {
    gCounter.fetch_add(1, std::memory_order_acq_rel);
  }
}

void BenchmarkAtomic() {
  const uint32_t maxThreads = std::thread::hardware_concurrency();
  std::vector<std::thread> thrs;
  thrs.reserve(maxThreads + 1);

  for (uint32_t nThreads = 1; nThreads <= maxThreads; nThreads++) {
    auto start = std::chrono::high_resolution_clock::now();
    for (uint32_t i = 0; i < nThreads; i++) {
      thrs.emplace_back(CountingThread);
    }
    for (uint32_t i = 0; i < nThreads; i++) {
      thrs[i].join();
    }
    auto elapsed = std::chrono::high_resolution_clock::now() - start;
    double nSec = 1e-6 * std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count();
    printf("%d threads: %.3lf Ops/sec, counter=%lld\n", (int)nThreads, (nThreads * gnAtomicIterations) / nSec,
      (long long)gCounter.load(std::memory_order_acquire));

    thrs.clear();
    gCounter.store(0, std::memory_order_release);
  }
}

int __cdecl main() {
  BenchmarkAtomic();
  return 0;
}

这是输出:

1 threads: 150836387.770 Ops/sec, counter=10000000
2 threads: 91198022.827 Ops/sec, counter=20000000
3 threads: 78989357.501 Ops/sec, counter=30000000
4 threads: 66808858.187 Ops/sec, counter=40000000
5 threads: 68732962.817 Ops/sec, counter=50000000
6 threads: 64296828.452 Ops/sec, counter=60000000
7 threads: 66575046.721 Ops/sec, counter=70000000
8 threads: 64487317.763 Ops/sec, counter=80000000
9 threads: 63598622.030 Ops/sec, counter=90000000
10 threads: 62666457.778 Ops/sec, counter=100000000
11 threads: 62341701.668 Ops/sec, counter=110000000
12 threads: 62043591.828 Ops/sec, counter=120000000
13 threads: 61933752.800 Ops/sec, counter=130000000
14 threads: 62063367.585 Ops/sec, counter=140000000
15 threads: 61994384.135 Ops/sec, counter=150000000
16 threads: 61760299.784 Ops/sec, counter=160000000

CPU 为 8 核 16 线程(Ryzen 1800X @3.9Ghz)。 因此，在使用 4 个线程之前，每秒所有线程的操作总数会急剧下降。然后它缓慢下降并略有波动。

那么这种现象对于其他CPU和编译器来说是不是普遍存在呢？是否有任何解决方法(除了求助于单线程)？

Answer 1

无锁多线程程序并不比单线程程序慢。使它变慢的是数据争用。您提供的示例实际上是一个极具争议的人工程序。在实际程序中，您将在每次访问共享数据之间做很多工作，因此缓存失效等情况会更少。 这CppCon talk Jeff Preshing 比我能更好地解释你的一些问题。

添加:尝试修改 CountingThread 并偶尔添加一个 sleep ，以假装您正忙于其他事情而不是递增原子变量 gCounter。然后继续尝试 if 语句中的值，看看它将如何影响程序的结果。

void CountingThread() {
  for (int64_t i = 0; i < gnAtomicIterations; i++) {
    // take a nap every 10000th iteration to simulate work on something
    // unrelated to access to shared resource
    if (i%10000 == 0) {
        std::chrono::milliseconds timespan(1);
        std::this_thread::sleep_for(timespan);
    }
    gCounter.fetch_add(1, std::memory_order_acq_rel);
  }
}

一般来说，每次调用 gCounter.fetch_add 都意味着在其他核心的缓存中将该数据标记为无效。它迫使他们将数据放入离核心更远的缓存中。这种影响是导致程序性能下降的主要原因。

local  L1 CACHE hit,                              ~4 cycles (   2.1 -  1.2 ns )
local  L2 CACHE hit,                             ~10 cycles (   5.3 -  3.0 ns )
local  L3 CACHE hit, line unshared               ~40 cycles (  21.4 - 12.0 ns )
local  L3 CACHE hit, shared line in another core ~65 cycles (  34.8 - 19.5 ns )
local  L3 CACHE hit, modified in another core    ~75 cycles (  40.2 - 22.5 ns )

remote L3 CACHE (Ref: Fig.1 [Pg. 5])        ~100-300 cycles ( 160.7 - 30.0 ns )

local  DRAM                                                   ~60 ns
remote DRAM                                                  ~100 ns

Above table taken from Approximate cost to access various caches and main memory?

无锁并不意味着您可以在线程之间免费交换数据。无锁意味着你不需要等待其他线程解锁互斥锁来让你读取共享数据。事实上，即使是无锁程序也使用锁定机制来防止数据损坏。

只需遵循简单的规则。尝试尽可能少地访问共享数据，以便从多核编程中获得更多 yield 。