effiziente Initialisirung mit Nullen

[Maxim (maxim)]

Grundlegende Frage: Wenn ich ein Array anlege, das aus later Nullen 
bestehen soll, muss die CPU nach der Speicherzuweisung jedes einzelne 
Arrayelement abfahren und auf Null setzen? Oder gibt es für diesen 
Spezialfall eine Abkürzung? Oder hängt das einfach nur von der Hardware 
ab und wird vom Compiler geregelt?

PS: Mir geht es eigentlich um GPUs, aber ich würde gerne wissen, wie es 
allgemein aussieht.

[Joachim D. (Firma: JDCC) (scheppertreiber)]

Hängt vom Rechenknecht ab. x86 kann das (glaube ich).

[Rufus Τ. F. (rufus)]

Maxim S. schrieb:
> Wenn ich ein Array anlege, das aus later Nullen
> bestehen soll, muss die CPU nach der Speicherzuweisung jedes einzelne
> Arrayelement abfahren und auf Null setzen?

Ja. Wobei "Arrayelement" hier nichts mit den von Deinem Programm 
genutzten Elementen zu tun hat, sondern einzelne Bytes bzw. bei 
Prozessoren mit größerer Datenbusbreite die korrespondierende Datengröße 
beschreibt.

Ein 32-Bit-Prozessor wird also ein Array mit 32-Bit-Zugriffen 
beschreiben, auch wenn das Array im Programm aus einzelnen Bytes 
besteht.

[Peter II (Gast)]

Joachim Drechsel schrieb:
> Hängt vom Rechenknecht ab. x86 kann das (glaube ich).

da eine CPU nicht mal arrays kennt, denke ich nicht das es dafür befehle 
gibt. Es wird maximal eine möglichkeit haben einen Speicherbereich mit 0 
zu überschreiben, aber auch das muss vom Programieren umgesetzt werden.

[Joachim D. (Firma: JDCC) (scheppertreiber)]

Peter II schrieb:
> da eine CPU nicht mal arrays kennt, denke ich nicht das es dafür befehle
> gibt. Es wird maximal eine möglichkeit haben einen Speicherbereich mit 0
> zu überschreiben, aber auch das muss vom Programieren umgesetzt werden.

Die x86er haben so etwas wie "Stringbefehle". Ob da ein
hardcodiertes memset dabei ist weiß ich jetzt gerade nicht.

[Peter II (Gast)]

Joachim Drechsel schrieb:
> Die x86er haben so etwas wie "Stringbefehle". Ob da ein
> hardcodiertes memset dabei ist weiß ich jetzt gerade nicht.

ja aber diesen Befehl muss man expliziert für einen Speicherbereich 
ausführen. die CPU kennt keine Variablen. Sie kann also auch nicht 
wissen wann eine Array angelegt wird.

[avion23 (Gast)]

Such nach
memset efficiency
mit google. Ja, es geht "effizienter". Die CPU muss nicht wissen, ob das 
ein Array o.ae. ist. Der Compiler ist an dieser Steller gefragt.

[Peter II (Gast)]

avion23 schrieb:
> Der Compiler ist an dieser Steller gefragt.

ich würde denke hier ist mehr der Entwickler der glibc gefragt. Er muss 
dann memset anders implemtieren. Die Stringbefehle der CPU werden kaum 
von einem compiler umgesetzt.

[Jörg W. (dl8dtl) (Moderator)]

Peter II schrieb:
> Die Stringbefehle der CPU werden kaum
> von einem compiler umgesetzt.

Warum nicht?  Hängt vom Compiler und Target ab.  AVR-GCC beispiels-
weise expandiert memset() inline:

        ldi r24,lo8(256)
        ldi r25,hi8(256)
        ldi r30,lo8(array)
        ldi r31,hi8(array)
        mov r26,r30
        mov r27,r31
        mov r18,r24
        mov r19,r25
        st X+,__zero_reg__
        subi r18,1
        sbci r19,0
        brne .-8

GCC 4.6 auf FreeBSD/i386 ebenfalls:

        movl    $array, %edx
        movl    $64, %ecx
        movl    $0, %eax
        movl    %edx, %edi
        rep stosl

GCC 4.1 auf Linux/x86_64 dagegen nicht:

        movl    $256, %edx
        xorl    %esi, %esi
        movl    $array, %edi
        jmp     memset

[Peter II (Gast)]

Jörg Wunsch schrieb:
> AVR-GCC beispiels-
> weise expandiert memset() inline:

optimiert er den code oder "kennt" er memset und setzt es anders um? Ich 
hätte jetzt gedacht das es in der libc einfach als asm umgesetzt ist.

[Jörg W. (dl8dtl) (Moderator)]

Peter II schrieb:
> optimiert er den code oder "kennt" er memset und setzt es anders um?

Was soll das "oder"?

Er kennt memset() und setzt es auf seine Weise optimal um.  Das ist
ihm in einem `hosted environment' durch den Standard gestattet.

[Peter II (Gast)]

Jörg Wunsch schrieb:
> Was soll das "oder"?

es könnte ja sein das er die funktion erkennt das ein speicherberich 
genullt werden soll und dieses mit hilfe der STringfunktionen umsetzt.

for( ... ) {
  x[y] = 0;
}


oder er weiss was memset macht und ersetzt es durch eine eigene 
implementierung. Was aber nicht mehr geht wenn ich mir die memset 
funtion umbenenne.

[Jörg W. (dl8dtl) (Moderator)]

Peter II schrieb:

> es könnte ja sein das er die funktion erkennt das ein speicherberich
> genullt werden soll und dieses mit hilfe der STringfunktionen umsetzt.
>
> for( ... ) {
>   x[y] = 0;
> }

Auch das könnte er erkennen, aber in meinem Falle war es ein
memset().

(Gerade probiert, eine explizite Schleife optimiert er auch mit
GCC 4.6 nicht, nur memset()).

[Rolf M. (rmagnus)]

Peter II schrieb:
> avion23 schrieb:
>> Der Compiler ist an dieser Steller gefragt.
>
> ich würde denke hier ist mehr der Entwickler der glibc gefragt. Er muss
> dann memset anders implemtieren.

memset ist im Falle von gcc im Compiler implementiert, wie ein Großteil 
der Standard-Blibliothek. Siehe 
http://gcc.gnu.org/onlinedocs/gcc-4.7.1/gcc/Other-Builtins.html#Other-Builtins

> Die Stringbefehle der CPU werden kaum von einem compiler umgesetzt.

Warum sollten sie nicht? Bei mir tut er genau das, wenn ich einen 
memset-Aufruf mache. Allerdings hängt das davon ab, für welchen 
Prozessor man optimiert und wie groß der zu kopierende Block ist. Wenn 
ich z.B. die SIMD-Instruktionen freischalte (-march=core2), nutzt er 
die, aber nicht bei allen Blockgrößen. Und wenn die Blockgröße keine 
Konstante ist, sieht's dann nochmal ganz anders aus.

Jörg Wunsch schrieb:
> (Gerade probiert, eine explizite Schleife optimiert er auch mit
> GCC 4.6 nicht, nur memset()).

Sie sehen bei mir unterschiedlich aus, aber optimieren tut er die 
Schleife auch. Er erkent zumindest, daß er nicht jedes Byte einzeln 
schreiben muß, sondern das auch in 32-Bit-Blöcken tun kann.

[Peter II (Gast)]

Rolf Magnus schrieb:
>> Die Stringbefehle der CPU werden kaum von einem compiler umgesetzt.
> Warum sollten sie nicht?

ich hatte mal gelesen das sie zu "kompliziert" für dien Compiler sind. 
Sie sollen auch nicht wirklich geschwindigkeitsvorteile bringen. Die 
Befehle waren zu einer Zeit eingaut wurden wo man noch von Hand 
optimiert hat.

Und wenn gcc hier diese befehle bei memeset verwendet, dann vermute ich 
ganz stark das jemand dieses expliziert von hand codiert hat. Der 
normale Optimizer wird also nicht auf die Idee kommen diese befehle zu 
verwenden. Sonst hätte er es auch bei einer schleife gemacht.

[Jörg W. (dl8dtl) (Moderator)]

Peter II schrieb:
> Und wenn gcc hier diese befehle bei memeset verwendet, dann vermute ich
> ganz stark das jemand dieses expliziert von hand codiert hat.

Alles im GCC hat jemand explizit von Hand codiert. ;-)  Oder was
dachtest du, wie der Compiler seinen Code generiert?

> Der
> normale Optimizer wird also nicht auf die Idee kommen diese befehle zu
> verwenden.

Deine Vorstellungen über die Art und Weise, wie ein Compiler optimiert,
dürften aus dem letzten Viertel des vorherigen Jahrhunderts stammen.

Heutzutage gibt's einfach nicht mehr "den Optimizer", erst recht nicht
einen "normalen". ;-)

[Peter II (Gast)]

Jörg Wunsch schrieb:

> Oder was
> dachtest du, wie der Compiler seinen Code generiert?
es ist doch wohl ein unterschied ob man eine complete funktion in ASM 
codiert wird (von hand) oder ob der optimierer anhand des C codes 
erkennen soll was gemeint ist und damit selber auf die Idee kommt die 
string befehle zu verwenden.

>> Der
>> normale Optimizer wird also nicht auf die Idee kommen diese befehle zu
>> verwenden.
> Deine Vorstellungen über die Art und Weise, wie ein Compiler optimiert,
> dürften aus dem letzten Viertel des vorherigen Jahrhunderts stammen.

du könntest mich davon überzeugen das es nicht stimmt, in dem du mir mal 
code zeigst wo der compiler die string-upcodes verwendet.

[Jörg W. (dl8dtl) (Moderator)]

Peter II schrieb:
> du könntest mich davon überzeugen das es nicht stimmt, in dem du mir mal
> code zeigst wo der compiler die string-upcodes verwendet.

Dazu müsstest du dir schon mal den Compiler-Sourcecode selbst
auspacken und in der Datei i386.md nach beispielsweise stosq
suchen.

[Peter II (Gast)]

Jörg Wunsch schrieb:
> Peter II schrieb:
>> du könntest mich davon überzeugen das es nicht stimmt, in dem du mir mal
>> code zeigst wo der compiler die string-upcodes verwendet.
>
> Dazu müsstest du dir schon mal den Compiler-Sourcecode selbst
> auspacken und in der Datei i386.md nach beispielsweise stosq
> suchen.

ich meinte zwar eine beispiel C datei wo mit hilfe des compilers am ende 
ein stosq verwendet wird.
Das der compiler grunsätzlich den upcode kennt, ist ja noch kein hinweis 
darauf das er ihn auch in der praxis irgenwie verwendet. Außer man 
schreibt gleich ASM code.

Werde mir aber mal die quellen saugen.

[Klaus (Gast)]

Peter II schrieb:
> upcode

Mach dich erstmal schlau, wie man Opcode überhaupt schreibt. Mist, 
jetzt hab ich es verraten...

[Jörg W. (dl8dtl) (Moderator)]

Peter II schrieb:
> ich meinte zwar eine beispiel C datei wo mit hilfe des compilers am ende
> ein stosq verwendet wird.

$ cat foo.c
char array[256];

#include <string.h>

void
init_array(void)
{
  int i;
  for (i = 0; i < 256; i++)
    array[i] = 0;
}
$ /junk/testroot/bin/gcc -O3 -S foo.c
$ cat foo.s
        .file   "foo.c"
        .text
        .p2align 4,,15
        .globl  init_array
        .type   init_array, @function
init_array:
.LFB0:
        .cfi_startproc
        movl    $array, %edx
        movl    $64, %ecx
        pushl   %edi
        .cfi_def_cfa_offset 8
        .cfi_offset 7, -8
        xorl    %eax, %eax
        movl    %edx, %edi
        rep stosl
        popl    %edi
        .cfi_restore 7
        .cfi_def_cfa_offset 4
        ret
        .cfi_endproc
.LFE0:
        .size   init_array, .-init_array
        .comm   array,256,32
        .ident  "GCC: (GNU) 4.8.0 20120530 (experimental)"
        .section        .note.GNU-stack,"",@progbits

Es wird stosl (und nicht stosq) benutzt, weil der Compiler im
32-bit-Modus arbeitet.

> Das der compiler grunsätzlich den upcode kennt, ist ja noch kein hinweis
> darauf das er ihn auch in der praxis irgenwie verwendet. Außer man
> schreibt gleich ASM code.

Dafür müsste der Compiler den Opcode nicht kennen, denn inline asm
reicht er ja nur an den Assembler durch.

[Peter II (Gast)]

@Jörg Wunsch

danke für die Mühe. Ist das etwas neu in

GCC: (GNU) 4.8.0 20120530 (experimental)

?. Weil mit GCC 4.6 scheint es ja nicht zu passieren

> Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
> Datum: 05.07.2012 15:32
>
> (Gerade probiert, eine explizite Schleife optimiert er auch mit
> GCC 4.6 nicht, nur memset()).

oder liegt das am experimental?

[Peter II (Gast)]

es scheint zumindest noch nicht lange so zu sein. Mein 4.6 macht es 
nicht-

        .file   "test.c"
        .text
        .p2align 4,,15
        .globl  init_array
        .type   init_array, @function
init_array:
.LFB12:
        .cfi_startproc
        movl    $array, %eax
        .p2align 4,,7
        .p2align 3
.L2:
        movl    $0, (%eax)
        addl    $4, %eax
        cmpl    $array+256, %eax
        jne     .L2
        rep
        ret
        .cfi_endproc
.LFE12:
        .size   init_array, .-init_array
        .comm   array,256,32
        .ident  "GCC: (Debian 4.6.3-1) 4.6.3"
        .section        .note.GNU-stack,"",@progbits

[Jörg W. (dl8dtl) (Moderator)]

Peter II schrieb:
> Mein 4.6 macht es
> nicht-

Aber du siehst, dass er auch jeweils 4 Bytes zu einem Schreibzugriff
zusammenfasst.

Ab welcher Version das konkret drin ist, kann ich dir auch nicht
sagen.  Sollte ja vor allem als Beispiel dienen, dass die Optimierung
moderner Compiler tatsächlich so feingliedrig ist, dass sie da
unwahrscheinlich viel aufdröseln kann.  Letztlich muss ihr das
natürlich ein Mensch beigebracht haben, welche Muster im Maschinencode
durch welche Befehle optimal abarbeitbar sind.

[Peter II (Gast)]

Jörg Wunsch schrieb:
> Aber du siehst, dass er auch jeweils 4 Bytes zu einem Schreibzugriff
> zusammenfasst.

ja das ist auch gut so. Mir ging es aber extra um die String Opcodes. Da 
hatte ich mal gelesen das sie vom compiler nicht genutzt werden. Dies 
schein bis jetzt auch so zu sein.

.ident  "GCC: (Debian 4.7.1-2) 4.7.1"

macht es auch nicht. Etweder ist das ganze experimental oder es ist nach 
20Jahren wirklich mal einer auf die Idee gekommen es umzusetzen.

[Peter II (Gast)]

MS macht es sich einfach:

_init_array PROC
; File c:\test.c
; Line 10
  push  256          ; 00000100H
  push  0
  push  OFFSET _array
  call  _memset
  add  esp, 12          ; 0000000cH
; Line 11
  ret  0
_init_array ENDP
_TEXT  ENDS
END

[Jörg W. (dl8dtl) (Moderator)]

Peter II schrieb:
> oder es ist nach
> 20Jahren wirklich mal einer auf die Idee gekommen es umzusetzen

Es hilft nichts, nur auf die Idee zu kommen. ;-)  Es muss auch die
Infrastruktur (im Compiler) da sein, die entsprechenden Codemuster
zu isolieren, auf die man das dann anwenden kann.

[X86 (Gast)]

Wenn bei Intel genau nachliest, dann findet man, daß es verschiede Arten 
von Opcodes gibt. Manche laufen optimal durch die Pipelines, andere, wie 
z.B. die Repeated Stringbefehle, passen nicht auf jeder CPU dazu und 
laufen dann effektiv langsamer als äquivalente Sequenzen "flinker" 
Befehle. Durchsatz und Latenz sind die Stichworte.