Понимание 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, Разве это не проблема, если вы создаете двоичный файл и запускаете его на других машинах с различными размерами строк кэша? Как он может защитить от ложного обмена в этом сценарии, когда вы не уверены, на каком компьютере будет работать ваш код?
Источник

2 ответа

Решение

Целью этих констант действительно является получение размера строки кэша. Лучшее место, чтобы прочитать об обосновании для них в самом предложении:

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

Я приведу здесь фрагмент обоснования для удобства чтения:

[...] зернистость памяти, которая не мешает (первому порядку) [обычно] называется размером строки кэша.

Использование размера строки кэша делится на две широкие категории:

  • Предотвращение деструктивных помех (ложное разделение) между объектами с временным разделением шаблонов доступа во время выполнения из разных потоков.
  • Содействие конструктивным помехам (истинное разделение) между объектами, которые имеют временные локальные шаблоны доступа во время выполнения.

Наиболее существенная проблема с этим полезным количеством реализации - сомнительная переносимость методов, используемых в современной практике для определения его ценности, несмотря на их распространенность и популярность как группы. [...]

Мы стремимся внести скромное изобретение по этой причине, абстракции для этого количества, которые могут быть консервативно определены для определенных целей реализациями:

  • Размер деструктивной помехи: число, которое подходит как смещение между двумя объектами, чтобы избежать ложного совместного использования из-за разных схем доступа во время выполнения из разных потоков.
  • Конструктивный размер помехи: число, которое подходит в качестве ограничения для объёма занимаемой памяти двумя объектами и базового выравнивания, чтобы, вероятно, способствовать истинному разделению между ними.

В обоих случаях эти значения предоставляются на основе качества реализации, просто как подсказки, которые могут улучшить производительность. Это идеальные переносимые значения для использования с alignas() Ключевое слово, для которого в настоящее время практически не существует стандартно поддерживаемых портативных приложений

"Как эти константы связаны с размером строки кэша L1?"

Теоретически довольно прямо.

Предположим, что компилятор точно знает, на какой архитектуре вы будете работать - тогда они почти наверняка точно дадут вам размер строки кэша L1. (Как отмечалось позже, это большое предположение.)

Для чего бы это ни стоило, я почти всегда ожидал бы, что эти значения будут одинаковыми. Я считаю, что единственная причина, по которой они объявляются отдельно, - это полнота. (Тем не менее, возможно, компилятор хочет оценить размер строки кэша L2 вместо размера строки кэша L1 для конструктивного вмешательства; хотя я не знаю, будет ли это на самом деле полезным.)

"Есть ли хороший пример, который демонстрирует их варианты использования?"

В конце этого ответа я приложил длинную тестовую программу, которая демонстрирует ложный обмен и истинный обмен.

Он демонстрирует ложное совместное использование, выделяя массив упаковщиков int: в одном случае несколько элементов помещаются в строку кэша L1, а в другом - один элемент занимает строку кэша L1. В узком цикле один, фиксированный элемент выбирается из массива и неоднократно обновляется.

Он демонстрирует истинное совместное использование путем выделения одной пары целых чисел в оболочке: в одном случае два целых числа в паре не соответствуют размеру строки кэша L1 вместе, а в другом они соответствуют друг другу. В узком цикле каждый элемент пары обновляется многократно.

Обратите внимание, что код для доступа к тестируемому объекту не изменяется; единственное отличие - это расположение и выравнивание самих объектов.

У меня нет компилятора C++17 (и я полагаю, что большинство людей в настоящее время не имеют его), поэтому я заменил эти константы своими собственными. Вам необходимо обновить эти значения, чтобы быть точными на вашем компьютере. Тем не менее, 64 байта, вероятно, правильное значение на типичном современном настольном оборудовании (на момент написания статьи).

Предупреждение: тест будет использовать все ядра на ваших машинах и выделять ~256 МБ памяти.Не забудьте скомпилировать с оптимизацией!

На моей машине вывод:

Аппаратное параллелизм: 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-кратное ускорение, обеспечивая истинное совместное использование.

"Оба определены статическим 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);
    }
}
Источник

Я почти всегда ожидал бы, что эти значения будут одинаковыми.

Что касается вышеизложенного, я хотел бы внести небольшой вклад в принятый ответ. Некоторое время назад я видел очень хороший вариант использования, где эти два должны быть определены отдельно в 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?");
Источник

Я протестировал приведенный выше код, но я думаю, что есть небольшая ошибка, мешающая нам понять базовое функционирование, одна строка кеша не должна разделяться между двумя отдельными атомами, чтобы предотвратить ложное совместное использование. Я изменил определение этих структур.

struct naive_int
{
    alignas ( sizeof ( int ) ) atomic < int >               value;
};

struct cache_int
{
    alignas ( hardware_constructive_interference_size ) atomic < int >  value;
};

struct bad_pair
{
    // two atomics sharing a single 64 bytes cache line 
    alignas ( hardware_constructive_interference_size ) atomic < int >  first;
    atomic < int >                              second;
};

struct good_pair
{
    // first cache line begins here
    alignas ( hardware_constructive_interference_size ) atomic < int >  
                                                first;
    // That one is still in the first cache line
    atomic < int >                              first_s; 
    // second cache line starts here
    alignas ( hardware_constructive_interference_size ) atomic < int >
                                                second;
    // That one is still in the second cache line
    atomic < int >                              second_s;
};

И получившийся запуск:

Hardware concurrency := 40
sizeof(naive_int)    := 4
alignof(naive_int)   := 4
sizeof(cache_int)    := 64
alignof(cache_int)   := 64
sizeof(bad_pair)     := 64
alignof(bad_pair)    := 64
sizeof(good_pair)    := 128
alignof(good_pair)   := 64
Running naive_int test.
Average time: 0.060303 seconds, useless result: 8212147
Running cache_int test.
Average time: 0.0109432 seconds, useless result: 8113799
Running bad_pair test.
Average time: 0.162636 seconds, useless result: 16289887
Running good_pair test.
Average time: 0.129472 seconds, useless result: 16420417

Я испытал большие расхождения в последнем результате, но никогда не посвящал конкретную проблему какой-либо конкретной сути. В любом случае это исчерпало 2 Xeon 2690V2 и из разных запусков с использованием 64 или 128 дляhardware_constructive_interference_size = 128 Я обнаружил, что 64 - это более чем достаточно, а 128 - очень плохое использование доступного кеша.

Я внезапно понял, что ваш вопрос помогает мне понять, о чем говорил Джефф Прешинг, все о полезной нагрузке!?

Источник
Другие вопросы по тегам