[ Hypercell ein ] [ Hypercell aus ] [ Zeige Navigation ] [ Verstecke Navigation ]
c++.de  
   
Forentreff 2012   [ Startseite ] [ Links ] [ FAQs ] [ Humor ] [ Compiler ] [ Bücher ] [ Magazin ] [ Tutorials ] [ Videos ] [ Impressum & AGB ] [ Twitter Twitter ] [ Facebook Facebook ] [ Kontakt ]
[ Anleitung ] [ Suchen ] [ Profil ] [ Eigene Beiträge ] [ Registrieren ]
[ Login ]
   
Bücher-Shop mit Amazon (Buchkategorien):  C++ : Referenzen zu C++ : C++ Builder : Visual C++ : C# : Java : Spieleprogrammierung : Systemprogrammierung Linux : Software-Entwicklung : .NET : Compilertechnik : Algorithmen & Datenstrukturen : Objektorientierung : Entwurfsmuster : UML : eXtreme Programming : Scrum : Projektmanagement : Software-Testing : Datenbanken : Tom DeMarco : Dilbert : User Friendly
C/C++ Forum :: Java ::  Effiziente Vektorrechnung     Zeige alle Beiträge auf einer Seite Auf Beitrag antworten
Autor Nachricht
Drawer
Unregistrierter
Beitrag Drawer Unregistrierter 00:06:26 14.11.2011   Titel:   Effiziente Vektorrechnung            Zitieren
Hallo.

Ich möchte gerne in Java für ein Android-Projekt mit Vektorklassen rechnen. Eigentlich brauche ich nur 2D-Vektoren, mit float-Koordinaten.

Wenn ich dafür eine Klasse Vector2f mache, würde man die Rechenoperationen ja wahrscheinlich so implementieren:

Java Code:
public static Vector2f add(Vector2f a, Vector2f b) {
    return new Vector2f(a.x + b.x, a.y + b.y);
}
Java Code:
public static Vector2f add(Vector2f a, Vector2f b) {
return new Vector2f(a.x + b.x, a.y + b.y);
}
Java Code:
public static Vector2f add(Vector2f a, Vector2f b) {
    return new Vector2f(a.x + b.x, a.y + b.y);
}


Das Problem dabei ist aber, dass sehr sehr viele Objekte erzeugt werden, die der GC später wegräumen darf. Und das kann insbesondere bei Android schnell mal zum Performance-Killer werden. Also versuche ich, das ohne neue Objekte zu machen.

Bisher habe ich zwei Ideen:

1. Zwei floats irgendwie in einen long packen und Funktionen schreiben, die sie da rein und raus holen, damit rechnen, etc. long würde halt nicht vom GC eingesammelt werden.

2. Der Vektorklasse einen "Cache" geben, der aus sagen wir mal 1000 Vektoren besteht. Anstatt "new" aufzurufen, hole ich mir einfach den nächsten freien Vektor aus dem Cache. Ist natürlich auch nicht gerade toll :( weil Vektoren, die man sich gespeichert hat, dann plötzlich ihren Wert ändern können.

Hat jemand bessere Vorschläge?
Drawer
Unregistrierter
Beitrag Drawer Unregistrierter 01:18:02 14.11.2011   Titel:              Zitieren
Ich hab das mit dem "floats in long packen" mal implementiert.
Funktioniert auf jeden Fall. Ist relativ hässlich, aber naja. Nun werde ich wohl mal die Performance messen müssen.

Hier ein paar Beispiele:

Java Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// Vektorrechnung ohne Garbage Collector!
public class Vec2f
{
    // "Konstruktor"
    public static long make(float x, float y)
    {
        return ((long)Float.floatToRawIntBits(x) << 32) | (Float.floatToRawIntBits(y) & 0xFFFFFFFFL);
    }
   
    // Liefert x-Koordinate.
    public static float x(long v)
    {
        return Float.intBitsToFloat((int)(v >> 32));
    }

    // Liefert y-Koordinate.
    public static float y(long v)
    {
        return Float.intBitsToFloat((int)v);
    }
   
    // Setzt x-Koordinate.
    public static long x(long v, float newX)
    {
        v &= 0xFFFFFFFFL;
        v |= (long)Float.floatToRawIntBits(newX) << 32;
        return v;
    }

    // Setzt y-Koordinate.
    public static long y(long v, float newY)
    {
        v &= 0xFFFFFFFF00000000L;
        v |= Float.floatToRawIntBits(newY) & 0xFFFFFFFFL;
        return v;
    }
   
    // Addiert zwei gepackte Vektoren.
    public static long add(long v1, long v2)
    {
        float x = Float.intBitsToFloat((int)(v1 >> 32)) + Float.intBitsToFloat((int)(v2 >> 32));
        float y = Float.intBitsToFloat((int)v1) + Float.intBitsToFloat((int)v2);
        return ((long)(Float.floatToRawIntBits(x)) << 32) | Float.floatToRawIntBits(y);
    }
   
    // und noch mehr ...
}
Java Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// Vektorrechnung ohne Garbage Collector!
public class Vec2f
{
// "Konstruktor"
public static long make(float x, float y)
{
return ((long)Float.floatToRawIntBits(x) << 32) | (Float.floatToRawIntBits(y) & 0xFFFFFFFFL);
}

// Liefert x-Koordinate.
public static float x(long v)
{
return Float.intBitsToFloat((int)(v >> 32));
}

// Liefert y-Koordinate.
public static float y(long v)
{
return Float.intBitsToFloat((int)v);
}

// Setzt x-Koordinate.
public static long x(long v, float newX)
{
v &= 0xFFFFFFFFL;
v |= (long)Float.floatToRawIntBits(newX) << 32;
return v;
}

// Setzt y-Koordinate.
public static long y(long v, float newY)
{
v &= 0xFFFFFFFF00000000L;
v |= Float.floatToRawIntBits(newY) & 0xFFFFFFFFL;
return v;
}

// Addiert zwei gepackte Vektoren.
public static long add(long v1, long v2)
{
float x = Float.intBitsToFloat((int)(v1 >> 32)) + Float.intBitsToFloat((int)(v2 >> 32));
float y = Float.intBitsToFloat((int)v1) + Float.intBitsToFloat((int)v2);
return ((long)(Float.floatToRawIntBits(x)) << 32) | Float.floatToRawIntBits(y);
}

// und noch mehr ...
}
Java Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// Vektorrechnung ohne Garbage Collector!
public class Vec2f
{
    // "Konstruktor"
    public static long make(float x, float y)
    {
        return ((long)Float.floatToRawIntBits(x) << 32) | (Float.floatToRawIntBits(y) & 0xFFFFFFFFL);
    }
   
    // Liefert x-Koordinate.
    public static float x(long v)
    {
        return Float.intBitsToFloat((int)(v >> 32));
    }

    // Liefert y-Koordinate.
    public static float y(long v)
    {
        return Float.intBitsToFloat((int)v);
    }
   
    // Setzt x-Koordinate.
    public static long x(long v, float newX)
    {
        v &= 0xFFFFFFFFL;
        v |= (long)Float.floatToRawIntBits(newX) << 32;
        return v;
    }

    // Setzt y-Koordinate.
    public static long y(long v, float newY)
    {
        v &= 0xFFFFFFFF00000000L;
        v |= Float.floatToRawIntBits(newY) & 0xFFFFFFFFL;
        return v;
    }
   
    // Addiert zwei gepackte Vektoren.
    public static long add(long v1, long v2)
    {
        float x = Float.intBitsToFloat((int)(v1 >> 32)) + Float.intBitsToFloat((int)(v2 >> 32));
        float y = Float.intBitsToFloat((int)v1) + Float.intBitsToFloat((int)v2);
        return ((long)(Float.floatToRawIntBits(x)) << 32) | Float.floatToRawIntBits(y);
    }
   
    // und noch mehr ...
}
/rant/
Mitglied

Benutzerprofil
Anmeldungsdatum: 18.10.2008
Beiträge: 1552
Beitrag /rant/ Mitglied 01:39:22 14.11.2011   Titel:              Zitieren
Wenn dir die Performance wichtig ist und du wirklich sehr viele Berechnungen durchführen musst, solltest du in Betracht ziehen, mit C weiter zu programmieren. Meine persönlichen Erfahrungen auf diesem Gebiet sprechen hier leider gegen Java, insbesondere auf ARM Smart Phones. Um das Problem auf den Punkt zu bringen: Vektoren als Referenztypen sind unbrauchbarer Schrott.

Egal wie du es wendest und drehst, um diese Tatsache kommst du nicht herum. Es gibt im SDK/NDK einige Beispiele, wie man mittels JNI C-Funktionen implementieren und aufrufen kann. Du musst allerdings beachten, dass rein mit einer C-Implentierung deiner Vektoren noch nichts gewonnen ist. Interop kostet auch wieder. Du wirst grössere Teile deines Programms mit C schreiben müssen.

MfG

_________________
MCPD, MCTS and more! | "It's 7:05am. I have not slept." | www.google.com

Zuletzt bearbeitet von /rant/ am 01:43:49 14.11.2011, insgesamt 1-mal bearbeitet
Drawer
Unregistrierter
Beitrag Drawer Unregistrierter 01:59:42 14.11.2011   Titel:              Zitieren
Jo ...
vielleicht schreibe ich nur das Framework in Java und den Rest in C++.

Ich habe nun mal gebenchmarkt.

"add" braucht ca. 0.014 ms pro Aufruf!
(bei einem 1 GHz-Prozessor)

Nun habe ich das auch mal mit JNI implementiert.
Ist dann doppelt so schnell.

Aber ich fürchte, immer noch zu langsam :(

C/C++ Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
union PackedVec2f
{
    jlong l;
    struct
    {
        float x;
        float y;
    };
};

JNIEXPORT jlong JNICALL Java_de_hanzo_vectortest_Vec2f_addNative(JNIEnv* p_env, jclass, jlong v1, jlong v2)
{
    PackedVec2f& p1 = *reinterpret_cast<PackedVec2f*>(&v1);
    const PackedVec2f& p2 = *reinterpret_cast<const PackedVec2f*>(&v2);
    p1.x += p2.x;
    p1.y += p2.y;
    return p1.l;
}
C/C++ Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
union PackedVec2f
{
jlong l;
struct
{
float x;
float y;
};
};

JNIEXPORT jlong JNICALL Java_de_hanzo_vectortest_Vec2f_addNative(JNIEnv* p_env, jclass, jlong v1, jlong v2)
{
PackedVec2f& p1 = *reinterpret_cast<PackedVec2f*>(&v1);
const PackedVec2f& p2 = *reinterpret_cast<const PackedVec2f*>(&v2);
p1.x += p2.x;
p1.y += p2.y;
return p1.l;
}
C/C++ Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
union PackedVec2f
{
    jlong l;
    struct
    {
        float x;
        float y;
    };
};

JNIEXPORT jlong JNICALL Java_de_hanzo_vectortest_Vec2f_addNative(JNIEnv* p_env, jclass, jlong v1, jlong v2)
{
    PackedVec2f& p1 = *reinterpret_cast<PackedVec2f*>(&v1);
    const PackedVec2f& p2 = *reinterpret_cast<const PackedVec2f*>(&v2);
    p1.x += p2.x;
    p1.y += p2.y;
    return p1.l;
}
/rant/
Mitglied

Benutzerprofil
Anmeldungsdatum: 18.10.2008
Beiträge: 1552
Beitrag /rant/ Mitglied 02:04:05 14.11.2011   Titel:              Zitieren
Du darfst eben nicht nur die Berechnung mit C schreiben, sondern musst im Prinzip den gesamten Berechnungsablauf so programmieren. Jeder JNI-Call kostet auch wieder sehr viel. Wenn du die Anzahl Calls reduzieren kannst, gewinnst du sehr viel. Im Idealfall fasst du mit Java keinen einzigen Vektor mehr direkt an :)

_________________
MCPD, MCTS and more! | "It's 7:05am. I have not slept." | www.google.com

Zuletzt bearbeitet von /rant/ am 02:06:30 14.11.2011, insgesamt 1-mal bearbeitet
Drawer
Unregistrierter
Beitrag Drawer Unregistrierter 09:01:38 14.11.2011   Titel:              Zitieren
Kleines Update:
ich hatte versehentlich im Debug-Modus gebenchmarkt -.-
Nun im Release sieht's schon etwas besser aus:

0.000352 ms/op bei Native

0.000670 ms/op bei Java-Implementierung

Wenn ich einfach nur floats addiere, komme ich auf

0.000182 ms/op reine Java-float-Performance (ohne GC)
Drawer
Unregistrierter
Beitrag Drawer Unregistrierter 09:04:10 14.11.2011   Titel:              Zitieren
... das gleiche mit Integern statt Floats: da kommt Java auf 0.000062 ms/op (dreimal so schnell wie floats).

Da überlegt man sich doch, ob man nicht fixed point benutzen will.
/rant/
Mitglied

Benutzerprofil
Anmeldungsdatum: 18.10.2008
Beiträge: 1552
Beitrag /rant/ Mitglied 11:45:05 14.11.2011   Titel:              Zitieren
Was für ein Prozessor ist das? Kein Qualcomm Snapdragon, oder? Die Snapdragons sind bei Floating-Point sehr schnell im Vergleich zu anderen ARMs. Und wie hast du das gemessen? :)

_________________
MCPD, MCTS and more! | "It's 7:05am. I have not slept." | www.google.com
Drawer
Unregistrierter
Beitrag Drawer Unregistrierter 14:12:51 14.11.2011   Titel:              Zitieren
Es ist ein 1 GHz TI OMAP 3620.

Gemessen habe ich es im Prinzip so (hab den Code jetzt nicht hier):

Java Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
long v = make(0.0f, 0.0f);
long w = make(0.001f, 0.001f);

long t0 = SystemClock.uptimeMillis();

for (int i = 0; i < NUM_OUTER_ITERATIONS; ++i)
{
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
}

long dt = SystemClock.uptimeMillis() - t0;
Java Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
long v = make(0.0f, 0.0f);
long w = make(0.001f, 0.001f);

long t0 = SystemClock.uptimeMillis();

for (int i = 0; i < NUM_OUTER_ITERATIONS; ++i)
{
v = add(v, w);
v = add(v, w);
v = add(v, w);
v = add(v, w);
v = add(v, w);
v = add(v, w);
v = add(v, w);
v = add(v, w);
v = add(v, w);
v = add(v, w);
v = add(v, w);
v = add(v, w);
v = add(v, w);
v = add(v, w);
v = add(v, w);
v = add(v, w);
v = add(v, w);
v = add(v, w);
v = add(v, w);
v = add(v, w);
}

long dt = SystemClock.uptimeMillis() - t0;
Java Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
long v = make(0.0f, 0.0f);
long w = make(0.001f, 0.001f);

long t0 = SystemClock.uptimeMillis();

for (int i = 0; i < NUM_OUTER_ITERATIONS; ++i)
{
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
    v = add(v, w);
}

long dt = SystemClock.uptimeMillis() - t0;


Ich hab die Schleife also "unrolled", damit der Overhead der Schleife selbst nicht so stark ins Gewicht fällt. Außerdem wird am Ende noch der Wert von "v" ausgegeben, damit der Compiler nix weg optimiert.
viktor_vektor
Unregistrierter
Beitrag viktor_vektor Unregistrierter 16:48:40 14.11.2011   Titel:              Zitieren
Ist es eine Bedingung, dass Vec2f immutable sein soll? Wenn nicht, könntest du dir zumindest das Erzeugen neuer Objekte sparen.

Java Code:
public void add(Vector2f a) {
  this.x += a.x;
  this.y += a.y;
}
Java Code:
public void add(Vector2f a) {
this.x += a.x;
this.y += a.y;
}
Java Code:
public void add(Vector2f a) {
  this.x += a.x;
  this.y += a.y;
}


Würde ich normalerweise zwar vermeiden, aber wenn es um Performance geht...
Vorschlag
Unregistrierter
Beitrag Vorschlag Unregistrierter 02:58:10 20.12.2011   Titel:              Zitieren
viktor_vektor schrieb:
Ist es eine Bedingung, dass Vec2f immutable sein soll? Wenn nicht, könntest du dir zumindest das Erzeugen neuer Objekte sparen.

Java Code:
public void add(Vector2f a) {
  this.x += a.x;
  this.y += a.y;
}
Java Code:
public void add(Vector2f a) {
this.x += a.x;
this.y += a.y;
}
Java Code:
public void add(Vector2f a) {
  this.x += a.x;
  this.y += a.y;
}


Würde ich normalerweise zwar vermeiden, aber wenn es um Performance geht...


Ich wollte genau das gleiche vorschlagen und falls du die Vektoren an 3d Objekte binden willst, würde ich die Vektoren in Arrays packen.

Also so etwas:

Java Code:
public void add(Vector2f a, int index) {
  this.x[index] += a.x[index];
  this.y[index] += a.y[index];
}
Java Code:
public void add(Vector2f a, int index) {
this.x[index] += a.x[index];
this.y[index] += a.y[index];
}
Java Code:
public void add(Vector2f a, int index) {
  this.x[index] += a.x[index];
  this.y[index] += a.y[index];
}


Damit kann man sich in manchen Fällen ein paar Methodenaufrufe sparen, weil man dann nicht für jeden Vektor ein eigenes Objekt hat.
Z.b. bietet sich das beim skalieren oder transformieren an.
C/C++ Forum :: Java ::  Effiziente Vektorrechnung   Auf Beitrag antworten

Zeige alle Beiträge auf einer Seite




Nächstes Thema anzeigen
Vorheriges Thema anzeigen
Sie können Beiträge in dieses Forum schreiben.
Sie können auf Beiträge in diesem Forum antworten.
Sie können Ihre Beiträge in diesem Forum nicht bearbeiten.
Sie können Ihre Beiträge in diesem Forum nicht löschen.
Sie können an Umfragen in diesem Forum nicht mitmachen.

Powered by phpBB © 2001, 2002 phpBB Group :: FI Theme

c++.de ist Teilnehmer des Partnerprogramms von Amazon Europe S.à.r.l. und Partner des Werbeprogramms, das zur Bereitstellung eines Mediums für Websites konzipiert wurde, mittels dessen durch die Platzierung von Werbeanzeigen und Links zu amazon.de Werbekostenerstattung verdient werden kann.

Die Vervielfältigung der auf den Seiten www.c-plusplus.de, www.c-plusplus.info, www.c-sar.de, www.c-plusplus.net und www.baeckmann.de enthaltenen Informationen ohne eine schriftliche Genehmigung des Seitenbetreibers ist untersagt (vgl. §4 Urheberrechtsgesetz). Die Nutzung und Änderung der vorgestellten Strukturen und Verfahren in privaten und kommerziellen Softwareanwendungen ist ausdrücklich erlaubt, soweit keine Rechte Dritter verletzt werden. Der Seitenbetreiber übernimmt keine Gewähr für die Funktion einzelner Beiträge oder Programmfragmente, insbesondere übernimmt er keine Haftung für eventuelle aus dem Gebrauch entstehenden Folgeschäden.