Warum sind Swift-Iteratoren langsamer als die Array-Erstellung?

8

Dies steht in engem Zusammenhang mit dieser Frage , in der davon ausgegangen wurde, dass sie verwendet wird Generatoren (Iteratoren) zum Durchqueren eines verschachtelten Arrays wären optimal für das Durchlaufen der Elemente, solange Sie das Ergebnis nicht speichern müssen, während die Verwendung wiederholter Array-Verkettungen am besten war, wenn Sie nur das Array glätten wollten.

>

Ich habe mich jedoch entschieden, einige Tests durchzuführen, und wenn ich diese Funktion implementiere (die ein Array [Any] , das entweder Int s oder [Int] s enthält, abflacht) sowohl in der Lazy- als auch in der gespeicherten Form, stellt sich heraus, dass das gespeicherte Formular ist schneller, auch wenn nur für die Iteration durch die Elemente verwendet! Das bedeutet, dass die Iteration durch den Generator mehr Zeit in Anspruch nimmt als die Konstruktion eines neuen Arrays im Speicher und dann durch das .

Unglaublich, es ist sogar etwa 5-70% langsamer als eine Python Implementierung des gleichen Programms, die sich mit kleinerer Eingabe verschlechtert. Swift wurde mit dem Flag -O erstellt.

Hier waren die drei Testfälle 1. kleiner Input, gemischt; 2. große Eingabe, [Int] dominant, 3. große Eingabe, Int dominant:

Schnell

%Vor%

Python

%Vor%

Der Generator und der Array Builder:

Schnell

%Vor%

Python

%Vor%

Und die Benchmark-Ergebnisse (100000 Schleifen beim ersten Testfall, 1000 bei den anderen):

Schnell

%Vor%

Python

%Vor%

Klar, Swift ist sehr, sehr gut im Aufbau von Arrays. Aber warum sind seine Generatoren so langsam, manchmal sogar langsamer als Pythons? (Markiert mit einem * in der Tabelle.) Das Testen mit extrem großer Eingabe (& gt; 100.000.000 Elemente, die Swift fast zum Absturz bringt) legt nahe, dass der Generator selbst am Limit langsamer als die Array-Füllung um mindestens einen Faktor ist von 3,25 im besten Fall.

Wenn dies der Sprache wirklich innewohnt, hat es einige witzige Auswirkungen. Zum Beispiel würde der gesunde Menschenverstand (für mich als Python-Programmierer sowieso) haben, dass wir, wenn wir ein unveränderliches Objekt (wie eine Zeichenfolge) synthetisieren wollten, zuerst die Quelle einer generierenden Funktion zuführen sollten, um sie zu entfalten und dann zu übergeben aus der Ausgabe in eine joined() -Methode, die auf einer einzigen flachen Sequenz arbeitet. Stattdessen scheint die effizienteste Strategie die Serialisierung über Array zu sein; Entfalten der Quelle zu einem intermediären Array und dann Konstruieren der Ausgabe aus dem Array.

Baut man ein ganzes neues Array auf und durchläuft es dann schneller, als eine faule Iteration auf dem ursprünglichen Array? Warum?

( Möglicherweise verwandte Javascript-Frage )

Bearbeiten

Hier ist der Testcode:

Schnell

%Vor%

Python

%Vor%     
taylor swift 19.11.2016, 04:09
quelle

1 Antwort

3

Sie haben gefragt: "Warum sind seine [Swift] -Generatoren so langsam, in einigen Fällen sogar langsamer als Pythons?"

Meine Antwort ist, dass ich nicht glaube, dass sie fast so langsam sind, wie Ihre Ergebnisse zeigen könnten. Insbesondere werde ich versuchen zu demonstrieren, dass das Durchlaufen eines Iterators schneller sein sollte als das Erstellen eines Arrays für alle Ihre Testfälle.

In früheren Arbeiten (siehe einen verwandten Blogeintrag im Ссылка ), ich fand heraus, dass Swift-Iteratoren bei der Arbeit über eine Bitset-Klasse etwa halb so schnell waren wie die Entsprechung in Java. Das ist nicht großartig, aber Java ist in dieser Hinsicht sehr effizient. Inzwischen geht Go schlechter. Ich unterbreite Ihnen, dass Swift-Iteratoren wahrscheinlich nicht ideal effizient sind, aber sie sind wahrscheinlich in einem Faktor von zwei von dem, was mit rohem C-Code möglich ist. Und die Performance-Lücke hat wahrscheinlich mit unzureichender Funktion in Swift zu tun.

Ich sehe, dass Sie AnyIterator verwenden. Ich schlage vor, stattdessen einen struct von IteratorProtocol abzuleiten, was den Vorteil hat sicherzustellen, dass es keinen dynamischen Versand geben muss. Hier ist eine relativ effiziente Möglichkeit:

%Vor%

Mit dieser Klasse bekomme ich die folgenden Zahlen. Für jeden Testfall werden die ersten vier Ansätze aus Ihrem Codebeispiel genommen, während die letzten zwei Ansätze (schneller Iterator) mit der neuen Struktur erstellt werden. Beachten Sie, dass "Schleifen durch einen schnellen Iterator" immer am schnellsten ist.

%Vor%

Sie finden mein komplettes Codebeispiel auf GitHub: Ссылка

    
Daniel Lemire 01.12.2016, 16:20
quelle