Java zu langsam

[tschinke]

Hi,

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])?

Viele Grüße



[1]
FAST Corner Detection -- Edward Rosten

[2]

for(y=3; y < ysize - 3; y++)
		for(x=3; x < xsize - 3; x++)
		{
			//const byte* p = im + y*stride + x;

            offset_pointer=y*stride+x;
			//int cb = *p + b;
			//int c_b= *p - b;

            int cb=im[offset_pointer]+b;
            int c_b=im[offset_pointer]-b;

        if(p[offset_pointer+pixel[0]] > cb)
         if(p[offset_pointer+pixel[1]] > cb)
          if(p[offset_pointer+pixel[2]] > cb)
           if(p[offset_pointer+pixel[3]] > cb)
            if(p[offset_pointer+pixel[4]] > cb)
             if(p[offset_pointer+pixel[5]] > cb)
              if(p[offset_pointer+pixel[6]] > cb)
               if(p[offset_pointer+pixel[7]] > cb)
                if(p[offset_pointer+pixel[8]] > cb)
                 {}
                else
                 if(p[offset_pointer+pixel[15]] > cb)
                  {}
                 else
                  continue;
....usw

 

[tuxedo]

Hast du das ganze schonmal mehrfach hintereinander laufen lassen (in einer JVM Instanz)? Wird/Ist der 2te, 3te etc. Durchlauf schneller?

- Alex

 

[Noctarius]

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.

 

[tschinke]

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?

 

[Noctarius]

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

 

[tschinke]

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.

 

[dergrüne]

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.

Gruß

 

[tschinke]

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.

 

[Noctarius]

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

 

[maki]

Welche VM (client oder server) hast du gewählt?

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.

 

[Spacerat]

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.

 

[tschinke]

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.

 

[tschinke]

Welche VM (client oder server) hast du gewählt?

Ich entwickle derzeit unter Ubuntu 8.10 64 bit. Die Java-Version ist:

java version "1.6.0_13"
Java(TM) SE Runtime Environment (build 1.6.0_13-b03)
Java HotSpot(TM) 64-Bit Server VM (build 11.3-b02, mixed mode)

Ansonsten würde ich das Ding mal durch den Profiler jagen um den Flaschenhals zu finden

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.

 

[EgonOlsen]

Du könntest...

y*stride

vor die innere Schleife ziehen. Oder ändert sich stride in deren Durchlauf?

 

[Noctarius]

Ui sogar schon unter Linux Starte das gleiche Programm mal unter Windows und freu dich über den Zeitzuwachs *gg*

 

[tschinke]

Du könntest...

y*stride

vor die innere Schleife ziehen.

Stride bleibt konstant und ich habe die Änderungen eingebaut. Allerdings keine messbare Verbesserung.

 

[Noctarius]

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".

 

[Marco13]

Ein bißchen mehr Code könnte helfen. Wenn dir langweilig ist, kannst du mal versuchen, das aufzudröseln in einzelne Methoden. Erst DANN kann der Hotspot-Compiler nämlich wirklich was dran machen - siehe The Java HotSpot Performance Engine: On-Stack Replacement Example und Frequently Asked Questions About the Java HotSpot VM

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....

 

[Marco13]

Hey ...
if(p[offset_pointer+pixel[0]] > cb)
warum rechnest du den offset_pointer nicht gleich in die pixel[0..n] mit rein?! :bahnhof:

 

[tschinke]

Schonmal versucht die oberen IFs über den && Operator miteinander zu verknüpfen (zumind. solang du keinen else-Zweig hast)?

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).

 

[tschinke]

Hey ...
if(p[offset_pointer+pixel[0]] > cb)
warum rechnest du den offset_pointer nicht gleich in die pixel[0..n] mit rein?! :bahnhof:

wurde schon gemacht:

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.

allerdings wurde eingeworfen, dass dies noch schneller gehen könnte ...

 

[tschinke]

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.

Wie hast du das denn in Java konvertiert?

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.

 

[tschinke]

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)

zu

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...

ich habe das ausgetestet und die Laufzeit (trotz private final static methoden deklaration) ist Katastrophal: 192ms

update: übrigens äquivalent zum Inlining von {ret_corners.add(new XY(x,y));continue;} in die leeren {} Blöcke der erfüllten IF-Statements.