Hier ist mein Python-Code:
%Vor%Und hier ist mein Rust-Code:
%Vor%Ich glaube, das sind ungefähr gleichwertig. Ich bekomme folgende Leistungsergebnisse:
%Vor%und
%Vor% (Erstellen mit cargo und --release gibt das gleiche Ergebnis).
Mir ist klar, dass Pythons set in C implementiert ist, und daher wird erwartet, dass es schnell ist, aber ich habe nicht erwartet, dass es schneller ist als Rust. Wäre es nicht nötig, extra zu prüfen, ob Rust nicht funktioniert?
Vielleicht fehlt mir etwas in der Art, wie ich mein Rust-Programm kompiliere. Gibt es noch andere Optimierungs-Flags, die ich verwenden sollte?
Eine andere Möglichkeit ist, dass der Code nicht wirklich gleichwertig ist, und Rust macht unnötige zusätzliche Arbeit, vermisse ich etwas?
Python-Version:
%Vor%Rustc-Version (ich weiß, dass 1.6 draußen ist)
%Vor% Ich verwende ubuntu 14.04 und meine Systemarchitektur ist x86_64.
Wenn ich das Set-Gebäude aus der Schleife entferne und nur die Kreuzung wiederhole, ist Rust für beide Fälle natürlich schneller als Python 2.7.
Ich habe nur Python 3 (setobject.c) gelesen , aber die Implementierung von Python hat einiges zu bieten.
Es nutzt die Tatsache, dass beide Python-Set-Objekte die gleiche Hash-Funktion verwenden, so dass der Hash nicht neu berechnet wird. Rust HashSet s haben instanzspezifische Schlüssel für ihre Hash-Funktionen, also müssen sie während der Überschneidung Schlüssel aus einem Satz mit der Hash-Funktion des anderen Satzes aufschlüsseln.
Andererseits muss Python eine dynamische Schlüsselvergleichsfunktion wie PyObject_RichCompareBool für jeden passenden Hash aufrufen, während der Rust-Code Generics verwendet und die Hash-Funktion und den Vergleichscode für i32 spezialisieren wird. Der Code zum Hashen eines i32 in Rust sieht relativ billig aus, und ein großer Teil des Hashalgorithmus (der eine längere Eingabe als 4 Bytes behandelt) wird entfernt.
Es scheint, dass es die Konstruktion der Sets ist, die Python und Rust auseinander setzen. Und tatsächlich ist nicht nur die Konstruktion, sondern auch ein bedeutender Code, der die Rust HashSet s zerstört. (Dies kann verbessert werden, Fehler hier eingereicht: # 31711 )
Das Leistungsproblem läuft auf die Standard-Hashing-Implementierung von HashMap und HashSet hinaus. Rosts Standard-Hash-Algorithmus ist ein guter Allzweck-Algorithmus, der auch gegen bestimmte Arten von DOS-Angriffen schützt. Es funktioniert jedoch nicht für sehr kleine oder sehr große Datenmengen.
Einige Profiler haben gezeigt, dass make_hash<i32, std::collections::hash::map::RandomState> etwa 41% der Gesamtlaufzeit beansprucht. Ab Rust 1.7 können Sie auswählen, welcher Hash-Algorithmus verwendet werden soll. Der Wechsel zum FNV-Hashalgorithmus beschleunigt das Programm beträchtlich:
Auf meinem Rechner benötigt das 2.714s verglichen mit Pythons 9.203s.
Wenn Sie dieselben Änderungen vornehmen, um das Set-Gebäude aus der Schleife zu entfernen , benötigt der Rust-Code 0,829s verglichen zu dem Python-Code 3.093s.