Понимание std :: hardware_destructive_interference_size и std :: hardware_constructive_interference_size

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

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 МБ памяти. Не забывайте компилировать с оптимизацией!

На моей машине результат:

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

«Оба определены 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);
    }
}

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

Что касается вышеизложенного, я хотел бы внести незначительный вклад в принятый ответ. Некоторое время назад я увидел очень хороший вариант использования, когда эти два элемента должны быть определены отдельно в библиотеке folly. См. Предупреждение о процессоре Intel Sandy Bridge.

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

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 - очень плохое использование доступного кеша.

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