Hey,

ich programmiere grad ne Simulation für das Ising Modell.
Ich habe eine Matrix mit Werten, die nur 2 Zustände annehmen können.
Bisher habe ich dafür aus verschiedenen Gründen ein vector < vector <unsigned char> > verwendet. (unsigned char** ginge genauso)

Das ganze wird dann mit QT visualisiert. Dazu verwende ich ein QImage mit Format Format_Indexed8.
In dem Format gibts ne Farbtabelle und eine Matrix aus chars, in der die Farbindizes gespeichert werden ( 256 mögliche Farben).
So kann ich ganz einfach den Inhalt der Werte-Matrix mit memcpy in die Index-Matrix zeilenweise reinkopieren.
Das sieht dann so aus:


Man kann über scanLine den Pointer des ersten Indexes einer Pixelzeile rausfinden.
Wenn man mit zwei for Schleifen den Pointer des Elements (x,y) dereferenziert und den Wert setzt dauerts 50 mal so lange. Deswegen memcpy.
Speicherplatz war bisher kein Thema, da ich neben der char Matrix auch eine gleichgroße Matrix mit 64bit integers hatte. Deswegen wars egal ob ich für die Werte ein byte (char) oder ein bit (bool) belege.
Jetzt hab ich aber nen Algorithmus gefunden, bei dem ich nur 2 Matrizen mit bool Werten brauche.
Die Frage ist, wie bekomm ich den Inhalt von nem vector<bool> oder von nem bool array effizient in das char array von dem Bild rein?
image->scanLine() liefert immer den Pointer auf das erste Byte. Wählt man statt Format_Indexed8 das Format Format_Mono, so sind in dem byte die ersten 8 Pixel drin und die Farbtabelle hat nur noch 2 Farben.

@thefiloe
Ja die Matrix ist immer eine NxN Matrix insofern ist sowohl die Zeilenlänge, als auch die Anzahl der Zeilen gleich.
Wenns rechteckig und nicht quadratisch wäre wüsste ich schon wo ich was ändern würde.

Das Problem ist nicht das kopieren der Werte von nem bool array in ein char array, sondern das effiziente kopieren.
Bisher war die memcpy Variante ziemlich effizient und zwar genau 50 mal schneller als das Setzen jedes einzelnen Pixels.
Dies war aber nur möglich weil ich ein char array blockweise per memcpy in ein anderes char array kopieren konnte.
Jetzt muss der Inhalt von nem bool array/ bool vector in das char array.
Denn scanline() liefert immer nen Pointer auf char, auch wenn (wie bei Format_Mono) die Pixel bitweise in ein Byte gepackt werden (8 Pixel in einem byte).

@RodFromGermany
Wieso ist data->matrix[dimY * dimX] performanter? Ich habe es bisher aus Bequemlichkeit und Übersichtlichkeit einen 2D vector genommen.
Ich hätte geraten, es ist Wurscht wie Käse, ob 1D oder 2D. Mit ist klar, dass in ersterem Fall es nur ein kontinuierlicher Speicherblock ist.

€:
Die einfachste Variante wäre es mit image->setPixel(x, y, data->matrix[y][x]) jeden Pixel einzeln zu setzen. Das dauert natürlich sehr viel länger als memcpy, vor allem weil man jedesmal nur 1 Bit setzt. (Wahrscheinlich nochmal Faktor 8 langsamer)

thefiloe schrieb:

Geht mein Beispiel nicht?

Also das Beispiel lößt nicht das Problem, weil ich wegen der Geschwindigkeit den Bereich gleich blockweise kopieren will.

Davon abgesehen weiß ich gar nicht was du mit deinem Code überhaupt machen willst.
Was soll dabei rauskommen, wenn du dem vector line einen Wert vom Typ char* zuweißt? Das kompiliert nicht mal.


Eine Möglichkeit wäre über 2 for Schleifen (ist natürlich langsam)


Was mir helfen würde, wäre die Speicheradresse vom ersten byte eines vector<bool>/ bool array.
Also ein Pointer auf char in dem sich die ersten 8 bit befinden. Da ginge memcpy.

@RodFromGermany
Ich vermute mal, dass das daran liegt, dass dein Bild "relativ" klein war. Dadurch haste durch die Cacheline nen Vorteil, wenn du zeilenweise drüber iterierst. Beim letzten Element einer Zeile haste dann automatisch schon die ersten Elemente der nächsten Zeile im Cache. Bei mir gehts um Matrizen/Bilder größer 20000^2. Ich glaub nicht, dass das da noch nen großen Unterschied macht.

Ich weiß was du meinst. Die Uint's 0-9 sehen in Binärform anders aus als die Chars '0' - '9'.
Das sollte allerdings keine Rolle spielen, weil bei memcpy z.B. nie eine Umwandlung stattfindet.
Man müsste einfach nur die Speicheradresse des ersten bytes eines vector<bool> rausfinden. Sozusagen ein reinterpret cast des bool pointers nach char pointer (mir ist klar das, dass byte 8bit hat und bool in nem vector<bool> nur 1bit ist).
Bin mir nicht sicher ob das geht.

thefiloe schrieb:

Was willst du immer mit memcpy

Ganz einfach: Die memcpy Variante ist Faktor 50 schneller (bei ner char Matrix) als die "normalen" Varianten aus Post#6
Mit scanline oder setPixel dauert 3-4 Sekunden und mit memcpy nur ~0.07 Sekunden. (bei 20000*20000)

@RodFromGermany
Ja, ich habe keine Ahnung von Bildverarbeitung. Aber hier gehts weniger um Bildverarbeitung als um die Darstellung eines Bildes. Genauer gesagt die schnellst möglichste graphische Darstellung einer NxN 2D Matrix mit bool-Werten (vetctor/array).

Der vector<bool> hat übrigens ne Sonderstellung unter allen vector Klassen. Er verhält sich leicht anders. (Ich sehe grad, dass die 8bool/byte Speicherung nicht garantiert ist)

thefiloe schrieb:

Aber wenn du ja sogar schon Zeitwerte hast, ist meine Frage was nicht funktioniert?

Der Zeitwert bezieht sich auf ne Matrix aus char. Da verwende ich bereits memcpy. Jetzt wollte ich auf vector<bool> umsteigen, um den Speicherplatz optimieren, um noch größere Systeme zu simulieren.
Dazu hatte ich vor die 8bool/byte Speicherung zu nutzen, um den minimalen Speicherbedarf zu erreichen. (Keine Sorge die Laufzeit der Simulation wächst langsamer als N^2)

thefiloe schrieb:

Außerdem wollt grad sagen... bool 1 bit? Soviel ich weiß geht das nicht. Wenn du nen bool array hättest wäre ja z.b. eine Adresse(natürlich nicht wirklich) 0xFA+1/8?

cplusplus.com sagt (link oben):

The storage is not necessarily an array of bool values, but the library implementation may optimize storage so that each value is stored in a single bit.

Die komprimierte Speicherung ist also erlaubt aber nicht garantiert. Bool Arrays sind glaub ich immer 1bool/byte.

Wie das bei vector<bool> mit den Adressen abläuft weiß ich nicht.

Mich interessiert nicht nur das Ergebnis der Simulation, sondern auch die Zwischenschritte. Ich will dabei zuschauen wie sich das System entwickelt.
Deswegen wird in regelmäßigen Abständen die Matrix visualisiert.
Ich denke ich werde bei dem vector<char> bleiben. Der Zugriff auf ein Element eines bit vectors dauert bei der kompakten Speicherung auch länger.
Man tauscht Speicherplatz gegen CPU Zeit. Da ich verhältnismäßig viele Zugriffe habe lohnt sich die kompakte Speicherung nicht wirklich.