Mein Python-Programm wird schneller ausgeführt als meine Java-Version desselben Programms. Woran liegt das?

Question

Aktualisierung: 2009-05-29

Vielen Dank für die vielen Anregungen und Ratschläge. Ich habe Ihre Vorschläge genutzt, um meinen Produktionscode im Durchschnitt 2,5 Mal schneller auszuführen als mein bestes Ergebnis vor ein paar Tagen. Am Ende war ich in der Lage, den Java-Code am schnellsten zu erstellen.

Lektionen:

• Mein Beispielcode unten zeigt das Einfügen von primitiven Ints, aber der Produktionscode speichert tatsächlich Strings (mein Fehler). Als ich das korrigiert habe, stieg die Python-Ausführungszeit von 2,8 Sekunden auf 9,6 Sekunden. Das heißt, dass Java beim Speichern von Objekten auf Anhieb schneller war.

• Aber das ist noch nicht alles. Ich hatte das Java-Programm wie folgt ausgeführt:

  java -Xmx1024m SpeedTest

Wenn Sie jedoch die anfängliche Heap-Größe wie folgt festlegen, erzielen Sie eine enorme Verbesserung:

java -Xms1024m -Xmx1024m SpeedTest

Durch diese einfache Änderung wurde die Ausführungszeit um mehr als 50 % verkürzt. Das Endergebnis für meinen SpeedTest lautet also: Python 9,6 Sekunden. Java 6,5 Sekunden.

Ursprüngliche Frage:

Ich hatte den folgenden Python-Code:

import time
import sys

def main(args):    
    iterations = 10000000
    counts = set()
    startTime = time.time();    
    for i in range(0, iterations):
        counts.add(i)
    totalTime = time.time() - startTime
    print 'total time =',totalTime
    print len(counts)

if __name__ == "__main__":
    main(sys.argv)

Auf meinem Rechner wurde es in etwa 3,3 Sekunden ausgeführt, aber ich wollte es schneller machen, also beschloss ich, es in Java zu programmieren. Ich nahm an, dass Java kompiliert ist und im Allgemeinen als schneller als Python angesehen wird, so dass ich einige große Vorteile sehen würde.

Hier ist der Java-Code:

import java.util.*;
class SpeedTest
{    
    public static void main(String[] args)
    {        
        long startTime;
        long totalTime;
        int iterations = 10000000;
        HashSet counts = new HashSet((2*iterations), 0.75f);

        startTime = System.currentTimeMillis();
        for(int i=0; i<iterations; i++)
        {
            counts.add(i);
        }
        totalTime = System.currentTimeMillis() - startTime;
        System.out.println("TOTAL TIME = "+( totalTime/1000f) );
        System.out.println(counts.size());
    }
}

Dieser Java-Code tut also im Grunde dasselbe wie der Python-Code. Aber er wurde in 8,3 Sekunden statt in 3,3 Sekunden ausgeführt.

Zur Vereinfachung habe ich dieses einfache Beispiel aus einem realen Beispiel entnommen. Das kritische Element ist, dass ich (Set oder HashSet) habe, die mit einer Menge von Mitgliedern ähnlich wie das Beispiel endet.

Hier sind meine Fragen:

1. Wie kommt es, dass meine Python-Implementierung schneller ist als meine Java-Implementierung?

2. Gibt es eine bessere Datenstruktur als das HashSet (Java) zu verwenden, um eine eindeutige Sammlung zu halten?

3. Was würde die Python-Implementierung schneller machen?

4. Was würde die Java-Implementierung schneller machen?

UPDATE:

Vielen Dank an alle, die bis jetzt beigetragen haben. Bitte erlauben Sie mir, einige Details hinzuzufügen.

Ich habe meinen Produktionscode nicht beigefügt, da er recht komplex ist. Und er würde eine Menge Ablenkung erzeugen. Der Fall, den ich oben dargestellt habe, ist so einfach wie möglich. Damit meine ich, dass der Java-Put-Aufruf viel langsamer zu sein scheint als das add() des Python-Sets.

Die Java-Implementierung des Produktionscodes ist auch etwa 2,5 bis 3 Mal langsamer als die Python-Version - genau wie oben.

Ich mache mir keine Sorgen über die Aufwärmphase oder den Start-Overhead von vm. Ich möchte nur den Code von meiner startTime mit meiner totalTime vergleichen. Bitte kümmern Sie sich nicht mit anderen Fragen.

Ich habe das Hashset mit mehr als genug Eimern initialisiert, so dass es nie einen Rehash durchführen muss. (Ich werde immer im Voraus wissen, wie viele Elemente die Sammlung letztendlich enthalten wird.) Ich nehme an, man könnte argumentieren, dass ich es auf Iterationen/0,75 hätte initialisieren sollen. Aber wenn Sie es ausprobieren, werden Sie sehen, dass die Ausführungszeit nicht wesentlich beeinträchtigt wird.

Ich habe Xmx1024m für diejenigen eingestellt, die neugierig sind (mein Rechner hat 4GB Ram).

Ich verwende die Java-Version: Java(TM) SE Runtime Environment (Build 1.6.0_13-b03).

In der Produktionsversion von speichere ich eine Zeichenfolge (2-15 Zeichen) im HashSet, so dass ich keine Primitive verwenden kann, obwohl dies ein interessanter Fall ist.

Ich habe den Code viele, viele Male ausgeführt. Ich bin sehr zuversichtlich, dass der Python-Code zwischen 2,5 und 3 Mal schneller ist als der Java-Code.

Answer 1

Sie testen nicht wirklich Java gegen Python, Sie testen java.util.HashSet Verwendung von autoboxed Integers im Vergleich zu Pythons nativer Mengen- und Ganzzahlverarbeitung.

Offensichtlich ist die Python-Seite in diesem speziellen Mikrobenchmark tatsächlich schneller.

Ich habe versucht, HashSet zu ersetzen durch TIntHashSet de GNU-Fundgrube und erreichte einen Beschleunigungsfaktor zwischen 3 und 4, wodurch Java leicht vor Python liegt.

Die eigentliche Frage ist, ob Ihr Beispielcode wirklich so repräsentativ für Ihren Anwendungscode ist, wie Sie denken. Haben Sie einen Profiler laufen lassen und festgestellt, dass der größte Teil der CPU-Zeit darauf verwendet wird, eine große Anzahl von Ints in ein HashSet zu setzen? Wenn nicht, ist das Beispiel irrelevant. Selbst wenn der einzige Unterschied darin besteht, dass Ihr Produktionscode andere Objekte als Ints speichert, könnten deren Erstellung und die Berechnung ihres Hashcodes leicht das Einfügen von Sets dominieren (und den Vorteil von Python bei der speziellen Behandlung von Ints völlig zunichte machen), was diese ganze Frage sinnlos macht.

Answer 2

Ich vermute, dass das daran liegt, dass Python den Integer-Wert selbst als Hash verwendet und die hashtable-basierte Implementierung von set diesen Wert direkt verwendet. Aus den Kommentaren in der Quelle :

Das ist nicht unbedingt schlecht! Im Gegenteil, in einer Tabelle der Größe 2**i werden die niederwertigen i-Bits als anfänglichen Tabellenindex zu nehmen, ist extrem schnell, und es gibt es überhaupt keine Kollisionen für Dicts, die durch einen zusammenhängenden Bereich von Ints indiziert sind. Dasselbe gilt ungefähr, wenn die Schlüssel "aufeinanderfolgende" Zeichenketten sind. Das bedeutet führt also in häufigen Fällen zu einem Verhalten, das besser ist als das des Zufalls, und das ist sehr wünschenswert.

Dieser Mikrobenchmark ist so etwas wie ein Best Case für Python, da er genau null Hash-Kollisionen ergibt. Wenn hingegen Javas HashSet die Schlüssel neu aufbereitet, muss es die zusätzliche Arbeit leisten und erhält auch ein viel schlechteres Verhalten bei Kollisionen.

Wenn Sie den Bereich (Iterationen) in einer temporären Variablen speichern und vor der Schleife eine random.shuffle darauf ausführen, ist die Laufzeit mehr als 2x langsamer, selbst wenn die Shuffle- und Listenerstellung außerhalb der Schleife erfolgt.

Answer 3

Im Allgemeinen habe ich die Erfahrung gemacht, dass Python-Programme schneller laufen als Java-Programme, obwohl Java eine etwas "niedrigere" Sprache ist. Übrigens werden beide Sprachen in Bytecode kompiliert (das sind diese .pyc-Dateien - man kann sie sich als eine Art .class-Dateien vorstellen). Beide Sprachen werden als Byte-Code auf einem virtuellen Stapelrechner interpretiert.

Man würde erwarten, dass Python bei Dingen wie zum Beispiel langsamer ist, a.b . In Java, das a.b wird in eine Dereferenz aufgelöst. Python hingegen muss eine oder mehrere Hash-Tabellenabfragen durchführen: den lokalen Bereich prüfen, den Modulbereich prüfen, den globalen Bereich prüfen, Builtins prüfen.

Andererseits ist Java notorisch schlecht bei bestimmten Operationen wie der Objekterzeugung (was wahrscheinlich der Übeltäter in Ihrem Beispiel ist) und der Serialisierung.

Zusammenfassend lässt sich sagen, dass es keine einfache Antwort gibt. Ich würde nicht erwarten, dass eine der beiden Sprachen für alle Codebeispiele schneller ist.

Korrektur: Mehrere Leute haben darauf hingewiesen, dass Java bei der Objekterstellung nicht mehr so schlecht ist. In Ihrem Beispiel ist es also etwas anderes. Vielleicht ist es das Autoboxing, das teuer ist, vielleicht ist der Standard-Hash-Algorithmus von Python in diesem Fall besser. In meiner praktischen Erfahrung, wenn ich Java-Code in Python umschreibe, sehe ich immer eine Leistungssteigerung, aber das könnte sowohl an der Sprache liegen als auch daran, dass das Umschreiben im Allgemeinen zu Leistungssteigerungen führt.

Answer 4

Eine andere mögliche Erklärung ist, dass Sets in Python nativ in C-Code implementiert sind, während HashSets in Java in Java selbst implementiert sind. Daher sollten Sets in Python von Natur aus viel schneller sein.

Answer 5

Ich möchte mit ein paar Mythen aufräumen, die ich in den Antworten gesehen habe:

Java wird zwar in Bytecode kompiliert, aber in den meisten Laufzeitumgebungen letztlich zu nativem Code. Leute, die sagen, dass C von Natur aus schneller ist, erzählen nicht die ganze Geschichte. Ich könnte argumentieren, dass byte-kompilierte Sprachen von Natur aus schneller sind, weil der JIT-Compiler maschinenspezifische Optimierungen vornehmen kann, die für "way-ahead-of-time"-Compiler nicht verfügbar sind.

Eine Reihe von Dingen, die den Unterschied ausmachen könnten, sind:

• Pythons Hash-Tabellen und Mengen sind die am stärksten optimierten Objekte in Python, und Pythons Hash-Funktion ist so konzipiert, dass sie für ähnliche Eingaben ähnliche Ergebnisse liefert: Das Hashing einer ganzen Zahl gibt nur die ganze Zahl zurück, was garantiert, dass in einer Hash-Tabelle mit aufeinanderfolgenden ganzen Zahlen in Python NIEMALS eine Kollision auftritt.
• Eine sekundäre Auswirkung des oben genannten ist, dass der Python-Code eine hohe Lokalität des Verweises haben wird, da Sie auf die Hash-Tabelle in Folge zugreifen werden.
• Java macht einige ausgefallene Boxing und Unboxing von Ganzzahlen, wenn Sie sie zu Sammlungen hinzufügen. Das hat den Vorteil, dass die Arithmetik in Java viel schneller ist als in Python (solange man sich von Bignums fernhält), aber auf der anderen Seite bedeutet es mehr Zuweisungen, als man es gewohnt ist.