Array mit memalign

[Daniel R. (zerrome)]

Hallo,

ich check es gerade total nicht, kann mir jemand auf die Sprünge helfen?

Code der so funktioniert:

typedef uint32_t trellis_value_t[4];
trellis_value_t trellis_matrix[10][100] __attribute__((aligned (16)));

Code der nicht funktioniert:

  trellis_value_t **trellis_matrix;
  trellis_matrix = (trellis_value_t**) memalign(16,10 *sizeof(trellis_value_t*));

  trellis_matrix = (trellis_value_t*) memalign(16,100 *sizeof(trellis_value_t*));

  uint32_t l;
  uint32_t j = 100 - 1;
  do {
    l = 10 - 1;
    do {
      trellis_matrix[l][j] = (trellis_value_t*) memalign(16,100*sizeof(trellis_value_t));
    } while (l--);
  } while (j--);

Ich möchte eine 10x100 Matrix von trellis_value_t Elementen...

Viele Grüße

Daniel

[Sam P. (Gast)]

Dein Code ist ja völlig wirr. Erst weist du zwei verschiedene Werte der 
Variablen trellis_matrix zu, und dann machst du ne Schleife über alle 
Elemente, wobei du jedem Element noch einmal ein Array zuweist.

Willst du nun ein zweidimensionales oder ein dreidimensionales Array? Du 
solltest dich nochmal in Ruhe mit Pointern (und den Parallelen zu 
Arrays) befassen, da du da offensichtlich einiges durcheinanderwirfst.

[Daniel R. (zerrome)]

Was ist an dem ersten Beispiel denn wirr?

Ich möchte eine n x m Matrix aus trellis_value_t Elementen.
Klappt ja auch im ersten Beispiel genau so wie ich das möchte! Nur 
dynamisch nicht so wie ich möchte...
Also wenn Du weißt wie es geht, wäre HILFE nett.

[Sam P. (Gast)]

Was du machst, ist wirr. Alleine diese Doppelzuweisung am Anfang ist 
vollkommen Sinnfrei. Du überschreibst ja den Zeiger zum gerade frisch 
allozierten Speicher gleich wieder -> Speicherleck. Deine seltsamen 
verschachtelten Schleifen sind auch seltsam.

Ich vermute jetzt mal, du willst etwas in dieser Art (Pseudocode!):

matrix_t **matrix = memalign(10*size);
for (i = 0; i < 10; i++) matrix[i] = memalign(100*size);

Du denkst zu kompliziert. Das ist ein starkes Indix dafür, dass dich 
Pointer noch verwirren. Darum wäre es Sinnvoll, darüber so lange zu 
grübeln, bis dir klar ist, was du alles falsch gemacht hast.

Und hab keine Angst vor "for". Das ist ein klassischer Einsatzzweck der 
"for"-Schleife.

[Daniel R. (zerrome)]

Schon mal assembler Code von for schleifen angeschaut? Besonders die 
Sprünge? Und ja *** Konstrukte benutze ich das erste mal, ist wirklich 
etwas verwirrend. Habs aber jetzt auch. Ist aber noch nicht wirklich 
performant, weil der Speicher nicht zusammenhängend ist. Da wird es 
jetzt wirklich kizelig...man müsste erst den ganzen Speicher besorgen 
und dann die Pointer für die Referenzierung der matrix[x][y][values] 
setzen.

  trellis_value_t **trellis_matrix;
  trellis_matrix = (trellis_value_t**) memalign(16, 100 * sizeof(trellis_value_t*));

  uint32_t l = 100 - 1;
  do {
    trellis_matrix[l] = (trellis_value_t*) memalign(16, 10 * sizeof(trellis_value_t));
  } while (l--);

[Sam P. (Gast)]

Ach so, was natürlich auch geht, fällt mir grad ein (wieder Pseudo-C):

// Matrix als zusammenhängender Speicherblock,
// spart eine Pointer-Dereferenzierung
matrix_t *matrix = memalign(10*100*size);

// Zugriff stattdessen über einfache Arithmetik,
// je nach Prozessor quasi-kostenlos
printf("x=%d, y=%d, wert=%d\n", x, y, matrix[x*10+y]);

Was sich mehr lohnt, ist aber stark CPU- und Compilerabhängig. Im 
zweifelsfall erstmal so machen, wie du es am besten verstehst. Wenn es 
dann zu lahm ist und der Profiler zeigt, dass es dieser Code ist, dann 
hast du jetzt ja zwei Varianten, die du versuchen kannst.

[Sam P. (Gast)]

Daniel R. schrieb:
> Schon mal assembler Code von for schleifen angeschaut?

Wenn du einen Compiler hast, der auch nur ein kleinstes bisschen Hirn 
hat (und du nicht vergessen hast, die Optimierung einzuschalten), dann 
sind for und while-Schleifen absolut identisch. 100%. Jede For-Schleife 
lässt sich als While-Schleife formulieren, und umgekehrt. Warum sollte 
der Compiler also unterschiedlichen Code erzeugen?

Mal ganz davon abgesehen, dass dir der Assemblercode egal sein sollte. 
Optimiere nicht aufwendig im Voraus. Ein funktionierendes und 
hinreichend fehlerarmes Programm ist viel wichtiger (und schwer genug).

Wenn's dann zu lahm ist, benutz einen Profiler und finde heraus, wo 
überhaupt Optimierungsbedarf besteht. "Optimierst" du von Hand an 
Stellen, die an der Gesamtlaufzeit kaum einen Einfluss haben, dann hast 
du effektiv nur wertvolle Zeit damit vergeudet, dein Programm unlesbar 
zu machen.

[Daniel R. (zerrome)]

Hm, ich glaube nicht das der Compiler einfach eine Schleife rückwärts 
laufen lässt bzw den Code so umschreibt das es auch geht (geht ja nicht 
immer). Beim rückwärts laufen muss dann nur noch bei jedem Durchlauf auf 
0 geprüft werden. Daraus hat der Compiler mit Optimierung bis jetzt 
immer den Besten Code gemacht. Deshalb hab ich mir einfach do while 
schleifen in dieser Form angewöhnt.

Ich hab mit Intrinsischen SSE Funktionen schon mal den Faktor 7 
rausgeholt :) das war sehr fummelig weil erst nachher darüber 
nachgedacht wurde wie viele Multiplikationen da bei diversen Berechnung 
anfallen (war aber vorher klar). Faktor 7 ist 100% CPU Last oder 14%.

Wenn man erst mal 3000 Zeilen Code schreibt und DANN die Dinge optimiert 
machen möchte ist das doppelt und dreifache Arbeit. Vorher nachdenken 
tut nicht weh...meine persönliche Meinung.

Hier: http://www.ics.uci.edu/~dan/class/165/notes/memory.html
Ist ganz unten ein Beispiel wie man erst die Pointer anlegt und dann 
zusammenhängenden Speicher. Danach werden die Pointer dann richtig 
"gesetzt". Das versuche ich mal nachzubauen.

Danke für die Hilfestellung

Viele Grüße

Daniel

[Sam P. (Gast)]

Was spricht denn gegen:

for (i = max-1; i >= 0; i--) { ... }

Ichmeinjanur. For-Schleifen signalisieren Zählschleifen. Technisch gibt 
es keinen Unterschied zwischen while und for, aber kann nicht mal einer 
an die Kin- äh -- Lesbarkeit denken?

Was die Optimierung angeht: Wenn du 30.000 statt 3.000 Zeilen schreibst, 
dann denkst du anders. Da ist schlicht keine Zeit, das gesamte Programm 
händisch zu optimieren.

Es ist wichtig, die großen Algorithmen gut zu planen, weil dir da kein 
Compiler hilft. Mikrooptimierung kann man aber in 90% der Fälle getrost 
dem Compiler überlassen. Wozu beim einmaligen Initialisieren Zeit 
vergeuden und dabei seinen Code schlechter wartbar machen?

Rückwärtszählen ist ein Klassiker, und ruiniert den Code nicht 
wesentlich, aber es gibt CPUs, wo es schlicht nichts ändert, und im 
Zusammenhang mit Cache-Prefetch auch welche, bei denen es langsamer ist. 
Kaum eine Mikrooptimierung kann man so pauschal als "besser" 
deklarieren. Seine Zeit und Aufmerksamkeit steckt man wirklich besser in 
Wartbarkeit.

Klar, in einem millionenfach ausgeführten Schleifenkörper kann man gut 
mal manuell rangehen. Ich würde aber stets erst einen Profiler befragen, 
bevor ich irgendwo Zeit reinstecke, wo am Ende gar kein Problem ist.

Da erlebt man gerne mal so seine Überraschung mit Caches, Pipeline 
Stalls oder Branch Prediction, und dann waren die scheinbar optimalen 
Assembleranweisungen sogar genau das falsche. Das sind nicht mehr die 
Zeiten des MOS 6502.