Templates und deren Grenzen

Dravere

Naja, wenn du dir überlegst, dass der operator new und new[] einen std::size_t Parameter für die Grösse erwarten und auch das sizeof Schlüsselwort eine Konstante vom Typ std::size_t zurück gibt, dann wäre das wohl schon der richtige Typ. Ein Array kann dann wohl nur schlecht grösser sein, als ein std::size_t aktzeptiert:

char arr[xxxx];
sizeof(arr); // <- gibt einen std::size_t zurück,
             //    die Zahl xxxx muss also in einen std::size_t reinpassen.

Und wie du auch selbst sagst, eine Matrix der Grösse 2^32-1 dürfte ein wenig gross sein
Du machst mit dem zusätzlichen Templateparameter dem Nutzer einfach zusätzliche Arbeit.

Grüssli

unskilled

hmm... ok ^^

edit: Der Vollständigkeit halber hier mal die richtige Version (die von oben war ein wenig sehr fehlerbehaftet, aber naja )

template <typename Treturnvaluetype, size_t dim, typename Tvaluetype>
Treturnvaluetype Determinant_LaPlace (const TMatrix <dim, dim, Tvaluetype> &thismatrix)
{
	Treturnvaluetype sum = Treturnvaluetype();
	typedef TMatrix <dim, dim, Tvaluetype>	TThisMatrix;
	typedef typename TThisMatrix::SizeType	SizeType;
	const SizeType nextdim (dim-1);
	typedef TMatrix <nextdim, nextdim, Tvaluetype> TNextMatrix;

	TNextMatrix nextmatrix;

	for (SizeType m = SizeType(); m != dim; ++m)
	{
		for (SizeType n = SizeType(); n != nextdim; ++n)
		{
			TNextMatrix::Line &line_to = nextmatrix[n];
			const TThisMatrix::Line &line_from = thismatrix[n+1];

			for (SizeType i = SizeType(); i != m; ++i)
			{
				line_to[i] = line_from[i];
			}
			for (SizeType i (m); i != nextdim; ++i)
			{
				line_to[i] = line_from[i+1];
			}
		}
		if (m%2)
			sum -= thismatrix[0][m] * Determinant_LaPlace <Treturnvaluetype> (nextmatrix);
		else
			sum += thismatrix[0][m] * Determinant_LaPlace <Treturnvaluetype> (nextmatrix);
	}
	return sum;
}

geloescht

a) Es gibt die Determinante einer 1x1-Matrix, nämlich das einzelne Element selbst. Also nix invalid_argument.
b) Ich würde durchaus statische Arrays einsetzen, du kannst ja eine Instanz der Klasse auf dem Heap erstellen, dann ist der Stack garnicht bis kaum gewachsen. Mit smart pointern ist die Speicherverwaltung keine große Sache. Also auch keine Obergrenze dadurch. Aber ist nicht zwingend notwendig, ich bin mir sicher, dass es bezogen auf Speicher und Geschwindigkeit sowohl Vorteile als auch Nachteile gibt. Z.B. macht shared_ptr eingesparte dynamische Allokationen wieder zunichte. Für jede Zeile eine dynamische Allokation zu machen ist aber unnötig, du kannst alles am Block allozieren!
c) Für riesige Matrizen ist diese Klasse sowieso nicht geeignet, das hätte gigantischen Speicherverbrauch zur Folge. Dafür gibt es spezielle Implementationen für große Matrizen mit vielen Nullen oder gleichen Elementen usw. Schau dir einfach mal boost::ublas an.

unskilled

geloescht schrieb:

a) Es gibt die Determinante einer 1x1-Matrix, nämlich das einzelne Element selbst. Also nix invalid_argument.

Japp, hab ich (jz) auch so

geloescht schrieb:

Ich würde durchaus statische Arrays einsetzen, du kannst ja eine Instanz der Klasse auf dem Heap erstellen, dann ist der Stack garnicht bis kaum gewachsen. Mit smart pointern ist die Speicherverwaltung keine große Sache. Also auch keine Obergrenze dadurch. Aber ist nicht zwingend notwendig, ich bin mir sicher, dass es bezogen auf Speicher und Geschwindigkeit sowohl Vorteile als auch Nachteile gibt. Z.B. macht shared_ptr eingesparte dynamische Allokationen wieder zunichte. Für jede Zeile eine dynamische Allokation zu machen ist aber unnötig, du kannst alles am Block allozieren!

Ich alloziere alles im Block - und mach danach nen placement new auf den Eintrag um ihn mit 0 oder was auch immer zu initialisieren

geloescht schrieb:

Für riesige Matrizen ist diese Klasse sowieso nicht geeignet, das hätte gigantischen Speicherverbrauch zur Folge. Dafür gibt es spezielle Implementationen für große Matrizen mit vielen Nullen oder gleichen Elementen usw. Schau dir einfach mal boost::ublas an.

Diese Klasse soll aber nicht für schwach besetzte Matrizen sein - sonst hätte ich sie kaum TMatrix genannt sondern iwie vermerkt, dass sie besser mit schwach besetzten Matrizen umgehen kann als mit voll besetzten...

Noch mal dazu:

Mit smart pointern ist die Speicherverwaltung keine große Sache

mit new und delete ja auch nicht, weil ich einmal den Speicher alloziere und einmal lösche - dann ist es noch in der copy-Fkt ein bisschen mehr Arbeit, aber alles in allem sind es vll 10 Zeilen die ich mir dadurch sparen könnte - Vorteile sehe ich davon aber keine - Nachteile würden mir aber ein paar einfallen - angefangen damit, dass ich nicht so schön mit dem Inhalt spielen kann, wie ich es mit den rohen Arrays tun kann ^^

bb

Nexus

Wieso verwendest du eigentlich kein std::tr1::array (oder bei fehlender TR1-Unterstützung boost::array )?

unskilled

Nexus schrieb:

Wieso verwendest du eigentlich kein std::tr1::array (oder bei fehlender TR1-Unterstützung boost::array )?

unskilled schrieb:

so weit ich weiß speichert auch std::tr1::array seinen Inhalt auf dem Stack, oder?

Da std::tr1::array meines Erachtens nach auf dem Stack operiert (was zwar schneller ist aber der ist eben auch sehr begrentzt...)
Außerdem glaube ich nicht, dass ich mit std::tr1::array so gut arbeiten kann, wie bis jetzt:

Line(ValueType fill_with = ValueType())
	:	values(new ValueType[row_count])
{
	for(SizeType i = SizeType(); i != row_count; ++i)
	{
		new (values + i) ValueType(fill_with);
	}
}

//bzw.

TMatrix(ValueType fill_with = ValueType())
	:	lines ((Line*) new char[sizeof(Line) * line_count])
{
	for(SizeType i = SizeType(); i != line_count; ++i)
	{
		new (lines + i) Line(fill_with);
	}
}

Und da es so auch geht und ich nicht weiß, ob (wenn ja, wie) es mit std::tr1::array geht, habe ich eben diese Lösung gewählt ^^ Oder ist gegen diese Variante irgendetwas zu sagen?

bb

Nexus

Sorry, das hab ich nicht gesehen. Ja, std::tr1::array ist ein einfacher Wrapper für C-Arrays, der noch weitere Funktionalität bereitstellt.

unskilled schrieb:

Oder ist gegen diese Variante irgendetwas zu sagen?

Findest du das schön?

lines ((Line*) new char[sizeof(Line) * line_count])

unskilled

Nexus schrieb:

Ja, std::tr1::array ist ein einfacher Wrapper für C-Arrays, der noch weitere Funktionalität bereitstellt

Gut - ich hatte daran gezweifelt, dass er auch bei großen Größen auf dem Stack bleibt (hätte ja sein können, dass es je nach Größe spezialisiert ist)...

Nexus schrieb:

Findest du das schön?

lines ((Line*) new char[sizeof(Line) * line_count])

Hältst du es für umgänglich? (extrem hübsch finde ich es zwar nicht aber ich hab keinen anderen Weg gefunden und außer den optischen Nachteil ist mir keiner aufgefallen - und wenn an mal 5 Sekunden Zeit investiert erkennt man auch als Außenstehender, was man dort macht)

bb

geloescht

Schön, dass du diese kleine Änderungen mit der Determinante gemacht hast - in deinem Originalpost war kein placement new zu sehen. Ich fürchte aber, dass es die Arbeit nicht wert ist, die dir ein statisches Array sparen würde. Vll. hab ich mich falsch ausgedrückt: Mit "statisches Array" meine ich, dass die Größe des Arrays zu Compilezeit feststeht, nicht darauf, ob das Array auf dem Heap, dem Stack oder sonstwo gespeichert ist. Du könntest eine Instanz von std::tr1::array immernoch auf dem Heap erstellen! Plus es ist leicht damit umzugehen plus es ist schnell plus es spart Speicherplatz ggü. einem std::vector plus es ist einfach kopierbar.
Ein Beispiel:

template <int size>
struct giant
{
  char bar[size];
};

int main()
{
  //Das da braucht gerademal nen Pointer auf dem Stack
  giant* A = new giant<1000>();
  //Das da braucht womöglich 1kB auf dem Stack
  giant B<1000>;
}

Über die Grenzen des Stacks brauchst du dir wohl erst Gedanken machen, wenn du auf sie stößt.
:xmas2:

Nexus

unskilled schrieb:

Nexus schrieb:
Findest du das schön?
lines ((Line*) new char[sizeof(Line) * line_count])
Hältst du es für umgänglich? (extrem hübsch finde ich es zwar nicht aber ich hab keinen anderen Weg gefunden und außer den optischen Nachteil ist mir keiner aufgefallen - und wenn an mal 5 Sekunden Zeit investiert erkennt man auch als Außenstehender, was man dort macht)

Aber was war dann mit deiner vorherigen Lösung?

lines(new Line[line_count])

geloescht schrieb:

Du könntest eine Instanz von std::tr1::array immernoch auf dem Heap erstellen! Plus es ist leicht damit umzugehen plus es ist schnell plus es spart Speicherplatz ggü. einem std::vector plus es ist einfach kopierbar.

Die Schnelligkeit, die aufgrund der Stack-Allokation gewonnen wird, geht hier auch wieder verloren. Ein std::tr1::array auf dem Heap dürfte etwa gleich schnell sein wie ein std::vector . Und der verschwendete Speicherplatz sollte eigentlich auch nicht gross ins Gewicht fallen. Aber darüber sollte man sich sowieso erst Gedanken machen, wenn es erforderlich ist...

Im Gegenzug nimmt man mit einem dynamisch allokierten std::tr1::array manuelle Speicherverwaltung und die damit verbundenen Probleme in Kauf. Ich selbst würde std::tr1::array wirklich nur für statische Arrays verwenden.

unskilled

Nexus schrieb:

unskilled schrieb:
Nexus schrieb:
Aber was war dann mit deiner vorherigen Lösung?
lines(new Line[line_count])

(boar - was ne Arbeit das alles fertig auszuzitieren ^^)
Hmm... Ist natürlich ne sehr gute Frage, wieso ich das gemacht habe - eigtl weil ich es für nötig hielt - allerdings kann ich dir weder sagen, warum ich das getan habe, noch hab ich jetzt beim Ändern auf die schönere Variante Fehlermeldungen erhalten.

Nur einwas ist sehr komisch:
main

{ //~0 KB
	my::TMatrix <1000, 1000, double> eins(23); //~n KB
} //~n/2 KB

(ich weiß, das OS nimmt nicht sofort wieder allen Speicher zurück etc - aber bei jeder Größe hat mein Programm nach dem Ende des Scopes immer noch die Hälfte des RAMs (priv. Arbeitssatz) wie im Scope...

counter

namespace my
{
	size_t v (0);
	size_t l (0);
	size_t v2 (0);
}

vor dem erstellen:
0
0
0

nach dem erstellen:
2000
1
1000

nach dem zerstören:
1000
0
0

//matrix -> matrix

TMatrix(ValueType fill_with = ValueType())
	:	lines (new Line[line_count])
{
	++::my::l;
	for(SizeType i = SizeType(); i != line_count; ++i)
	{
		new (lines + i) Line(fill_with);
	}
	::my::v2 += line_count;
}

~TMatrix()
{
	--::my::l;
	::my::v2 -= line_count;
	delete [] lines;
}

matrix -> line

Line(ValueType fill_with = ValueType())
	:	values(new ValueType[row_count])
{
	++::my::v;
	for(SizeType i = SizeType(); i != row_count; ++i)
	{
		new (values + i) ValueType(fill_with);
	}
}
~Line()
{
	--::my::v;
	delete []values;
}

Nun erscheint mir ein nach char* casten im ctor doch wieder sinnvoll - allerdings wird dann der dtor ja trotzdem nicht aufgerufen - geht ein placement new überhaupt auf eine struktur, die selbst im ctor werte initialisiert? Oder gibts zum placement new irgend nen Gegenstück, was ich kennen sollte?

Danke schon mal - bb

pumuckl

Zwei Anmerkungen zu der initialisierung von lines in der Initliste:

Ist die Variante mit dem new char... nicht nur unschön, sie müsste sogar wenn mans genau nimmt noch unschöner sein - aus C-Cast mach reinterpret_cast
ist die Variante dann nicht nur noch unschöner, sondern es müsste eigentlich, getriggert durch den reinterpret_cast auf ein Array, folgendes passieren: sämtliche Alamrglocken schrillen und es blinkt ein großes, grelles Schild mit der Aufschrift "alignment/padding?!"
Die neue Variante ist zwar schöner anzusehn, aber nicht exception-safe (falls das für dich von Bedeutung ist): Wenn irgendwo im Rest der init-Liste eine Exception hochkommt dann hat das Objekt selbst nie existiert, weil nie alle Member initialisiert wurden, und alles was bleibt nachdem die bereits initialisierten Objekte abgeräumt wurden ist ein Speicherleck. Also kein new in Init-Listen, wenn man Exception safe bleiben möchte (es sei denn man initialisiert damit einen Smartpointer, dessen entsprechender Konstruktor unter Garantie keine Exceptions wirft.)

unskilled

pumuckl schrieb:

Ist die Variante mit dem new char... nicht nur unschön, sie müsste sogar wenn mans genau nimmt noch unschöner sein - aus C-Cast mach reinterpret_cast

Jopp - das wärs schon noch geworden, aber wollte ja erst mal wissen, ob es von der theorie so richtig wäre

pumuckl schrieb:

ist die Variante dann nicht nur noch unschöner, sondern es müsste eigentlich, getriggert durch den reinterpret_cast auf ein Array, folgendes passieren: sämtliche Alamrglocken schrillen und es blinkt ein großes, grelles Schild mit der Aufschrift "alignment/padding?!"

Oh - daran hatte ich wirklich nicht gedacht - aber habs ja jz auch wieder mit nem "sauberen" new und placement new - aber das speicherleck bleibt bestehen - und ich weiß nicht, warum -.-

pumuckl schrieb:

Die neue Variante ist zwar schöner anzusehn, aber nicht exception-safe (falls das für dich von Bedeutung ist): Wenn irgendwo im Rest der init-Liste eine Exception hochkommt dann hat das Objekt selbst nie existiert, weil nie alle Member initialisiert wurden, und alles was bleibt nachdem die bereits initialisierten Objekte abgeräumt wurden ist ein Speicherleck. Also kein new in Init-Listen, wenn man Exception safe bleiben möchte (es sei denn man initialisiert damit einen Smartpointer, dessen entsprechender Konstruktor unter Garantie keine Exceptions wirft.)

Also pack ich nen try / catch um die schleife und fange bad_alloc auf - und falls es geworfen wurde, führe ich den dtor aus und werfe die exception einfach ganz normal weiter?!

bb

edit: Also vll weiß ichs auch einfach nicht, aber ich glaube das normale new darf gar kein new auf Line sein sondern _muss_ auf nen intergralen Typen sein?!
Meine Lösung sieht jetzt folgendermaßen aus
(ich weiß nicht, ob man den exception-safe ctor normalerweise ähnlich implementiert aber ich hab anscheind noch irgendwo nen fehler drin - jedenfalls gibt er bei nem bad_alloc anscheind nicht wieder alles frei ><

Minimal-Code (fertig für copy&paste ^^):

template <size_t line_count, size_t row_count, typename ValueType>
class TMatrix
{
public:
	typedef size_t					SizeType;

	class Line
	{
	private:
		ValueType *values;

		void destruct(SizeType i = row_count) throw()
		{
			if(!values)
				return;

			for(; i != 0; --i)
			{
				values[i-1].~ValueType();
			}
			delete [] values;
			values = nullptr;
		}
	public:
		Line(ValueType fill_with = ValueType())
			:	values(new ValueType[row_count])
		{
			SizeType i = SizeType();
			try
			{
				for(; i != row_count; ++i)
				{
					new (values + i) ValueType(fill_with);
				}
			}
			catch (...)
			{
				destruct(i);
				throw;
			}
		}

		~Line()
		{
			destruct();
		}
	};

private:
	Line *lines;

	void destruct(SizeType i = line_count) throw()
	{
		if(!lines)
			return;

		for(; i != 0; --i)
		{
			lines[i-1].~Line();
		}
		delete [] reinterpret_cast <char*> (lines);
		lines = nullptr;
	}

public:
	TMatrix(ValueType fill_with = ValueType())
		:	lines ( reinterpret_cast <Line*> (new char[sizeof(Line) * line_count]) )
	{
		SizeType i = SizeType();
		try
		{
			for(; i != line_count; ++i)
			{
				new (lines + i) Line(fill_with);
			}
		}
		catch(...)
		{
			destruct(i);
			throw;
		}
	}

	~TMatrix()
	{
		destruct();
	}
};

Nun könnte man aus destruct noch nen template machen und wahrscheinlich auch noch nen template für init oder so - aber im Grunde genommen sollte es doch so (oder ähnlich) gehen, oder?

Zu Alignment/Padding: Sicher, dass das hier eine Rolle spielt?

bb und danke schon mal fürs angucken?! : >

Dravere schrieb:

// Und jetzt Spezialisierungen:
template <typename Treturnvaluetype, typename Tvaluetype>
Treturnvaluetype Determinant_LaPlace<Treturnvaluetype, 2, Tvaluetype> (const TMatrix <2, 2, Tvaluetype> &thismatrix)
{
    return Treturnvaluetype(thismatrix[0][0] * thismatrix[1][1] - thismatrix[0][1] * thismatrix[1][0]);
}
// ...

Leider sind partielle Spezialisierungen von Funktionstemplates nicht erlaubt, oder kompiliert das dein Compiler ?

drakon

*mist*

Dravere

KasF schrieb:

Leider sind partielle Spezialisierungen von Funktionstemplates nicht erlaubt, oder kompiliert das dein Compiler ?

Jap, tut er. Zwar habe ich jetzt nicht genau das gemacht, aber habe ein foo-Test gemacht:

#include "Test.hpp"

#include <iostream>

template<typename T>
void foo()
{
	std::cout << "T!" << std::endl;
}

template<>
void foo<void>()
{
	std::cout << "void" << std::endl;
}

int main()
{
	foo<int>();
	foo<void>();

	test::wait("Press ENTER to exit...");

	return 0;
}

Mir persönlich ist der genaue Standard dazu nicht bekannt. Verwende den MSVC 2005.

Aber was soll, dann nimmt man statt Templatespezialisierung Funktionsüberladung. Sollte genauso gehen.

Grüssli

drakon

Das entscheidende war, dass du dort eben partielle Spezialisierung benutzt hast. Komplette Spezialisierung ist erlaubt, partielle eben nicht..

Dravere

drakon schrieb:

Das entscheidende war, dass du dort eben partielle Spezialisierung benutzt hast. Komplette Spezialisierung ist erlaubt, partielle eben nicht..

Achso ... *Kopf -> Tisch*
Das kommt ja auch erst mit dem nächsten Standard

Naja, aber in diesem Fall sollten Funktionsüberladungen Abhilfe schaffen.

Grüssli

Nexus

Dravere schrieb:

Das kommt ja auch erst mit dem nächsten Standard

Sind in C++0x partielle Spezialisierungen von Funktionen möglich? Was war der Grund, sie bisher nicht einzuführen?

Dravere schrieb:

*Kopf -> Tisch*

Hehe, als ich das zuerst gesehen habe, dachte ich, es handle sich um eine Dereferenzierung. Dann hat mich verwirrt, dass bei "Tisch" das * nach dem Bezeichner steht... Vielleicht sollte ich langsam ins Bett...

drakon

Dravere schrieb:

drakon schrieb:

Das entscheidende war, dass du dort eben partielle Spezialisierung benutzt hast. Komplette Spezialisierung ist erlaubt, partielle eben nicht..

Achso ... *Kopf -> Tisch*
Das kommt ja auch erst mit dem nächsten Standard

Naja, aber in diesem Fall sollten Funktionsüberladungen Abhilfe schaffen.

Grüssli

Hehe..

Wenn wir schon bei dabei sind..

Das dürfte für dich interessant sein (warst doch du,der Probleme hatte, oder?:))
http://developer.amd.com/documentation/videos/pages/IntroductiontoAMDCodeAnalystPerformanceAnalyzer.aspx

(Achtung lautes Video.. -.-)