Performance Bottleneck from Hidden Atomic Operations

Introduction

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.

Performance Bottleneck from Hidden Atomic Operations

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.

hidden_multi_threaded_atomics.cpp

#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;
}

} // namespace

int 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.

$ 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
Each 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 alive

threads      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.

References

• C++ Shared Pointer Thread-Safety