Performance Bottleneck from Hidden Atomic Operations

A benchmark of multi-threaded C++ programs shows that copying the same std::shared_ptr once per iteration forces every thread to contend on a single cache line, because each copy increments and decrements the shared control block's atomic reference count. The comparison program, which instead uses a reference to an immutable object kept alive outside the timed region, performs the same lightweight work without that contention, so throughput scales with thread count where the shared_ptr version does not. The benchmark is built with g++ -O3 -DNDEBUG -std=c++17 -pthread and run with --max-threads 16 --iterations 20000000.

Performance Bottleneck from Hidden Atomic Operations Atomic operations are very useful for ensuring correct behavior in concurrent programs, while sacrificing much less performance compared to traditional locking mechanisms. However, for high performance C, C++, and CUDA concurrent programs, experienced developers are aware that even atomic operations can become a performance bottleneck, and they will try to minimize their usage whenever possible. However, some atomic operations are hidden behind seemingly innocuous constructs, such as copying a shared pointer, which can lead to unexpected performance degradation. In this blog post, we will explore a common performance bottleneck caused by hidden atomic operations, specifically focusing on the case of copying shared pointers in multi-threaded C++ programs. We will demonstrate how seemingly harmless operations can introduce contention and degrade performance, and discuss strategies to mitigate these issues. In the following code, we will set up a benchmark to measure the throughput scaling with the number of threads. In one implementation, each thread will repeatedly copy the same shared pointer followed by some extremely lightweight work on the data it points to. In the other implementation, each thread will use a reference to an immutable object followed by the same extremely lightweight work on the referenced object. These two implementations look similar and interchangable at first glance. In practice, seeing the first implementation is also common. If there is no performance difference between using shared pointers and using references to immutable objects, the throughput should scale with the number of threads and both implementations should exhibit similar performance scaling. | 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298 | include <algorithm include <atomic include <chrono include <condition variable include <cstddef include <cstdint include <cstdlib include <exception include <iomanip include <iostream include <memory include <mutex include <string include <thread include <vector // Build and run in a C++ development container:// g++ -O3 -DNDEBUG -std=c++17 -pthread hidden multi threaded atomics.cpp// -o hidden multi threaded atomics// ./hidden multi threaded atomics --max-threads 16 --iterations 20000000//// The shared ptr benchmark deliberately copies the same shared ptr once per// iteration. Each copy increments and decrements its shared control block's// atomic reference count, so threads contend on one cache line. The borrowed// benchmark keeps the owner alive outside the timed region and uses a reference// to the same immutable object instead.namespace{struct Payload{ // The immutable data object managed by owner. Its volatile read prevents // the compiler from removing the per-iteration work; it is not the // contended atomic state. volatile std::uint64 t value{0x9e3779b97f4a7c15ULL};};struct Options{ std::size t max threads{std::min<std::size t std::max 1U, std::thread::hardware concurrency , 32 }; std::size t iterations{5'000'000};};struct Measurement{ double seconds; std::uint64 t checksum;};class StartGate{public: explicit StartGate std::size t participants : participants {participants} { } void wait { std::unique lock<std::mutex lock{mutex }; ++arrived ; if arrived == participants { ready .notify one ; } start .wait lock, this { return started ; } ; } void start when ready { std::unique lock<std::mutex lock{mutex }; ready .wait lock, this { return arrived == participants ; } ; started = true; start .notify all ; }private: std::size t const participants ; std::size t arrived {0}; bool started {false}; std::mutex mutex ; std::condition variable ready ; std::condition variable start ;};std::uint64 t consume Payload const& payload, std::size t iteration { return payload.value + iteration 0xd6e8feb86659fd93ULL;}Measurement run shared ptr copies std::shared ptr<Payload const const& owner, std::size t thread count, std::size t iterations { StartGate gate{thread count}; std::vector<std::uint64 t checksums thread count ; std::vector<std::thread workers{}; workers.reserve thread count ; for std::size t thread{0}; thread < thread count; ++thread { workers.emplace back &, thread { gate.wait ; std::uint64 t checksum{0}; for std::size t iteration{0}; iteration < iterations; ++iteration { // All workers copy the same owner. Copy construction and // destruction atomically update one shared control block. std::shared ptr<Payload const const copy{owner}; checksum ^= consume copy, iteration ; } checksums thread = checksum; } ; } auto const begin{std::chrono::steady clock::now }; gate.start when ready ; for auto& worker : workers { worker.join ; } auto const end{std::chrono::steady clock::now }; std::uint64 t checksum{0}; for std::uint64 t const value : checksums { checksum ^= value; } return {std::chrono::duration<double end - begin .count , checksum};}Measurement run borrowed reference std::shared ptr<Payload const const& owner, std::size t thread count, std::size t iterations { StartGate gate{thread count}; std::vector<std::uint64 t checksums thread count ; std::vector<std::thread workers{}; workers.reserve thread count ; for std::size t thread{0}; thread < thread count; ++thread { workers.emplace back &, thread { gate.wait ; std::uint64 t checksum{0}; for std::size t iteration{0}; iteration < iterations; ++iteration { // This is a non-owning borrow. Unlike copying owner, it // does not change the shared control block's refcount. Payload const& payload{ owner}; checksum ^= consume payload, iteration ; } checksums thread = checksum; } ; } auto const begin{std::chrono::steady clock::now }; gate.start when ready ; for auto& worker : workers { worker.join ; } auto const end{std::chrono::steady clock::now }; std::uint64 t checksum{0}; for std::uint64 t const value : checksums { checksum ^= value; } return {std::chrono::duration<double end - begin .count , checksum};}std::size t parse positive char const value, char const option { std::string const text{value}; std::size t parsed characters{0}; std::size t result{0}; try { result = std::stoull text, &parsed characters ; } catch std::exception const& { std::cerr << "Invalid value for " << option << ": " << text << std::endl; std::exit EXIT FAILURE ; } if parsed characters = text.size || result == 0 { std::cerr << option << " must be a positive integer" << std::endl; std::exit EXIT FAILURE ; } return result;}Options parse options int argc, char argv { Options options{}; for int index{1}; index < argc; ++index { std::string const option{argv index }; if option == "--max-threads" || option == "--iterations" { if ++index == argc { std::cerr << option << " requires a value" << std::endl; std::exit EXIT FAILURE ; } std::size t const value{ parse positive argv index , option.c str }; if option == "--max-threads" { options.max threads = value; } else { options.iterations = value; } } else if option == "--help" { std::cout << "Usage: " << argv 0 << " --max-threads N --iterations N " << std::endl; std::exit EXIT SUCCESS ; } else { std::cerr << "Unknown option: " << option << std::endl; std::exit EXIT FAILURE ; } } return options;}void print result std::size t threads, Measurement const& shared, Measurement const& borrowed, std::size t iterations { double const operations{static cast<double threads static cast<double iterations }; double const shared rate{operations / shared.seconds / 1e6}; double const borrowed rate{operations / borrowed.seconds / 1e6}; std::cout << std::setw 7 << threads << std::setw 16 << std::fixed << std::setprecision 1 << shared rate << std::setw 16 << borrowed rate << std::setw 12 << std::setprecision 2 << borrowed rate / shared rate << std::endl;}} // namespaceint main int argc, char argv { Options const options{parse options argc, argv }; // The sole shared owner. Its lifetime covers both benchmark calls and all // worker joins, so the borrowed-reference benchmark is safe. auto const owner{std::make shared<Payload const }; std::cout << "Each thread performs " << options.iterations << " iterations. Rates are aggregate million iterations/second." << std::endl << " shared ptr: copies one shared owner every iteration" << std::endl << " borrowed: uses a reference while the owner stays alive" << std::endl << std::endl << std::setw 7 << "threads" << std::setw 16 << "shared ptr" << std::setw 16 << "borrowed ref" << std::setw 12 << "speedup" << std::endl; std::size t threads{1}; while true { Measurement const shared{ run shared ptr copies owner, threads, options.iterations }; Measurement const borrowed{ run borrowed reference owner, threads, options.iterations }; if shared.checksum = borrowed.checksum { std::cerr << "Benchmark variants produced different results" << std::endl; return EXIT FAILURE; } print result threads, shared, borrowed, options.iterations ; if threads == options.max threads { break; } threads = std::min options.max threads, threads 2 ; }} | To build and run the benchmark, please run the following commands. I built and ran the benchmark on my local desktop that has an 8-core 16-thread Intel Core i9-9900K CPU. | 123456789101112 | bash $ g++ -O3 -DNDEBUG -std=c++17 -pthread hidden multi threaded atomics.cpp -o hidden multi threaded atomics$ ./hidden multi threaded atomics --max-threads 16 --iterations 20000000Each thread performs 20000000 iterations. Rates are aggregate million iterations/second. shared ptr: copies one shared owner every iteration borrowed: uses a reference while the owner stays alivethreads shared ptr borrowed ref speedup 1 73.2 2686.8 36.70 2 21.0 5216.1 248.81 4 22.3 10351.4 464.46 8 19.9 11874.6 597.84 16 21.9 15878.3 724.76 | It turns out that the throughput of using shared pointers does not scale well with the number of threads, while using references to immutable objects scales much better. In fact, the throughput of using shared pointers remains almost consstant regardless of the number of threads, suggesting that there is a performance bottleneck associated with shared pointer management in a multi-threaded context. The reason for this behavior is that shared pointers internally use atomic reference counting to manage the lifetime of the object they own. There are costs associated with these atomic operations. In the single-threaded case where work is heavy, the overhead of atomic reference counting is almost negligible, but in the multi-threaded case, contention on the atomic operations becomes a bottleneck, limiting scalability. In our case, every time a shared pointer is copied or destroyed, the reference count is updated atomically, which introduces contention and limits scalability in a multi-threaded environment. On the other hand, using references to immutable objects avoids this overhead, allowing for much better performance and scalability. It should also be noted that when using shared pointers, the througput with two threads is significantly lower than the throughput with a single thread. To understand this, we have to understand how atomic operation works with cache coherence in multi-core systems. When multiple threads on different cores try to update the same atomic variable, such as the reference count of a shared pointer, the cache lines containing that variable must be synchronized across cores. This synchronization introduces additional latency and reduces throughput, even with just two threads. Consequently, the performance degradation with two threads compared to a single thread is a result of cache coherence overhead and contention on the atomic reference count. Performance Bottleneck from Hidden Atomic Operations https://leimao.github.io/blog/Hidden-Atomics-Performance-Bottleneck/ https://leimao.github.io/blog/Hidden-Atomics-Performance-Bottleneck/