Holomino
20.11.2018, 12:28
Ähh,
mir gings eigentlich nicht um die Optimierung.
Mir gings um die Begründung, warum ein kleines Stück Algorithmus, dessen Hauptanteil sich aus einfacher Registerlogik (Subtraktion, Addition, Inkrementierung, Dekrementierung) im 32-Bit-Bereich zusammensetzt, auf dem einen System nominal 5x langsamer abläuft.
In der while-Schleife in Bresenham steht doch nun wirklich nix, was sich nicht 1:1 in Assembler umsetzen lässt.
Kurz: Halte doch mal die beiden ASM-Listings unten nebeneinander und erklär mir, warum der eine Code auf'm Notebook bei 1,8Ghz in 0,2s durchläuft und der andere Code auf'm ARM mit knapp 1GHz 2,5 s braucht.
So schlecht kann ein Befehlssatz doch nicht implementiert sein, da steckt doch bestimmt noch irgendwas mit Wartezyklen oder Speichercaches dahinter.
Ich verstehe es (noch) nicht so ganz. Da hänge ich mental gerade etwas fest.
g++ -S Bresenham.c auf'm Notebook
.file "Bresenham.c"
.text
.globl _Z9Bresenham8IPoint_tS_PFviiE
.def _Z9Bresenham8IPoint_tS_PFviiE; .scl 2; .type 32; .endef
.seh_proc _Z9Bresenham8IPoint_tS_PFviiE
_Z9Bresenham8IPoint_tS_PFviiE:
.LFB4:
pushq %rbp
.seh_pushreg %rbp
movq %rsp, %rbp
.seh_setframe %rbp, 0
subq $80, %rsp
.seh_stackalloc 80
.seh_endprologue
movq %rcx, 16(%rbp)
movq %rdx, 24(%rbp)
movq %r8, 32(%rbp)
movl 16(%rbp), %eax
movl %eax, -4(%rbp)
movl 20(%rbp), %eax
movl %eax, -8(%rbp)
movl 24(%rbp), %eax
movl %eax, -16(%rbp)
movl 28(%rbp), %eax
movl %eax, -20(%rbp)
movl -16(%rbp), %eax
subl -4(%rbp), %eax
movl %eax, %edx
movl %edx, %eax
sarl $31, %eax
xorl %eax, %edx
movl %edx, -24(%rbp)
subl %eax, -24(%rbp)
movl -4(%rbp), %eax
cmpl -16(%rbp), %eax
jge .L2
movl $1, %eax
jmp .L3
.L2:
movl $-1, %eax
.L3:
movl %eax, -28(%rbp)
movl -20(%rbp), %eax
subl -8(%rbp), %eax
movl %eax, %edx
movl %edx, %eax
sarl $31, %eax
xorl %eax, %edx
movl %edx, -32(%rbp)
subl %eax, -32(%rbp)
movl -8(%rbp), %eax
cmpl -20(%rbp), %eax
jge .L4
movl $1, %eax
jmp .L5
.L4:
movl $-1, %eax
.L5:
movl %eax, -36(%rbp)
movl -24(%rbp), %eax
cmpl -32(%rbp), %eax
jg .L6
movl -32(%rbp), %eax
negl %eax
movl %eax, %edx
shrl $31, %edx
addl %edx, %eax
sarl %eax
jmp .L7
.L6:
movl -24(%rbp), %eax
movl %eax, %edx
shrl $31, %edx
addl %edx, %eax
sarl %eax
.L7:
movl %eax, -12(%rbp)
.L12:
movl -8(%rbp), %edx
movl -4(%rbp), %ecx
movq 32(%rbp), %rax
call *%rax
movl -4(%rbp), %eax
cmpl -16(%rbp), %eax
jne .L8
movl -8(%rbp), %eax
cmpl -20(%rbp), %eax
je .L14
.L8:
movl -12(%rbp), %eax
movl %eax, -40(%rbp)
movl -24(%rbp), %eax
negl %eax
cmpl -40(%rbp), %eax
jge .L10
movl -32(%rbp), %eax
subl %eax, -12(%rbp)
movl -28(%rbp), %eax
addl %eax, -4(%rbp)
.L10:
movl -40(%rbp), %eax
cmpl -32(%rbp), %eax
jge .L12
movl -24(%rbp), %eax
addl %eax, -12(%rbp)
movl -36(%rbp), %eax
addl %eax, -8(%rbp)
jmp .L12
.L14:
nop
nop
addq $80, %rsp
popq %rbp
ret
.seh_endproc
.ident "GCC: (tdm64-1) 5.1.0"
gcc -S Bresenham.c auf BPI
.arch armv6
.eabi_attribute 27, 3
.eabi_attribute 28, 1
.fpu vfp
.eabi_attribute 20, 1
.eabi_attribute 21, 1
.eabi_attribute 23, 3
.eabi_attribute 24, 1
.eabi_attribute 25, 1
.eabi_attribute 26, 2
.eabi_attribute 30, 6
.eabi_attribute 34, 1
.eabi_attribute 18, 4
.file "Bresenham.c"
.text
.align 2
.global Bresenham
.type Bresenham, %function
Bresenham:
@ args = 4, pretend = 0, frame = 56
@ frame_needed = 1, uses_anonymous_args = 0
stmfd sp!, {fp, lr}
add fp, sp, #4
sub sp, sp, #56
sub ip, fp, #52
stmia ip, {r0, r1}
sub r1, fp, #60
stmia r1, {r2, r3}
ldr r3, [fp, #-52]
str r3, [fp, #-8]
ldr r3, [fp, #-48]
str r3, [fp, #-12]
ldr r3, [fp, #-60]
str r3, [fp, #-20]
ldr r3, [fp, #-56]
str r3, [fp, #-24]
ldr r2, [fp, #-20]
ldr r3, [fp, #-8]
rsb r3, r3, r2
cmp r3, #0
rsblt r3, r3, #0
str r3, [fp, #-28]
ldr r2, [fp, #-8]
ldr r3, [fp, #-20]
cmp r2, r3
bge .L2
mov r3, #1
b .L3
.L2:
mvn r3, #0
.L3:
str r3, [fp, #-32]
ldr r2, [fp, #-24]
ldr r3, [fp, #-12]
rsb r3, r3, r2
cmp r3, #0
rsblt r3, r3, #0
str r3, [fp, #-36]
ldr r2, [fp, #-12]
ldr r3, [fp, #-24]
cmp r2, r3
bge .L4
mov r3, #1
b .L5
.L4:
mvn r3, #0
.L5:
str r3, [fp, #-40]
ldr r2, [fp, #-28]
ldr r3, [fp, #-36]
cmp r2, r3
bgt .L6
ldr r3, [fp, #-36]
rsb r3, r3, #0
mov r2, r3, lsr #31
add r3, r2, r3
mov r3, r3, asr #1
b .L7
.L6:
ldr r3, [fp, #-28]
mov r2, r3, lsr #31
add r3, r2, r3
mov r3, r3, asr #1
.L7:
str r3, [fp, #-16]
.L12:
ldr r3, [fp, #4]
ldr r0, [fp, #-8]
ldr r1, [fp, #-12]
blx r3
ldr r2, [fp, #-8]
ldr r3, [fp, #-20]
cmp r2, r3
bne .L8
ldr r2, [fp, #-12]
ldr r3, [fp, #-24]
cmp r2, r3
bne .L8
b .L13
.L8:
ldr r3, [fp, #-16]
str r3, [fp, #-44]
ldr r3, [fp, #-28]
rsb r2, r3, #0
ldr r3, [fp, #-44]
cmp r2, r3
bge .L10
ldr r2, [fp, #-16]
ldr r3, [fp, #-36]
rsb r3, r3, r2
str r3, [fp, #-16]
ldr r2, [fp, #-8]
ldr r3, [fp, #-32]
add r3, r2, r3
str r3, [fp, #-8]
.L10:
ldr r2, [fp, #-44]
ldr r3, [fp, #-36]
cmp r2, r3
bge .L11
ldr r2, [fp, #-16]
ldr r3, [fp, #-28]
add r3, r2, r3
str r3, [fp, #-16]
ldr r2, [fp, #-12]
ldr r3, [fp, #-40]
add r3, r2, r3
str r3, [fp, #-12]
.L11:
b .L12
.L13:
sub sp, fp, #4
@ sp needed
ldmfd sp!, {fp, pc}
.size Bresenham, .-Bresenham
.ident "GCC: (Raspbian 4.9.2-10+deb8u1) 4.9.2"
.section .note.GNU-stack,"",%progbits
BTW: Du kannst mal zum Spielen im BresenhamTest die sum aus dem Callback mit als Ergebnis ausgeben lassen. Daran sieht man zumindest, dass der Algorithmus was tut und nicht wegoptimiert wird.
Powered by vBulletin® Version 4.2.5 Copyright ©2024 Adduco Digital e.K. und vBulletin Solutions, Inc. Alle Rechte vorbehalten.