Sollte ich mir in C ++ die Mühe machen, Variablen zwischenzuspeichern, oder den Compiler die Optimierung durchführen lassen? (Aliasing)

114

Betrachten Sie den folgenden Code ( pist vom Typ unsigned char*und bitmap->widthhat einen ganzzahligen Typ, der genau unbekannt ist und davon abhängt, welche Version einer externen Bibliothek wir verwenden):

for (unsigned x = 0;  x < static_cast<unsigned>(bitmap->width);  ++x)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

Lohnt es sich, es zu optimieren [..]

Könnte es einen Fall geben, in dem dies durch Schreiben zu effizienteren Ergebnissen führen könnte:

unsigned width(static_cast<unsigned>(bitmap->width));
for (unsigned x = 0;  x < width;  ++x)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

... oder ist das für den Compiler trivial zu optimieren?

Was würden Sie als "besseren" Code betrachten?

Anmerkung des Herausgebers (Ike): Für diejenigen, die sich über den Streiktext wundern, war die ursprüngliche Frage, wie formuliert, gefährlich nahe am Gebiet außerhalb des Themas und trotz positiver Rückmeldungen sehr nahe daran, geschlossen zu werden. Diese wurden gestrichen. Bitte bestrafen Sie jedoch nicht die Antwortenden, die diese angeschlagenen Abschnitte der Frage angesprochen haben.

Yaron Cohen-Tal
quelle
19
Wenn *pes vom selben Typ ist wie widthdann, ist es nicht trivial zu optimieren, da es innerhalb der Schleife darauf pverweisen widthund es ändern könnte.
Emlai
31
Die Frage, ob der Compiler eine bestimmte Operation optimiert, ist normalerweise die falsche Frage. Was Sie (normalerweise) letztendlich interessiert, ist, welche Version schneller läuft, die Sie einfach messen sollten.
SirGuy
4
@GuyGreer Ich stimme zu, obwohl ich sagen würde, dass die Frage gut oder zumindest interessant ist. Leider lautet die Antwort "Sie müssen sie pro Anwendungsfall messen". Der Grund dafür ist, dass die Funktionalität portabel ist, die Leistung jedoch nicht. Es hängt also tatsächlich von jedem Teil des Erstellungsprozesses ab, angefangen beim Compiler bis hin zum Ziel am Zielstandort (Kombination aus Betriebssystem und Hardware). Und natürlich ist die beste Vermutung, dass der Compiler dabei schlauer ist als der Mensch.
luk32
19
Wenn ich ein Compiler wäre, würde ich sehen, dass Ihre beiden Beispiele nicht gleich sind. Es ist möglich, dass pauf den gleichen Speicher wie verweist bitmap->width. Daher kann ich das erste Beispiel nicht legal auf das zweite optimieren.
Mysticial
4
Wo ist "p" gespeichert? Ich würde vorschlagen, dass Sie einen wirklich großen Leistungsgewinn erzielen, wenn Sie so etwas wie "char * einschränken p2 = p;" und dann "p2" anstelle von "p" in Ihrer Schleife verwenden. Wenn Sie möchten, dass die Änderungen an "p2" wieder auf p angewendet werden, verwenden Sie "p + = (p2-p);". Beachten Sie, dass kein Zeiger, der innerhalb der Lebensdauer von p2 von einem Zeiger geschrieben wurde, der nicht aus p2 kopiert wurde, mit einem von p2 kopierten Zeiger gelesen werden kann oder umgekehrt, und dass nach der Lebensdauer von p2 keine Kopie von p2 für irgendeinen Zweck verwendet werden darf, aber ein Compiler kann diese verwenden Fakten, um Optimierungen zu ermöglichen, die auf keine andere Weise erreicht werden können.
Supercat

Antworten:

81

Auf den ersten Blick dachte ich, der Compiler könnte für beide Versionen eine äquivalente Assembly mit aktivierten Optimierungsflags generieren. Als ich es überprüfte, war ich überrascht, das Ergebnis zu sehen:

Quelle unoptimized.cpp

Hinweis: Dieser Code soll nicht ausgeführt werden.

struct bitmap_t
{
    long long width;
} bitmap;

int main(int argc, char** argv)
{
    for (unsigned x = 0 ; x < static_cast<unsigned>(bitmap.width) ; ++x)
    {
        argv[x][0] = '\0';
    }
    return 0;
}

Quelle optimized.cpp

Hinweis: Dieser Code soll nicht ausgeführt werden.

struct bitmap_t
{
    long long width;
} bitmap;

int main(int argc, char** argv)
{
    const unsigned width = static_cast<unsigned>(bitmap.width);
    for (unsigned x = 0 ; x < width ; ++x)
    {
        argv[x][0] = '\0';
    }
    return 0;
}

Zusammenstellung

  • $ g++ -s -O3 unoptimized.cpp
  • $ g++ -s -O3 optimized.cpp

Montage (nicht optimiert)

    .file   "unoptimized.cpp"
    .text
    .p2align 4,,15
.globl main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    .cfi_personality 0x3,__gxx_personality_v0
    movl    bitmap(%rip), %eax
    testl   %eax, %eax
    je  .L2
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
.L3:
    mov %eax, %edx
    addl    $1, %eax
    movq    (%rsi,%rdx,8), %rdx
    movb    $0, (%rdx)
    cmpl    bitmap(%rip), %eax
    jb  .L3
.L2:
    xorl    %eax, %eax
    ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
.globl bitmap
    .bss
    .align 8
    .type   bitmap, @object
    .size   bitmap, 8
bitmap:
    .zero   8
    .ident  "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-16)"
    .section    .note.GNU-stack,"",@progbits

Montage (optimiert.s)

    .file   "optimized.cpp"
    .text
    .p2align 4,,15
.globl main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    .cfi_personality 0x3,__gxx_personality_v0
    movl    bitmap(%rip), %eax
    testl   %eax, %eax
    je  .L2
    subl    $1, %eax
    leaq    8(,%rax,8), %rcx
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
.L3:
    movq    (%rsi,%rax), %rdx
    addq    $8, %rax
    cmpq    %rcx, %rax
    movb    $0, (%rdx)
    jne .L3
.L2:
    xorl    %eax, %eax
    ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
.globl bitmap
    .bss
    .align 8
    .type   bitmap, @object
    .size   bitmap, 8
bitmap:
    .zero   8
    .ident  "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-16)"
    .section    .note.GNU-stack,"",@progbits

diff

$ diff -uN unoptimized.s optimized.s
--- unoptimized.s   2015-11-24 16:11:55.837922223 +0000
+++ optimized.s 2015-11-24 16:12:02.628922941 +0000
@@ -1,4 +1,4 @@
-   .file   "unoptimized.cpp"
+   .file   "optimized.cpp"
    .text
    .p2align 4,,15
 .globl main
@@ -10,16 +10,17 @@
    movl    bitmap(%rip), %eax
    testl   %eax, %eax
    je  .L2
+   subl    $1, %eax
+   leaq    8(,%rax,8), %rcx
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
 .L3:
-   mov %eax, %edx
-   addl    $1, %eax
-   movq    (%rsi,%rdx,8), %rdx
+   movq    (%rsi,%rax), %rdx
+   addq    $8, %rax
+   cmpq    %rcx, %rax
    movb    $0, (%rdx)
-   cmpl    bitmap(%rip), %eax
-   jb  .L3
+   jne .L3
 .L2:
    xorl    %eax, %eax
    ret

Die generierte Assembly für die optimierte Version lädt tatsächlich ( lea) die widthKonstante im Gegensatz zur nicht optimierten Version, die den widthOffset bei jeder Iteration berechnet ( movq).

Wenn ich Zeit habe, poste ich irgendwann einen Benchmark dafür. Gute Frage.

YSC
quelle
3
Es wäre interessant zu sehen, ob der Code anders generiert wurde, wenn Sie ihn const unsignedanstatt nur unsignedim nicht optimierten Fall umwandeln.
Mark Ransom
2
@ MarkRansom Ich denke, es sollte keinen Unterschied machen: Das "Versprechen", const zu sein, ist nur während des einzelnen Vergleichs, nicht für die gesamte Schleife
Hagen von Eitzen
13
Bitte NIEMALS verwenden , um die Funktion mainzu Test für eine Optimierung. Gcc markiert es absichtlich als kalt und deaktiviert daher einige Optimierungen dafür. Ich weiß nicht, ob das hier der Fall ist, aber das ist eine wichtige Angewohnheit.
Marc Glisse
3
@MarcGlisse Du hast 100% Recht. Ich habe es in Eile geschrieben, das werde ich verbessern.
YSC
3
Hier ist ein Link zu beiden Funktionen in einer Kompilierungseinheit auf Godbolt , vorausgesetzt, es bitmaphandelt sich um eine globale. Die Nicht-CSEd-Version verwendet einen Speicheroperanden cmp, was in diesem Fall für perf kein Problem darstellt. Wenn es sich um ein lokales Element handelt, kann der Compiler davon ausgehen, dass andere Zeiger nichts davon "wissen" und darauf verweisen können. Es ist keine schlechte Idee, Ausdrücke mit Globalen in temporären Variablen zu speichern, solange dies die Lesbarkeit verbessert (oder nicht beeinträchtigt) oder wenn die Leistung kritisch ist. Wenn nicht viel los ist, können solche Einheimischen normalerweise nur in Registern leben und niemals verschüttet werden.
Peter Cordes
38

Es gibt tatsächlich nicht genügend Informationen aus Ihrem Code-Snippet, um sie erkennen zu können, und das einzige, woran ich denken kann, ist Aliasing. Aus unserer Sicht ist es ziemlich klar , dass Sie nicht möchten , pund bitmapum auf die gleiche Stelle im Speicher, aber der Compiler nicht weiß , dass und (wegen pder Art ist char*) hat der Compiler diesen Code arbeiten zu lassen , auch wenn pund bitmapüberlappen.

Dies bedeutet in diesem Fall, dass, wenn sich die Schleife bitmap->widthdurch den Zeiger ändert p, dies beim bitmap->widthspäteren erneuten Lesen gesehen werden muss , was wiederum bedeutet, dass das Speichern in einer lokalen Variablen unzulässig wäre.

Abgesehen davon glaube ich, dass einige Compiler tatsächlich manchmal zwei Versionen desselben Codes generieren (ich habe Indizien dafür gesehen, aber nie direkt nach Informationen darüber gesucht, was der Compiler in diesem Fall tut) und schnell prüfen, ob die Zeiger vorhanden sind Alias ​​und führen Sie den schnelleren Code aus, wenn er feststellt, dass dies in Ordnung ist.

Abgesehen davon stehe ich zu meinem Kommentar, einfach die Leistung der beiden Versionen zu messen. Mein Geld besteht darin, keinen konsistenten Leistungsunterschied zwischen den beiden Versionen des Codes zu sehen.

Meiner Meinung nach sind Fragen wie diese in Ordnung, wenn Sie sich mit Theorien und Techniken zur Compileroptimierung vertraut machen möchten. Sie sind jedoch Zeitverschwendung (eine nutzlose Mikrooptimierung), wenn Ihr Endziel darin besteht, das Programm schneller laufen zu lassen.

SirGuy
quelle
1
@ GuyGreer: Es ist ein wichtiger Optimierungsblocker. Ich halte es für bedauerlich, dass sich die Sprachregeln auf Regeln über effektive Typen konzentrieren, anstatt Situationen zu identifizieren, in denen das Schreiben und Lesen verschiedener Elemente nicht sequenziert wird oder nicht. Regeln, die in einem solchen Begriff geschrieben wurden, könnten die Anforderungen von Compilern und Programmierern viel besser erfüllen als die gegenwärtigen.
Supercat
3
@GuyGreer - wäre ein restrictQualifizierer in diesem Fall nicht die Antwort auf das Aliasing-Problem?
LThode
4
Nach meiner Erfahrung restrictist weitgehend ein Hit-and-Miss. MSVC ist der einzige Compiler, den ich gesehen habe, der es richtig zu machen scheint. ICC verliert Aliasing-Informationen durch Funktionsaufrufe, auch wenn sie inline sind. Und GCC erhält normalerweise keinen Vorteil, es sei denn, Sie deklarieren jeden einzelnen Eingabeparameter als restrict(einschließlich)this für Mitgliedsfunktionen).
Mysticial
1
@Mystical: Eine Sache, an die Sie sich erinnern sollten, ist, dass charalle Typen Aliase sind. Wenn Sie also ein Zeichen * haben, müssen Sie es verwendenrestrict alles verwenden. Oder wenn Sie die strengen Aliasing-Regeln von GCC mit deaktiviert haben, wird -fno-strict-aliasingalles als möglicher Alias ​​angesehen.
Zan Lynx
1
@ Ray Der neueste Vorschlag für eine restrictähnliche Semantik in C ++ ist N4150 .
TC
24

Ok, Leute, also habe ich gemessen GCC -O3(mit GCC 4.9 unter Linux x64).

Es stellt sich heraus, dass die zweite Version 54% schneller läuft!

Also, ich denke Aliasing ist die Sache, ich hatte nicht darüber nachgedacht.

[Bearbeiten]

Ich habe die erste Version mit allen mit definierten Zeigern erneut versucht __restrict__, und die Ergebnisse sind dieselben. Seltsam .. Entweder ist Aliasing nicht das Problem, oder aus irgendeinem Grund optimiert der Compiler es selbst mit nicht gut __restrict__.

[Bearbeiten 2]

Ok, ich glaube, ich konnte so ziemlich beweisen, dass Aliasing das Problem ist. Ich wiederholte meinen ursprünglichen Test, diesmal mit einem Array anstelle eines Zeigers:

const std::size_t n = 0x80000000ull;
bitmap->width = n;
static unsigned char d[n*3];
std::size_t i=0;
for (unsigned x = 0;  x < static_cast<unsigned>(bitmap->width);  ++x)
{
    d[i++] = 0xAA;
    d[i++] = 0xBB;
    d[i++] = 0xCC;
}

Und gemessen (musste "-mcmodel = large" verwenden, um es zu verknüpfen). Dann habe ich versucht:

const std::size_t n = 0x80000000ull;
bitmap->width = n;
static unsigned char d[n*3];
std::size_t i=0;
unsigned width(static_cast<unsigned>(bitmap->width));
for (unsigned x = 0;  x < width;  ++x)
{
    d[i++] = 0xAA;
    d[i++] = 0xBB;
    d[i++] = 0xCC;
}

Die Messergebnisse waren die gleichen - Scheint, als ob der Compiler es selbst optimieren konnte.

Dann habe ich die Originalcodes (mit einem Zeiger p) ausprobiert , diesmal wenn sie pvom Typ sind std::uint16_t*. Auch hier waren die Ergebnisse dieselben - aufgrund des strengen Aliasing. Dann habe ich versucht, mit "-fno-strict-aliasing" zu bauen, und wieder einen Zeitunterschied festgestellt.

Yaron Cohen-Tal
quelle
4
Dies scheint ein Kommentar zu sein, obwohl es die Frage technisch beantwortet. Beachten Sie auch, dass Sie leider nicht nachgewiesen haben, dass Aliasing die Sache war. Es scheint wahrscheinlich, sicherlich plausibel, aber das ist etwas anderes als die Schlussfolgerung, dass es das war.
SirGuy
@GuyGreer: Siehe meine [bearbeiten 2] - jetzt denke ich, dass es ziemlich bewiesen ist.
Yaron Cohen-Tal
2
Ich frage mich nur, warum Sie angefangen haben, die Variable "i" zu verwenden, wenn Sie "x" in Ihrer Schleife haben.
Jesper Madsen
1
Ist es nur ich, der es schwierig findet, den Satz 54% schneller zu verstehen? Meinst du, es ist das 1,54-fache der Geschwindigkeit des nicht optimierten oder etwas anderes?
Roddy
3
@ YaronCohen-Tal also doppelt so schnell? Beeindruckend, aber nicht das, was ich unter "54% schneller" verstanden hätte!
Roddy
24

Andere Antworten haben darauf hingewiesen, dass das Heben der Zeigeroperation aus der Schleife das definierte Verhalten aufgrund von Aliasing-Regeln ändern kann, die es char ermöglichen, irgendetwas zu aliasen, und daher keine zulässige Optimierung für einen Compiler darstellt, obwohl dies in den meisten Fällen für einen Menschen offensichtlich korrekt ist Programmierer.

Sie haben auch darauf hingewiesen, dass das Heben des Betriebs aus der Schleife normalerweise, aber nicht immer eine Verbesserung unter dem Gesichtspunkt der Leistung darstellt und unter dem Gesichtspunkt der Lesbarkeit häufig negativ ist.

Ich möchte darauf hinweisen, dass es oft einen "dritten Weg" gibt. Anstatt bis zur gewünschten Anzahl von Iterationen zu zählen, können Sie bis auf Null herunterzählen. Dies bedeutet, dass die Anzahl der Iterationen zu Beginn der Schleife nur einmal benötigt wird und danach nicht mehr gespeichert werden muss. Besser noch auf Assembler-Ebene ist häufig kein expliziter Vergleich erforderlich, da bei der Dekrementierungsoperation normalerweise Flags gesetzt werden, die angeben, ob der Zähler sowohl vor (Übertragsflag) als auch nach (Nullflag) der Dekrementierung Null war.

for (unsigned x = static_cast<unsigned>(bitmap->width);x > 0;  x--)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

Beachten Sie, dass diese Version der Schleife x-Werte im Bereich 1..width anstelle des Bereichs 0 .. (width-1) liefert. Das spielt in Ihrem Fall keine Rolle, da Sie x eigentlich für nichts verwenden, aber es ist etwas, das Sie beachten sollten. Wenn Sie eine Countdown-Schleife mit x-Werten im Bereich 0 .. (Breite-1) möchten, können Sie dies tun.

for (unsigned x = static_cast<unsigned>(bitmap->width); x-- > 0;)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

Sie können die Casts in den obigen Beispielen auch entfernen, wenn Sie möchten, ohne sich über die Auswirkungen auf die Vergleichsregeln Gedanken machen zu müssen, da Sie mit bitmap-> width nur eine Variable direkt zuweisen.

Plugwash
quelle
2
Ich habe gesehen, dass dieser zweite Fall so formatiert ist x --> 0, dass der Operator "Downto" angezeigt wird. Ziemlich witzig. PS Ich halte eine Variable für die Endbedingung nicht für negativ für die Lesbarkeit, es kann tatsächlich das Gegenteil sein.
Mark Ransom
Es kommt wirklich darauf an, dass eine Aussage manchmal so schrecklich wird, dass das Aufteilen in mehrere Aussagen die Lesbarkeit verbessert, aber ich glaube nicht, dass dies hier der Fall ist.
Plugwash
1
+1 Gute Beobachtung, obwohl ich argumentieren würde, dass das Anheben static_cast<unsigned>(bitmap->width)und Verwenden widthstattdessen in der Schleife tatsächlich eine Verbesserung der Lesbarkeit darstellt, da der Leser jetzt weniger Dinge pro Zeile analysieren muss. Die Ansichten anderer können jedoch abweichen.
SirGuy
1
Es gibt viele andere Situationen, in denen das Abwärtszählen überlegen ist (z. B. beim Entfernen von Elementen aus einer Liste). Ich weiß nicht, warum das nicht öfter gemacht wird.
Ian Goldby
3
Wenn Sie Schleifen schreiben möchten, die eher dem optimalen asm ähneln, verwenden Sie do { } while(), da Sie in ASM Schleifen mit einem bedingten Zweig am Ende erstellen. Die üblichen for(){}und while(){}Schleifen erfordern zusätzliche Anweisungen, um die Schleifenbedingung einmal vor der Schleife zu testen, wenn der Compiler nicht beweisen kann, dass sie immer mindestens einmal ausgeführt wird. Verwenden Sie auf jeden Fall for()oder while()wenn es nützlich ist, um zu überprüfen, ob die Schleife überhaupt einmal ausgeführt werden soll oder wann sie besser lesbar ist.
Peter Cordes
11

Das einzige, was hier die Optimierung verhindern kann, ist die strikte Aliasing-Regel . Kurzum :

"Striktes Aliasing ist eine Annahme des C- (oder C ++) Compilers, dass die Dereferenzierung von Zeigern auf Objekte unterschiedlichen Typs niemals auf denselben Speicherort verweist (dh auf einander Alias)."

[…]

Die Ausnahme von der Regel ist a char*, die auf einen beliebigen Typ verweisen darf.

Die Ausnahme gilt auch für unsignedund signed charZeiger.

Dies ist in Ihrem Code der Fall: Sie ändern, *pdurch pwelche ein unsigned char*, daher muss der Compiler davon ausgehen, dass er darauf verweisen könnte bitmap->width. Daher ist das Caching von bitmap->widtheine ungültige Optimierung. Dieses optimierungsverhindernde Verhalten wird in der Antwort von YSC gezeigt .

Wenn und nur wenn pauf einen Nicht- charund Nicht- decltype(bitmap->width)Typ verwiesen wird , wäre das Caching eine mögliche Optimierung.

Emlai
quelle
10

Die ursprünglich gestellte Frage:

Lohnt es sich, es zu optimieren?

Und meine Antwort darauf (eine gute Mischung aus Up- und Down-Stimmen).

Lassen Sie den Compiler sich darum kümmern.

Der Compiler wird mit ziemlicher Sicherheit einen besseren Job machen als Sie. Und es gibt keine Garantie dafür, dass Ihre "Optimierung" besser ist als der "offensichtliche" Code - haben Sie ihn gemessen?

Haben Sie, was noch wichtiger ist, einen Beweis dafür, dass der von Ihnen optimierte Code Auswirkungen auf die Leistung Ihres Programms hat?

Trotz der Abstimmungen (und jetzt des Aliasing-Problems) bin ich damit immer noch als gültige Antwort zufrieden. Wenn Sie nicht wissen, ob es sich lohnt, etwas zu optimieren, ist dies wahrscheinlich nicht der Fall.

Eine ganz andere Frage wäre natürlich:

Wie kann ich feststellen, ob es sich lohnt, ein Codefragment zu optimieren?

Muss Ihre Anwendung oder Bibliothek schneller ausgeführt werden als derzeit? Wartet der Benutzer zu lange? Prognostiziert Ihre Software das Wetter von gestern statt von morgen?

Nur Sie können dies wirklich sagen, basierend darauf, wofür Ihre Software gedacht ist und was Ihre Benutzer erwarten.

Vorausgesetzt, Ihre Software muss optimiert werden, müssen Sie als Nächstes mit der Messung beginnen. Profiler sagen Ihnen, wo Ihr Code seine Zeit verbringt. Wenn Ihr Fragment nicht als Engpass angezeigt wird, lassen Sie es am besten in Ruhe. Profiler und andere Messinstrumente zeigen Ihnen auch an, ob Ihre Änderungen einen Unterschied gemacht haben. Es ist möglich, Stunden damit zu verbringen, Code zu optimieren, nur um festzustellen, dass Sie keinen erkennbaren Unterschied gemacht haben.

Was meinst du überhaupt mit "Optimieren"?

Wenn Sie keinen "optimierten" Code schreiben, sollte Ihr Code so klar, sauber und präzise wie möglich sein. Das Argument "Vorzeitige Optimierung ist böse" ist keine Entschuldigung für schlampigen oder ineffizienten Code.

Optimierter Code opfert normalerweise einige der oben genannten Attribute für die Leistung. Dies könnte die Einführung zusätzlicher lokaler Variablen, Objekte mit einem größeren als erwarteten Bereich oder sogar die Umkehrung der normalen Schleifenreihenfolge umfassen. All dies ist möglicherweise weniger klar oder prägnant. Dokumentieren Sie daher den Code (kurz!), Warum Sie dies tun.

Bei „langsamem“ Code sind diese Mikrooptimierungen jedoch häufig der letzte Ausweg. Der erste Blick auf Algorithmen und Datenstrukturen. Gibt es eine Möglichkeit, die Arbeit überhaupt zu vermeiden? Können lineare Suchen durch binäre ersetzt werden? Wäre eine verknüpfte Liste hier schneller als ein Vektor? Oder eine Hash-Tabelle? Kann ich Ergebnisse zwischenspeichern? Gute „effiziente“ Entscheidungen zu treffen, kann die Leistung oft um eine Größenordnung oder mehr beeinträchtigen!

Roddy
quelle
12
Wenn Sie über die Breite eines Bitmap-Bildes iterieren, kann die Schleifenlogik einen erheblichen Teil der in der Schleife verbrachten Zeit ausmachen. In diesem Fall ist es besser, Best Practices zu entwickeln, die von Anfang an effizient sind, anstatt sich um vorzeitige Optimierung zu sorgen.
Mark Ransom
4
@MarkRansom stimmte teilweise zu: "Best Practices" wären entweder a: Verwenden einer vorhandenen Bibliothek oder eines API-Aufrufs zum Füllen von Bildern oder b: Lassen Sie die GPU dies für Sie tun. Es sollte niemals die Art von nicht gemessener Mikrooptimierung sein, die das OP vorschlägt. Und woher wissen Sie, dass dieser Code jemals mehr als einmal ausgeführt wird oder mit Bitmaps, die größer als 16 Pixel sind ...?
Roddy
@Veedrac. Schätzen Sie die Rechtfertigung für die -1. Der Schub der Frage hat sich subtil und wesentlich geändert, seit ich geantwortet habe. Wenn Sie der Meinung sind, dass die (erweiterte) Antwort immer noch nicht hilfreich ist, ist die Zeit für mich, sie zu löschen ... "Lohnt es sich ..." sowieso immer in erster Linie meinungsbasiert.
Roddy
@Roddy Ich schätze die Änderungen, sie helfen (und mein Kommentar klang wahrscheinlich sowieso viel zu hart). Ich bin immer noch am Zaun, da dies wirklich eine Antwort auf eine Frage ist, die nicht für Stack Overflow geeignet ist. Es fühlt sich so an, als wäre eine richtige Antwort spezifisch für das Snippet, so wie es die hoch bewerteten Antworten hier sind.
Veedrac
6

In dieser Situation verwende ich das folgende Muster. Es ist fast so kurz wie der erste Fall von Ihnen und besser als der zweite Fall, da die temporäre Variable lokal in der Schleife bleibt.

for (unsigned int x = 0, n = static_cast<unsigned>(bitmap->width); x < n; ++x)
{
  *p++ = 0xAA;
  *p++ = 0xBB;
  *p++ = 0xCC;
}

Dies ist schneller mit einem weniger als intelligenten Compiler, Debug-Build oder bestimmten Kompilierungsflags.

Edit1 : Es ist gut, eine konstante Operation außerhalb einer Schleife zu platzieren Programmiermuster. Es zeigt das Verständnis der Grundlagen des Maschinenbetriebs, insbesondere in C / C ++. Ich würde argumentieren, dass die Bemühungen, sich zu beweisen, auf Menschen gerichtet sein sollten, die dieser Praxis nicht folgen. Wenn der Compiler für ein gutes Muster bestraft, ist dies ein Fehler im Compiler.

Edit2 :: Ich habe meinen Vorschlag anhand des Originalcodes in vs2013 gemessen und eine Verbesserung von% 1 erhalten. Können wir es besser machen? Eine einfache manuelle Optimierung bietet eine dreifache Verbesserung gegenüber der ursprünglichen Schleife auf einem x64-Computer, ohne auf exotische Anweisungen zurückzugreifen. Der folgende Code setzt ein kleines Endian-System und eine richtig ausgerichtete Bitmap voraus. TEST 0 ist original (9 Sek.), TEST 1 ist schneller (3 Sek.). Ich wette, jemand könnte dies noch schneller machen, und das Ergebnis des Tests würde von der Größe der Bitmap abhängen. Auf jeden Fall wird der Compiler bald in der Lage sein, konstant schnellsten Code zu produzieren. Ich befürchte, dass dies die Zukunft sein wird, in der der Compiler auch eine Programmierer-KI sein wird, sodass wir arbeitslos wären. Schreiben Sie vorerst nur Code, der zeigt, dass Sie wissen, dass keine zusätzliche Operation in der Schleife erforderlich ist.

#include <memory>
#include <time.h>

struct Bitmap_line
{
  int blah;
  unsigned int width;
  Bitmap_line(unsigned int w)
  {
    blah = 0;
    width = w;
  }
};

#define TEST 0 //define 1 for faster test

int main(int argc, char* argv[])
{
  unsigned int size = (4 * 1024 * 1024) / 3 * 3; //makes it divisible by 3
  unsigned char* pointer = (unsigned char*)malloc(size);
  memset(pointer, 0, size);
  std::unique_ptr<Bitmap_line> bitmap(new Bitmap_line(size / 3));
  clock_t told = clock();
#if TEST == 0
  for (int iter = 0; iter < 10000; iter++)
  {
    unsigned char* p = pointer;
    for (unsigned x = 0; x < static_cast<unsigned>(bitmap->width); ++x)
    //for (unsigned x = 0, n = static_cast<unsigned>(bitmap->width); x < n; ++x)
    {
      *p++ = 0xAA;
      *p++ = 0xBB;
      *p++ = 0xCC;
    }
  }
#else
  for (int iter = 0; iter < 10000; iter++)
  {
    unsigned char* p = pointer;
    unsigned x = 0;
    for (const unsigned n = static_cast<unsigned>(bitmap->width) - 4; x < n; x += 4)
    {
      *(int64_t*)p = 0xBBAACCBBAACCBBAALL;
      p += 8;
      *(int32_t*)p = 0xCCBBAACC;
      p += 4;
    }

    for (const unsigned n = static_cast<unsigned>(bitmap->width); x < n; ++x)
    {
      *p++ = 0xAA;
      *p++ = 0xBB;
      *p++ = 0xCC;
    }
  }
#endif
  double ms = 1000.0 * double(clock() - told) / CLOCKS_PER_SEC;
  printf("time %0.3f\n", ms);

  {
    //verify
    unsigned char* p = pointer;
    for (unsigned x = 0, n = static_cast<unsigned>(bitmap->width); x < n; ++x)
    {
      if ((*p++ != 0xAA) || (*p++ != 0xBB) || (*p++ != 0xCC))
      {
        printf("EEEEEEEEEEEEERRRRORRRR!!!\n");
        abort();
      }
    }
  }

  return 0;
}
0kcats
quelle
Sie können weitere 25% auf 64-Bit sparen, wenn Sie drei int64_t anstelle von int64_t und int32_t verwenden.
Antonín Lejsek
5

Es gibt zwei Dinge zu beachten.

A) Wie oft wird die Optimierung ausgeführt?

Wenn die Antwort nicht sehr häufig ist, beispielsweise nur, wenn ein Benutzer auf eine Schaltfläche klickt, stören Sie sich nicht, wenn Ihr Code dadurch unlesbar wird. Wenn die Antwort 1000 Mal pro Sekunde lautet, möchten Sie wahrscheinlich mit der Optimierung fortfahren. Wenn es auch nur ein bisschen komplex ist, geben Sie unbedingt einen Kommentar ein, um zu erklären, was los ist, um dem nächsten Mann zu helfen, der mitkommt.

B) Wird dies die Wartung / Fehlerbehebung des Codes erschweren?

Wenn Sie keinen großen Leistungszuwachs feststellen, ist es keine gute Idee, Ihren Code kryptisch zu machen, um nur ein paar Taktstriche zu sparen. Viele Leute werden Ihnen sagen, dass jeder gute Programmierer in der Lage sein sollte, sich den Code anzusehen und herauszufinden, was los ist. Das ist wahr. Das Problem ist, dass in der Geschäftswelt die zusätzliche Zeit, um das herauszufinden, Geld kostet. Wenn Sie es also schöner machen können, zu lesen, dann tun Sie es. Deine Freunde werden es dir danken.

Das heißt, ich würde persönlich das B-Beispiel verwenden.

Soulsabr
quelle
4

Der Compiler kann viele Dinge optimieren. In Ihrem Beispiel sollten Sie sich für die Lesbarkeit, die Wartbarkeit und das, was Ihrem Codestandard folgt, entscheiden. Weitere Informationen darüber, was (mit GCC) optimiert werden kann, finden Sie in diesem Blogbeitrag .

Guillaume Racicot
quelle
4

Lassen Sie den Compiler in der Regel die Optimierung für Sie durchführen, bis Sie festgelegt haben, dass Sie übernehmen sollen. Die Logik hierfür hat nichts mit Leistung zu tun, sondern mit menschlicher Lesbarkeit. In den allermeisten Fällen ist die Lesbarkeit Ihres Programms wichtiger als seine Leistung. Sie sollten darauf abzielen, Code zu schreiben, der für einen Menschen leichter zu lesen ist, und sich dann nur dann um die Optimierung kümmern, wenn Sie davon überzeugt sind, dass die Leistung wichtiger ist als die Wartbarkeit Ihres Codes.

Sobald Sie feststellen, dass die Leistung wichtig ist, sollten Sie einen Profiler für den Code ausführen, um festzustellen, welche Schleifen ineffizient sind, und diese einzeln optimieren. Es kann zwar Fälle geben, in denen Sie diese Optimierung durchführen möchten (insbesondere, wenn Sie in Richtung C ++ migrieren, wo STL-Container beteiligt sind), aber die Kosten für die Lesbarkeit sind hoch.

Außerdem kann ich mir pathologische Situationen vorstellen, in denen der Code tatsächlich verlangsamt werden könnte. Stellen Sie sich zum Beispiel den Fall vor, in dem der Compiler nicht beweisen konnte, dass dies während bitmap->widthdes Prozesses konstant war. Durch Hinzufügen der widthVariablen zwingen Sie den Compiler, eine lokale Variable in diesem Bereich zu verwalten. Wenn diese zusätzliche Variable aus einem bestimmten plattformspezifischen Grund eine Optimierung des Stapelbereichs verhinderte, muss sie möglicherweise die Ausgabe von Bytecodes neu organisieren und etwas weniger Effizientes erzeugen.

Unter Windows x64 muss beispielsweise __chkstkin der Präambel der Funktion ein spezieller API-Aufruf aufgerufen werden, wenn die Funktion mehr als eine Seite lokaler Variablen verwendet. Mit dieser Funktion können Fenster die Schutzseiten verwalten, mit denen sie den Stapel bei Bedarf erweitern. Wenn Ihre zusätzliche Variable die Stapelverwendung von unter 1 Seite auf über oder über 1 Seite erhöht, muss Ihre Funktion jetzt bei __chkstkjeder Eingabe aufrufen . Wenn Sie diese Schleife auf einem langsamen Pfad optimieren, können Sie den schnellen Pfad tatsächlich stärker verlangsamen, als Sie auf dem langsamen Pfad gespeichert haben!

Sicher, es ist ein bisschen pathologisch, aber der Sinn dieses Beispiels ist, dass Sie den Compiler tatsächlich verlangsamen können. Es zeigt nur, dass Sie Ihre Arbeit profilieren müssen, um festzustellen, wohin die Optimierungen führen. In der Zwischenzeit sollten Sie die Lesbarkeit in keiner Weise für eine Optimierung opfern, die möglicherweise von Bedeutung ist oder nicht.

Cort Ammon
quelle
4
Ich wünschte, C und C ++ würden mehr Möglichkeiten bieten, Dinge explizit zu identifizieren, die dem Programmierer egal sind. Sie würden nicht nur den Compilern mehr Möglichkeiten bieten, Dinge zu optimieren, sondern auch anderen Programmierern, die den Code lesen, ersparen, dass sie erraten müssen, ob z. B. jedes Mal die Bitmap-> Breite erneut überprüft wird, um sicherzustellen, dass Änderungen daran die Schleife beeinflussen, oder Gibt an, ob Bitmap-> width zwischengespeichert werden soll, um sicherzustellen, dass Änderungen keine Auswirkungen auf die Schleife haben. Wenn Sie die Möglichkeit haben, "Cache dies oder nicht - es ist mir egal" zu sagen, wird der Grund für die Wahl des Programmierers deutlich.
Superkatze
@supercat Ich stimme voll und ganz zu, da man sehen kann, ob man sich die Stapel tattierter fehlgeschlagener Sprachen ansieht, die ich schreiben wollte, um dies zu beheben. Ich habe festgestellt, dass es bemerkenswert schwierig ist zu definieren, "was" jemand ohne so viel gottlose Syntax nicht interessiert, dass es sich einfach nicht lohnt. Ich setze meine Suche vergebens fort.
Cort Ammon
Es ist nicht in allen Fällen möglich, es zu definieren, aber ich denke, es gibt viele Fälle, in denen das Typsystem helfen könnte. Es ist zu C, sich dafür zu entscheiden, Zeichentypen zum "universellen Accessor" zu machen, anstatt ein Typqualifikationsmerkmal zu haben, das etwas lockerer als "flüchtig" ist und auf jeden Typ angewendet werden kann , mit der Semantik, mit der Zugriffe solcher Typen nacheinander verarbeitet werden Zugriffe vom nicht qualifizierten äquivalenten Typ sowie Zugriffe auf alle Arten von Variablen mit demselben Qualifizierer. Das würde helfen, klar zu machen, ob man Zeichentypen verwendet, weil man den ...
Supercat
... Aliasing-Verhalten oder ob man sie verwendet, weil sie die richtige Größe haben, um den eigenen Bedürfnissen zu entsprechen. Es wäre auch hilfreich, explizite Aliasing-Barrieren zu haben, die in vielen Fällen außerhalb von Schleifen platziert werden könnten, im Gegensatz zu den impliziten Barrieren, die mit Zugriffen vom Typ Charakter verbunden sind.
Supercat
1
Dies ist ein kluger Vortrag, aber wenn Sie bereits C für Ihre Aufgabe auswählen, ist die Leistung wahrscheinlich sehr wichtig und es sollten die verschiedenen Regeln gelten. Andernfalls ist es möglicherweise besser, Ruby, Java, Python oder ähnliches zu verwenden.
Audrius Meskauskas
4

Der Vergleich ist falsch, da die beiden Codefragmente

for (unsigned x = 0;  x < static_cast<unsigned>(bitmap->width);  ++x)

und

unsigned width(static_cast<unsigned>(bitmap->width));
for (unsigned x = 0;  x<width ;  ++x)

sind nicht gleichwertig

Im ersten Fall widthist abhängig und nicht const, und man kann nicht davon ausgehen, dass es sich zwischen nachfolgenden Iterationen nicht ändert. Daher kann es nicht optimiert werden, sondern muss bei jeder Schleife überprüft werden .

In Ihrem optimierten Fall wird einer lokalen Variablenbitmap->width irgendwann während der Programmausführung der Wert von zugewiesen . Der Compiler kann überprüfen, ob sich dies tatsächlich ändert.

Haben Sie über Multithreading nachgedacht, oder könnte der Wert extern abhängig sein, sodass sein Wert volatil ist? Wie würde man erwarten, dass der Compiler all diese Dinge herausfindet, wenn Sie es nicht sagen?

Der Compiler kann nur so gut, wie es Ihr Code zulässt.

g24l
quelle
2

Wenn Sie nicht genau wissen, wie der Compiler den Code optimiert, ist es besser, Ihre eigenen Optimierungen vorzunehmen, indem Sie die Lesbarkeit und das Design des Codes beibehalten. Praktisch ist es schwierig, den Assemblycode für jede Funktion zu überprüfen, die wir für neue Compilerversionen schreiben.

Vinayak SM
quelle
1

Der Compiler kann nicht optimieren, bitmap->widthda der Wert von widthzwischen den Iterationen geändert werden kann. Es gibt einige häufigste Gründe:

  1. Multithreading. Der Compiler kann nicht vorhersagen, ob ein anderer Thread den Wert ändern wird.
  2. Änderung innerhalb der Schleife, manchmal ist es nicht einfach zu sagen, ob die Variable innerhalb der Schleife geändert wird.
  3. Es ist Funktionsaufruf, zB iterator::end()oder container::size()so ist es schwer vorherzusagen , ob es immer das gleiche Ergebnis zurückgibt.

Um (meine persönliche Meinung) für Orte zusammenzufassen, die ein hohes Maß an Optimierung erfordern, müssen Sie dies selbst tun. An anderen Orten lassen Sie es einfach, der Compiler kann es optimieren oder nicht, wenn es keinen großen Unterschied gibt. Die Lesbarkeit des Codes ist das Hauptziel.

ST3
quelle