Grundlegendes zu std :: hardware_destructive_interference_size und std :: hardware_constructive_interference_size

78

C ++ 17 hinzugefügt std::hardware_destructive_interference_sizeundstd::hardware_constructive_interference_size . Zuerst dachte ich, es sei nur eine tragbare Möglichkeit, die Größe einer L1-Cache-Zeile zu ermitteln, aber das ist eine übermäßige Vereinfachung.

Fragen:

  • Wie hängen diese Konstanten mit der L1-Cache-Zeilengröße zusammen?
  • Gibt es ein gutes Beispiel, das ihre Anwendungsfälle demonstriert?
  • Beide sind definiert static constexpr. Ist das kein Problem, wenn Sie eine Binärdatei erstellen und auf anderen Computern mit unterschiedlichen Cache-Zeilengrößen ausführen? Wie kann es in diesem Szenario vor falscher Freigabe schützen, wenn Sie nicht sicher sind, auf welchem ​​Computer Ihr Code ausgeführt wird?
Philipp Claßen
quelle

Antworten:

69

Die Absicht dieser Konstanten ist in der Tat, die Cache-Zeilengröße zu erhalten. Der beste Ort, um über die Gründe für sie zu lesen, ist der Vorschlag selbst:

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

Ich werde hier einen Ausschnitt der Gründe zitieren, um das Lesen zu vereinfachen:

[...] Die Granularität des Speichers, die (in erster Ordnung) nicht stört, wird üblicherweise als Cache-Zeilengröße bezeichnet .

Die Verwendung der Cache-Zeilengröße fällt in zwei große Kategorien:

  • Vermeiden destruktiver Interferenzen (Falschfreigabe) zwischen Objekten mit zeitlich getrennten Laufzeitzugriffsmustern von verschiedenen Threads.
  • Förderung konstruktiver Interferenzen (True-Sharing) zwischen Objekten mit zeitlich lokalen Laufzeitzugriffsmustern.

Das wichtigste Problem bei dieser nützlichen Implementierungsmenge ist die fragwürdige Portabilität der Methoden, die in der gegenwärtigen Praxis verwendet werden, um ihren Wert zu bestimmen, trotz ihrer Verbreitung und Popularität als Gruppe. [...]

Wir wollen eine bescheidene Erfindung für diesen Zweck einbringen, Abstraktionen für diese Menge, die durch Implementierungen für bestimmte Zwecke konservativ definiert werden können:

  • Destruktive Interferenzgröße : Eine Zahl, die als Versatz zwischen zwei Objekten geeignet ist, um eine falsche Freigabe aufgrund unterschiedlicher Laufzeitzugriffsmuster von verschiedenen Threads zu vermeiden.
  • Konstruktive Interferenzgröße : Eine Zahl, die als Begrenzung für die kombinierte Speichergröße und Basisausrichtung von zwei Objekten geeignet ist, um wahrscheinlich eine echte gemeinsame Nutzung zwischen ihnen zu fördern.

In beiden Fällen werden diese Werte auf Basis der Implementierungsqualität bereitgestellt, lediglich als Hinweise, die die Leistung verbessern können. Dies sind ideale tragbare Werte für die Verwendung mit dem alignas()Schlüsselwort, für die es derzeit fast keine standardunterstützten tragbaren Verwendungen gibt.


"Wie hängen diese Konstanten mit der L1-Cache-Zeilengröße zusammen?"

Theoretisch ziemlich direkt.

Angenommen, der Compiler weiß genau, auf welcher Architektur Sie ausgeführt werden - dann erhalten Sie mit ziemlicher Sicherheit genau die Größe der L1-Cache-Zeile. (Wie später erwähnt, ist dies eine große Annahme.)

Für das, was es wert ist, würde ich fast immer erwarten, dass diese Werte gleich sind. Ich glaube, der einzige Grund, warum sie separat deklariert werden, ist der Vollständigkeit halber. (Das heißt, vielleicht möchte ein Compiler die Größe der L2-Cache-Zeile anstelle der Größe der L1-Cache-Zeile für konstruktive Interferenzen schätzen. Ich weiß jedoch nicht, ob dies tatsächlich nützlich wäre.)


"Gibt es ein gutes Beispiel, das ihre Anwendungsfälle demonstriert?"

Am Ende dieser Antwort habe ich ein langes Benchmark-Programm angehängt, das Falsch-Teilen und Wahr-Teilen demonstriert.

Es demonstriert die falsche Freigabe durch Zuweisen eines Arrays von Int-Wrappern: In einem Fall passen mehrere Elemente in die L1-Cache-Zeile, und in dem anderen Fall nimmt ein einzelnes Element die L1-Cache-Zeile ein. In einer engen Schleife wird ein einzelnes, festes Element aus dem Array ausgewählt und wiederholt aktualisiert.

Es demonstriert True-Sharing, indem ein einzelnes Int-Paar in einem Wrapper zugewiesen wird: In einem Fall passen die beiden Ints innerhalb des Paares nicht zusammen in die L1-Cache-Zeilengröße, in dem anderen. In einer engen Schleife wird jedes Element des Paares wiederholt aktualisiert.

Beachten Sie, dass sich der Code für den Zugriff auf das zu testende Objekt nicht ändert. Der einzige Unterschied ist das Layout und die Ausrichtung der Objekte selbst.

Ich habe keinen C ++ 17-Compiler (und nehme an, dass die meisten Leute dies derzeit auch nicht tun), daher habe ich die fraglichen Konstanten durch meine eigenen ersetzt. Sie müssen diese Werte aktualisieren, um auf Ihrem Computer genau zu sein. Das heißt, 64 Bytes sind wahrscheinlich der richtige Wert auf typischer moderner Desktop-Hardware (zum Zeitpunkt des Schreibens).

Warnung: Der Test verwendet alle Kerne auf Ihren Computern und weist ~ 256 MB Speicher zu. Vergessen Sie nicht, mit Optimierungen zu kompilieren!

Auf meinem Computer lautet die Ausgabe:

Hardware-Parallelität: 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-Test ausführen.
Durchschnittliche Zeit: 0,0873625 Sekunden, nutzloses Ergebnis: 3291773
Cache_int Test ausführen.
Durchschnittliche Zeit: 0,024724 Sekunden, nutzloses Ergebnis: 3286020
Bad_pair-Test ausführen.
Durchschnittliche Zeit: 0,308667 Sekunden, nutzloses Ergebnis: 6396272
Good_pair-Test ausführen.
Durchschnittliche Zeit: 0,174936 Sekunden, nutzloses Ergebnis: 6668457

Ich erhalte eine ~ 3,5-fache Geschwindigkeit, indem ich falsches Teilen vermeide, und eine ~ 1,7-fache Geschwindigkeit, indem ich wahres Teilen sicherstelle.


"Beide sind als statische Constexpr definiert. Ist das kein Problem, wenn Sie eine Binärdatei erstellen und auf anderen Computern mit unterschiedlichen Cache-Zeilengrößen ausführen? Wie kann sie in diesem Szenario vor falscher Freigabe schützen, wenn Sie nicht sicher sind, auf welchem ​​Computer sich Ihr Code befindet in Betrieb sein?"

Dies wird in der Tat ein Problem sein. Es ist nicht garantiert, dass diese Konstanten einer Cache-Zeilengröße auf dem Zielcomputer zugeordnet werden, sie sollen jedoch die beste Annäherung sein, die der Compiler aufbringen kann.

Dies wird im Vorschlag erwähnt und im Anhang wird ein Beispiel dafür gegeben, wie einige Bibliotheken versuchen, die Größe der Cache-Zeile zur Kompilierungszeit anhand verschiedener Umgebungshinweise und Makros zu ermitteln. Ihnen wird garantiert, dass dieser Wert mindestens ist alignof(max_align_t), was eine offensichtliche Untergrenze darstellt.

Mit anderen Worten, dieser Wert sollte als Fallback-Fall verwendet werden. Sie können einen genauen Wert definieren, wenn Sie ihn kennen, z.

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
}

Wenn Sie während der Kompilierung eine Cache-Zeilengröße annehmen möchten, definieren Sie diese einfach KNOWN_L1_CACHE_LINE_SIZE.

Hoffe das hilft!

Benchmark-Programm:

#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);
    }
}
GManNickG
quelle
36
Ich habe den Vorschlag verfasst, tolle Antwort! Um einen Punkt zu verdeutlichen, den Sie gemacht haben: "Ich würde fast immer erwarten, dass diese Werte gleich sind. Ich glaube, der einzige Grund, warum sie separat deklariert werden, ist der Vollständigkeit halber." Ja, sie sollten immer gleich sein, es sei denn: 1) die ISA hat mit unterschiedlichen Cacheline-Größen geliefert und es ist kein Zielbogen angegeben; 2) Sie zielen auf eine virtuelle ISA wie WebAssembly ab, für die die tatsächliche ISA unbekannt ist (dann erhalten Sie die bestmögliche Leistung). Bei constexpr: Es ist erforderlich, constexpr zu verwenden, damit der Wert zur Bestimmung des Strukturlayouts verwendet werden kann. Laufzeitwerte sind unter anderen Umständen nützlich.
JF Bastien
16

Ich würde fast immer erwarten, dass diese Werte gleich sind.

In Bezug auf das oben Gesagte möchte ich einen kleinen Beitrag zur akzeptierten Antwort leisten. Vor einiger Zeit habe ich einen sehr guten Anwendungsfall gesehen, bei dem diese beiden in der follyBibliothek separat definiert werden sollten . Bitte beachten Sie die Einschränkung zum Intel Sandy Bridge-Prozessor.

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?");
Validus Oculus
quelle
1
Ja, Intels räumlicher L2-Prefetcher (Nehalem und höher, einschließlich der gesamten Sandybridge-Familie) versucht, ausgerichtete Paare von Cache-Zeilen zu vervollständigen (wenn freie Bandbreite vorhanden ist). Das Vorabrufen von Daten in L1 und L2 enthält einen Auszug aus dem Optimierungshandbuch von Intel. In welchem ​​Zustand beginnt der DCU-Prefetcher mit dem Prefetching? hat einige Details darüber, wann genau sie auslösen.
Peter Cordes
1
Beachten Sie, dass eine Änderung des Werts in Abhängigkeit von -march=sandybridgevs. -march=znver1(ryzen) in x86 zu einer Inkompatibilität des Strukturlayouts führen kann, wenn unterschiedlich kompilierte Objekte oder Bibliotheken verknüpft werden. ( clang-developers.42468.n3.nabble.com/… ). Aus diesem Grund implementiert clang immer noch keine der Konstanten. Die Verwendung von destruktiv = 128 für x86 im Allgemeinen ist eine gute Idee. Eine konservative Umgebung ist überall sicher.
Peter Cordes
0

Ich habe den obigen Code getestet, aber ich denke, es gibt einen kleinen Fehler, der uns daran hindert, die zugrunde liegende Funktion zu verstehen. Eine einzelne Cache-Zeile sollte nicht zwischen zwei verschiedenen Atomics geteilt werden, um eine falsche Freigabe zu verhindern. Ich habe die Definition dieser Strukturen geändert.

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

Und der daraus resultierende Lauf:

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

Ich habe im letzten Ergebnis große Unterschiede festgestellt, aber nie genau einen Kern für dieses spezielle Problem verwendet. Auf jeden Fall gingen 2 Xeon 2690V2 aus und aus verschiedenen Läufen mit 64 oder 128 heraus, denn hardware_constructive_interference_size = 12864 war mehr als genug und 128 eine sehr schlechte Nutzung des verfügbaren Caches.

Mir wurde plötzlich klar, dass Ihre Frage mir hilft zu verstehen, wovon Jeff Preshing sprach, alles über Nutzlast !?

Gold
quelle