Welche einfachen Techniken verwenden Sie, um die Leistung zu verbessern?

Ich spreche über die Art und Weise, wie wir einfache Routinen schreiben, um die Leistung zu verbessern, ohne dass der Code schwerer zu lesen ist. Dies ist beispielsweise das typische Beispiel für Folgendes:

for(int i = 0; i < collection.length(); i++ ){
   // stuff here
}

Aber normalerweise mache ich das, wenn a foreachnicht anwendbar ist:

for(int i = 0, j = collection.length(); i < j; i++ ){
   // stuff here
}

Ich denke, dies ist ein besserer Ansatz, da die lengthMethode nur einmal aufgerufen wird ... meine Freundin sagt, dass sie jedoch kryptisch ist. Gibt es einen anderen einfachen Trick, den Sie für Ihre eigenen Entwicklungen verwenden?

Legen Sie eine vorzeitige Diskussion als die Wurzel des Bösen ein

Das heißt, hier sind einige Gewohnheiten, die ich eingeführt habe, um unnötige Effizienz zu vermeiden, und in einigen Fällen meinen Code einfacher und korrekter zu machen.

Hierbei geht es nicht um allgemeine Prinzipien, sondern um einige Dinge, die beachtet werden müssen, um unnötige Ineffizienzen im Code zu vermeiden.

Kenne deinen Big-O

Dies sollte wahrscheinlich in die obige ausführliche Diskussion einbezogen werden. Es ist ziemlich normal, dass eine Schleife in einer Schleife, in der die innere Schleife eine Berechnung wiederholt, langsamer sein wird. Beispielsweise:

for (i = 0; i < strlen(str); i++) {
    ...
}

Wenn der String wirklich lang ist, wird dies eine horrende Zeit in Anspruch nehmen, da die Länge bei jeder Iteration der Schleife neu berechnet wird. Beachten Sie, dass GCC diesen Fall tatsächlich optimiert, weilstrlen() als reine Funktion markiert ist.

Wenn Sie eine Million 32-Bit-Ganzzahlen sortieren, ist die Blasensortierung der falsche Weg . Im Allgemeinen kann die Sortierung in der Zeit O (n * log n) (oder besser im Fall der Radix-Sortierung) durchgeführt werden. Wenn Sie also nicht wissen, dass Ihre Daten klein sein werden, suchen Sie nach einem Algorithmus, der mindestens O (n) ist * log n).

Achten Sie auch beim Umgang mit Datenbanken auf Indizes. Wenn duSELECT * FROM people WHERE age = 20 keinen Index für Personen (Alter) haben, ist eher ein O (n) -Sequenz-Scan als ein viel schnellerer O (log n) -Index-Scan erforderlich.

Ganzzahlige arithmetische Hierarchie

Bedenken Sie beim Programmieren in C, dass einige Rechenoperationen teurer sind als andere. Für ganze Zahlen sieht die Hierarchie ungefähr so ​​aus (am billigsten zuerst):

• + - ~ & | ^
• << >>
• *
• /

Zugegeben, wird der Compiler in der Regel optimize Dinge wie n / 2zu n >> 1automatisch , wenn Sie einen Mainstream - Computer targeting sind, aber wenn Sie ein eingebettetes Gerät Targeting sind, können Sie diesen Luxus nicht zu bekommen.

Auch % 2und & 1haben unterschiedliche Semantik. Division und Modul runden normalerweise gegen Null, aber die Implementierung ist definiert. Gut alt >>und &rundet immer in Richtung negative Unendlichkeit, was (meiner Meinung nach) viel sinnvoller ist. Zum Beispiel auf meinem Computer:

printf("%d\n", -1 % 2); // -1 (maybe)
printf("%d\n", -1 & 1); // 1

Verwenden Sie daher, was Sinn macht. Denken Sie nicht, dass Sie ein guter Junge sind, indem Sie verwenden, % 2als Sie ursprünglich schreiben wollten& 1 .

Teure Gleitkommaoperationen

Vermeiden Sie schwere Gleitkommaoperationen wie pow()und log()in Code, die diese nicht wirklich benötigen, insbesondere im Umgang mit Ganzzahlen. Nehmen Sie zum Beispiel das Lesen einer Zahl:

int parseInt(const char *str)
{
    const char *p;
    int         digits;
    int         number;
    int         position;

    // Count the number of digits
    for (p = str; isdigit(*p); p++)
        {}
    digits = p - str;

    // Sum the digits, multiplying them by their respective power of 10.
    number = 0;
    position = digits - 1;
    for (p = str; isdigit(*p); p++, position--)
        number += (*p - '0') * pow(10, position);

    return number;
}

Diese Verwendung von pow()(und die dazu erforderlichen int<-> doubleKonvertierungen) ist nicht nur ziemlich teuer, sondern bietet auch die Möglichkeit eines Präzisionsverlusts (der obige Code weist übrigens keine Präzisionsprobleme auf). Deshalb zucke ich zusammen, wenn ich diese Art von Funktion in einem nicht mathematischen Kontext sehe.

Beachten Sie auch, dass der unten stehende "clevere" Algorithmus, der bei jeder Iteration mit 10 multipliziert wird, prägnanter ist als der obige Code:

int parseInt(const char *str)
{
    const char *p;
    int         number;

    number = 0;
    for (p = str; isdigit(*p); p++) {
        number *= 10;
        number += *p - '0';
    }

    return number;
}

Aus Ihrer Frage und dem Kommentarthread geht hervor, dass Sie denken, dass diese Codeänderung die Leistung verbessert, aber Sie wissen nicht wirklich, ob dies der Fall ist oder nicht.

Ich bin ein Fan von Kent Becks Philosophie:

"Lass es funktionieren, mach es richtig, mach es schnell."

Meine Technik zur Verbesserung der Codeleistung besteht darin, dass der Code zuerst die Unit-Tests besteht und gut berücksichtigt wird. Anschließend schreibe ich (insbesondere für Schleifenoperationen) einen Unit-Test, der die Leistung prüft und dann den Code umstrukturiert, oder denke an einen anderen Algorithmus, wenn ich Die von Ihnen gewählte Funktion funktioniert nicht wie erwartet.

Um beispielsweise die Geschwindigkeit mit .NET-Code zu testen, verwende ich das Timeout-Attribut von NUnit , um die Behauptung zu erstellen , dass ein Aufruf einer bestimmten Methode innerhalb einer bestimmten Zeit ausgeführt wird.

Wenn Sie das Timeout-Attribut von NUnit mit dem von Ihnen angegebenen Codebeispiel (und einer großen Anzahl von Iterationen für die Schleife) verwenden, können Sie tatsächlich nachweisen, ob Ihre "Verbesserung" des Codes wirklich zur Leistung dieser Schleife beigetragen hat.

Ein Haftungsausschluss: Obwohl dies auf der "Mikro" -Ebene effektiv ist, ist es sicherlich nicht die einzige Möglichkeit, die Leistung zu testen, und berücksichtigt keine Probleme, die auf der "Makro" -Ebene auftreten könnten - aber es ist ein guter Anfang.

Denken Sie daran, dass Ihr Compiler möglicherweise Folgendes ausführt:

for(int i = 0; i < collection.length(); i++ ){
   // stuff here
}

in:

int j = collection.length();
for(int i = 0; i < j; i++ ){
   // stuff here
}

oder etwas ähnliches, wenn collection über die Schleife unverändert ist.

Wenn sich dieser Code in einem zeitkritischen Abschnitt Ihrer Anwendung befindet, sollten Sie herausfinden, ob dies der Fall ist oder nicht - oder ob Sie die Compileroptionen ändern können, um dies zu tun.

Auf diese Weise bleibt die Lesbarkeit des Codes erhalten (wie die meisten Leute erwarten werden), und Sie profitieren von den wenigen zusätzlichen Maschinenzyklen. Sie können sich dann auf die anderen Bereiche konzentrieren, in denen der Compiler Ihnen nicht weiterhelfen kann.

Nebenbei bemerkt: Wenn Sie collectioninnerhalb der Schleife Änderungen vornehmen, indem Sie Elemente hinzufügen oder entfernen (ja, ich weiß, dass dies eine schlechte Idee ist, aber es passiert), führt Ihr zweites Beispiel entweder keine Schleife über alle Elemente aus oder versucht, auf frühere Elemente zuzugreifen das Ende des Arrays.

Diese Art der Optimierung wird normalerweise nicht empfohlen. Diese Optimierung kann leicht vom Compiler durchgeführt werden. Sie arbeiten mit einer höheren Programmiersprache anstelle von Assembler. Denken Sie also auf derselben Ebene.

Dies gilt möglicherweise nicht so sehr für die allgemeine Codierung, aber ich entwickle diese Tage hauptsächlich eingebettet. Wir haben einen bestimmten Zielprozessor (der nicht schneller werden wird - er wird merkwürdig veraltet sein, wenn das System in mehr als 20 Jahren aus dem Verkehr gezogen wird) und sehr restriktive Fristen für einen Großteil des Codes. Der Prozessor hat, wie alle Prozessoren, gewisse Macken, welche Operationen schnell oder langsam sind.

Wir verwenden eine Technik, um sicherzustellen, dass wir den effizientesten Code generieren und die Lesbarkeit für das gesamte Team aufrechterhalten. An den Stellen, an denen das natürlichste Sprachkonstrukt nicht den effizientesten Code generiert, haben wir Makros erstellt, die sicherstellen, dass der optimale Code verwendet wird. Wenn wir ein Folgeprojekt für einen anderen Prozessor durchführen, können wir die Makros für die optimale Methode auf diesem Prozessor aktualisieren.

Als spezielles Beispiel für unseren aktuellen Prozessor leeren Zweige die Pipeline und blockieren den Prozessor für 8 Zyklen. Der Compiler nimmt diesen Code:

 bool isReady = (value > TriggerLevel);

und verwandelt es in das Assembly-Äquivalent von

isReady = 0
if (value > TriggerLevel)
{
  isReady = 1;
}

Dies dauert entweder 3 Zyklen oder 10, wenn es überspringt isReady=1;. Der Prozessor verfügt jedoch über einen maxEinzelzyklusbefehl, daher ist es viel besser, Code zu schreiben, um diese Sequenz zu generieren, die garantiert immer 3 Zyklen dauert:

diff = value-TriggerLevel;
diff = max(diff, 0);
isReady = min(1,diff);

Offensichtlich ist die Absicht hier weniger klar als das Original. Deshalb haben wir ein Makro erstellt, das wir immer dann verwenden, wenn wir einen booleschen Größer-als-Vergleich wünschen:

#define BOOL_GT(a,b) min(max((a)-(b),0),1)

//isReady = value > TriggerLevel;
isReady = BOOL_GT(value, TriggerLevel);

Wir können ähnliche Dinge für andere Vergleiche tun. Für einen Außenstehenden ist der Code etwas weniger lesbar als wenn wir nur das natürliche Konstrukt verwenden würden. Es wird jedoch schnell klar, wenn Sie ein wenig mit dem Code gearbeitet haben, und es ist viel besser, als jeden Programmierer mit seinen eigenen Optimierungstechniken experimentieren zu lassen.

Nun, der erste Ratschlag wäre, solche vorzeitigen Optimierungen zu vermeiden, bis Sie genau wissen, was mit dem Code passiert, damit Sie sicher sind, dass Sie ihn tatsächlich schneller und nicht langsamer machen.

In C # optimiert der Compiler beispielsweise den Code, wenn Sie die Länge eines Arrays in einer Schleife anzeigen, da er weiß, dass er den Index nicht überprüfen muss, wenn Sie auf das Array zugreifen. Wenn Sie versuchen, es zu optimieren, indem Sie die Array-Länge in eine Variable einfügen, unterbrechen Sie die Verbindung zwischen der Schleife und dem Array und verlangsamen den Code erheblich.

Wenn Sie eine Mikrooptimierung durchführen, sollten Sie sich auf Dinge beschränken, von denen bekannt ist, dass sie viele Ressourcen verbrauchen. Wenn es nur einen geringen Leistungszuwachs gibt, sollten Sie stattdessen den lesbarsten und wartbarsten Code verwenden. Wie sich die Computerarbeit im Laufe der Zeit ändert, ist möglicherweise etwas, das Sie jetzt herausfinden, etwas schneller.

Ich habe eine sehr einfache Technik.

1. Ich bringe meinen Code zum Laufen.
2. Ich teste es auf Geschwindigkeit.
3. Wenn es schnell ist, gehe ich für eine andere Funktion zu Schritt 1 zurück. Wenn es langsam ist, profiliere ich es, um den Engpass zu finden.
4. Ich behebe den Engpass. Gehen Sie zurück zu Schritt 1.

Es gibt viele Fälle, in denen Zeit gespart wird, um diesen Prozess zu umgehen, aber im Allgemeinen werden Sie wissen, ob dies der Fall ist. Im Zweifelsfall halte ich mich standardmäßig daran.

Nutzen Sie die Vorteile des Kurzschlusses:

if(someVar || SomeMethod())

Code dauert genauso lange und ist genauso lesbar wie:

if(someMethod() || someVar)

dennoch wird es mit der Zeit schneller ausgewertet.

Warten Sie sechs Monate, und lassen Sie Ihren Chef neue Computer kaufen. Ernst. Programmiererzeit ist auf lange Sicht viel teurer als Hardware. Hochleistungscomputer ermöglichen es Codierern, Code auf einfache Weise zu schreiben, ohne sich Gedanken über die Geschwindigkeit machen zu müssen.

Versuchen Sie, nicht zu viel im Voraus zu optimieren. Wenn Sie dann optimieren, sorgen Sie sich etwas weniger um die Lesbarkeit.

Dort hasse ich wenig mehr als unnötige Komplexität, aber wenn Sie in eine komplexe Situation geraten, ist oft eine komplexe Lösung erforderlich.

Wenn Sie den Code auf die naheliegendste Weise schreiben, erläutern Sie in einem Kommentar, warum er geändert wurde, als Sie die komplexe Änderung vorgenommen haben.

Insbesondere in Bezug auf Ihre Bedeutung finde ich, dass es manchmal hilfreich ist, das Boolesche Gegenteil des Standardansatzes zu tun:

for(int i = 0, j = collection.length(); i < j; i++ ){
// stuff here
}

kann werden

for(int i = collection.length(); i > 0; i-=1 ){
// stuff here
}

In vielen Sprachen, solange Sie den Teil "Zeug" entsprechend anpassen und er noch lesbar ist. Es geht einfach nicht so an das Problem heran, wie die meisten Leute es zuerst denken würden, weil es rückwärts zählt.

in c # zum Beispiel:

        string[] collection = {"a","b"};

        string result = "";

        for (int i = 0, j = collection.Count() - 1; i < j; i++)
        {
            result += collection[i] + "~";
        }

könnte auch geschrieben werden als:

        for (int i = collection.Count() - 1; i > 0; i -= 1)
        {
            result = collection[i] + "~" + result;
        }

(und ja, das solltest du mit einem Join oder einem Stringbuilder machen, aber ich versuche ein einfaches Beispiel zu machen)

Es gibt viele andere Tricks, die man anwenden kann und die nicht schwer zu befolgen sind, aber viele davon gelten nicht für alle Sprachen, wie die Verwendung von mid auf der linken Seite einer Zuweisung in old vb, um die Strafe für die Neuzuweisung von Zeichenfolgen oder das Lesen von Textdateien im Binärmodus zu vermeiden in .net, um die Pufferungsstrafe zu überwinden, wenn die Datei zu groß für ein Readtoend ist.

Der einzige andere wirklich generische Fall, von dem ich mir vorstellen kann, dass er überall zutrifft, wäre, eine Boolesche Algebra auf komplexe Bedingungen anzuwenden, um zu versuchen, die Gleichung in etwas umzuwandeln, das eine bessere Chance hat, eine Kurzschlussbedingung auszunutzen oder einen Komplex zu verwandeln Satz verschachtelter If-Then- oder Case-Anweisungen vollständig in eine Gleichung. Beides funktioniert nicht in allen Fällen, kann jedoch zu einer erheblichen Zeitersparnis führen.

1. Profil. Haben wir überhaupt ein Problem? Woher?
2. Wenden Sie in 90% der Fälle, in denen es in irgendeiner Weise mit E / A zu tun hat, das Zwischenspeichern an (und erhalten Sie möglicherweise mehr Arbeitsspeicher).
3. Wenn es sich um eine CPU handelt, wenden Sie die Zwischenspeicherung an
4. Wenn die Leistung immer noch ein Problem ist, haben wir den Bereich der einfachen Techniken verlassen - machen Sie die Mathematik.

Verwenden Sie die besten Tools, die Sie finden können - einen guten Compiler, einen guten Profiler und gute Bibliotheken. Holen Sie sich die richtigen Algorithmen oder noch besser - verwenden Sie die richtige Bibliothek, um dies für Sie zu tun. Die Trivial-Loop-Optimierungen sind kleine Kartoffeln, und Sie sind nicht so schlau wie der Optimierungs-Compiler.

Für mich ist es am einfachsten, den Stapel immer dann zu verwenden, wenn ein allgemeines Verwendungsmuster in einen Bereich von beispielsweise [0, 64] passt, aber in seltenen Fällen keine kleine Obergrenze aufweist.

Einfaches C-Beispiel (vorher):

void some_hotspot_called_in_big_loops(int n, ...)
{
    // 'n' is, 99% of the time, <= 64.
    int* values = calloc(n, sizeof(int));

    // do stuff with values
    ...
    free(values);
}

Und danach:

void some_hotspot_called_in_big_loops(int n, ...)
{
    // 'n' is, 99% of the time, <= 64.
    int values_mem[64] = {0}
    int* values = (n <= 64) ? values_mem: calloc(n, sizeof(int));

    // do stuff with values
    ...
    if (values != values_mem)
        free(values);
}

Ich habe das so verallgemeinert, da diese Arten von Hotspots beim Profiling häufig auftreten:

void some_hotspot_called_in_big_loops(int n, ...)
{
    // 'n' is, 99% of the time, <= 64.
    MemFast values_mem;
    int* values = mf_calloc(&values_mem, n, sizeof(int));

    // do stuff with values
    ...

    mf_free(&values_mem);
}

Das oben Genannte verwendet den Stapel, wenn die zugeteilten Daten in diesen 99,9% -Fällen klein genug sind, und verwendet den Heap ansonsten.

In C ++ habe ich dies mit einer standardkonformen kleinen Sequenz verallgemeinert (ähnlich den SmallVectorImplementierungen, die es gibt), die sich um dasselbe Konzept dreht.

Es ist keine epische Optimierung (ich habe Kürzungen von beispielsweise 3 Sekunden erhalten, damit eine Operation auf 1,8 Sekunden abgeschlossen ist), aber es erfordert einen so geringen Aufwand, um sie anzuwenden. Wenn Sie durch einfaches Einfügen einer Codezeile und Ändern von zwei etwas von 3 Sekunden auf 1,8 Sekunden reduzieren können, ist dies ein ziemlich guter Knall für einen so kleinen Dollar.

Nun, Sie können beim Zugriff auf Daten zahlreiche Leistungsänderungen vornehmen, die einen enormen Einfluss auf Ihre Anwendung haben. Wenn Sie Abfragen schreiben oder einen ORM verwenden, um auf eine Datenbank zuzugreifen, müssen Sie einige Leistungsoptimierungsbücher für das von Ihnen verwendete Datenbank-Backend lesen. Möglicherweise verwenden Sie bekannte Techniken mit schlechter Leistung. Es gibt keinen Grund, dies zu tun, außer Unwissenheit. Dies ist keine vorzeitige Optimierung (ich verfluche den Typen, der dies gesagt hat, weil es so weit verbreitet ist, dass er sich nie um die Leistung kümmert), dies ist ein gutes Design.

Nur eine kurze Auswahl von Leistungsverbesserern für SQL Server: Verwenden Sie geeignete Indizes, vermeiden Sie Cursor - verwenden Sie satzbasierte Logik, verwenden Sie sargable where-Klauseln, stapeln Sie Ansichten nicht über Ansichten und geben Sie nicht mehr Daten zurück, als Sie benötigen oder mehr Verwenden Sie keine korrelierten Unterabfragen.

Wenn dies C ++ ist, sollten Sie sich daran gewöhnen ++i eher als i++. ++iwird niemals schlechter, es bedeutet genau dasselbe wie eine eigenständige Aussage, und in einigen Fällen könnte es eine Leistungsverbesserung sein.

Es lohnt sich nicht, vorhandenen Code zu ändern, wenn dies nicht möglich ist, aber es ist eine gute Angewohnheit, sich darauf einzulassen.

Ich verstehe das etwas anders. Nur einfach den Ratschlägen zu folgen, die Sie hier erhalten, wird keinen großen Unterschied machen, denn es gibt einige Fehler, die Sie machen müssen, die Sie dann beheben müssen, und aus denen Sie dann lernen müssen.

Der Fehler, den Sie machen müssen, besteht darin, Ihre Datenstruktur so zu gestalten, wie es jeder tut. Das heißt, mit redundanten Daten und vielen Abstraktionsebenen, mit Eigenschaften und Benachrichtigungen, die sich in der gesamten Struktur ausbreiten und versuchen, diese konsistent zu halten.

Dann müssen Sie eine Leistungsoptimierung (Profilerstellung) durchführen und sich zeigen lassen, wie in vielerlei Hinsicht Sie unzählige Zyklen durch die vielen Abstraktionsebenen mit Eigenschaften und Benachrichtigungen kosten, die sich über die gesamte Struktur ausbreiten und versuchen, diese konsistent zu halten.

Möglicherweise können Sie diese Probleme etwas beheben, ohne größere Änderungen am Code vorzunehmen.

Wenn Sie Glück haben, können Sie feststellen, dass weniger Datenstruktur besser ist und dass es besser ist, vorübergehende Inkonsistenzen zu tolerieren, als zu versuchen, viele Dinge in enger Übereinstimmung mit Nachrichtenwellen zu halten.

Wie man Loops schreibt, hat eigentlich nichts damit zu tun.