Effiziente Vektorrechnung

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:

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?

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:

// 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*

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

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

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*

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

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)

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

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?

Es ist ein 1 GHz TI OMAP 3620.

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

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.

Ist es eine Bedingung, dass Vec2f immutable sein soll? Wenn nicht, könntest du dir zumindest das Erzeugen neuer Objekte sparen.

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

viktor_vektor schrieb:

Ist es eine Bedingung, dass Vec2f immutable sein soll? Wenn nicht, könntest du dir zumindest das Erzeugen neuer Objekte sparen.
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:

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.