Fastware

    Andrei Alexandrescu ist eine lebende Legende. Dies ist eine Person, die einen bedeutenden Beitrag zur Geschichte der modernen Programmiersprachen und generalisierten und Metaprogrammiertechniken geleistet hat. Wie viele Exemplare wurden in der Diskussion gebrochen „Moderne C ++ Design“ und „Coding Standards 101“ (Co-Autor von Herb «Außergewöhnliche C ++» Sutter) und andere Bücher und Artikel . Als Mitautor der D-Sprache hatte er die Möglichkeit, seinen Traum nicht nur zu theoretisieren, sondern auch zu verwirklichen - und das ist charakteristisch, was er verkörpert .

    Jetzt halten Sie seinen Berichtvon der DotNext 2018 Piter Konferenz, die über moderne Optimierungstechnologien spricht. Was hat .NET damit zu tun? Dies ist ein grundlegender Bericht von einer Person, die ihr ganzes Leben lang optimiert hat. Wenn Leistung für Sie wichtig ist, müssen Sie sie ansehen (oder diesen Artikel lesen). Willkommen bei Katze!




    Die Kunst des Benchmarking


    Ich möchte mit Ihnen einige Themen im Zusammenhang mit Benchmarking erörtern. Lassen Sie uns zunächst einige grundlegende Dinge wiederholen. Amdahls Gesetz- Teil der Klassiker der Informatik, wird es hauptsächlich im Parallel-Computing verwendet, funktioniert aber in jedem komplexen System. Wenn wir die Arbeit eines bestimmten Systems verbessern wollen, müssen wir dort beginnen, wo sich die Hauptprobleme dieses Systems konzentrieren. Das Gesetz selbst ist offensichtlich: Wenn eine Komponente 20% des Systems ausmacht, beträgt die maximale Verbesserung der Systemleistung, die durch die Optimierung des Betriebs nur dieser Komponente erzielt werden kann, 20%. Zu oft muss ich Leute treffen (unsere Leser gehören natürlich nicht zu ihnen), die Dinge wie das Optimieren der Befehlszeilenanalyse tun. Diese Operationen dauern die ersten 10 Mikrosekunden Ihres Programms, und die Mitarbeiter analysieren ihre algorithmische Komplexität und sind entsetzt, wenn die Zeit quadratisch ist.

    Wie Sie wahrscheinlich wissen, müssen Sie vor dem Starten der Optimierung die Anwendung profilieren und Hotspots auswählen. Es sollte über das Gesetz von Ladma gesagt werden(Dies ist kein richtiger Familienname, und Amdal, rückwärts gelesen). Sie müssen sich auf die Komponente konzentrieren, die zum größten Zeitaufwand führt. Es muss aus der Anwendung entfernt, die erforderlichen Arbeiten ausgeführt, zurückgesetzt und erneut getestet werden. Der Grund, warum Sie dies tun müssen, ist, dass eine Leistungsverbesserung von 20% häufig das Ergebnis von zehn Verbesserungen von 2% ist. Und im Rahmen eines großen Systems ist es unmöglich, eine so kleine Verbesserung zu messen. Dazu muss die Komponente in einer Testsuite getestet werden. Eine 20% ige Verbesserung der Leistung einer der Hauptkomponenten des Systems kann eine 5% ige Verbesserung für das Gesamtsystem bedeuten. In einigen Bereichen ist dies ein hervorragendes Ergebnis. Denken Sie daran, dass Optimierungen eine Reihe von globalen Auswirkungen haben können,

    Ein Fehler, den unsere Leser sicher nicht machen, der aber allgemein üblich ist: Die Leute messen die Geschwindigkeit der Fehlerbehebung beim Zusammenbau. Dies sollte niemals getan werden. Das ist ähnlich wie wenn man sich wegen der geringen Geschwindigkeit der Schnecke bei den Rennen aufregt: Es ist nicht für einen solchen Wettbewerb gedacht, es hat andere Ziele im Leben. Ein weiterer, etwas weniger offensichtlicher Fehler: Die Leute messen zuerst die Grundleistung des Systems und führen unmittelbar danach ein Benchmarking durch. Nach dem Sammeln der Basislinie werden jedoch viele Ressourcen aufgewärmt. Beispielsweise werden geöffnete Dateien gepuffert und verbleiben im Speicher (zumindest unter Linux). Somit ist der zweite Test nur deshalb schneller, weil er nach dem ersten gestartet wird. Dies geschieht auch bei Malloc-Aufrufen. Nach diesen Aufrufen kehrt das System nicht in seinen ursprünglichen Zustand zurück, selbst wenn Speicherfreigabeaufrufe getätigt werden. Durch die interne Konfiguration, Zwischenspeicherung und die vom Speicherzuweiser verwendeten Funktionen können die folgenden Malloc-Aufrufe viel schneller ausgeführt werden. Auch ohne Berücksichtigung des Cache-Effekts merkt sich malloc, dass beispielsweise einige Funktionen mehrmals Speicher für Objekte mit einer Größe von 4 Kilobyte zugewiesen haben, was bedeutet, dass Sie eine freie Liste mit einer Elementgröße von 4 Kilobyte benötigen. Oder ein anderes Beispiel: DNS-Lookups werden nach der ersten Abfrage zur Wiederverwendung zwischengespeichert. Wenn möglich, müssen Sie während des Benchmarks den gesamten Prozess jedes Mal von Anfang bis Ende neu starten. Erlaube den folgenden Malloc-Aufrufen, viel schneller zu laufen. Auch ohne Berücksichtigung des Cache-Effekts merkt sich malloc, dass beispielsweise einige Funktionen mehrmals Speicher für Objekte mit einer Größe von 4 Kilobyte zugewiesen haben, was bedeutet, dass Sie eine freie Liste mit einer Elementgröße von 4 Kilobyte benötigen. Oder ein anderes Beispiel: DNS-Lookups werden nach der ersten Abfrage zur Wiederverwendung zwischengespeichert. Wenn möglich, müssen Sie während des Benchmarks den gesamten Prozess jedes Mal von Anfang bis Ende neu starten. Erlaube den folgenden Malloc-Aufrufen, viel schneller zu laufen. Auch ohne Berücksichtigung des Cache-Effekts merkt sich malloc, dass beispielsweise einige Funktionen mehrmals Speicher für Objekte mit einer Größe von 4 Kilobyte zugewiesen haben, was bedeutet, dass Sie eine freie Liste mit einer Elementgröße von 4 Kilobyte benötigen. Oder ein anderes Beispiel: DNS-Lookups werden nach der ersten Abfrage zur Wiederverwendung zwischengespeichert. Wenn möglich, müssen Sie während des Benchmarks den gesamten Prozess jedes Mal von Anfang bis Ende neu starten.

    Um beispielsweise das System vollständig in den ursprünglichen Zustand zu versetzen, müssen Dateien auf einer separaten Festplatte geöffnet werden, die nach Abschluss des Tests entfernt werden muss (dies kann meines Wissens auch unter Windows erfolgen). Die Bedienung ist nicht einfach, aber in den meisten Fällen notwendig.

    Ich habe das Gespräch über Fehler während der Optimierung fortgesetzt und musste mich mit solchen Fällen befassen, in denen die Kosten für den Ausdruck in den Testergebnissen enthalten sind. Es gibt Verfahrensfehler, wenn mehr als eine Sache vor jeder Messung geändert wird, was gegen die grundlegendsten Prinzipien eines wissenschaftlichen Experiments verstößt, da nicht klar ist, welchen Effekt Sie messen. Ein weiterer schwerwiegender Fehler besteht darin, dass einige seltene Fälle optimiert werden, was in anderen Situationen zu einer Pessimisierung führt.



    Hier ist ein Beispiel für einen Stapelüberlauf. Der Autor sortiert häufig bereits sortierte Daten und ist überrascht, weil die Funktion "is_sorted" offensichtlich viel schneller als "sort" ist. Warum ist dann in `sort die erste Zeile nicht` if is_sorted return? Sie optimieren einen äußerst seltenen Fall, vollständig sortierte Daten, und alle anderen, die mindestens ein nicht sortiertes Element haben, müssen die Kosten für diese Optimierung tragen. Das ist es nicht wert.

    Ich glaube, ich muss nicht lange nachweisen, dass die heutigen konkurrierenden Architekturen äußerst komplex sind: dynamische Frequenzänderung, Unterbrechung durch andere Prozesse, Virtualisierung usw. Daher ist es fast unmöglich, beim Messen die gleiche Zeit zu erhalten, Ihre Indikatoren werden immer zittern. Daher sollte man sich nicht auf Dinge verlassen, die offensichtlich erscheinen. Angenommen, es mag uns offensichtlich erscheinen, dass weniger Anweisungen einen schnelleren Code bedeuten, und dies ist nicht immer der Fall. Es kann auch den Anschein haben, dass die Verwendung gespeicherter Daten immer schneller ist als die erneute Ausführung der Berechnungen. Wenn Sie also die Ergebnisse zwischenspeichern, ist alles in Ordnung. Wie im vorigen Fall ist es unmöglich, dies eindeutig zu formulieren, so wie das Gegenteil nicht unbedingt gesagt werden kann - alles hängt vom Kontext ab. Natürlich sollte man nur eines haben: Alles muss gemessen werden.

    Es gibt eine Reihe ziemlich zuverlässiger Praktiken, deren Diskussion Sie zu interessanten Gedanken führen kann. Wir müssen mit der Tatsache beginnen, dass die Mathematik Sie nicht im Stich lässt. Es kann gezeigt werden, dass Systeme mit unterschiedlichen Geschwindigkeiten gleichwertig sein können. Die Mathematik gibt Regeln vor, um die Gleichwertigkeit bestimmter Dinge zu zeigen und einige Eigenschaften zu identifizieren. Obwohl sie nicht voreingenommen ist, spielt es keine Rolle, welche Dinge interessant sind und welche nicht. Viele Leute denken, dass Optimierung auf dem Wissen über Maschinencode und der Arbeit mit Bits basiert, aber in Wirklichkeit hat es viel Mathematik, da Sie beweisen, dass ein schnelleres System einem langsameren System entspricht.

    Eine andere allgemeine Regel ist, dass Computer Dinge lieben, die langweilig sind. Müssen Sie sich mit zwei Vektoren multiplizieren, die jeweils eine Milliarde Elemente enthalten? Dies ist eine ideale Aufgabe für einen Computer. Alle darin enthaltenen Geräte sind speziell für diese Art von Aufgaben geschärft. Um diese Daten zu analysieren, basierend auf ihnen, um einen regulären Ausdruck zu erstellen, möchte ich dies nicht tun. Computer mögen keine Dinge wie Zweige, Abhängigkeiten, indirekte Aufrufe, kurz gesagt, sie mögen keinen intelligenten Code, sie mögen langweiligen Code. Computer mögen keine indirekten Aufzeichnungen - ein komplexes Problem, mit dem die Menschen, die mit Eisen zu tun haben, seit langer Zeit zu kämpfen haben und das sie nicht lösen können.

    Eine andere Regel ist, dass Sie möglichst niedrige Operationen bevorzugen, mit anderen Worten, die Addition der Multiplikation und die Multiplikation der Exponentiation vorziehen. Auch hier ist Mathematik nützlich.

    Schließlich die letzte Regel - je kleiner, desto schöner. Durch die geringe Größe können Computer ihre Vorteile am besten nutzen, da sie es vorziehen, dass die Daten und insbesondere die Anweisungen nahe beieinander liegen. Die Ergebnisse mehrerer Messungen der Geschwindigkeit der Anwendung werden sich immer unterscheiden, Sie werden eine gewisse Verteilung der Ergebnisse haben. Normalerweise nehmen wir nur den Durchschnitt dieser wenigen Ergebnisse. Das Problem ist jedoch, dass der Durchschnitt aufgrund der Besonderheiten von Computern viel Rauschen enthält. Wenn Bill Gates einen Bus fährt, ist im Durchschnitt jeder Passagier in einem Bus ein Milliardär. Das hört sich gut an, ist aber für einen Obdachlosen, der mit demselben Bus fährt, wenig bequem. Ähnliches gilt für Unterbrechungen: Die Multiplikation dauert Nanosekunden. Wenn Sie jedoch viele Messungen solcher Vorgänge durchführen, wird einer dieser Vorgänge zwangsläufig zwei Millisekunden lang unterbrochen. Der Unterschied beträgt drei Größenordnungen, und dennoch berücksichtigen Entwickler diesen Umstand nicht immer.

    Also wiederhole ich: Das Geräusch in Computern ist immer additiv; Für Menschen mag es unbedeutend erscheinen, aber für Mikrobankmarkierungen ist es bedeutend, und das arithmetische Mittel enthält viel Rauschen. Anstelle des Durchschnitts benötigen Sie einen Indikator, der nur die Zeit misst, die Sie irgendwie beeinflussen können. Wenn wir uns diesem Problem aus mathematischer Sicht nähern, werden wir feststellen, dass wir einen Wert finden müssen, der der größten Anzahl von Messungen entspricht, die wir durchgeführt haben. Mit anderen Worten, wir brauchen einen Mod. Das bringt uns sofort zum Problem: Was passiert, wenn du den Quicksort Mod nimmst? Wenn der Algorithmus probabilistisch ist oder wenn die Daten zufällig sind, wird es so gut wie nie einen Modus geben. Die Dichte der Werte ist im gesamten Spektrum nahezu gleich. In diesem Fall verwerfen wir einfach die 5% der größten Messungen und nehmen danach den Durchschnittswert - oder das Maximum -, in letzterem Fall haben wir eine Obergrenze, die in 95% der Fälle nicht überschritten wird. Fast immer sitzt ein Thema mit einem langsamen Modem im alten Keller, in dem jede Seite eine Stunde lang geladen wird. Rein menschlich sympathisieren wir natürlich mit ihm, aber wir können technisch nicht jedem helfen - daher müssen die restlichen 5% der Fälle vernachlässigt werden. Im Allgemeinen konzentrieren wir uns bei der Lösung von Netzwerkproblemen häufig auf das 95. Perzentil, da es unmöglich ist, sich auf das 100. Perzentil zu konzentrieren. Das hundertste Perzentil bedeutet das langsamste Ergebnis aller erfassten Messungen - dies ist nicht aussagekräftig. Fast immer sitzt ein Thema mit einem langsamen Modem im alten Keller, in dem jede Seite eine Stunde lang geladen wird. Rein menschlich sympathisieren wir natürlich mit ihm, aber wir können technisch nicht jedem helfen - daher müssen die restlichen 5% der Fälle vernachlässigt werden. Im Allgemeinen konzentrieren wir uns bei der Lösung von Netzwerkproblemen häufig auf das 95. Perzentil, da es unmöglich ist, sich auf das 100. Perzentil zu konzentrieren. Das hundertste Perzentil bedeutet das langsamste Ergebnis aller erfassten Messungen - dies ist nicht aussagekräftig. Fast immer sitzt ein Thema mit einem langsamen Modem im alten Keller, in dem jede Seite eine Stunde lang geladen wird. Rein menschlich sympathisieren wir natürlich mit ihm, aber wir können technisch nicht jedem helfen - daher müssen die restlichen 5% der Fälle vernachlässigt werden. Im Allgemeinen konzentrieren wir uns bei der Lösung von Netzwerkproblemen häufig auf das 95. Perzentil, da es unmöglich ist, sich auf das 100. Perzentil zu konzentrieren. Das hundertste Perzentil bedeutet das langsamste Ergebnis aller erfassten Messungen - dies ist nicht aussagekräftig. Bei der Lösung von Netzwerkproblemen konzentrieren wir uns häufig auf das 95. Perzentil, da es unmöglich ist, sich auf das 100. Perzentil zu konzentrieren. Das hundertste Perzentil bedeutet das langsamste Ergebnis aller erfassten Messungen - dies ist nicht aussagekräftig. Bei der Lösung von Netzwerkproblemen konzentrieren wir uns häufig auf das 95. Perzentil, da es unmöglich ist, sich auf das 100. Perzentil zu konzentrieren. Das hundertste Perzentil bedeutet das langsamste Ergebnis aller erfassten Messungen - dies ist nicht aussagekräftig.

    Ersetzen Sie Zweige durch Arithmetik


    Wie ich hoffe, wurde klar, dass die Messung kein einfaches Problem ist. Schauen wir uns einige Beispiele an und versuchen zunächst, die Verzweigung durch Arithmetik zu ersetzen. Wir sprechen über Fälle, in denen wir eine if-Anweisung benötigen, diese jedoch zu oft verwenden, ist unerwünscht. Stattdessen wird das Verzweigungsergebnis als 0/1-Wert integriert. Der Code sieht linear aus, der Computer muss ihn nur von Anfang bis Ende durchlaufen, ohne darüber nachzudenken, welchen Schritt Sie als Nächstes ausführen müssen.

    Versuchen wir, das folgende Problem zu lösen: Übertragen Sie die Minima jedes Quartils des Arrays auf das erste Quartil. Mit anderen Worten, das Array muss in vier Teile unterteilt sein und der Mindestwert jedes Teils sollte am Anfang des Arrays stehen.

    static void min4(double[] p) {
      int n = p.Length;
      int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4;
      for (; i < n / 4; ++i, ++j, ++k, ++l) {
        int m = p[i] <= p[j] ? i : j;
        if (p[k] < p[m]) m = k;
        if (p[l] < p[m]) m = l;
        Swap(ref p[i], ref p[m]);
      }
    }

    Oben ist der Basiscode. Übrigens kann ich stolz verkünden, dass ich diese Beispiele in C # übersetzt habe und sie erfolgreich kompiliert wurden. Der Code selbst ist recht einfach: `m wird der Index des kleinsten der beiden Werte zugewiesen, die sich an den Indizes` i und `j befinden, und dann wird eine ähnliche Zuweisung je nach den beiden anderen Indizes noch zweimal wiederholt. Schließlich wird der Wert am Index `m im Array mit dem Wert am Index` i umgekehrt. Wie Sie sehen, umgehen wir das Array mit vier induktiven Variablen.

    Das Problem, einen solchen Algorithmus zu testen, wird interessant und nicht offensichtlich sein. Wir müssen es nicht an einem Datensatz testen, sondern an Daten, die in verschiedenen Fällen auftreten können. Zum Beispiel bei Daten, die wie Orgelpfeifen aussehen: Zuerst erhöhen, dann verringern; auf zufälligen Daten mit einer gleichmäßigen Verteilung; auf einer zufälligen Menge von Nullen und Einsen - von nur zufälligen Daten hier besteht der Unterschied darin, dass es viele sich wiederholende Werte geben wird; auf bereits sortierten Daten; schließlich auf Daten, die durch reale Messungen eines physikalischen Phänomens erhalten wurden. Dies wird ein ernstzunehmender Ansatz zur Messung der Geschwindigkeit eines Algorithmus sein, und er wird allgemein von Leuten akzeptiert, die Algorithmen studieren.

    Versuchen wir, den Code zu verbessern, den wir gerade kennengelernt haben.

    static void min4(double[] p) {
      int q = p.Length / 4;
      int i = 0, j = n / 4, k = n / 2, l = 3 * n / 4;
      for (; i < q; ++i, ++j, ++k, ++l) {
        int m = p[i] <= p[j] ? i : j;
        if (p[k] < p[m]) m = k;
        if (p[l] < p[m]) m = l;
        Swap(ref p[i], ref p[m]);
      }
    }

    Als erste Optimierung werden wir versuchen, übermäßige Wiederholungen von Operationen zu vermeiden. Dazu nehmen wir mehrere Divisionsoperationen aus der Schleife heraus - dividieren Sie `n durch 2 und 4 und dividieren Sie 3 *` n durch 4. Nach dieser Optimierung stellen wir jedoch fest, dass die Berechnungen nicht für geeignet waren uns das Hauptproblem: der Code wird nicht schneller, obwohl es kompakter sein wird. Im besten Fall werden wir eine Verbesserung von einem halben Prozent erzielen.

    static void min4(double[] p) {
      int q = p.Length / 4;
      int i = 0, j = q, k = 2 * q, l = 3 * q;
      for (; i < q; ++i, ++j, ++k, ++l) {
        int m0 = p[i] <= p[j] ? i : j;
        int m1 = p[k] <= p[l] ? k : l;
        Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]);
      }
    }

    Die zweite Änderung, die wir am Code vornehmen, besteht darin, die Abhängigkeiten zu verringern. In der vorherigen Version des Algorithmus hängt die Zuweisung von "m" zu "k" oder "l" von dem Wert ab, der der obigen Zeile "m" zugewiesen wurde. Um die Anzahl von m Abhängigkeiten zu verringern, berechnen wir m0 und m1 getrennt und vergleichen sie dann. Als ich diese Optimierung durchführte, hoffte ich auf eine signifikante Verbesserung der Geschwindigkeit des Algorithmus, aber am Ende stellte sich heraus, dass er Null war. Meiner Meinung nach ist es wichtig, die Anzahl der Abhängigkeiten so gering wie möglich zu halten. Deshalb habe ich den Code gespeichert.

    static void min4(double[] p) {
      int q = p.Length / 4;
      for (int  i = 0; i < q; ++i) {
        int m0 = p[i] <= p[i + q] ? i : i + q;
        int m1 = p[i + 2 * q] <= p[i + 3 * q] ?
          i + 2 * q : i + 3 * q;
        Swap(ref p[i], ref p[p[m0] <= p[m1] ? m0 : m1]);
      }
    }

    Versuchen wir nun, die Anzahl der induktiven Variablen von vier auf eins zu reduzieren, und berechnen die verbleibenden drei arithmetisch, da sie in einem konstanten Verhältnis zueinander stehen. Dies ist ganz einfach: Anstelle von 'k' haben wir 'i + q' anstelle der beiden anderen Variablen 'i + 2 * q' und 'i + 3 * q'. Ich hatte auch große Hoffnungen auf diese Optimierung, aber wie bei der vorherigen gab es keine Ergebnisse in der Zeit. Dies zeigt erneut die Wichtigkeit von Messungen: Ohne sie könnte ich mich rühmen, die Funktionsweise des Algorithmus wesentlich verbessert zu haben, und ich hätte sehr wichtige Argumente.

    static void min4(double[] p) {
      int q = p.Length / 4, q2 = q + q;
      for (int i = q; i < q2: ++i) {
        int m0 = p[i - q] < p[i] ? i - q : i;
        int m1 = p[i + q2] < p[i + q] ? i + q2 ? i + q;
        Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]);
      }
    }

    Als vierten Versuch strukturieren wir den Zyklus neu, um die Multiplikation mit 3 loszuwerden. Dies ergibt eine Verbesserung von 3%. Das Ergebnis ist immer noch nicht beeindruckend. Versuchen Sie als nächstes, die ternären Operatoren loszuwerden.

    // Returns: value if flag is true, 0 otherwise
    static int optional(bool flag, int value) {
     return -Convert.ToInt32(flag) & value;
    }

    Dazu möchte ich Ihnen eine neue Funktion vorstellen - `static int optional (bool flag, int value). Der eingegebene Boolesche Wert wird in Int32 konvertiert, mit -1 multipliziert und zusammen mit dem zweiten Eingabewert an den bitweisen AND-Operator übergeben. Wenn das Eingabe-Flag falsch war, ist es in int32 0, und nach allen Konvertierungen in der Ausgabe erhalten wir immer noch 0. Wenn das Eingabe-Flag wahr war, ist es in int32 1, multipliziert mit -1, und nach dem Bit erhalten wir FFFFFFFF "Und" mit einer beliebigen Nummer gibt diese zweite Nummer an. Bitte beachten Sie, dass es nirgends eine if-Anweisung gibt, der Code ist ohne Verzweigung, es ist für einen Computer langweilig (obwohl es uns kompliziert erscheint).

    static void min4(double[] p) {
      int q = p.Length / 4, q2 = q + q;
      for (int i = q; i < q2; ++i) {
        int m0 = i - optional(p[i - q] <= p[i], q);
        int m1 = i + q + optional(p[i + q2] < p[i + q], q);
        Swap(ref p[i - q], ref p[p[m0] <= p[m1] ? m0 : m1]);
      }
    }

    Wir werden ternäre Operatoren durch diese "optionale" Funktion ersetzen und diese in die Berechnung integrieren. Wir wenden es zweimal an und lassen im dritten Fall das Fragezeichen. Anstelle von vier Prüfungen in diesem Zyklus werde ich also nur eine haben.



    Aus den Messergebnissen auf dem Objektträger geht hervor, wie wichtig es war, den Algorithmus an mehreren verschiedenen Datensätzen zu testen. An einem Set würden wir nichts verstehen. Bei Zufalls- und Realdaten haben wir eine mehr als zweifache Beschleunigung, bei Orgelpfeifen und sortierten Daten eine leichte Verlangsamung. Dies liegt an der Tatsache, dass es bei sortierten Daten für den Übergangsprädiktor keine Überraschungen gibt, die mit 100% iger Genauigkeit vorhergesagt werden. Bei Orgelpfeifen haben wir eine falsche Vorhersage in der Mitte des Datensatzes - wiederum eine sehr hohe Genauigkeit. Im Gegensatz dazu wird der Unterschied zwischen unseren beiden Ansätzen bei zufälligen Daten sehr groß sein. Wir haben alle unvorhersehbaren Prüfungen durch einfache Logik ersetzt. Hier kommen wir zu einer einfachen Wahrheit zurück: Computer sind, wie der Name schon sagt, für das Rechnen bestimmt (Computer - Computing). Verzweigen, Bilder auf dem Bildschirm anzeigen - das tun sie alle viel schlimmer. Das bitweise „Und“ ist für sie viel einfacher als das Übergeben der if-Anweisung.

    static void min4(double[] p) {
      int q = p.Length / 4, q2 = q + q;
      for (int i = 0; i < q; ++i) {
        int m = i + optional(p[i + q] < p[i], q);
        m += optional(p[i + q2] < p[m], q);
        m += optional(p[i + q2 + q] < p[m], q);
        Swap(ref p[i], ref p[m]);
      }
    }

    Nachdem die Optimierung ein positives Ergebnis gebracht hat, werden wir versuchen, den letzten ternären Operator durch unsere optionale Funktion zu ersetzen. Diesmal ist der Geschwindigkeitsgewinn gering. Um zu verstehen, warum dies geschieht, müssen Sie sich den generierten Code ansehen. In der vorherigen Version des Codes, in der das Fragezeichen noch vorhanden war, hat der Compiler bereits eine Möglichkeit gefunden, den Code ohne Verzweigung auszuführen. Und wenn er zum ternären Operator kommt, kann er es bereits vorhersagen. Wenn Sie dieses letzte Stück durch `optional ersetzen, erhalten Sie einen etwas schlechteren Code. Deshalb, wiederhole ich, ist es wichtig, jedes Mal Messungen vorzunehmen.

    // Returns: v1 if flag is true, v2 otherwise
    static int ifelse(bool flag, int v1, int v2) {
      return (-Convert.ToInt32(flag) & v1) |
        ((Convert.ToInt32(flag) - 1) & v2);
    }
    

    Eine weitere Funktion, die ich Ihnen empfehlen möchte, ist ifelse ohne Verzweigungen, die Sie jetzt auf dem Bildschirm sehen. Die Leistungsverbesserungen in unserem Beispiel konnte ich damit jedoch nicht erreichen. Wenn 0 als Flag übergeben wird, ist die erste Zeile 0; im zweiten subtrahieren wir 1 von 0 in Int32 und erhalten FFFFFFFF, woraufhin dieser Wert zusammen mit dem Funktionsargument 'v2 an das Bit' Und 'übergeben wird, was uns dieses Argument selbst ohne Änderungen gibt; Schließlich werden die erste und die zweite Zeile an das bitweise "OR" übergeben, das uns wiederum "v2" gibt. Wenn das Flag 1 ist, ist die erste Zeile gleich 'v1; im zweiten subtrahieren wir 1 von 1 und erhalten 0, wodurch die gesamte Zeile 0 ist, und 0 und 'v1 im bitweisen' OR 'ergeben' v1 '.

    Ich hoffe, dass ein solches "ifelse ohne Verzweigungsfunktion" diejenigen interessieren wird, die am Backend beteiligt sind - moderne Compiler verwenden aus irgendeinem Grund diesen Ansatz derzeit nicht. Mit diesen Funktionen können Sie die Algorithmen neu organisieren, damit die Compiler sie für Sie verstehen, da Sie schlauer und kreativer sind als Ihr Compiler.

    Große festgelegte Kreuzung


    Wechseln Sie das Gesprächsthema ein wenig und gehen Sie zum Schnittpunkt großer Mengen über. Bisher haben wir über einzelne Operatoren gesprochen, jetzt werden wir neue Algorithmen erstellen, also müssen wir uns von den Details ablenken und unseren Geist für eine größere Perspektive öffnen. Ich gehe davon aus, dass Sie mit Mergesort vertraut sind, zwei Vektoren multiplizieren und nach gemeinsamen Elementen von zwei sortierten Vektoren suchen. Zwei sortierte Mengen werden durchlaufen, und wenn gleiche Elemente enthalten sind, wird dies als Übereinstimmung betrachtet. Wenn eines der beiden verglichenen Elemente kleiner ist, verschiebt es sich. Dieser Algorithmus ist recht einfach, aber sehr verbreitet - wahrscheinlich der weltweit am häufigsten verwendete. Es wird in allen Abfragen aus mehreren Wörtern verwendet. Jede solche Abfrage ist der Schnittpunkt zweier Mengen. Dieser Algorithmus,

    int Intersect(double[] a1, double[] a2, double[] t) {
      if (a1.Length == 0 || a2.Length == 0) return 0;
      int i1 = 0, i2 = 0, i = 0;
      for (;;)
        if (a1[i1] < a2[i2]) {
          if (++i1 == a1.Length) break;
        } else if (a2[i2] < a1[i1]) {
          if (++i2 == a2.Length) break;
        } else {
          t[i++] = a1[i1];
          if (++i1 == a1.Length || ++i2 == a2.Length)
            break:
        }
      return i;
    }

    Sehen Sie sich die grundlegende Implementierung dieses Algorithmus an. Wenn beide Eingabesätze leer sind, geben wir natürlich 0 zurück. Als nächstes starten wir eine Endlosschleife, in der wir bei Übereinstimmung das Ergebnis um 1 erhöhen und prüfen, ob der Zyklus abgeschlossen werden soll. Anstelle einer Endlosschleife könnte man die for-Anweisung verwenden und die Bedingung zum Beenden der Schleife angeben. Aber das würde zusätzliche Arbeit bedeuten. In der Implementierung, die Sie auf der Folie sehen, haben wir im ersten Zweig "if" (a1 [i1] <a2 [i2]), wonach es eine Zunahme von "i1" um 1 gibt, und wir können nur "i1" überprüfen. Ebenso müssen wir im zweiten Zweig nur 'i2' prüfen. Beide Werte müssen nur im dritten Zweig überprüft werden. Wenn diese Prüfung zu Beginn des Zyklus wäre, würden wir die zusätzliche Arbeit erledigen.

    Versuchen wir, diese Implementierung zu verbessern. Derzeit ist die algorithmische Komplexität linear und hängt von zwei Eingabeargumenten ab. Beim maschinellen Lernen ist es häufig erforderlich, die Schnittmenge von Mengen zu finden, die sich in Größe oder Statistik stark voneinander unterscheiden. Beispielsweise haben Sie einen langen Eingabevektor und einen kurzen Merkmalsvektor, mit denen Sie vergleichen. In unserem Code kann es eine Million Datensätze in 'a1' und tausend in 'a2' geben. In diesem Fall sind wir nicht bereit, eine Million Schritte zu durchlaufen, um diesen Algorithmus zu vervollständigen. Die größte Last wird hier in der folgenden Codezeile sein: `if (++ i1 == a1.length) break. Kurz davor erfolgt ein Vergleich und anschließend eine Inkrementierung des Werts in dieser Zeile. Dies ist im Wesentlichen eine lineare Suche. Wir iterieren über einen langen Vektor, um nach Elementen eines kurzen zu suchen.

    Versuchen wir, diesen Algorithmus zu verbessern. Nun, wenn nicht lineare Suche, dann ist Binär besser, oder? Verwenden wir die Binärdatei. Sein Vorteil ist, dass er den Index des größten der kleineren Elemente angibt.

    int Intersect(double[] a1, double[] a2, double[] t) {
      int i1 = 0, i = 0;
      for (; i1 != a1.Length; ++i1) {
        auto m = Bsearch(a2, a1[i1]);
        if (m == a2.Length) continue;
        --m;
        if (!(a2[m] < a1[i1]))
          t[i++] = a1[i1];
      }
      return i;
    }
    

    Der obige Code ist eine Implementierung unseres binären Suchalgorithmus. Aber es ist nicht sehr effektiv. Die schlimmste Situation ist hier, wenn die binäre Suche jedes Mal fehlschlägt. Und es wird in ganz wichtigen Szenarien auftreten - zum Beispiel, wenn beide Sätze identisch sind. Sie schneiden wie ein Idiot Kreise mit der binären Suche, während Sie nur den ersten linearen Algorithmus durchlaufen mussten. Warum binäre Suche, wenn der gewünschte Eintrag - immer gleich hier, der erste in der Liste?

    Wie lässt sich der Algorithmus erfolgreich auf identischen und unterschiedlichen Daten anwenden? Das Überprüfen aller Daten ist für Ressourcen zu kostspielig. Ich mache einen Vorbehalt, dass es sich nicht um völlig identische Daten handelt, sondern um sehr ähnliche, mit ähnlichen Statistiken auch unterschiedliche Größen. Sie können die folgenden Punkte überprüfen. Die naheliegende Lösung besteht darin, Ihre Suche zu reduzieren. Wenn wir eine binäre Suche durchführen, sind wir nach dem Finden eines Elements nicht mehr an kleineren Elementen interessiert, da der zweite Vektor ebenfalls sortiert wird. So können wir jedes Mal unseren Suchbereich verkleinern und alle Elemente aus dem gefundenen Element entfernen.

    int Intersect(double[] a1, double[] a2, double[] t) {
      int i1 = 0, i2 = 0, i = 0;
      for (; i1 != a1.Length; ++i1) {
        auto m = Bsearch(a2, i2, a2.Length, a1[i1]);
        if (m == i2) continue;
        if (!(a2[m - 1] < a1[i1]))
          t[i++] = a1[i1];
        i2 = m + 1;
      }
      return i;
    }

    Hier ist die Umsetzung dieses Ansatzes. Sie sehen, dass wir jedes Mal eine binäre Suche nach einem Teil des ursprünglichen Arrays durchführen, beginnend mit "i2" und endend mit "a2.length". Da `i2 mit jeder Suche größer wird, wird der Suchbereich verkleinert.

    Die nächste Optimierung, die ich hier implementieren möchte, bezieht sich auf den Galloping Search-Algorithmus. Im Wesentlichen ist dies eine binäre Suche mit einem anderen Schritt. Bei der binären Suche beginnen wir jedes Mal mit der Mitte - aber denken wir, wenn wir im Telefonbuch nach einem Namen suchen, öffnen wir ihn nicht in der Mitte? Wenn der Nachname einer Person mit "B" beginnt, öffnen wir das Buch näher am Anfang. Dieses Prinzip wird in einer galoppierenden Suche implementiert: Wir beginnen mit dem Crawlen der Daten in aufsteigender Richtung mit einem Schritt, der nach jeder Überprüfung exponentiell zunimmt: zuerst 1, dann 2, dann 4. Dies gibt uns eine gute algorithmische Komplexität. Wenn die Stufe linear wächst, ist die Komplexität quadratisch. Wenn wir das gewünschte Element "springen", führen wir eine normale binäre Suche für das verbleibende Segment durch. Dies ist bereits gering und hat keinen wesentlichen Einfluss auf die Ausführungszeit des Algorithmus. Somit kombinieren wir alle Vorteile beider Ansätze. Implementierung eines solchen Algorithmus:

    int GBsearch(double[] a, int i, int j, double v) {
      for (int step = 1;; step *= 2) {
        if (i >= j) break;
        if (a[i] > v) break;
        if (i + step >= j)
          return Bsearch(a, i + 1, J, v);
        if (a[i + step] > v)
          return Bsearch(a, i + 1, i + step, v);
        i += step + 1;
      }
      return i;
    }

    Wir diskutieren nun die Skalierung, dh versuchen, den Schnittpunkt von mehr als zwei Mengen zu finden. Für jede Suche nach mehreren Wörtern müssen wir den Schnittpunkt mehrerer Mengen finden. Dazu können wir zum Beispiel die ersten beiden Mengen vergleichen, dann deren Schnittmenge mit der dritten und so weiter. Dies ist jedoch keine optimale Lösung. Wir müssen die ersten Elemente aller Mengen nehmen und die kleinsten finden, die dann verschoben werden müssen. Wir brauchen eine Datenstruktur, die es uns ermöglicht, das kleinste der vielen Elemente zu finden, und die eine konstante Komplexität aufweist. Eine solche Datenstruktur ist ein Haufen. Aber es wird ein seltsamer Haufen sein, es wird nicht auf einem physischen Array basieren. Es wird imaginär sein, wir werden nur die ersten Elemente unserer Sets darin organisieren. Den kleinsten Gegenstand auf dem Haufen finden,

    Die Arbeit an den Themen, die wir heute in der Praxis diskutieren, hat eine eher handwerkliche Form. In der Praxis werden wir meistens mehrere Sets haben, nicht nur zwei, und es wurde viel Arbeit zu diesem Thema geschrieben. Der klassische Algorithmus ist hier SVS, bei dem wir die Mengen gruppieren, die zwei kleinsten nehmen und die kürzesten als Kandidaten auswählen. Nach dem Link können Sie einen guten Überblick über das Thema finden. Die Probleme, die mit sich überschneidenden Mengen, dem Skalarprodukt von Vektoren mit geringer Dichte, dem Sortieren durch Zusammenführen und jeglichen Formen des Vergleichs mit dem Bild im Laufe der Zeit verbunden sind, werden immer interessanter. Der Algorithmus, den ich Ihnen gezeigt habe, hat sich als sehr nützlich erwiesen. Vielen Dank für Ihre Aufmerksamkeit.

    Andrei Alexandrescu wird nicht zur DotNext 2018 Moskau kommen, aber Jeffrey Richter, Greg Young, Pavel Yosifovich und andere werden dort sein. Die Namen der Referenten und Berichtsthemen finden Sie hier , Tickets hier . Jetzt mitmachen!

    Jetzt auch beliebt: