boost::array - Semantik

Blue-Tiger

Hiho!

Ich verwende ein boost::array um ein Array aus einer Funktion zurueckzugeben. Jetzt wollte ich wissen ob boost::arrays das ueberhaupt ermoeglichen und falls ja, wie aufwaendig sowas ist.

Im Grunde mach ich sowas:

typedef boost::array<int, N> FooArray;

FooArray createArray()
{
	Foo a = createFoo(...);
	Foo b = createFoo(...);
	Foo c = createFoo(...);
	FooArray retval = {{a, b, c}}; // (1)
	return retval;
}

Folgende Fragen:
a) wird in (1) fuer jedes in retval eingefuegte Element der Copy-Ctor aufgerufen?
b) kann ein FooArray kopiert werden? Falls ja: werden dann alle enthaltenen Elemente auch kopiert?
c) gibts eine elegantere Art, Arrays aus einer Funktion zurueck zu geben?
d) wie schreib ich eigentlich selbst einen operator=, der eine Initialisierungsliste akzeptiert wie die in (1)?

*D*Evil

a) Kommt auf boost::array an. Denke schon.
b) Richtig.
c) Referenzen.
d) Ja, aber das ist wohl etwas zu schwer für dich.

Blue-Tiger

(D)Evil schrieb:

c) Referenzen.

Kannst du mir dafuer mal ein Beispiel zeigen? Oder meinst du einfach sowas wie

void createArray(FooArray* arrayThatStoresTheReturnValues)
{
    // ...
}

?

d) Ja, aber das ist wohl etwas zu schwer für dich.

DASS es geht ist mir klar, das war auch nicht die Frage. Die Frage war, _WIE_ es geht

camper

Blue-Tiger schrieb:

typedef boost::array<int, N> FooArray;

FooArray createArray()
{
	Foo a = createFoo(...);
	Foo b = createFoo(...);
	Foo c = createFoo(...);
	FooArray retval = {{a, b, c}}; // (1)
	return retval;
}
d) wie schreib ich eigentlich selbst einen operator=, der eine Initialisierungsliste akzeptiert wie die in (1)?

Gar nicht.
1. Ein Zuweisungsoperator ist hier nicht im Spiel (und ein Konstruktor auch nicht, denn int ist keine Klasse), höchtens ein Konvertierungsoperator, je nachdem, was Foo ist.
2. Eine Aggregatinitialisierungsliste kann mit boost::array (bzw. std::tr1::array) verwendet werden, weil array - ganz bewusst - als POD konzipiert ist.

Mit der gegenwärtigen Sprache ist so eine Initialisierungssyntax für Klassen im Allgemeinen ist nicht möglich. Im nächsten Standard wird das wahrscheinlich anders aussehen.

Blue-Tiger schrieb:

c) gibts eine elegantere Art, Arrays aus einer Funktion zurueck zu geben?

Noch eleganter? Was soll das sein?

*D*Evil

Nicht zurück geben, aber sowas ist eleganter:

void foo(arr& dest)
{ /* fill dest */ }

... sparst du dir das kopieren ...

camper

(D)Evil schrieb:

Nicht zurück geben, aber sowas ist eleganter:
void foo(arr& dest)
{ /* fill dest */ }
... sparst du dir das kopieren ...

Dafür opferst du damit die einfache Initialisierung und benötigst zusätzlich ein bereits konstruiertes Objekt. Effizienter ist das jedenfalls nicht, und Eleganz vermisse ich auch.

*D*Evil

? Ob ich jetzt folgendes mache:

std::string result(const char* sample)
{ return std::string(sample); }

int main()
{
    const std::string my_text(result("123456789"));
}

oder

void result(const char* sample, std::string & dest)
{ dest = sample; }

int main()
{
    std::string my_text;
    result("123456789", dest);
}

... da sparst du dir 1x kopieren ... ob du es willst, oder nicht.
okay ich kann dafür my_text nicht const setzen ...

camper

(D)Evil schrieb:

... da sparst du dir 1x kopieren ...

wo? Im ersten Fall ist keine Kopie involviert, die nicht nach 12.8/15 eliminiert werden darf (und konsequenterweise von jedem anständigen Compiler eliminiert werden wird).

Blue-Tiger

Na ja, aber allein um die Objekte in das boost::array hinein zu kopieren wird der Copy-Ctor aufgerufen.

Mein Problem ist, dass die Funktion teil des performance-kritischen Teils meines Programmes ist. In Wirklichkeit schaut das so aus:

class VectorArraySSE
{
	public:
		// ... ein paar Operatoren

	private:
		boost::array<VectorSSE, 3> v;
};

typedef boost::array<Vector3D, 4> VectorArray3D;
inline VectorArray3D convertToVector3D(const VectorArraySSE& va)
{
	const unsigned int shuffle1 = _MM_SHUFFLE(0, 1, 2, 3);
	const unsigned int shuffle2 = _MM_SHUFFLE(4, 3, 0, 1);
	const VectorSSE x0y0x1y1(_mm_unpacklo_ps(va[0].vec, va[1].vec));
	const VectorSSE x0x1z0z1(_mm_movelh_ps(va[0].vec, va[2].vec));
	const VectorSSE a(_mm_shuffle_ps(x0y0x1y1.vec, x0x1z0z1.vec, shuffle1));
	const VectorSSE b(_mm_shuffle_ps(va[2].vec, x0y0x1y1.vec, shuffle2));

	const unsigned int shuffle3 = _MM_SHUFFLE(3,4, 0, 1);
	const VectorSSE x3y3x4y4(_mm_unpackhi_ps(va[0].vec, va[1].vec));
	const VectorSSE c(_mm_shuffle_ps(x3y3x4y4.vec, va[2].vec, shuffle1));
	const VectorSSE d(_mm_shuffle_ps(va[2].vec, x3y3x4y4.vec, shuffle3));

	VectorArray3D retval = {{Vector3D(a.v[0], a.v[1], a.v[2]),
		Vector3D(b.v[0], b.v[1], b.v[2]),
		Vector3D(c.v[0], c.v[1], c.v[2]),
		Vector3D(d.v[0], d.v[1], d.v[2])}};

	return retval;
}

Das Ganze ist SSE-Zeugs, und wandelt 3 SSE-Vektoren (Structure of Arrays) in 4 normale 3D-Vektoren (Array of Structures) um.

So wie's momentan ist, hab ich bei jedem Aufruf der Funktion zuerst 4 normale Vector3D-Ctor Aufrufe (zum erstellen der Objekte) und nachher 4 Copy-Ctor Aufrufe, wobei erstere evtl. vom Compiler ja wegoptimiert werden koennten, oder seh ich das falsch?
Wuerde ich das ganze so Umschreiben, wie (D)Evil vorschlaegt (4 Vector3D* als Eingangsparameter), muesste ich trotzdem immer noch 4 Vector3D-Ctors aufrufen, gewinne also gar nix (sondern verliere eher noch was, weil ich die 4 Pointer vorher ja als normale Vector3D initialisieren muss).

camper

Blue-Tiger schrieb:

So wie's momentan ist, hab ich bei jedem Aufruf der Funktion zuerst 4 normale Vector3D-Ctor Aufrufe (zum erstellen der Objekte) und nachher 4 Copy-Ctor Aufrufe, wobei erstere evtl. vom Compiler ja wegoptimiert werden koennten, oder seh ich das falsch?

Die Copy-ctor-Aufrufe können elimniert werden, nicht die Anderen. Im Übrigen ist dieser Art von Code ohnehin eher ein Spezialfall - allemal sollte deine Vector3D-Klasse über einen Konstruktor verfügen, der direkt mit SSE-Vektoren arbeiten kann. Dann lassen sich einige Variablen einsparen, was durchaus in effizienterem Code resultieren kann. So wie es jetzt aussieht, könntest du auf den SSE-Code auch ganz verzichten, und die Vector3Ds direkt aus den Komponenten von VectorArraySSE konstruieren.

Blue-Tiger

camper schrieb:

Blue-Tiger schrieb:

So wie's momentan ist, hab ich bei jedem Aufruf der Funktion zuerst 4 normale Vector3D-Ctor Aufrufe (zum erstellen der Objekte) und nachher 4 Copy-Ctor Aufrufe, wobei erstere evtl. vom Compiler ja wegoptimiert werden koennten, oder seh ich das falsch?

Die Copy-ctor-Aufrufe können elimniert werden, nicht die Anderen. Im Übrigen ist dieser Art von Code ohnehin eher ein Spezialfall - allemal sollte deine Vector3D-Klasse über einen Konstruktor verfügen, der direkt mit SSE-Vektoren arbeiten kann. Dann lassen sich einige Variablen einsparen, was durchaus in effizienterem Code resultieren kann. So wie es jetzt aussieht, könntest du auf den SSE-Code auch ganz verzichten, und die Vector3Ds direkt aus den Komponenten von VectorArraySSE konstruieren.

Na ja, jeder der 4 Vector3D enthaelt Komponenten aus jedem der VectorSSEs, die im VectorArraySSE gespeichert sind. Wenn ich diese "Zerlegung" in den Vector3D-Ctor verschiebe, muss ich sie 4 mal vornehmen (fuer jeden Vector 1x), das waer eine Vervierfachung der Laufzeit, und der Code ist wie gesagt performancekritisch

camper

Blue-Tiger schrieb:

camper schrieb:

Blue-Tiger schrieb:

So wie's momentan ist, hab ich bei jedem Aufruf der Funktion zuerst 4 normale Vector3D-Ctor Aufrufe (zum erstellen der Objekte) und nachher 4 Copy-Ctor Aufrufe, wobei erstere evtl. vom Compiler ja wegoptimiert werden koennten, oder seh ich das falsch?

Die Copy-ctor-Aufrufe können elimniert werden, nicht die Anderen. Im Übrigen ist dieser Art von Code ohnehin eher ein Spezialfall - allemal sollte deine Vector3D-Klasse über einen Konstruktor verfügen, der direkt mit SSE-Vektoren arbeiten kann. Dann lassen sich einige Variablen einsparen, was durchaus in effizienterem Code resultieren kann. So wie es jetzt aussieht, könntest du auf den SSE-Code auch ganz verzichten, und die Vector3Ds direkt aus den Komponenten von VectorArraySSE konstruieren.

Na ja, jeder der 4 Vector3D enthaelt Komponenten aus jedem der VectorSSEs, die im VectorArraySSE gespeichert sind. Wenn ich diese "Zerlegung" in den Vector3D-Ctor verschiebe, muss ich sie 4 mal vornehmen (fuer jeden Vector 1x), das waer eine Vervierfachung der Laufzeit, und der Code ist wie gesagt performancekritisch

Du unternimmst sie doch sowieso 4 mal:

VectorArray3D retval = {{Vector3D(a.v[0], a.v[1], a.v[2]),
        Vector3D(b.v[0], b.v[1], b.v[2]),
        Vector3D(c.v[0], c.v[1], c.v[2]),
        Vector3D(d.v[0], d.v[1], d.v[2])}};

wieso ist das nicht

VectorArray3D retval = {Vector3D(a), Vector3D(b), Vector3D(c), Vector3D(d)}};

Wenn du wirklich Wert auf Performance legst, sollte Vector3D wahrscheinlich sowieso nur ein Wrapper um VectorSSE sein.

Blue-Tiger

camper schrieb:

Blue-Tiger schrieb:

Na ja, jeder der 4 Vector3D enthaelt Komponenten aus jedem der VectorSSEs, die im VectorArraySSE gespeichert sind. Wenn ich diese "Zerlegung" in den Vector3D-Ctor verschiebe, muss ich sie 4 mal vornehmen (fuer jeden Vector 1x), das waer eine Vervierfachung der Laufzeit, und der Code ist wie gesagt performancekritisch

Du unternimmst sie doch sowieso 4 mal:
VectorArray3D retval = {{Vector3D(a.v[0], a.v[1], a.v[2]),
        Vector3D(b.v[0], b.v[1], b.v[2]),
        Vector3D(c.v[0], c.v[1], c.v[2]),
        Vector3D(d.v[0], d.v[1], d.v[2])}};
wieso ist das nicht
VectorArray3D retval = {Vector3D(a), Vector3D(b), Vector3D(c), Vector3D(d)}};

Ok, das erspart Tipperei, aber warum koennte ich mir damit Variablen sparen?

Wenn du wirklich Wert auf Performance legst, sollte Vector3D wahrscheinlich sowieso nur ein Wrapper um VectorSSE sein.

warum?

camper

inline VectorArray3D convertToVector3D(const VectorArraySSE& va)
{
    __m128 x0x1x2x3 = va[0].vec; // kann man ggf. einsparen, hier erst einmal der Übersichtlichkeit wegen
    __m128 y0y1y2y3 = va[1].vec;
    __m128 z0z1z2z3 = va[2].vec;
    __m128 x0y0x1y1 = _mm_unpacklo_ps( x0x1x2x3, y0y1y2y3 ); // 2
    __m128 x2y2x3y3 = _mm_unpackhi_ps( x0x1x2x3, y0y1y2y3 ); // 2

    VectorArray3D retval = {
        Vector3D( _mm_shuffle_ps( x0y0x1y1, z0z1z2z3, _MM_SHUFFLE( 0, 1, 0, 0 ) ) ), // 2
        Vector3D( _mm_shuffle_ps( x0y0x1y1, z0z1z2z3, _MM_SHUFFLE( 2, 3, 1, 1 ) ) ), // 2
        Vector3D( _mm_shuffle_ps( x2y2x3y3, z0z1z2z3, _MM_SHUFFLE( 0, 1, 2, 2 ) ) ), // 2
        Vector3D( _mm_shuffle_ps( x2y2x3y3, z0z1z2z3, _MM_SHUFFLE( 2, 3, 3, 3 ) ) )  // 2
    };

    return retval;
}

in Kommentaren jeweils die Mindestanzahl an SSE-Instruktionen, die generiert werden müssten. Das ist regelmäßiger (man erkennt sehr schnell, dass sich etwa die shuffle-Indizes nach einem Muster ändern, und 4 hat dort sowieso nichts zu suchen) und einfacher auf Fehler zu überprüfen (man kann sogar noch etwas einsparen: x0x1y0y1/x2x3y2y3 kann mit weniger Instruktionen generiert werden) . Ist Vector3D kein Wrapper um SSE-Register, dann kann bei der Initialisierung (egal ob nun direkt oder über Komponenten) nur Komponentenweise kopiert werden, dann war die ganze Arbeit per SSE aber völlig überflüssig. Im Übrigen ist das wahrscheinlich ohnehin mit zu feiner Granularität optimiert - die hohe Zahl an hin- und hergeshuffle indiziert, dass man bei einer einzelnen Transformation nicht viel gewinnen wird. So oder so hat das alles eigentlich nichts mit dem urspünglichen Thema zu tun.

Blue-Tiger

Thx fuer die Erklaerungen

EDIT: aber warum benoetigt ein _mm_unpackhi_ps 2 Instruktionen?

EDIT2: koenntest du mir nochmal genauer erklaeren, WIE man mit _MM_SHUFFLE angibt, wie geshufflt werden soll? ich glaub ich hab da was falsch verstanden
(ich erhalte z. B. mit deinem obigen Code komplett falsche Shuffles, ich muss die Reihenfolge der Zahlen im _MM_SHUFFLE Ausdruck umdrehen, um die richtigen zu erhalten)