Schnelles Iterieren über Matrix mit beliebiger Dimensionalität

Eisflamme

Hi,

ich möchte gerne über eine Matrix mit beliebiger Dimensionalität iterieren, d.h. eine Schleifenvariante, die mit folgendem Umgehen kann:

std::vector<int> vec1(10 * 20 * 30);
std::vector<int> vec2(10 * 20 * 30 * 40);

, wobei hier jeder Faktor des Produkts der Ausdehnung einer Dimension entspricht. Wichtig: Ich brauche in jeder Iteration die Indizes, also bei einer zweidimensionalen Matrix mit $a_{ij}$ eben i und j.

Eine einfache Lösung fand ich, die aber langsam ist. MSVC12 gibt für

#include <ctime>
#include <vector>
#include <iostream>

using namespace std;

struct type
{
	unsigned int cost;
};

int main()
{
	using namespace std;

	vector<type> vec(11 * 50 * 50 * 50 * 50);

	clock_t start = clock();

	for(unsigned int a = 0; a < 50; ++a)
    {
		for(unsigned int b = 0; b < 50; ++b)
		{
			for(unsigned int c = 0; c < 50; ++c)
            {
            	for(unsigned int d = 0; d < 50; ++d)
                {
                	for(unsigned int e = 0; e < 11; ++e)
                    {
    					vec[a + b * 50 + c * 50 + d * 50 + e * 50].cost = a + b + c + d + e;
                    }
                }
            }
		}

	}

	clock_t end = clock();

	unsigned int indices[] = {0, 0, 0, 0, 0};
	unsigned int maxIndices[] = {50, 50, 50, 50, 11};

	clock_t start2 = clock();

	for(;;)
	{
		vec[indices[0] + indices[1] * 50 + indices[2] * 50 + indices[3] * 50 + indices[4] * 50].cost =
			indices[0] + indices[1] * 50 + indices[2] * 50 + indices[3] * 50 + indices[4] * 50;

		int n;
		for(n = 4; n >= 0; --n)
		{
			if(++indices[n] == maxIndices[n])
				indices[n] = 0;
            else
				break;
		}

		if(n < 0) break;
	}

	clock_t end2 = clock();

	std::cout << "Diff1: " << end - start << '\n'
		<< "Diff2: " << end2 - start2 << '\n';

	char dummy;
	std::cin >> dummy;

	return 0;
}

aus:

Diff1: 57
Diff2: 421

Messe ich falsch? Das Ergebnis scheint verheerend. Es ist nicht der Flaschenhals in meiner eigentlichen Simulation, aber es ist bemerkbar. Gibt es eine bessere Lösung?

Danke und beste Grüße

Skym0sh0

Die Frage ist, was der eigentliche Flaschenhals ist.

Wenn du über (große) Matrizen iterierst , kannst du mit etwas Geschicklich viel Geschwindigkeit rausholen (Stichwort Speicherzugriffszeite, Linesize, Cachegröße, Blocking, Unrolling, usw...)

Dein Frage richtet sich jedoch in Richtung Dimensionalität. Ich würd mir mehrere Klassen schreiben, die jede für eine gewisse Dimensionalität zuständig ist. Diese würde ich dann jeweils etwas optimieren (ja, ist etwas Coderedundanz).

Was du in deinem Code andeutest, das jongliert etwas mit den Indizes rum. Ich hab jetzt leider grad nicht die Zeit mich da reinzudenken, es sieht auf den ersten Blick jedoch etwas komisch aus. Kommen die gleichen Ergebnisse raus? Ja müssten, denke ich.

Aber der Grund, dass es langsamer ist, dass du ungünstig auf den Speicher zugreifst.

knivil

vec[a + b * 50 + c * 50 + d * 50 + e * 50]

Auf welchen Index greifst du hier zu? Tip: es ist nicht (a, b, c, d, e), d.h. du iterierst nicht ueber die Matrix.

Desweiteren ist dein Iterationsschema in Variante 1 nicht cachefriendly. Variante 2 habe ich nicht angeschaut, da da ganze sowieso fehlerhaft ist.

Vergleiche bitte auch:

vec[a + b * 50 + c * 50 + d * 50 + e * 50].cost = a + b + c + d + e;

mit

vec[indices[0] + indices[1] * 50 + indices[2] * 50 + indices[3] * 50 + indices[4] * 50].cost = 
indices[0] + indices[1] * 50 + indices[2] * 50 + indices[3] * 50 + indices[4] * 50;

Es ist nicht das gleiche. Dein Benchmark ist hinfaellig.

Eisflamme

Skym0sh0:

Aber der Grund, dass es langsamer ist, dass du ungünstig auf den Speicher zugreifst.

Wie verbessere ich das?

Die Coderedundanz-Variante wollte ich eigentlich vermeiden, wenn möglich. Das wird ja echt viel Schreibarbeit.

knivil:
Stimmt, das ist so unsinnig. Spielt das performancetechnisch eine Rolle? Edit: Nach Korrektur sind die Varianten tatsächlich gleich schnell, so was.

Wie könnte ich Variante1 cachefreundlicher machen? Aber eigentlich will ich ja eher Variante2 optimieren.

Edit: Den Rest lese ich gleich, schon Mal danke für die Anregungen.

knivil

Stimmt, das ist so unsinnig. Spielt das performancetechnisch eine Rolle?

Definitiv. Wenn ich nur ca. 40 kByte anfasse, dann passt das vermutlich alles in den Cache. Weiterhin moechtest du einen Benchmark um ueber Matrizen zu iterieren. Was hilft dir da ein Test, der das nicht testet.

Shade Of Mine

iterieren tust du am besten von 0 bis N.

Wenn du bei dem index I bist, musst du anhand von I herausbekommen welche "indexes" du verwenden willst - dein a,b,c,... Nur ist das halt willkürlich festgelegt.

du könntest zB bei einer 2 dim matrix sagen:
Bei I hast du a = I/spalten und b = I%spalten