ich habe den FAST Corner Detector [1] von C nach Java übersetzt. Dieser wurde zum Teil automatisch generiert (die detect-Methode enthält ca. 3000 Zeilen mit If-Statements), dafür ist er in der C Version sehr schnell (auf einem 2,6GHz Opteron 1,3ms für ein 768x288 Bild). Eine portierte unmanged C# Version ist fast vergleichbar schnell.
Für die Java-Version brauchte ich nur wenige Anpassungen zu machen, dennoch benötigt der Algorithmus unter Java auf einer vergleichbaren Maschine 123ms, wovon ca. 80 ms auf die 3000 Zeilen if-Statements entfallen: Damit ist Java 92mal langsamer als die native C-Variante! Diverse Spielereien mit VM-Optionen (GC-, JIT-, Heap-Einstellungen) brachten keine wesentlichen Verbesserungen.
Nun meine Frage: Ist dieser Geschwindigkeitsunterschied normal für Java oder ist dies ein Spezialfall, indem Java die If-Statements weniger gut optimieren kann als ein C Compiler (vgl. Ausschnitt [2])?
tuxedo hat Recht. Die JVM benutzt einen sogenannten HotSpot Compiler, der zur Laufzeit sinnvolle Optimierungen und Neukompilierungen vornimmt.
Dadurch ist es tatsächlich so, dass normal Code erst nach mehreren Durchläufen optimiert wird. Einer der Haupgründe wieso Java - C++ Vergleiche meistens hinken.
jupp, natürlich (Schleife mit 100 durchläufen und gemittelter Zeitmessung). Ferner habe ich folgende VM-Optionen zusätzlich ausprobiert:
-XX:+AggressiveOpts
-XX:CompileThreshold=1
Dabei zeigt sich, dass der Jit die Performance etwas mehr als verdoppelt.
Allerdings ist mir gerade ein anderer fundamentaler Fehler aufgefallen: Und zwar musste ich bei der Übersetzung natürlich die Pointerarithemtik ersetzen und mit einem "Arrays-Zeiger" simulieren. Dabei habe ich mit "search and replace" einfach die Position mit einer Addition in jedem If-Statement errechnet (p[offset_pointer+pixel[0]]). Allerdings gibt es nur 15 unterschiedliche Berechnungen pro Schleifendurchlauf und redundante Berechnungen können offenbar nicht erkannt werden. Ich berechne diese Werte nun einmalig pro innerer Schleife und vergleiche auf diesen Werten. Dadurch entstand eine sehr starke Verbesserung. Der gesamte Vorgang -inklusive Bild laden- dauert nun nur noch 52 ms wobei der komplette FAST-Algorithmus nur 11ms benötigt.
Das macht den Java-Algorithmus um den Faktor 8,5 langsamer als die C Variante. Das klingt schon realistischer oder?
Ich halte das imemr noch für zuviel. Da der Hotspot quasi nativen Code erzeugt denke ich immernoch, dass man irgendwo was wegoptimieren kann. Ich bleibe weiterhin auf dem Punkt Java ist nicht langsamer (Ausnahmefälle z.B. Inline-Assembler ausgenommen) als C / C++ ist
Poste mal den ganzen Code (wenn du magst) in Gruppenarbeit mit der Community bekommen wir den bestimmt noch schneller
Ich glaube zum Posten ist das zuviel. Der Code ist aber Bestandteil von einer kleiner Bibliothek, in der ich ein paar Bilderkennungsalgorithmen bei Gelegenheit zusammenfasse. Die aktuellen Sourcen kann man anonym mit Subversion unter svn://neotos.de/jaiwls/trunk/imageAnalyzer auschecken.
Im Verzeichnis /trunk/imageAnalyzer/core/test/de/neotos/imageanalyzer/cheapsift findet sich ein einfacher JUnit-Test, der den FastCornerDetecor aufruft.
Also es ist definitiv so das Java gerade in Punkto Berechnung teilweise schneller oder genauso schnell wie c++ ist. Gerade wenn man den Code native compiled. Wieso es jetzt bei deinem Beispiel so stark hinter der Performance bleibt weiß ich nicht, muss man sich den Code genau anschauen.
Aber wie gesagt es macht mich sehr sehr stutzig das Java sooo viel langsamer sein soll.
Tatsächlich hatte ich die Variante die 123ms benötigt auch mal mit dem gcj nativ kompiliert. Das war allerdings eine totale Katastrophe, da sich die Laufzeit auf dramatische 300ms verschlechterte. Die neue variante mit insgesamt 52ms habe ich noch nicht probiert.
gcj ist auch nicht immer up2date und der Compiler ist nicht so sehr gut (hab's auch nur gehört). Ich kenne auf jedenfall keinen der das tatsächlich einsetzt.
Ich werde mir bei Gelegenheit den Code mal anschauen, nur auf Arbeit etwas schwierig
Die JIT/Hotspot Optimierungen funzen nur richtig bei der Server VM, diese ist standardmässig nur im JDK und nicht im JRE enthalten, unter Linux wird mit einem JDK immer die Server variante gewählt (wenn ich mich recht erinnnere), unter Windows sollte man den Kommandozeilen Parameter -server mitangeben.
Ansonsten würde ich das Ding mal durch den Profiler jagen um den Flaschenhals zu finden, Cross-Compiler erzeugen nicht immer den optimalsten Code.
Ist jetzt zwar nicht aus dem gepostetem Codeschnipsel nich ersichtlich, aber möglicherweise werden ja an anderer Stelle innerhalb der Methode ständig neue Objekte angelegt und dadurch vorhergehende Objekte verworfen und dem GC überlassen, welcher dann ab einer gewissen Anzahl nicht mehr hinterher kommt. Ich hatte so ein Problem bereits beim Rendern von 3D-Objekten in JOGL. Ich habe dort noch einen entscheidenden Performancevorteil durch Objektrecycling (Wortschöpfung des Autors!?) bekommen.
Mit der Problematik wurde ich erstmals auch richtig bei JOGL vertraut.
Ich habe allerdings von der C übersetzung nur die Structs der Features (mehr gab es auch nicht) als Javaklassen modelliert (die auch nie weggeworfen werden) und ansonsten 1-2 LinkedList für die Ergebnislisten. Ich sehe im Algorithmus selbst keine ObjectReusing Möglichkeiten.
Natürlich passiert (Netbeans 6.5 Profiler), leider ist die kleinste Einheit eine Methode, und da der ganze Algorithmus aus tausenden von primitiven IF-Statements besteht, bringt mich das für den Algorithmus selbst nicht weiter.
Schonmal versucht die oberen IFs über den && Operator miteinander zu verknüpfen (zumind. solang du keinen else-Zweig hast)? Ob das was bringt weiß ich nicht, aber nen Versuch wäre es wert.
Der Grund der Annahme. Ein IF erzeugt immer ein JMP (Jump) und diese sind "recht langsam".
EDIT: Zumindest den innersten Teil der Schleife solltest du auf jeden Fall mal in eine Methode packen...
EDIT2: Ah, hab gerade mal den C-Code angeguckt - das ist natürlich ... naja, schwer handhabbar. Wie hast du das denn in Java konvertiert? Einfach so? Ideal wäre es, wenn man den Code-Generator hätte, der den C-Code erzeugt hat, damit man den auf Java umbiegen könnte....
Dem subjektiven Blick nach, hat jedes if auch einen else-Zweig. Allerdings scheinen alle else Zweige der detect-Methode nur ein continue zu enthalten. Die Erfüllung eines if-Zweiges hingegen hat nur einen Leeren Block zur Folge, so dass (sofern ich den erzeugten Code richtig interpretiere) die If-Statements an einem Blatt angelangen, dort entsprechend herausgesprungen wird und die x/y Coordinaten dann eine erkannte Ecke darstellen (letzte Anweisung der inneren Schleife). Eine Ecke könnte also niemals aus Koordinaten bestehen, die irgendeine Bedingung nicht erfüllen.
Diesen monolithischen Block aus 3000 Zeilen verschachtelten if/else Statements per Hand anzufassen halte ich für unmöglich und eine automatische Maßnahme dies hinzubekommen, sehe ich momentan nicht.
Ferner würde ich erwarten, dass derartig primitive Operationen sich sehr gut durch den Compiler optimieren lassen müssten, sodass hier keine Unterschiede zwischen Java und C entstehen dürften? Zu den jumps: würde eine mit && verkette IF Bedingung nicht sowieso in einzelne x86 JG, JNLE, ... etc Befehle zerlegt und damit nicht anders ausehen als verschachtelte IFs? Und wäre es nicht logischer für die VM nur dann zu Labels zu jumpen wenn man einen {}-Block angibt? (was nicht der Fall ist).
Allerdings ist mir gerade ein anderer fundamentaler Fehler aufgefallen: Und zwar musste ich bei der Übersetzung natürlich die Pointerarithemtik ersetzen und mit einem "Arrays-Zeiger" simulieren. Dabei habe ich mit "search and replace" einfach die Position mit einer Addition in jedem If-Statement errechnet (p[offset_pointer+pixel[0]]). Allerdings gibt es nur 15 unterschiedliche Berechnungen pro Schleifendurchlauf und redundante Berechnungen können offenbar nicht erkannt werden. Ich berechne diese Werte nun einmalig pro innerer Schleife und vergleiche auf diesen Werten. Dadurch entstand eine sehr starke Verbesserung. Der gesamte Vorgang -inklusive Bild laden- dauert nun nur noch 52 ms wobei der komplette FAST-Algorithmus nur 11ms benötigt.
Java HotSpot Performance Engine: On-Stack Replacement Example[/url]
EDIT: Zumindest den innersten Teil der Schleife solltest du auf jeden Fall mal in eine Methode packen...
Interessanter Punkt. Ich habe -bevor ich dort anfange umzubauen - 11.000 mal diese Methode aufgerufen, Sicherheitshalber. Nach der Theorie müsste das also ausreichen damit der JIT in jedem Fall Wirkung zeigt, auch ohne den inneren Part in eine eigene Methode auszulagern, das würde entsprechend nur dafür sorgen, dass der JIT deutlich schneller greift. Leider stabilisiert sich das Ausührungsverhalten bereits nach den ca. ersten 20 Iterationen (22ms auf 11ms) und bleibt bis zur 11.000 Iterationen konstant.
Im wesentlichsten straight forward, da die Syntax sich kaum unterscheidet. Ich musste nur bei der Scoring-Methode die Goto's umschiffen, da java mit der Label-Syntax nicht zwischen Blöcken springen kann. Ansonsten anstatt direkt mit dem Pointer zu rechnen habe ich eine Variable in Form eines ints zusätzlich in die Methoden eingeführt um im 1D-Bild (Array) herumzuspringen, wie üblich also. Das konnte ich mit ein paar einfachen Search/Replace Vorgängen machen. Zudem habe ich nur den 9er Detektor übersetzt.
Ich habe noch ein wenig weiter experimentiert, der gesamte Prozess benötigt jetzt nach 1000 Iterationen 16ms im Schnitt:
1)
3ms für die Konvertierung von BufferedImage in kompatibles int[] array
2)
13ms für den FAST Algorithmus (etwas mehr geworden, da es durch die veränderte Konvertierung - nur Verwendung des grünen Kanals - zu mehr Features kommt)
Java HotSpot Performance Engine: On-Stack Replacement Example[/url]
EDIT: Zumindest den innersten Teil der Schleife solltest du auf jeden Fall mal in eine Methode packen...
