[解決済み] std::hardware_destructive_interference_size と std::hardware_constructive_interference_size を理解する。

質問

C++17の追加 std::hardware_destructive_interference_size と std::hardware_constructive_interference_size . まず、L1キャッシュラインのサイズを取得するための単なるポータブルな方法だと思ったのですが、それは単純化しすぎです。

質問です。

• これらの定数は、L1 キャッシュ ライン サイズとどのように関係しているのですか？
• これらの使用例を示す良い例はありますか?
• 両方とも定義されています。 static constexpr . バイナリをビルドして、それをキャッシュラインサイズの異なる他のマシンで実行した場合、問題はないのでしょうか？あなたのコードがどのマシンで実行されるかが定かでない場合、そのシナリオではどのようにして誤った共有から保護することができますか？

どのように解決するのですか?

これらの定数の意図は、確かにキャッシュラインサイズを取得することです。それらの根拠について読むのに最適な場所は、提案自体にあります。

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0154r1.html

読みやすくするために、その根拠の一部をここに引用しておきます。

[...] (一次的に) 妨害しないメモリの粒度 [は、] 一般的に キャッシュラインサイズ .

の用途は キャッシュラインサイズ は 2 つの大きなカテゴリに分類されます。

• 異なるスレッドからの時間的に不連続な実行時アクセスパターンを持つオブジェクト間の破壊的な干渉（false-sharing）を回避すること。
• 時間的に局所的な実行時アクセスパターンを持つオブジェクト間の建設的な干渉（真の共有）を促進する。

この有用な実装量に関する最も重大な問題は、グループとして普及し人気があるにもかかわらず、その価値を決定するために現在の実務で使用されている方法の移植性に疑問があることです。[...]

私たちはこの目的のためにささやかな発明、すなわち、実装によって与えられた目的のために保守的に定義することができるこの量のための抽象化に貢献することを目的としています。

• 破壊的な干渉のサイズ : 異なるスレッドからの異なる実行時アクセスパターンによる偽共有を避けるために、2つのオブジェクト間のオフセットとして適切な数値です。
• 建設的干渉サイズ : 2 つのオブジェクトの合計メモリ フットプリント サイズとベース アライメントの制限値として適切な数値で、それらの間の真の共有を促進する可能性があります。

どちらの場合も、これらの値は実装の品質に基づいて提供され、純粋にパフォーマンスを向上させる可能性のあるヒントとして提供されます。これらの値は alignas() キーワードで使用するのに理想的なポータブルな値です。

"これらの定数は、L1キャッシュラインサイズとどのように関係していますか?"。

理論的には、かなり直接的です。

コンパイラーが実行するアーキテクチャを正確に知っていると仮定すると、これらはほぼ確実に L1 キャッシュラインのサイズを正確に教えてくれるでしょう。(後で述べるように、これは大きな仮定です)。

価値あるものであるために、私はこれらの値が同じであることをほとんど常に期待しています。これらが別々に宣言されている唯一の理由は、完全性のためだと思います。(そうは言っても、コンパイラーは、建設的な干渉のために、L1 キャッシュライン サイズの代わりに L2 キャッシュライン サイズを推定したいと思うかもしれませんが、これが実際に有用であるかどうかはわかりません)。

"そのユースケースを示す良い例はありませんか？

この回答の一番下に、偽共有と真共有を実証する長いベンチマークプログラムを添付しました。

これは、int 型ラッパーの配列を割り当てることによって、偽共有を実証します。一方では複数の要素が L1 キャッシュラインに適合し、他方では単一の要素が L1 キャッシュラインを占めます。タイトループでは、配列から単一の固定要素が選択され、繰り返し更新されます。

ラッパーで1組のintを割り当てることにより、真の共有を実証します。1つのケースでは、ペア内の2つのintは一緒にL1キャッシュラインサイズに収まらず、もう1つのケースでは、それらは収まります。タイトなループの中で、ペアの各要素は繰り返し更新されます。

テスト対象のオブジェクトにアクセスするコードは、以下のようになります。 ではなく 唯一の違いは、オブジェクト自体のレイアウトとアラインメントです。

私は C++17 コンパイラーを持っていないので (そして現在ほとんどの人も持っていないと仮定します)、問題の定数を私自身のものに置き換えています。あなたのマシンで正確になるように、これらの値を更新する必要があります。とはいえ、64 バイトというのは、典型的な現代のデスクトップ ハードウェアではおそらく正しい値でしょう (執筆時)。

警告: このテストでは、マシンのすべてのコアを使用し、~256MB のメモリを割り当てます。最適化でコンパイルすることを忘れないでください!

私のマシンでは、出力は次のとおりです。

ハードウェアの同時実行数: 16
sizeof(naive_int): 4
alignof(naive_int): 4
sizeof(cache_int): 64
alignof(cache_int): 64
sizeof(bad_pair): 72
alignof(bad_pair)：4個
sizeof(good_pair)：8個
alignof(good_pair): 4
naive_intテストを実行中。
平均時間：0.0873625秒、無駄な結果：3291773
cache_int テストを実行中。
平均時間: 0.024724秒、無駄な結果: 3286020
bad_pairテストを実行中。
平均時間: 0.308667秒、無駄な結果: 6396272
good_pairテストを実行中。
平均時間：0.174936秒、無駄な結果：6668457

偽共有を避けることで～3.5倍のスピードアップを、真の共有を保証することで～1.7倍のスピードアップを得ることができます。

"どちらもstatic constexprで定義されています。バイナリをビルドして、キャッシュラインサイズが異なる他のマシンで実行した場合、問題はないのでしょうか？あなたのコードがどのマシンで実行されるかがわからない場合、そのシナリオではどのようにして誤った共有から保護することができますか?

これは確かに問題でしょう。これらの定数は、特定のターゲット マシン上の任意のキャッシュ ライン サイズにマッピングすることを保証するものではなく、コンパイラーが作り出せる最良の近似値であることを意図しています。

これは提案の中で指摘されており、付録では、いくつかのライブラリが、さまざまな環境ヒントやマクロに基づいて、コンパイル時にキャッシュラインサイズを検出しようとする方法を例示しています。あなたは は この値が少なくとも alignof(max_align_t) であることが保証されており、これは明らかな下界です。

言い換えれば、この値はフォールバックのケースとして使用されるべきです。正確な値を知っている場合は、自由に定義することができます。

constexpr std::size_t cache_line_size() {
#ifdef KNOWN_L1_CACHE_LINE_SIZE
  return KNOWN_L1_CACHE_LINE_SIZE;
#else
  return std::hardware_destructive_interference_size;
#endif
}

コンパイル時に、キャッシュラインサイズを仮定したい場合は、単に KNOWN_L1_CACHE_LINE_SIZE .

これが役立つといいのですが!

ベンチマークプログラムです。

#include <chrono>
#include <condition_variable>
#include <cstddef>
#include <functional>
#include <future>
#include <iostream>
#include <random>
#include <thread>
#include <vector>

// !!! YOU MUST UPDATE THIS TO BE ACCURATE !!!
constexpr std::size_t hardware_destructive_interference_size = 64;

// !!! YOU MUST UPDATE THIS TO BE ACCURATE !!!
constexpr std::size_t hardware_constructive_interference_size = 64;

constexpr unsigned kTimingTrialsToComputeAverage = 100;
constexpr unsigned kInnerLoopTrials = 1000000;

typedef unsigned useless_result_t;
typedef double elapsed_secs_t;

//////// CODE TO BE SAMPLED:

// wraps an int, default alignment allows false-sharing
struct naive_int {
    int value;
};
static_assert(alignof(naive_int) < hardware_destructive_interference_size, "");

// wraps an int, cache alignment prevents false-sharing
struct cache_int {
    alignas(hardware_destructive_interference_size) int value;
};
static_assert(alignof(cache_int) == hardware_destructive_interference_size, "");

// wraps a pair of int, purposefully pushes them too far apart for true-sharing
struct bad_pair {
    int first;
    char padding[hardware_constructive_interference_size];
    int second;
};
static_assert(sizeof(bad_pair) > hardware_constructive_interference_size, "");

// wraps a pair of int, ensures they fit nicely together for true-sharing
struct good_pair {
    int first;
    int second;
};
static_assert(sizeof(good_pair) <= hardware_constructive_interference_size, "");

// accesses a specific array element many times
template <typename T, typename Latch>
useless_result_t sample_array_threadfunc(
    Latch& latch,
    unsigned thread_index,
    T& vec) {
    // prepare for computation
    std::random_device rd;
    std::mt19937 mt{ rd() };
    std::uniform_int_distribution<int> dist{ 0, 4096 };

    auto& element = vec[vec.size() / 2 + thread_index];

    latch.count_down_and_wait();

    // compute
    for (unsigned trial = 0; trial != kInnerLoopTrials; ++trial) {
        element.value = dist(mt);
    }

    return static_cast<useless_result_t>(element.value);
}

// accesses a pair's elements many times
template <typename T, typename Latch>
useless_result_t sample_pair_threadfunc(
    Latch& latch,
    unsigned thread_index,
    T& pair) {
    // prepare for computation
    std::random_device rd;
    std::mt19937 mt{ rd() };
    std::uniform_int_distribution<int> dist{ 0, 4096 };

    latch.count_down_and_wait();

    // compute
    for (unsigned trial = 0; trial != kInnerLoopTrials; ++trial) {
        pair.first = dist(mt);
        pair.second = dist(mt);
    }

    return static_cast<useless_result_t>(pair.first) +
        static_cast<useless_result_t>(pair.second);
}

//////// UTILITIES:

// utility: allow threads to wait until everyone is ready
class threadlatch {
public:
    explicit threadlatch(const std::size_t count) :
        count_{ count }
    {}

    void count_down_and_wait() {
        std::unique_lock<std::mutex> lock{ mutex_ };
        if (--count_ == 0) {
            cv_.notify_all();
        }
        else {
            cv_.wait(lock, [&] { return count_ == 0; });
        }
    }

private:
    std::mutex mutex_;
    std::condition_variable cv_;
    std::size_t count_;
};

// utility: runs a given function in N threads
std::tuple<useless_result_t, elapsed_secs_t> run_threads(
    const std::function<useless_result_t(threadlatch&, unsigned)>& func,
    const unsigned num_threads) {
    threadlatch latch{ num_threads + 1 };

    std::vector<std::future<useless_result_t>> futures;
    std::vector<std::thread> threads;
    for (unsigned thread_index = 0; thread_index != num_threads; ++thread_index) {
        std::packaged_task<useless_result_t()> task{
            std::bind(func, std::ref(latch), thread_index)
        };

        futures.push_back(task.get_future());
        threads.push_back(std::thread(std::move(task)));
    }

    const auto starttime = std::chrono::high_resolution_clock::now();

    latch.count_down_and_wait();
    for (auto& thread : threads) {
        thread.join();
    }

    const auto endtime = std::chrono::high_resolution_clock::now();
    const auto elapsed = std::chrono::duration_cast<
        std::chrono::duration<double>>(
            endtime - starttime
            ).count();

    useless_result_t result = 0;
    for (auto& future : futures) {
        result += future.get();
    }

    return std::make_tuple(result, elapsed);
}

// utility: sample the time it takes to run func on N threads
void run_tests(
    const std::function<useless_result_t(threadlatch&, unsigned)>& func,
    const unsigned num_threads) {
    useless_result_t final_result = 0;
    double avgtime = 0.0;
    for (unsigned trial = 0; trial != kTimingTrialsToComputeAverage; ++trial) {
        const auto result_and_elapsed = run_threads(func, num_threads);
        const auto result = std::get<useless_result_t>(result_and_elapsed);
        const auto elapsed = std::get<elapsed_secs_t>(result_and_elapsed);

        final_result += result;
        avgtime = (avgtime * trial + elapsed) / (trial + 1);
    }

    std::cout
        << "Average time: " << avgtime
        << " seconds, useless result: " << final_result
        << std::endl;
}

int main() {
    const auto cores = std::thread::hardware_concurrency();
    std::cout << "Hardware concurrency: " << cores << std::endl;

    std::cout << "sizeof(naive_int): " << sizeof(naive_int) << std::endl;
    std::cout << "alignof(naive_int): " << alignof(naive_int) << std::endl;
    std::cout << "sizeof(cache_int): " << sizeof(cache_int) << std::endl;
    std::cout << "alignof(cache_int): " << alignof(cache_int) << std::endl;
    std::cout << "sizeof(bad_pair): " << sizeof(bad_pair) << std::endl;
    std::cout << "alignof(bad_pair): " << alignof(bad_pair) << std::endl;
    std::cout << "sizeof(good_pair): " << sizeof(good_pair) << std::endl;
    std::cout << "alignof(good_pair): " << alignof(good_pair) << std::endl;

    {
        std::cout << "Running naive_int test." << std::endl;

        std::vector<naive_int> vec;
        vec.resize((1u << 28) / sizeof(naive_int));  // allocate 256 mibibytes

        run_tests([&](threadlatch& latch, unsigned thread_index) {
            return sample_array_threadfunc(latch, thread_index, vec);
        }, cores);
    }
    {
        std::cout << "Running cache_int test." << std::endl;

        std::vector<cache_int> vec;
        vec.resize((1u << 28) / sizeof(cache_int));  // allocate 256 mibibytes

        run_tests([&](threadlatch& latch, unsigned thread_index) {
            return sample_array_threadfunc(latch, thread_index, vec);
        }, cores);
    }
    {
        std::cout << "Running bad_pair test." << std::endl;

        bad_pair p;

        run_tests([&](threadlatch& latch, unsigned thread_index) {
            return sample_pair_threadfunc(latch, thread_index, p);
        }, cores);
    }
    {
        std::cout << "Running good_pair test." << std::endl;

        good_pair p;

        run_tests([&](threadlatch& latch, unsigned thread_index) {
            return sample_pair_threadfunc(latch, thread_index, p);
        }, cores);
    }
}