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

Edit: Ein TreeSet könnte für den realen Anwendungsfall schneller sein, abhängig von den Zuordnungsmustern. Meine nachstehenden Bemerkungen beziehen sich nur auf dieses vereinfachte Szenario. Ich glaube jedoch nicht, dass es einen signifikanten Unterschied machen würde. Das eigentliche Problem liegt woanders.

Mehrere Leute hier haben empfohlen, das HashSet durch ein TreeSet zu ersetzen. Dies klingt für mich wie ein sehr seltsamer Ratschlag, da es keine Möglichkeit gibt, dass eine Datenstruktur mit O(log n)-Einfügezeit schneller ist als eine O(1)-Struktur, die genügend Buckets zum Speichern aller Elemente vorbesetzt.

Hier ist etwas Code, um dies zu überprüfen:

import java.util.*;
class SpeedTest
{    
    public static void main(String[] args)
    {        
        long startTime;
        long totalTime;
        int iterations = 10000000;
        Set counts;

        System.out.println("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());

        counts.clear();

        System.out.println("TreeSet:");
        counts = new TreeSet();
        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());
    }
}

Und hier ist das Ergebnis auf meinem Rechner:

$ java -Xmx1024M SpeedTest
HashSet:
TOTAL TIME = 4.436
10000000
TreeSet:
TOTAL TIME = 8.163
10000000

Mehrere Personen argumentierten auch, dass Boxing kein Leistungsproblem darstellt und dass die Objekterstellung kostengünstig ist. Es stimmt zwar, dass die Objekterstellung schnell ist, aber definitiv nicht so schnell wie Primitive:

import java.util.*;
class SpeedTest2
{    
    public static void main(String[] args)
    {        
        long startTime;
        long totalTime;
        int iterations = 10000000;

        System.out.println("primitives:");
        startTime = System.currentTimeMillis();
        int[] primitive = new int[iterations];
        for (int i = 0; i < iterations; i++) {
            primitive[i] = i;
        }
        totalTime = System.currentTimeMillis() - startTime;
        System.out.println("TOTAL TIME = "+( totalTime/1000f) );

        System.out.println("primitives:");
        startTime = System.currentTimeMillis();
        Integer[] boxed = new Integer[iterations];
        for (int i = 0; i < iterations; i++) {
            boxed[i] = i;
        }
        totalTime = System.currentTimeMillis() - startTime;
        System.out.println("TOTAL TIME = "+( totalTime/1000f) );
    }
}

Ergebnis:

$ java -Xmx1024M SpeedTest2
primitives:
TOTAL TIME = 0.058
primitives:
TOTAL TIME = 1.402

Außerdem führt die Erstellung vieler Objekte zu einem zusätzlichen Overhead durch den Garbage Collector. Dies ist von Bedeutung, wenn man anfängt, Dutzende von Millionen von lebenden Objekten im Speicher zu halten.

Answer 2

Ich halte solche Benchmarks für sinnlos. Ich löse keine Probleme, die wie der Testfall aussehen. Das ist nicht sonderlich interessant.

Ich würde viel lieber eine Lösung für eine sinnvolle lineare Algebra-Lösung mit NumPy und JAMA sehen. Vielleicht probiere ich es aus und melde mich mit Ergebnissen.

Answer 3

Ich bin nicht sehr vertraut mit Python, aber ich weiß HashSet kann keine Primitive enthalten, wenn Sie also sagen counts.add(i) die i dort wird in eine Autobox verfrachtet new Integer(i) anrufen. Das ist wahrscheinlich Ihr Problem.

Wenn Sie aus irgendeinem Grund wirklich eine "Menge" von ganzen Zahlen zwischen 0 und einem großen n benötigen, ist es wahrscheinlich am besten, sie als "boolean[] set = new boolean[n]" zu deklarieren. Dann könnte man das Array durchgehen und die Elemente in der Menge als "wahr" markieren, ohne den Overhead der Erstellung von n Integer-Wrapper-Objekten in Kauf nehmen zu müssen. Wenn Sie noch weiter gehen wollen, könnten Sie ein Byte[] der Größe n/8 verwenden und die einzelnen Bits direkt nutzen. Oder vielleicht BigInteger.

EDITAR

Hören Sie auf, meine Antwort zu bewerten. Sie ist falsch.

EDITAR

Nein, wirklich, das ist falsch. Ich erhalte vergleichbare Leistung, wenn ich tue, was die Frage vorschlagen, füllen Sie den Satz mit N Integers. wenn ich den Inhalt der for-Schleife mit diesem ersetzen:

    Integer[] ints = new Integer[N];
    for (int i = 0; i < N; ++i) {
        ints[i] = i;
    }

Dann dauert es nur 2 Sekunden. Wenn man den Integer gar nicht speichert, dauert es weniger als 200 Millisekunden. Das Erzwingen der Zuweisung von 10000000 Integer-Objekten nimmt einige Zeit in Anspruch, aber es sieht so aus, als ob die meiste Zeit innerhalb der HashSet-Put-Operation verbracht wird.

Answer 4

Es gibt hier eine Reihe von Themen, die ich gerne zusammenfassen möchte.

Wenn es sich um ein Programm handelt, das Sie nur einmal ausführen, ist es dann nicht egal, wenn es ein paar Sekunden länger dauert?

Zweitens ist dies nur ein Mikrobenchmark. Mikrobenchmarks sind für Leistungsvergleiche sinnlos.

Bei der Inbetriebnahme gibt es eine Reihe von Problemen.

Die Java-Laufzeitumgebung ist viel größer als Python und braucht daher länger, um von der Festplatte geladen zu werden, und nimmt mehr Speicherplatz in Anspruch, was wichtig sein kann, wenn Sie Swapping betreiben.

Wenn Sie nicht die -Xms kann es sein, dass Sie die GC nur ausführen, um die Größe des Heaps zu ändern. Sie können den Heap genauso gut von Anfang an richtig dimensionieren.

Es stimmt, dass Java zunächst interpretiert und dann kompiliert. Etwa 1.500 Iterationen für Sun Client [C1] Hotspot und 10.000 für Server [C2]. Der Server-Hotspot bietet zwar eine bessere Leistung, benötigt aber mehr Speicherplatz. Es kann vorkommen, dass Client-Hotspot den Server für sehr häufig ausgeführten Code verwendet, um das Beste aus beiden Welten zu erhalten. In der Regel sollte dies jedoch keine Frage von Sekunden sein.

Am wichtigsten ist, dass Sie möglicherweise zwei Objekte pro Iteration erstellen. Bei den meisten Codes würden Sie diese winzigen Objekte nicht für einen so großen Teil der Ausführung erstellen. TreeSet kann bei der Anzahl der Objekte besser sein, wobei 6u14 und Harmony sogar noch besser werden.

Python kann möglicherweise gewinnen, indem es kleine Integer-Objekte in Referenzen speichert, anstatt tatsächlich ein Objekt zu haben. Das ist zweifelsohne eine gute Optimierung.

Ein Problem bei vielen Benchmarks ist, dass man in einer Methode viele verschiedene Codes vermischt. So würden Sie keinen Code schreiben, der Ihnen am Herzen liegt, oder? Warum versuchen Sie also, Leistungstests durchzuführen, die im Gegensatz zu dem Code stehen, den Sie eigentlich schnell ausführen möchten?

Bessere Datenstruktur: Etwas wie BitSet scheint sinnvoll zu sein (auch wenn dies mit einer Synchronisierung verbunden ist, was sich auf die Leistung auswirken kann).

Answer 5

Verwenden Sie das Flag -server mit dem jvm? Ohne dieses Flag können Sie die Leistung nicht testen. (Außerdem müssen Sie die jvm vor dem Test aufwärmen).

Außerdem sollten Sie wahrscheinlich TreeSet<Integer> . HashSet wird auf Dauer langsamer sein.

Und welchen JVM verwenden Sie? Den neuesten, hoffe ich.

EDITAR

Wenn ich sage, dass man TreeSet verwenden soll, dann meine ich das im Allgemeinen, nicht für diesen Benchmark. TreeSet behandelt das Problem der ungleichmäßigen Hash-Werte von Objekten in der realen Welt. Wenn Sie zu viele Objekte im gleichen Bin in einem HashSet erhalten, werden Sie etwa O(n) ausführen.