了解std :: hardware_destructive_interference_size和std :: hardware_constructive_interference_size

Question

了解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.如果您构建二进制文件并在具有不同缓存行大小的其他计算机上执行它,这不是问题吗？当您不确定您的代码将运行在哪台机器上时,如何防止错误共享？

Answer 1

GMa*_*ckG 59

这些常量的意图确实是获取缓存行大小.阅读有关它们的基本原理的最佳位置是提案本身:

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

为了便于阅读,我将引用一小部分理由:

[...]不干扰(对于一阶)的内存粒度[通常]称为缓存行大小.

的使用高速缓存行的大小分为两大类:

避免来自不同线程的时间上不相交的运行时访问模式的对象之间的破坏性干扰(错误共享).

促进具有暂时本地运行时访问模式的对象之间的建设性干扰(真实共享).

这个有用的实施数量最显着的问题是当前实践中用于确定其价值的方法的可疑的可移植性,尽管它们作为一个群体的普遍性和普及性.[...]

我们的目标是为这个原因贡献一个适度的发明,这个数量的抽象可以通过实现保守地定义给定目的:

破坏性干扰大小:适合作为两个对象之间的偏移量的数字,以避免由于来自不同线程的不同运行时访问模式而导致的错误共享.

构造性干扰大小:一个适合作为对两个对象的组合内存占用大小和基本对齐的限制的数字,可能促进它们之间的真实共享.

在这两种情况下,这些值都是基于实现质量提供的,纯粹是可能提高性能的提示.这些是与alignas()关键字一起使用的理想便携值,目前几乎没有标准支持的便携式用途.

"这些常量与L1缓存行大小有什么关系？"

从理论上讲,非常直接.

假设编译器确切地知道您将运行什么体系结构 - 那么这些几乎肯定会精确地为您提供L1缓存行大小.(如后所述,这是一个很大的假设.)

对于它的价值,我几乎总是期望这些价值是相同的.我认为他们被单独宣布的唯一原因是完整性.(也就是说,编译器可能想要估计L2缓存行大小而不是L1缓存行大小以获得建设性干扰;但我不知道这是否真的有用.)

"有一个很好的例子可以证明他们的用例吗？"

在这个答案的底部,我附上了一个长基准程序,演示了虚假共享和真实共享.

它通过分配int包装器数组来演示错误共享:在一种情况下,多个元素适合L1缓存行,而在另一种情况下,单个元素占用L1缓存行.在紧密循环中,从阵列中选择单个固定元素并重复更新.

它通过在包装器中分配一对int来演示真正的共享:在一种情况下,该对中的两个int不一致地适合L1缓存行大小,而在另一种情况下它们适合.在紧密循环中,对的每个元素都会重复更新.

请注意,访问被测对象的代码不会改变; 唯一的区别是对象本身的布局和对齐方式.

我没有C++ 17编译器(假设大多数人目前都没有),所以我用自己的代码替换了有问题的常量.您需要更新这些值才能在您的计算机上准确无误.也就是说,64字节可能是典型现代桌面硬件上的正确值(在撰写本文时).

警告:测试将使用您计算机上的所有核心,并分配~216MB的内存.不要忘记使用优化进行编译!

在我的机器上,输出是:

Hardware concurrency: 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
Running naive_int test.
Average time: 0.0873625 seconds, useless result: 3291773
Running cache_int test.
Average time: 0.024724 seconds, useless result: 3286020
Running bad_pair test.
Average time: 0.308667 seconds, useless result: 6396272
Running good_pair test.
Average time: 0.174936 seconds, useless result: 6668457

我通过避免错误共享来获得~3.5倍的加速,并通过确保真正共享来实现~1.7倍的加速.

"两者都定义为静态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
}

Run Code Online (Sandbox Code Playgroud)

在编译期间,如果要假设只是定义缓存行大小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);
    }
}

Run Code Online (Sandbox Code Playgroud)

我写了这个提议,很好的回答!为了澄清你提出的一点:"我几乎总是期望这些价值是相同的.我相信它们被单独宣布的唯一原因是完整性." 是的,它们应该始终相同,除非:1)ISA已经发运了不同的高速缓存行大小,并且没有给出目标拱门; 2)你的目标是一个虚拟的ISA,例如WebAssembly,其实际的ISA是未知的(然后你得到最大的努力).在constexpr:需要constexpr以确定可用于确定结构布局的值.运行时值在其他情况下很有用. (32认同)

Answer 2

Val*_*lus 10

我几乎总是期望这些值是相同的.

关于上述内容,我想对接受的答案作出微小的贡献.不久之前,我看到了一个非常好的用例,这两个应该在folly库中单独定义.请参阅有关Intel Sandy Bridge处理器的警告.

https://github.com/facebook/folly/blob/3af92dbe6849c4892a1fe1f9366306a2f5cbe6a0/folly/lang/Align.h

//  Memory locations within the same cache line are subject to destructive
//  interference, also known as false sharing, which is when concurrent
//  accesses to these different memory locations from different cores, where at
//  least one of the concurrent accesses is or involves a store operation,
//  induce contention and harm performance.
//
//  Microbenchmarks indicate that pairs of cache lines also see destructive
//  interference under heavy use of atomic operations, as observed for atomic
//  increment on Sandy Bridge.
//
//  We assume a cache line size of 64, so we use a cache line pair size of 128
//  to avoid destructive interference.
//
//  mimic: std::hardware_destructive_interference_size, C++17
constexpr std::size_t hardware_destructive_interference_size =
    kIsArchArm ? 64 : 128;
static_assert(hardware_destructive_interference_size >= max_align_v, "math?");

//  Memory locations within the same cache line are subject to constructive
//  interference, also known as true sharing, which is when accesses to some
//  memory locations induce all memory locations within the same cache line to
//  be cached, benefiting subsequent accesses to different memory locations
//  within the same cache line and heping performance.
//
//  mimic: std::hardware_constructive_interference_size, C++17
constexpr std::size_t hardware_constructive_interference_size = 64;
static_assert(hardware_constructive_interference_size >= max_align_v, "math?");

Run Code Online (Sandbox Code Playgroud)

是的，Intel 的 L2 空间预取器（Nehalem 及更高版本，包括所有 Sandybridge 系列）尝试完成缓存行对的对齐（如果有空闲带宽）。[在 L1 和 L2 预取数据](/sf/ask/1438144221/) 摘录了英特尔优化手册。[DCU 预取器在什么条件下开始预取？](/sf/ask/3746235741/) 有一些关于它们何时触发的详细信息。 (2认同)
请注意，如果链接不同编译的对象或库，在 x86 中根据 `-march=sandybridge` 和 `-march=znver1` (ryzen) 更改值可能会导致结构布局不兼容。（http://clang-developers.42468.n3.nabble.com/RFC-C-17-hardware-constructive-corruption-interference-size-td4060786.html）。这就是为什么 clang 仍然没有实现任何一个常量。通常对 x86 使用破坏性=128 是一个好主意；保守的环境在任何地方都是安全的。 (2认同)

归档时间：	9 年，3 月前
查看次数：	4605 次
最近记录：	7 年，3 月前