8Bit Array möglichst schnell mit konstante füllen füllen

Nick H.

Ich hab einen 8Bit-Array, besser bekannt als char-Array
jedes der 786432 Felder will ich möglichst schnell mit dem gleichen Wert füllen
es ist wirklich wichtig dass das so schnell wie möglich geht
die schnellste möglichkeit denke ich ist ihn mit 32-Bit Werten zu füllen
(isn 32-Bit Prozessor)

wenn ich das ganze so mach:

char array[786432];
for(int i = 0; i < 786432; i++)
{
 array[i] = konstante;
}

würde das a 4x so lange dauern da ich in einem Schritt nur 8Bit kopiere

memcpy wär da schon ne alternative, aber da bräucht ich ja erstmal einen Array der schon voll ist, von dem ich das ganze kopieren kann
und das füllen von dem Array würde dann wieder genauso lange daueren
das hätte nur den Vorteil das ich den nur einmal füllen müsste und dann immer wieder kopieren kann

aber das hört sich für mich trotzdem sinnlos an
man muss ja irgendwie nen bestimmten Bereich mit longs überschreiben können
ich denk mal das geht irgendwie mit Zeigern
ich bräucht ja nur nen long Zeiger auf die Anfangsadresse von dem char-Array
und dann könnt ich den mit longs überschreiben

aber wie genau funktioniert das?
hab noch nich wirklich Ahnung von Zeigern

Neku

memset (array, konstante, 786432);

'konstante' darf dabei nur 1 Byte haben (also idR char)

oder auf'n int* casten...

char *array
int *zeiger=(int*)array

zeiger[i]=wert von der konstante viermal hintereinander (bitweise quasi)

Neku

memset ist glaube ich schneller als eine Zuweisung durch ints in einer Schleife, bin aber nicht sicher.

Worum geht es eigentlich? Wenn du die Initialisierung mehrmals machen musst, dann füll ein Array mit der Konstanten und benutz für weitere Arrays memcpy, das wäre dann wesentlich schneller.

c.rackwitz

char array[786432]; // muss vielfaches von 4 sein (sizeof unsigned int), sonst wird ueber die grenzen geschrieben (kann man aber behandeln)
unsigned int konstante = 0;
for(int i = 0; i < 786432; i += 4)
{
  *(unsigned int*)(array+i) = konstante;
}

Nick H.

jetzt ist halt die Frage was schneller geht
einmal eine Array mit der Konstante füllen
und dann immer wieder mit memcpy kopieren,
oder immer wieder mit memset das ganze auf den gleichen Wert setzen
(das ganze über Integer zu machen würde wahrscheinlich ungefähr das gleiche wie memset bringen)

ich schätz mal memset geht am schnellsten

Nick H.

moment, memset is ja sinnlos
das würde ja wieder pro Kopiervorgang nur 8 Bit kopieren
außer die Funktion ist schon optimiert
aber rackwitz Idee scheint gut zu sein
das probier ich mal aus

Nick H.

@rackwitz
die Idee war super mein Program fliegt nur so, danke!

jetzt gibts nur noch ein anderes Problem
in Assembler wär das einfach

wenn die Konstante nun zB 192 ist, also binär 11000000
woher weiß ich welcher 32 Bit Integer Wert das dann ist
der müsste dann ja 11000000110000001100000011000000
das könnte man zwar nun einfach mit nem Taschenrechner umrechnen
die Konstante bleibt zwar die komplette Programmausführung gleich
kann sich aber bei der nächsten durchaus ändern

also wie mach ich im klar das er die Konstante erst 4 mal aneinander Reihen muss?
nen char Array mit der Konstante initalisieren und dann auf int casten?
oder gehts auh einfacher, bzw. schneller?

Nick H.

okay klappt nun auch hab einfach nen 4-char-Array auf int gecastet
natürlich bin ich für schnellere Möglichkeiten immernoh zu haben

Sorry das ich hier mit mir selbst red, aber das hat mich selber überrascht das ich das mit dem casten selbst hinbekommen hab

jetzt wird mir auch klar warum mein Programm so langsam ist
ich verschwend die ganze Geschwindigkeit mit sinnlos langsamen Kopiervorgängen

mal was anderes.. wenn man schreibt:
int i=4;
wird das doch zur compilezeit schon initialisiert, wie auch bei
int i[]={4,4,4,4}
oder lieg ich da falsch? musst du dir halt n precompiler schreiben, der das entsprechend oft kodiert

Klar ginge das, aber ein Array mit fast 800000 Elementen dürfte etwas zu groß für den Stack sein

er legt es doch statisch an. obs vorinitialisiert wird oder nich macht doch keinen unterschied

Nick H.

aber die Zahl wird auch erst kurz nach Programmstat bekannt
das sieht dann ungefähr so aus:

int i[4]={x,x,x,x};

und das wird bestimmt nicht zur compilerzeit initalisiert

Nick H.

komisch, ich hab jetzt

memset(array, 192, 786432);

ausprobiert und das ist noch schneller als mit den Referenzen
das passt jetzt irgendwie nicht in mein Weltbild

kann man sich den Code von den C-Libs vielleicht irgendwo runterladen?

Neku

Ich habe da mal ein wenig geforscht...

Wie gesagt, memset dürfte um einiges schneller sein.
Ich habe gelesen, dass das die Assembler-Befehle zum Initialisieren und Kopieren von Speicher mit Assembler ein Takt pro Durchlauf (also Ideal 4 Byte pro Takt, 8 Byte mit SIMD) benötigen, was bei 2GHz theoretisch bis zu 8GB/s wären.
Quelle: http://www.activevb.de/tutorials/tut_asm/asm2.html (nach STOSx suchen)

Ich habe mir mal die memset.asm von Visual C++ 2005 angesehen und war überrascht wie lang die ist. Dort wird ebenfalls in 2- bzw. 4-Byte-Blöcken initialisiert falls möglich. Des weiteren wird SSE2 verwendet, falls vorhanden. Alles in allem also gut optimiert.

Nick H.

aber warum ist die Referenz Methode dann langsamer?
die benutzt ja genauso 4 Byte Blöcke

Neku

Verstehe nicht ganz was du mit Referenzen meinst - was haben die mit deinem Problem zu tun?

Nick H.

ich hab das ganze jetzt doch mit Referenzen gelöst (bzw. rackwitz)
und ich frag mich wie das langsamer sein kann als memset
aber da werden die wahrscheinlich irgendwas dran gedreht haben...

Neku

Aber wie hast du das mit Referenzen gelöst?
Oder meinst du das Füllen per Schleife?

Miq

Argh... b*llsh*t! Ich sollte vorher nachdenken...

Nick H.

so hab ich das ganze jetzt gemacht:

char array[786432]; // muss vielfaches von 4 sein (sizeof unsigned int), sonst wird ueber die grenzen geschrieben (kann man aber behandeln)
unsigned int konstante = 0;
for(int i = 0; i < 786432; i += 4)
{
  *(unsigned int*)(array+i) = konstante;
}

das war rackwitz Idee

oh, stimmt das hat gar nichts mit Referenzen zu tun
mein Fehler...