45 Stimmen

Warum ist dieser Java-Code 6x schneller als der identische C#-Code?

Ich habe ein paar verschiedene Lösungen für Projekt Euler-Problem 5 aber der Unterschied in der Ausführungszeit zwischen den beiden Sprachen/Plattformen bei dieser speziellen Implementierung macht mich neugierig. Ich habe keine Optimierung mit Compiler-Flags vorgenommen, sondern einfach nur javac (über die Befehlszeile) und csc (über Visual Studio).

Hier ist der Java-Code. Er wird in 55ms beendet.

public class Problem005b
{
    public static void main(String[] args)
    {
        long begin = System.currentTimeMillis();
        int i = 20;
        while (true)
        {
            if (
                    (i % 19 == 0) &&
                    (i % 18 == 0) &&
                    (i % 17 == 0) &&
                    (i % 16 == 0) &&
                    (i % 15 == 0) &&
                    (i % 14 == 0) &&
                    (i % 13 == 0) &&
                    (i % 12 == 0) &&
                    (i % 11 == 0)
                )
            {
                break;
            }
            i += 20;
        }
        long end = System.currentTimeMillis();
        System.out.println(i);
        System.out.println(end-begin + "ms");
    }   
}

Hier ist der identische C#-Code. Er wird in 320ms beendet

using System;

namespace ProjectEuler05
{
    class Problem005
    {
        static void Main(String[] args)
        {
            DateTime begin = DateTime.Now;
            int i = 20;
            while (true)
            {
                if (
                        (i % 19 == 0) &&
                        (i % 18 == 0) &&
                        (i % 17 == 0) &&
                        (i % 16 == 0) &&
                        (i % 15 == 0) &&
                        (i % 14 == 0) &&
                        (i % 13 == 0) &&
                        (i % 12 == 0) &&
                        (i % 11 == 0)
                    )
                    {
                        break;
                    }
                i += 20;
            }
            DateTime end = DateTime.Now;
            TimeSpan elapsed = end - begin;
            Console.WriteLine(i);
            Console.WriteLine(elapsed.TotalMilliseconds + "ms");
        }
    }
}

40voto

Femaref Punkte 59547
  1. Um die Ausführung von Code zu verzögern, sollten Sie die StopWatch Klasse.
  2. Außerdem müssen Sie die JIT, die Laufzeit usw. berücksichtigen, also lassen Sie den Test ausreichend oft laufen (z. B. 10.000 oder 100.000 Mal) und ermitteln Sie eine Art Durchschnitt. Es ist wichtig, den Code mehrere Male, no das Programm. Schreiben Sie also eine Methode, und führen Sie in der Hauptmethode eine Schleife durch, um Ihre Messungen zu erhalten.
  3. alle Debugging-Funktionen aus den Assemblies entfernen und den Code in einem Release-Build eigenständig laufen lassen

24voto

finnw Punkte 46519

Es sind einige Optimierungen möglich. Vielleicht führt das Java JIT sie durch und die CLR nicht.

Optimierung #1:

(x % a == 0) && (x % b == 0) && ... && (x % z == 0)

ist gleichbedeutend mit

(x % lcm(a, b, ... z) == 0)

In Ihrem Beispiel könnte die Vergleichskette also ersetzt werden durch

if (i % 232792560 == 0) break;

(aber wenn Sie die LCM bereits berechnet haben, macht es natürlich wenig Sinn, das Programm überhaupt zu starten).

Optimierung #2 :

Dies ist auch gleichwertig:

if (i % (14549535 * 16)) == 0 break;

oder

if ((i % 16 == 0) && (i % 14549535 == 0)) break;

Die erste Division kann durch eine Maske ersetzt und mit Null verglichen werden:

if (((i & 15) == 0) && (i % 14549535 == 0)) break;

Die zweite Division kann durch eine Multiplikation mit der modularen Umkehrung ersetzt werden:

final long LCM = 14549535;
final long INV_LCM = 8384559098224769503L; // == 14549535**-1 mod 2**64
final long MAX_QUOTIENT = Long.MAX_VALUE / LCM;
// ...
if (((i & 15) == 0) &&
    (0 <= (i>>4) * INV_LCM) &&
    ((i>>4) * INV_LCM < MAX_QUOTIENT)) {
    break;
}

Es ist etwas unwahrscheinlich, dass das JIT dies anwendet, aber es ist nicht so weit hergeholt, wie Sie vielleicht denken - einige C-Compiler implementieren Zeigersubtraktion auf diese Weise.

12voto

ShuggyCoUk Punkte 35230

Der Schlüssel zu einer Annäherung zwischen den beiden liegt darin, dass der Vergleich fair ist.

Zunächst einmal sicherstellen, dass die Kosten im Zusammenhang mit der Ausführung von Debug-Builds, Laden pdb Symbole, wie Sie getan haben.

Als nächstes müssen Sie sicherstellen, dass keine Initiativkosten gezählt werden. Natürlich sind dies echte Kosten, die für manche Leute wichtig sein können, aber in diesem Fall sind wir an der Schleife selbst interessiert.

Als nächstes müssen Sie sich mit dem plattformspezifischen Verhalten befassen. Wenn Sie mit einem 64-Bit-Windows-Rechner arbeiten, können Sie entweder im 32-Bit- oder im 64-Bit-Modus arbeiten. Im 64bit-Modus ist das JIT in vielerlei Hinsicht anders, was den resultierenden Code oft erheblich verändert. Speziell, und ich würde erraten Das bedeutet, dass Sie Zugriff auf doppelt so viele Universalregister haben.

In diesem Fall müsste der innere Teil der Schleife, wenn er naiv in Maschinencode übersetzt wird, die in den Modulo-Tests verwendeten Konstanten in Register laden. Wenn die Register nicht ausreichen, um alles zu speichern, was in der Schleife benötigt wird, müssen sie aus dem Speicher geholt werden. Selbst wenn die Konstanten aus dem Level-1-Cache stammen, wäre dies ein erheblicher Aufwand im Vergleich zur Speicherung in Registern.

In VS 2010 MS das Standardziel von anycpu auf x86 geändert . Ich verfüge weder über die Ressourcen noch über das Kundenwissen von MSFT, also werde ich nicht versuchen, das in Frage zu stellen. Allerdings sollte jeder, der so etwas wie die von Ihnen durchgeführte Leistungsanalyse anstrebt, auf jeden Fall beides ausprobieren.

Wenn diese Unterschiede beseitigt sind, erscheinen die Zahlen weitaus vernünftiger. Alle weiteren Unterschiede erfordern wahrscheinlich mehr als nur Vermutungen, sondern eine Untersuchung der tatsächlichen Unterschiede im generierten Maschinencode.

Es gibt einige Dinge, die meiner Meinung nach für einen optimierenden Compiler interessant wären.

  • Die, die finnw bereits erwähnt hat:
    • Die Option lcm ist interessant, aber ich kann mir nicht vorstellen, dass ein Compilerschreiber sich die Mühe macht.
    • die Reduzierung der Division auf Multiplikation und Maskierung.
      • Ich weiß nicht genug darüber, aber andere Leute haben versucht Beachten Sie, dass sie den Teiler auf den neueren Intel-Chips deutlich besser hervorheben.
      • Vielleicht können Sie sogar etwas Komplexes mit SSE2 arrangieren.
      • Die Modulo-16-Operation eignet sich natürlich hervorragend für die Umwandlung in eine Maske oder eine Verschiebung.
    • Ein Compiler könnte feststellen, dass keiner der Tests Nebeneffekte hat.
      • Es könnte spekulativ versuchen, mehrere von ihnen gleichzeitig auszuwerten. Auf einem Superskalarprozessor könnte dies die Dinge um einiges schneller machen, würde aber stark davon abhängen, wie gut das Layout des Compilers mit der OO-Ausführungsmaschine interagiert.
    • Wenn die Register knapp bemessen sind, könnten Sie die Konstanten als eine einzige Variable implementieren, die zu Beginn jeder Schleife gesetzt und dann im weiteren Verlauf inkrementiert wird.

Dies sind alles nur Vermutungen und sollten als müßige Abschweifungen betrachtet werden. Wenn Sie wollen wissen demontieren.

3voto

Robert Harvey Punkte 173098

(Verschoben aus OP)

Ändern des Ziels von x86 auf anycpu hat die durchschnittliche Ausführungszeit von 282 ms pro Lauf auf 84 ms gesenkt. Vielleicht sollte ich dieses Thema in einen zweiten Thread abspalten?

UPDATE :
Dank an Femaref, der wies auf einige Testprobleme hin und in der Tat sind die Zeiten nach Befolgung seiner Vorschläge niedriger, was darauf hindeutet, dass die VM-Einrichtungszeit in Java signifikant war, in C# aber wahrscheinlich nicht. In C# waren es die Debugsymbole, die von Bedeutung waren.

Ich habe meinen Code so aktualisiert, dass jede Schleife 10.000 Mal ausgeführt wird und nur die durchschnittlichen ms am Ende ausgegeben werden. Die einzige wesentliche Änderung, die ich vorgenommen habe, war die C#-Version, bei der ich für eine bessere Auflösung zur [StopWatch-Klasse][3] gewechselt habe. Ich bin bei Millisekunden geblieben, weil das gut genug ist.

Ergebnisse:
Die Teständerungen erklären nicht, warum Java (immer noch) so viel schneller ist als C#. Die Leistung von C# war besser, aber das lässt sich ausschließlich durch das Entfernen der Debugsymbole erklären. Wenn Sie [Mike Two][4] und ich den Austausch in den Kommentaren zu dieser OP lesen, werden Sie sehen, dass ich ~280ms Durchschnitt in fünf Durchläufen des C#-Codes nur durch den Wechsel von Debug zu Release bekam.

Zahlen:

  • Eine Schleife mit 10.000 Zählungen des unveränderten Java-Codes ergab einen Durchschnitt von 45 ms (statt 55 ms).
  • Eine Schleife mit 10.000 Zählungen des C#-Codes unter Verwendung der StopWatch-Klasse ergab einen Durchschnitt von 282 ms (statt 320 ms).

All dies lässt den Unterschied unerklärt. Tatsächlich hat sich der Unterschied sogar noch vergrößert. Java wurde von ~5,8x schneller auf ~6,2x schneller.

2voto

darron Punkte 4129

Diese Aufgabe ist zu kurz, um sie richtig zu timen. Sie müssen beide mindestens 1000 Mal ausführen und sehen, was passiert. Es sieht so aus, als würdest du sie von der Kommandozeile aus ausführen, in diesem Fall vergleichst du möglicherweise die JIT-Compiler für beide. Versuchen Sie, beide hinter Schaltflächen in einer einfachen grafischen Benutzeroberfläche zu platzieren, und lassen Sie diese Schaltfläche mindestens ein paar hundert Mal durchlaufen, bevor Sie die verstrichene Zeit zurückgeben. Selbst wenn man die JIT-Kompilierung außer Acht lässt, könnte das Timing durch die Granularität des OS-Schedulers beeinträchtigt werden.

Oh, und wegen JIT... zählt nur das ZWEITE Ergebnis eines Tastendrucks :)

CodeJaeger.com

CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.

Powered by:

X