Arrays

Bei einem Array werden mehrere gleichartige Elemente nacheinander im Speicher abgelegt. Wenn man mit Arrays arbeiten möchte muss man also wissen:

Wo beginnt das Array?
Wie groß sind die einzelnen Elemente?
Wie viele Elemente sind im Array?

Erstes Beispiel mit einem Array

day04/vecsum.c

unsigned x[5] = {1, 2, 3, 4, 5};

unsigned *p;

unsigned sum = 0;

void

csum()

{

    for (p=x; p!=&(x[5]); ++p) {

        sum += *p;

    }

}

$shell> gcc-4.8 -S -fno-asynchronous-unwind-tables vecsum.c

Folgende Dinge muss man wissen, um den C-Code zu verstehen:

Aufgabe: Vollzieht nach, wie diese im Assembler Code umgesetzt wird.

day04/vecsum.s

                .globl _x

                .data

                .align 4

_x:

                .long           1

                .long           2

                .long           3

                .long           4

                .long           5

                .comm           _p,8,3

                .globl _sum

                .zerofill __DATA,__pu_bss2,_sum,4,2

                .text

                .globl _csum

_csum:

                pushq           %rbp

                movq            %rsp, %rbp

                movq            _p@GOTPCREL(%rip), %rax

                leaq            _x(%rip), %rdx

                movq            %rdx, (%rax)

                jmp             L2

L3:

                movq            _p@GOTPCREL(%rip), %rax

                movq            (%rax), %rax

                movl            (%rax), %edx

                movl            _sum(%rip), %eax

                addl            %edx, %eax

                movl            %eax, _sum(%rip)

                movq            _p@GOTPCREL(%rip), %rax

                movq            (%rax), %rax

                leaq            4(%rax), %rdx

                movq            _p@GOTPCREL(%rip), %rax

                movq            %rdx, (%rax)

L2:

                movq            _p@GOTPCREL(%rip), %rax

                movq            (%rax), %rdx

                leaq            20+_x(%rip), %rax

                cmpq            %rax, %rdx

                jne             L3

                popq            %rbp

                ret

                .subsections_via_symbols

Weiteres Beispiel mit einem Array

Wenn man Numerik betreibt, dann möchte man auf Arrays mittels Indices zugreifen:

day04/vecsum2.c

unsigned x[5] = {1, 2, 3, 4, 5};

unsigned sum = 0;

unsigned i;

void

csum()

{

    for (i=0; i<5; ++i) {

        sum += x[i];

    }

}

$shell> gcc-4.8 -S -fno-asynchronous-unwind-tables vecsum2.c

day04/vecsum2.s

                .globl _x

                .data

                .align 4

_x:

                .long           1

                .long           2

                .long           3

                .long           4

                .long           5

                .globl _sum

                .zerofill __DATA,__pu_bss2,_sum,4,2

                .comm           _i,4,2

                .text

                .globl _csum

_csum:

                pushq           %rbp

                movq            %rsp, %rbp

                movq            _i@GOTPCREL(%rip), %rax

                movl            $0, (%rax)

                jmp             L2

L3:

                movq            _i@GOTPCREL(%rip), %rax

                movl            (%rax), %eax

                movl            %eax, %eax

                leaq            0(,%rax,4), %rdx

                leaq            _x(%rip), %rax

                movl            (%rdx,%rax), %edx

                movl            _sum(%rip), %eax

                addl            %edx, %eax

                movl            %eax, _sum(%rip)

                movq            _i@GOTPCREL(%rip), %rax

                movl            (%rax), %eax

                leal            1(%rax), %edx

                movq            _i@GOTPCREL(%rip), %rax

                movl            %edx, (%rax)

L2:

                movq            _i@GOTPCREL(%rip), %rax

                movl            (%rax), %eax

                cmpl            $4, %eax

                jbe             L3

                popq            %rbp

                ret

                .subsections_via_symbols

Vergleich der Array Zugriffe

day04/vecsum3.c

unsigned x[5] = {1, 2, 3, 4, 5};

unsigned sum = 0;

unsigned *p;

unsigned i;

void

csum1()

{

    sum += x[0];

    sum += x[1];

    sum += x[2];

    sum += x[3];

    sum += x[4];

}

void

csum2()

{

    p = x;

    sum += *(p++);

    sum += *(p++);

    sum += *(p++);

    sum += *(p++);

    sum += *(p++);

}

Aufgabe:

Nachvollziehen was da gemacht wird.
Welche Art von Optimierung wurde hier von Hand durchgeführt? Mit welcher Option kann man versuchen den Compiler dazu zu zwingen dies für euch zu machen?
Was vermutet ihr ist effizienter? Hinweis:
- Schaut euch den erzeugten Assembler Code ohne Optimierung an,
- dann mit Optimierung
Welche Variante kommt ohne Optimierung der optimierten am nächsten?
Was ist schneller, wenn man mit Optimierung -O3 übersetzt?

$shell> gcc-4.8 -S -fno-asynchronous-unwind-tables vecsum3.c

day04/vecsum3.s

                .globl _x

                .data

                .align 4

_x:

                .long           1

                .long           2

                .long           3

                .long           4

                .long           5

                .globl _sum

                .zerofill __DATA,__pu_bss2,_sum,4,2

                .comm           _p,8,3

                .comm           _i,4,2

                .text

                .globl _csum1

_csum1:

                pushq           %rbp

                movq            %rsp, %rbp

                movl            _x(%rip), %edx

                movl            _sum(%rip), %eax

                addl            %edx, %eax

                movl            %eax, _sum(%rip)

                movl            4+_x(%rip), %edx

                movl            _sum(%rip), %eax

                addl            %edx, %eax

                movl            %eax, _sum(%rip)

                movl            8+_x(%rip), %edx

                movl            _sum(%rip), %eax

                addl            %edx, %eax

                movl            %eax, _sum(%rip)

                movl            12+_x(%rip), %edx

                movl            _sum(%rip), %eax

                addl            %edx, %eax

                movl            %eax, _sum(%rip)

                movl            16+_x(%rip), %edx

                movl            _sum(%rip), %eax

                addl            %edx, %eax

                movl            %eax, _sum(%rip)

                popq            %rbp

                ret

                .globl _csum2

_csum2:

                pushq           %rbp

                movq            %rsp, %rbp

                movq            _p@GOTPCREL(%rip), %rax

                leaq            _x(%rip), %rdx

                movq            %rdx, (%rax)

                movq            _p@GOTPCREL(%rip), %rax

                movq            (%rax), %rax

                leaq            4(%rax), %rcx

                movq            _p@GOTPCREL(%rip), %rdx

                movq            %rcx, (%rdx)

                movl            (%rax), %edx

                movl            _sum(%rip), %eax

                addl            %edx, %eax

                movl            %eax, _sum(%rip)

                movq            _p@GOTPCREL(%rip), %rax

                movq            (%rax), %rax

                leaq            4(%rax), %rcx

                movq            _p@GOTPCREL(%rip), %rdx

                movq            %rcx, (%rdx)

                movl            (%rax), %edx

                movl            _sum(%rip), %eax

                addl            %edx, %eax

                movl            %eax, _sum(%rip)

                movq            _p@GOTPCREL(%rip), %rax

                movq            (%rax), %rax

                leaq            4(%rax), %rcx

                movq            _p@GOTPCREL(%rip), %rdx

                movq            %rcx, (%rdx)

                movl            (%rax), %edx

                movl            _sum(%rip), %eax

                addl            %edx, %eax

                movl            %eax, _sum(%rip)

                movq            _p@GOTPCREL(%rip), %rax

                movq            (%rax), %rax

                leaq            4(%rax), %rcx

                movq            _p@GOTPCREL(%rip), %rdx

                movq            %rcx, (%rdx)

                movl            (%rax), %edx

                movl            _sum(%rip), %eax

                addl            %edx, %eax

                movl            %eax, _sum(%rip)

                movq            _p@GOTPCREL(%rip), %rax

                movq            (%rax), %rax

                leaq            4(%rax), %rcx

                movq            _p@GOTPCREL(%rip), %rdx

                movq            %rcx, (%rdx)

                movl            (%rax), %edx

                movl            _sum(%rip), %eax

                addl            %edx, %eax

                movl            %eax, _sum(%rip)

                popq            %rbp

                ret

                .subsections_via_symbols