Opis std :: hardware_destructive_interference_size i std :: hardware_constructive_interference_size

Question

C++ 17 dodano std::hardware_destructive_interference_size and std::hardware_constructive_interference_size. Po pierwsze, myślałem, że jest to przenośny sposób na uzyskanie rozmiaru linii pamięci podręcznej L1, ale jest to nadmierne uproszczenie.

Pytania:

• Jak są te stałe związane z wielkością linii cache L1?
• Czy istnieje dobry przykład demonstrujący ich przypadki użycia?
• Oba są zdefiniowane jako static constexpr. Czy to nie problem, jeśli zbudujesz plik binarny i uruchomisz go na innych komputerach o różnych rozmiarach linii pamięci podręcznej? W jaki sposób można zabezpieczyć się przed fałszywym udostępnianiem w tym scenariuszu, gdy nie masz pewności, na którym komputerze będzie działał twój kod?

Answer 1

Celem tych stałych jest uzyskanie rozmiaru pamięci podręcznej. To najlepsze miejsce, aby przeczytać o uzasadnienie dla nich jest w propozycji samego:

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

Zacytuję fragment uzasadnienia tutaj łatwość czytania

[. ..] ziarnistość pamięci, która nie ingeruje (w pierwszej kolejności) [powszechnie zwana jest wielkością bufora pamięci.

Zastosowań cache-size linii można podzielić na dwie kategorie:

• Unikanie niszczącej ingerencji (false-sharing) między obiektami z czasowo rozłącznych wzorców Access Runtime z różnych wątków.
• Promowanie konstruktywnej interferencji (prawdziwego współdzielenia) między obiektami, które mają tymczasowo lokalne wzorce dostępu do środowiska wykonawczego.

Najbardziej znaczącym zagadnieniem związanym z tą przydatną wielkością wdrożeniową jest wątpliwa przenośność metod stosowanych w obecnej praktyce w celu określenia jej wartości, pomimo ich wszechobecności i popularności jako grupy. [...]

Chcemy przyczynić się skromny wynalazek dla tej przyczyny, abstrakcje dla tej ilości, które mogą być konserwatywnie zdefiniowane dla celów podanych przez implementacje:

• destrukcyjna rozmiar ingerencja: liczba, która jest odpowiednie jako przesunięcie między dwoma obiektami, aby prawdopodobnie uniknąć fałszywego współdzielenia z powodu różnych wzorców dostępu do środowiska wykonawczego z różnych wątków.
• Konstrukcyjny rozmiar interferencji: liczba, która jest odpowiednia dla limitu rozmiaru dwóch obiektów w połączeniu z wielkością pamięci i wyrównaniem podstawy, aby prawdopodobnie promować prawdziwe dzielenie między nimi.

W obu przypadkach wartości te są dostarczane na podstawie jakości wdrożenia, wyłącznie jako wskazówki, które mogą poprawić wydajność. Są to idealne przenośne wartości do użycia ze słowem kluczowym alignas(), dla którego obecnie nie ma prawie żadnych standardowych obsługiwanych przenośnych zastosowań.

---

"Jak są te stałe związane z wielkością cache L1 linii?"

Teoretycznie całkiem bezpośrednio.

Załóżmy, że kompilator nie wie dokładnie, co architektura będziesz działa na - wtedy to prawie na pewno daje rozmiar cache L1-line precyzyjnie. (Jak zauważył później, to jest duży założenie.)

Na co warto, to prawie zawsze oczekiwałby te wartości będą takie same. Uważam, że jedynym powodem, dla którego są one zadeklarowane osobno, jest kompletność. (To powiedziawszy, może kompilator chce oszacować wielkość pamięci podręcznej L2-line zamiast L1 Cache Size rzutu konstruktywnej interferencji; nie wiem, czy to rzeczywiście być przydatne, choć.)

---

" Czy istnieje dobry przykład demonstrujący ich przypadki użycia? "

U dołu tej odpowiedzi załączam długi program testowy, który demonstruje dzielenie się błędami i prawdziwe udostępnianie.

Demonstruje dzielenie się błędami poprzez przydzielenie tablicy elementów opakowania int: w jednym przypadku wiele elementów mieści się w linii podręcznej L1, a w drugim pojedynczy element zajmuje linię pamięci podręcznej L1. W ciasnej pętli pojedynczy, stały element jest wybierany z tablicy i aktualizowany wielokrotnie.

Demonstruje prawdziwe dzielenie się przez przydzielenie pojedynczej pary znaków w opakowaniu: w jednym przypadku dwa numery wewnętrzne w obrębie pary nie pasują do rozmiaru linii pamięci podręcznej L1, a w drugim - do drugiej. W ciasnej pętli każdy element pary jest aktualizowany wielokrotnie.

Należy pamiętać, że kod dostępu do badanego obiektu zmienia się na , a nie na; jedyną różnicą jest układ i wyrównanie samych obiektów.

nie mam C++ 17 kompilatora (a zakładamy, że większość ludzi obecnie też nie), więc mam zastąpić stałe w pytaniu z moim własnym. Musisz zaktualizować te wartości, aby były dokładne na twoim komputerze. To powiedziawszy, 64 bajty to prawdopodobnie poprawna wartość na typowym nowoczesnym sprzęcie biurkowym (w chwili pisania tego tekstu).

Ostrzeżenie: test będzie wykorzystywać wszystkie rdzenie na swoich maszynach, i przeznaczyć ~ 256MB pamięci. Nie zapomnij skompilować z optymalizacją!

Na moim komputerze, wyjście jest:

 
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 

mam ~ 3.5x przyspieszenie poprzez unikanie fałszywego podziału, a ~ 1.7x przyspieszenie poprzez zapewnienie prawdziwego podziału.

---

„Oba są określone statyczne constexpr. Czy to nie jest problem, jeśli zbudować binarny i wykonać go na innych maszynach z innej linii cache rozmiary? W jaki sposób można chronić przed fałszywym dzielenia w tym scenariuszu, gdy jesteś nie masz pewności, na którym komputerze będzie działał Twój kod? "

To rzeczywiście będzie problem.Stałe te nie są gwarantowane, aby odwzorować na dowolny rozmiar pamięci podręcznej na maszynie docelowej, ale mają być najlepszym przybliżeniem, na jakie może się zdobyć kompilator.

Zostało to odnotowane we wniosku, a w dodatku podano przykład tego, jak niektóre biblioteki próbują wykryć rozmiar pamięci podręcznej podczas kompilacji w oparciu o różne wskazówki i makra dotyczące środowiska. Ty jest gwarantowana, że ​​ta wartość wynosi co najmniej alignof(max_align_t), co jest oczywistym dolnym ograniczeniem.

Innymi słowy, ta wartość powinna być używana jako przypadek zastępczy; jesteś wolny, aby określić dokładną wartość jeśli go znasz, np .:

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 
} 

Podczas kompilacji, jeśli chcesz założyć rozmiar cache-line wystarczy zdefiniować KNOWN_L1_CACHE_LINE_SIZE.

Mam nadzieję, że to pomoże! Program

Benchmark:

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