Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Werbeanzeige

1

27.04.2014, 22:04

if-Abfragen komplett rausoptimieren

Hi,

ich habe ein kleines Programm geschrieben, bei dem klassische Verzweigungen (mit if) komplett rausoptimniert werden.
Genauer gesagt kann man durch einen Trick die Ifs schon zur Compilezeit auflösen.
Das ganze geht mit Templates in C++ und bietet einen enormen Performancegewinn, unter den Testbedingungen.

Ob ich das ganze praktisch nutzen werde weiß ich noch nicht. Aber eine Verwendung hätte ich schon dafür.

Würde gerne mal wissen was ihr dazu meint.

Die Klasse "Branch" verzweigt klassich.
Die Klasse "Template" verzweigt zur Kompilezeit.

Im Test:
Die Performance verdoppelt, oder vervielfacht sich, je nach Testfall, wenn man "Template" nutzt.
Ich überlege auf 8 Argumente zu erweitern.

C-/C++-Quelltext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <cstdlib>
#include <iostream>

#include <windows.h> 
#include <time.h>

int Data = 0;
int Data2 = 0;

class Branch
{
public:
    void Work(const bool Arg1, const bool Arg2, const int Iterations)
    {
        for (int n = 0; n < Iterations; ++n)
        {
            if (Arg1)
            {
                Data = Data2;
                Data2 += 1;;
            }

            if (Arg2)
            {
                Data = Data2;
                Data2 += 2;;
            }
        }
    };
};

template<const bool Arg1, const bool Arg2>
class Template
{
public:
    void Work(const int Iterations)
    {
        for (int n = 0; n < Iterations; ++n)
        {
            if (Arg1)
            {
                Data = Data2;
                Data2 += 1;;
            }

            if (Arg2)
            {
                Data = Data2;
                Data2 += 2;;
            }
        }
    };
};


int main(int argc, wchar_t* argv[])
{
    //testobjekte
    Template<false, false> TemplateObj0;
    Template<true, false> TemplateObj1;
    Template<false, true> TemplateObj2;
    Template<true, true> TemplateObj3;

    Branch BranchObj;


    //einstellungen (volatile verhindert optimierungen)
    volatile bool Arg1 = false;
    volatile bool Arg2 = true;
    volatile int Iterations = 1000000000;
    volatile int TemplateNum = (int)Arg1 + ((int)Arg2 * 2);
    std::cout << "TemplateNum" << TemplateNum << "\n";

    //performance messungs variablen
    LONGLONG g_Frequency;
    QueryPerformanceFrequency((LARGE_INTEGER*)&g_Frequency);

    //test branch
    {
        LONGLONG g_CurentCount, g_LastCount;
        QueryPerformanceCounter((LARGE_INTEGER*)&g_CurentCount);

        Data = 0;
        Data2 = 0;
        BranchObj.Work(Arg1, Arg2, Iterations);

        QueryPerformanceCounter((LARGE_INTEGER*)&g_LastCount);
        double dTimeDiff = (((double)(g_LastCount - g_CurentCount)) / ((double)g_Frequency));
        std::cout << dTimeDiff << "\n";
        std::cout << "Result " << Data << "\n";
    }

    //test template
    {
        LONGLONG g_CurentCount, g_LastCount;
        QueryPerformanceCounter((LARGE_INTEGER*)&g_CurentCount);

        Data = 0;
        Data2 = 0;
        switch (TemplateNum)
        {
        case 0:
            TemplateObj0.Work(Iterations);
            break;
        case 1:
            TemplateObj1.Work(Iterations);
            break;
        case 2:
            TemplateObj2.Work(Iterations);
            break;
        case 3:
            TemplateObj3.Work(Iterations);
            break;
        }

        QueryPerformanceCounter((LARGE_INTEGER*)&g_LastCount);
        double dTimeDiff = (((double)(g_LastCount - g_CurentCount)) / ((double)g_Frequency));
        std::cout << dTimeDiff << "\n";
        std::cout << "Result " << Data << "\n";
    }

    std::getchar();

    return 0;
}



Seht ihr da Probleme?

Nutzt ihr solche Pattern auch?

MFG
Bilder zu meinem Projekt: ParSim

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Horus« (28.04.2014, 08:25)


2

27.04.2014, 22:17

Ich persönlich sehe keinen Nutzen dabei, wenn ich alle möglichen Verzweigungen ein Templateobjekt anlegen muss um nachher noch auszuwerten, welches ich dann nehme.

Bei 8 argumenten hast du dann schon 2^8 mögliche verzweigungen, also 256 case-Anweisungen? Oder habe ich in dem Pattern was missverstanden?
EnvisionGame(); EnableGame(); AchieveGame(); - Visionen kann man viele haben. Sie umzusetzen und auf das Ergebnis stolz zu sein ist die eigentliche Kunst.

Evrey

Treue Seele

Beiträge: 245

Beruf: Weltherrscher

  • Private Nachricht senden

3

28.04.2014, 00:34

C-/C++-Quelltext

1
2
3
4
int main(int _argc, char** _argv) noexcept {
  asm volatile("lock cmpxchg8b %eax");
  return 0;
} // ::main
(Dieses kleine Biest vermochte einst x86-Prozessoren lahm zu legen.)

=> Und er blogt unter Hackish.Codes D:

Tobiking

1x Rätselkönig

  • Private Nachricht senden

4

28.04.2014, 01:10

Konstante Ausdrücke und Bedingungen kann der Compiler selber wegoptimieren. Das von Hand zu tun ist entsprechend unnötig.

Der Knackpunkt in deinem Benchmark ist das volatile. Es deaktiviert nicht einfach nur Optimierungen. Du sagst damit dem Compiler, dass Arg1 und Arg2 jederzeit von Außen (z.B. von einem anderen Thread) verändert werden können. Deswegen muss der Compiler den Branch (das If) in die Schleife stecken. Wenn sich Arg1 oder Arg2 während der Iterationen ändert, wird bei der nächsten Iteration der neue Wert benutzt. In deinem Template Code ist der Branch (das switch-case) außerhalb der Schleife. Damit werden alle Iterationen gleich ausgeführt, unabhängig davon ob sich Arg1 oder Arg2 ändern. Lässt du aber das volatile weg, sind beide Varianten vom Verhalten identisch, haben dann aber auch keinen Zeitunterschied mehr.

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

5

28.04.2014, 06:39

Wer misst misst Mist.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

6

28.04.2014, 08:12


Das wollte ich auch sagen :D
Die Zensurfunktion des Forums funktioniert leider nicht für zusammengesetzte Wörter. :(

7

28.04.2014, 08:25

@iSmokiieZz
Ja es würden dann 256 Templates. Nach 32 Items hätte ich die Verzweigungen der Switch raus. Ich rechne mit tausenden Items.
Außerdem wird aus der Switch noch eine vtable oder ein Funktionspointer-Ararray.
Die main ist nur zum testen der Klassen.

@Tobiking

Zitat

Konstante Ausdrücke und Bedingungen kann der Compiler selber wegoptimieren. Das von Hand zu tun ist entsprechend unnötig.

Das kenne ich bisschen anders. if (Arg1) kann nur wegoptimiert werden wenn es zur compilezeit bekannt ist.
Es const bool zu übergeben reicht dazu nicht aus. Es kann ja sonst woher kommen und zufällig sein.

Das Volatile ist nötig, da er in der main nicht rumoptimiert. So werden die Testklassen "richtig" aufgerufen. In den Testklassen (deren performance gemessen wird) sind die Args const, dort ist nichts volatile.
Lasse ich das volatile weg gehts gleich schnell das ist klar. Im realen Anwendungsfall sind die jedoch nicht zu compilezeit bekannt. Die sind also hier nötig um den realen Anwendungsfall nachzubilden.

Zitat

Wenn sich Arg1 oder Arg2 während der Iterationen ändert, wird bei der nächsten Iteration der neue Wert benutzt. In deinem Template Code ist der Branch (das switch-case) außerhalb der Schleife.


Jenau darum geht es. Einmal erzeugt der Compiler einen Code mit klass branches und einmal einen code ohne branches in verschiedenen Varianten.

Es geht darum das ich viele Items verarbeiten will, die sich unterscheiden. Dabei habe ich meherer Möglichkeiten.

1. die lege ich alle hintereinander und brachche mit if oder der vtable/vererbung.
2. ich lege Templates an, die jeweils eine Gruppe gleichartiger Items beinhalten und verarbeiten. Dort geht es ohne branches, wei ein entsprechendes template existiert.

Der performancegewinnd durch Verarbeitung in gleichartigen Gruppen (ohne branches) ist sehr deutlich.


@Bluecobold
Messen macht schon Sinn.
Ich mache ja irgendwelche Simulationssoftware. Da brummt die CPU.

Beispiel:
Weder die disassembly noch der gesunde Menschenverstand machten es möglich z.B. Cache-Effekte vorauszusagen.
Genau so mit der Frage ob die PPL oder OpenMP in einen Anwendungsfall schnller ist. Einfach Messen...
Usw.

MFG



EDIT: das mit den if-Abfragen hab ich mal geändert :)
Bilder zu meinem Projekt: ParSim

8

28.04.2014, 08:59

Zitat

Du verhinderst also Optimierungen und wunderst dich dann, dass es nicht optimal läuft :D


Jein. Ich will die verhindern, weil es ein Modell ist, mit dem ich einen realen Anwendungsfall konstruieren will.

Aber egal ich habe das volatile entfernt.
Die Variablen zum testen sind nun:

bool Arg1 = (rand()%2);
bool Arg2 = (rand() % 2);
int Iterations = 1000000000 + (rand() % 2);
int TemplateNum = (int)Arg1 + ((int)Arg2 * 2);

Also sind sie nicht zur Compilezeit bekannt.
Und nicht volatile.
So ist es auch im Realfall.

Damit ändert sich an den Ergebnissen nichts.
Weiterhin ist es mit den Templates mindestens doppels so schnell.

MFG
Bilder zu meinem Projekt: ParSim

TrommlBomml

Community-Fossil

Beiträge: 2 117

Wohnort: Berlin

Beruf: Software-Entwickler

  • Private Nachricht senden

9

28.04.2014, 09:09

Ist das wirklich sinnvoll? Das geht mir ja persönlich schon sehr in Richtung virtuelle Methoden sind langsam und muss man vermeiden. Macht das wirklich so viel aus?

Schrompf

Alter Hase

Beiträge: 1 470

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

10

28.04.2014, 09:11

Ich habe den Testfall nicht konkret nachgemessen, aber ich würde wie alle anderen auch vermuten, dass der Compiler das sowieso optimiert. Entweder die Bedingungen sind zur Compile Time bekannt, dann kann der Compiler das optimieren (Release Build und nach Möglichkeit LTCG vorausgesetzt). Oder die Bedingungen sind zur Laufzeit variabel, dann darf er das nicht statisch auflösen.
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

Werbeanzeige