Moin,
ich habe mir die letzte Zeit über einige Gedanken über das Thema Metin2 Source & Branch Prediction gemacht. Wer nichts mit dem Begriff anfangen kann hier eine kurze Beschreibung.
Stellt euch diese Weiche vor.
Bitte melden Sie sich an, um dieses Bild zu sehen.
Zusätlich stellt ihr euch vor, dass wir im Jahr 1810 sind, lange vor der Zeit von Radio- und Weitstreckenkommunikation, und ihr diese Weiche für die vorbeifahrenden Züge bedienen müsst.
Wenn ihr den zug hört wisst ihr noch nicht in welche Richtung der Zug fahren möchte.Also haltet ihr den Zug an und fragt den Fahrer wo er hin möchte. Anhand seiner Aussage stellt ihr die Weiche.
Züge sind zu der Zeit äußerst schwer und benötigen viel Zeit um zu stoppen und wieder Geschwindigkeit aufzunehmen.
Kann man diesen Workflow verbessern? - Ihr ratet in welche Richtung der Zug fahren will!
- Wenn ihr richtig geraten habt wird der Zug weiter fahren
- Wenn ihr falsch geraten habt wird der Zugführer den Zug stoppen. Zurück fahren, euch anschreien die Weiche zu stellen und dann weiter fahren
Wenn ihr jedes Mal richtig ratet wird der Zug niemals stoppen müssen.
Wenn ihr euch zu oft verschätzt wird der Zug viel Zeit damit verbringen zu stoppen, zurück zu fahren und neu zu starten.
Nun stellt euch ein IF-Statement vor. Dieses ist auf Prozessorebene eine Branchanweisung.
Bitte melden Sie sich an, um dieses Bild zu sehen.
Du bist ein Prozessor und du siehst einen Branch(Zweig). Du hast keine Ahnungin welche Richung er geht. Was tust du?
Du hältst die Ausführung and und wartest, bis die vorherigen Anweisungen vollständig sind. Dann fährst du den richtigen Weg weiter.
Merksatz:
Moderne Prozessoren sind kompliziert und haben lange Pipelines. So baruchen sie ewig zum "aufwärmen" und "verlangsamen".
Kann man diesen Workflow verbessern? - Du ratest in welche Richtung der Zweig gehen wird!
- Wenn du richtig geraten hast, wird die Ausführen weiter gehen.
- Wenn du falsch geraten hast muss die Pipeline geleert werden und zurück zum Zweig gehen. Dann kannst du den anderen Weg neu starten.
Wenn du jedes Mal richtig ratest, wird die Ausführung niemals aufhören müssen.
Wenn du zu oft falsch ratest, verbringst du viel Zeit damit den Zweig zurückzurollen und neu zu starten.
Das ist eine Branch Prediction. Ich gebe zu, dass dies nicht das beste Beispiel ist, da der Zug einfach die Richtung mit einer Fahne signalisieren könnte. Aber der Prozessor weiß bis zum letzten Moment nicht in welche Richtung ein Branch gehen wird.
Also, wie würdest du strategisch vorgehen um die Zeit zu minimieren, in der der Zug zurück fahren und den anderen Weg fahren muss? Du siehst die Vergangenheit an! Wenn der Zug zu 99% der Zeit nach links fährt, dann vermutest du links. Wenn links und rechts sich abwechseln, dann wechselst du auch deine Vermutung. Wenn der Zug jedes 3. Mal links fährt, dann rätst du auch so ...
Mit anderen Worten: Du versuchst ein Muster zu erkennen und ihm zu folgen.
Können erfahrene Coder hier vielleicht mal ihre Gedanken teilen? Gibt der Metin2 Source genügend Einstiegspunkte her um dort eventuell die Performance zu boosten?
Als Anmerkung:
Das Beispiel, welches ich in der Erklärung angedruckt habe
lässt sich wie folgt ändern um einen Performance-Boost zu erzielen:
Benchmarks: Core i7 920 @ 3.5 GHz
C++ - Visual Studio 2010 - x64 Release
Kompletter Code:
- #include <algorithm>
- #include <ctime>
- #include <iostream>
- int main()
- {
- // Generate data
- const unsigned arraySize = 32768;
- int data[arraySize];
- for (unsigned c = 0; c < arraySize; ++c)
- data[c] = std::rand() % 256;
- // Test
- clock_t start = clock();
- long long sum = 0;
- for (unsigned i = 0; i < 100000; ++i)
- {
- // Primary loop
- for (unsigned c = 0; c < arraySize; ++c)
- {
- if (data[c] >= 128)
- sum += data[c];
- }
- }
- double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
- std::cout << elapsedTime << std::endl;
- std::cout << "sum = " << sum << std::endl;
- }
Danke für euer Interesse