BASIC und C sowie Assembler-Geschwindigkeitsvergleich und -optimierung spielen mit IchigoJam

Einführung

Ich habe die Geschwindigkeit von Programmen, die mit BASIC, C und Assembler erstellt wurden, mit IchigoJam verglichen und versucht, sie für das Spielen zu optimieren. Das Programm ist ein BASIC-Programm, das Mandelbrot-Set mit IchigoJam Creative Commons License anzeigt. Wiki /% E3% 82% AF% E3% 83% AA% E3% 82% A8% E3% 82% A4% E3% 83% 86% E3% 82% A3% E3% 83% 96% E3% 83% BB % E3% 82% B3% E3% 83% A2% E3% 83% B3% E3% 82% BA% E3% 83% BB% E3% 83% A9% E3% 82% A4% E3% 82% BB% E3 Es gibt eine Person, die unter% 83% B3% E3% 82% B9 veröffentlicht ist, und ich verwende dies, weil es für diesen Vergleich praktisch war. Das Verarbeitungssystem jeder verwendeten Sprache ist

Ich benutze das oben genannte. BASIC Geben Sie Original Source in IchigoJam ein, löschen Sie die 20. Zeile, fügen Sie die folgende Zeile hinzu und führen Sie sie aus.

python

5 CLS:CLT
50 LC0,23:?TICK()

Misst die Zeit vom Löschen des Bildschirms bis zur Anzeige des Mandelbrot-Sets. Die Zeit wird mit der Funktion TICK () von IchigoJam BASIC gemessen und die Einheit beträgt ungefähr 1/60 Sekunde. Das Ausführungsergebnis ist wie folgt. Das Ergebnis ist 31008, aber da die Einheit ungefähr 1/60 Sekunden beträgt, ist 31008 * 1/60 = 516,8, wenn Sie dies in Zeit umrechnen, was bedeutet, dass es ungefähr 8 Minuten und 37 Sekunden gedauert hat. Der Autor dieses Programms ist in Artikel geschrieben, dass "es ungefähr 15 Minuten dauert, um alles zu zeichnen", aber zu der Zeit, als dieser Artikel geschrieben wurde Es scheint, dass die Ausführungsgeschwindigkeit von IchigoJam BASIC durch das Versions-Upgrade erheblich verbessert wurde. C

Versuchen Sie es mit gcc

Das Folgende ist ein Port des obigen BASIC-Programms nach C, mit Ausnahme der Größe der Variablen.

mandelbrot.c

#include <stdint.h>

int mandelbrot(int16_t arg, uint8_t* ram, const uint8_t* font)
{
    (void)arg; (void)font;
    int n = 32;
    int w = 64, h = 48;
    int a = 2 << 6, b = a * a, c = (3 << 12) / w;
    for (int y = 0; y < h; y++) {
        int v = (y - h / 2) * c;
        for (int x = 0; x < w; x++) {
            int u = (x - (w * 3) / 4) * c;
            uint8_t* z = &ram[0x900 + (x / 2) + (y / 2) * 32];
            int j = 1 << ((y % 2) * 2 + (x % 2));
            int k = j | 0x80 | *z;
            *z = k;
            int p = u, q = v, i = 0;
            do {
                int r = p / 64; p = r * r; if (p < 0) goto l40;
                int s = q / 64; q = s * s; if (q < 0) goto l40;
                if (p + q < 0 || p + q > b) goto l40;
                p = p - q + u;
                q = 2 * r * s + v;
            } while (++i < n);
            *z = k ^ j;
          l40:;
        }
    }
    return 0;
}

Kompilieren Sie dies mit dem folgenden Makefile- und Perl-Skript in Maschinensprache, konvertieren Sie es in das BASIC-Kommentarformular und erstellen Sie mandelbrot.apo. Die Optimierungsoption des Compilers gibt "-Ofast" an, da die Geschwindigkeit betont wird.

Makefile

target: mandelbrot.apo

mandelbrot.s: mandelbrot.c
	arm-none-eabi-gcc -Wall -W -mcpu=cortex-m0 -mthumb -fpic -Ofast -S $<

mandelbrot.o: mandelbrot.s
	arm-none-eabi-as $< -o$@ -a=$(<:.s=.prn)

mandelbrot.x: mandelbrot.o
	arm-none-eabi-ld --entry 0x700 -Ttext 0x700 $< -o $@ -Map $(@:.x=.map)

mandelbrot.mot: mandelbrot.x
	arm-none-eabi-objcopy -O srec $< $@

mandelbrot.apo: mandelbrot.mot
	perl hex2apo.pl $< > $@

hex2apo.pl

#!/usr/bin/perl
$start = 0xffffffff;
$end = 0x00000000;
while(<>) {
    $S = substr($_, 0, 1);
    $type = substr($_, 1, 1);
    die if ($S != "S" || !($type >= 0 && $type <= 9));
    $size = hex(substr($_, 1 + 1, 2));
    for ($sum = 0, $i = 0; $i <= $size; $i++) {
        $sum += hex(substr($_, 1 + 1 + 2 * $i, 2));
    }
    die if (($sum & 0xff) != 0xff);
    if ($type >= 1 && $type <= 3) {
        $size = $size - 1 - ($type + 1);
        $address = hex(substr($_, 1 + 1 + 2, 2 * ($type + 1)));
        if ($start > $address) {
            $start = $address;
        }
        if ($end < $address + $size - 1) {
            $end = $address + $size - 1;
        }
        for ($i = 0; $i < $size; $i++) {
            $mem[$address + $i] = hex(substr($_, 1 + 1 + 2 + 2 * ($type + 1) + 2 * $i, 2));
        }
    }
}
$line = 10;
for ($i = $start; $i <= $end;) {
    printf("%d '", $line);
    for ($j = 0; $j < 15; $j++) {
        $n = 0;
        for ($k = 0; $k < 8; $k++) {
            $n = ($n << 8) & 0xff00;
            if ($k < 7) {
                $n += $mem[$i++];
            }
            &putc((($n >> ($k + 1)) & 0x7f));
            if ($i > $end) {
                if ($k < 7) {
                    &putc((($n << (6 - $k)) & 0x7f));
                }
                last;
            }
        }
        if ($i > $end) {
            last;
        }
    }
    printf("\n");
    $line += 1;
}

sub putc {
    my ($c) = @_;
    $c += 0x21;
    if ($c >= 0x7f) {
        $c += (0xa1 - 0x7f);
    }
    printf("%c", $c);
}

mandelbrot.apo

10 'Sa NL Ki Sz-eD4IekP, Um2a#=?""&j""%^y%Chi Hn2aj)%c&n-B 9bW")q!J;M!$ja%Z{;ACNrcA-r-#n7 ･';3Ig#GmUEr-{DH)a*-Ga"ｩ g1%f-"23 js#Cga)jUQ'ｦ
11 'D'B.#"1UdBra:1#G*C CDA%ｬ!!i2iU9%Sae-1 a"Qxq ｧ&Se BZ,![A1D.9 / 12neA1!Ö!bBwiYÖ､KfｶXA*|J.9D9Ö､4ｧUｳ!i-ca eX.)|DQ'ｧ"Oer ")seQ7X ”C.!GQMm ”L.
12 's Taste A.#!?""].Bild)K.;egvr.,Ju J.-"nu'39GｳｴZ""/Kochi!EIN`Tuu

Das Folgende ist eine zusammengeführte Version mit einem BASIC-Programm, das dies liest, in den Speicher schreibt, als Maschinensprachenprogramm ausführt und mit TICK () die Ausführungszeit misst und anzeigt.

text:mandelbrot.gcc.1.bas

1 ' Mandelbrot set(gcc)
2 Z=#C03:Y=#700
3 X=0
4 IFPEEK(Z)=39X=X-1:W=33-PEEK(Z-X):IFW<1V=V<<7-W+W/96*34:POKEY,V>>(X&7):Y=Y+(X&7<7):GOTO4
5 Z=Z+PEEK(Z-1)+4:IFPEEK(Z-3)+PEEK(Z-2)GOTO3
6 CLS:CLT:Z=USR(#700,0):LC0,23:?TICK()
10 'Sa NL Ki Sz-eD4IekP, Um2a#=?""&j""%^y%Chi Hn2aj)%c&n-B 9bW")q!J;M!$ja%Z{;ACNrcA-r-#n7 ･';3Ig#GmUEr-{DH)a*-Ga"ｩ g1%f-"23 js#Cga)jUQ'ｦ
11 'D'B.#"1UdBra:1#G*C CDA%ｬ!!i2iU9%Sae-1 a"Qxq ｧ&Se BZ,![A1D.9 / 12neA1!Ö!bBwiYÖ､KfｶXA*|J.9D9Ö､4ｧUｳ!i-ca eX.)|DQ'ｧ"Oer ")seQ7X ”C.!GQMm ”L.
12 's Taste A.#!?""].Bild)K.;egvr.,Ju J.-"nu'39GｳｴZ""/Kochi!EIN`Tuu

Das Ergebnis der Eingabe und Ausführung in IchigoJam ist wie folgt. Der numerische Wert des Ergebnisses ist zu klein, und die Größe des Werts nach dem zum Zeitpunkt der Messung abgeschnittenen Dezimalpunkt ist als Fehler zu groß, um das Ergebnis auszuwerten. Ändern Sie daher das Programm

python

6 CLS:CLT:FORI=1TO100:Z=USR(#700,0):NEXT:LC0,23:?TICK()

100 Mal ausführen und das Ergebnis auswerten. Es heißt 293, aber entfernen Sie Z = USR (# 700,0) aus der vorherigen Zeile

python

6 CLS:CLT:FORI=1TO100:NEXT:LC0,23:?TICK()

Das Ergebnis der 100-maligen Ausführung nur der Schleife ohne Ausführung des Maschinensprachenteils ist Da es 9 ist, ist (293-9) / 100 = 2,84 die ungefähre Ausführungszeit pro Ausführung.

Versuchen Sie es mit Klirren

Die Zeile, die arm-none-eabi-gcc im vorherigen Makefile aufruft

	clang -Wall -W -target arm-eabi -mcpu=cortex-m0 -fpic -Ofast -S $<

Sie können den C-Compiler so ändern, dass er klirrt, indem Sie zu wechseln. Die Optimierungsoption gibt `-Ofast'as in gcc an. Das BASIC-Programm, das den durch clang generierten Code enthält, lautet wie folgt.

text:mandelbrot.clang.1.bas

1 ' Mandelbrot set(clang)
2 Z=#C03:Y=#700
3 X=0
4 IFPEEK(Z)=39X=X-1:W=33-PEEK(Z-X):IFW<1V=V<<7-W+W/96*34:POKEY,V>>(X&7):Y=Y+(X&7<7):GOTO4
5 Z=Z+PEEK(Z-1)+4:IFPEEK(Z-3)+PEEK(Z-2)GOTO3
6 CLS:CLT:FORI=1TO100:Z=USR(#700,0):NEXT:LC0,23:?TICK()
10 'Sa NRl!'C!1"S!C<!A#E-%:V3a-#s/)^c9&!Machen=ｬ'*2 g ”N.!""(153bE!#JB.3!!5a,>Schlüssel d-2cIA$mB$!-""'~!jw5<EU#nCD!}{=a%FgU=!c:Bb o 1+u*:%N59 ｬ 8j
11 '-!$1Ua=g&H!z i mP<(]ｦ*ye]g\1 Also^Damit>ｧ-ｬ ・ 4 ・:idq'BZui(1B$\(!""-<Pq i!!KV%-<Dc"Xl|%G!Shi k&!'m!O!m{=A,X-)#Y./-&kGe!A'M?,Ö$~ﾂﾂﾂ｢ﾂｾDamit"}
12 'Tatsui p Tachi"!!!!

Wenn Sie dies tun, wird das Ergebnis sein Es wurde 307. , (307-9) / 100 = 2,98 ist die ungefähre Ausführungszeit pro Lauf. Unglücklicherweise für die Clang-Sekte war dieser Test etwas (ungefähr 5%) schlechter als gcc.

Versuchen Sie die manuelle Optimierung

In diesem Makefile wird die Assembler-Quelle zum Zeitpunkt des Builds einmal ausgegeben, zusammengestellt und verknüpft. Der Inhalt der Assembler-Quelle, die im Fall des vorherigen gcc generiert wurde, ist wie folgt.

mandelbrot.s

	.syntax unified
	.cpu cortex-m0
	.fpu softvfp
	.eabi_attribute 23, 1
	.eabi_attribute 24, 1
	.eabi_attribute 25, 1
	.eabi_attribute 26, 1
	.eabi_attribute 30, 2
	.eabi_attribute 34, 0
	.eabi_attribute 18, 4
	.thumb
	.syntax unified
	.file	"mandelbrot.c"
	.text
	.align	2
	.global	mandelbrot
	.code	16
	.thumb_func
	.type	mandelbrot, %function
mandelbrot:
	@ args = 0, pretend = 0, frame = 24
	@ frame_needed = 0, uses_anonymous_args = 0
	push	{r4, r5, r6, r7, lr}
	mov	r7, fp
	mov	r6, r10
	mov	r4, r8
	mov	r5, r9
	ldr	r3, .L12
	push	{r4, r5, r6, r7}
	mov	r8, r3
	movs	r3, #0
	sub	sp, sp, #28
	str	r3, [sp, #20]
	movs	r3, #128
	lsls	r3, r3, #7
	movs	r7, #63
	mov	r10, r3
	str	r1, [sp, #16]
.L6:
	movs	r1, #1
	ldr	r2, [sp, #20]
	ldr	r6, .L12+4
	asrs	r3, r2, #1
	lsls	r3, r3, #5
	ands	r1, r2
	str	r3, [sp, #8]
	lsls	r3, r1, #1
	str	r3, [sp, #12]
	movs	r3, #0
	mov	fp, r3
.L5:
	movs	r2, #144
	mov	r3, fp
	lsls	r2, r2, #4
	mov	ip, r2
	ldr	r2, [sp, #8]
	asrs	r3, r3, #1
	add	r3, r3, ip
	mov	ip, r2
	ldr	r2, [sp, #16]
	add	r3, r3, ip
	mov	ip, r2
	mov	r2, fp
	add	ip, ip, r3
	movs	r3, #1
	ands	r3, r2
	ldr	r2, [sp, #12]
	movs	r1, r6
	mov	r9, r2
	movs	r2, #1
	add	r3, r3, r9
	lsls	r2, r2, r3
	mov	r9, r2
	movs	r2, #128
	mov	r3, r9
	orrs	r2, r3
	mov	r3, ip
	ldrb	r3, [r3]
	movs	r4, #32
	orrs	r2, r3
	mov	r3, r8
	str	r2, [sp, #4]
	str	r3, [sp]
	b	.L4
.L2:
	subs	r1, r1, r2
	ldr	r2, [sp]
	lsls	r0, r0, #1
	mov	r8, r2
	muls	r3, r0
	subs	r4, r4, #1
	adds	r1, r6, r1
	add	r3, r3, r8
	cmp	r4, #0
	beq	.L11
.L4:
	asrs	r0, r1, #31
	asrs	r2, r3, #31
	ands	r0, r7
	ands	r2, r7
	adds	r1, r0, r1
	adds	r3, r2, r3
	asrs	r0, r1, #6
	asrs	r3, r3, #6
	movs	r1, r0
	movs	r2, r3
	muls	r1, r0
	muls	r2, r3
	adds	r5, r1, r2
	cmp	r5, r10
	ble	.L2
	ldr	r3, [sp]
	mov	r2, sp
	mov	r8, r3
	mov	r3, ip
	ldrb	r2, [r2, #4]
	strb	r2, [r3]
.L3:
	movs	r3, #1
	mov	ip, r3
	add	fp, fp, ip
	mov	r3, fp
	adds	r6, r6, #192
	cmp	r3, #64
	bne	.L5
	movs	r2, #192
	mov	ip, r2
	ldr	r3, [sp, #20]
	add	r8, r8, ip
	adds	r3, r3, #1
	str	r3, [sp, #20]
	cmp	r3, #48
	bne	.L6
	movs	r0, #0
	add	sp, sp, #28
	@ sp needed
	pop	{r2, r3, r4, r5}
	mov	r8, r2
	mov	r9, r3
	mov	r10, r4
	mov	fp, r5
	pop	{r4, r5, r6, r7, pc}
.L11:
	mov	r2, r9
	ldr	r3, [sp, #4]
	eors	r3, r2
	mov	r2, ip
	strb	r3, [r2]
	b	.L3
.L13:
	.align	2
.L12:
	.word	-4608
	.word	-9216
	.size	mandelbrot, .-mandelbrot
	.ident	"GCC: (GNU Tools for ARM Embedded Processors) 5.4.1 20160919 (release) [ARM/embedded-5-branch revision 240496]"

Da in der Optimierungsoption "-Ofast" angegeben ist, wird davon ausgegangen, dass der Code, der die Ausführungsgeschwindigkeit betont, ausgespuckt wird, aber schließlich liegt er am modernen Compiler, sodass es einen verschwenderischen Teil gibt. Eine der Theorien zur Beschleunigung ist "Fokus auf das Innere der Schleife". Dieses C-Programm hat eine Dreifachschleifenstruktur, aber den innersten Schleifenteil

python

            int p = u, q = v, i = 0;
            do {
                int r = p / 64; p = r * r; if (p < 0) goto l40;
                int s = q / 64; q = s * s; if (q < 0) goto l40;
                if (p + q < 0 || p + q > b) goto l40;
                p = p - q + u;
                q = 2 * r * s + v;
            } while (++i < n);

Ich werde in Betracht ziehen, nur für zu beschleunigen. Der innerste Schleifenteil ist die obere Assemblerquelle

python

	movs	r4, #32
	orrs	r2, r3
	mov	r3, r8
	str	r2, [sp, #4]
	str	r3, [sp]
	b	.L4
.L2:
	subs	r1, r1, r2
	ldr	r2, [sp]
	lsls	r0, r0, #1
	mov	r8, r2
	muls	r3, r0
	subs	r4, r4, #1
	adds	r1, r6, r1
	add	r3, r3, r8
	cmp	r4, #0
	beq	.L11
.L4:
	asrs	r0, r1, #31
	asrs	r2, r3, #31
	ands	r0, r7
	ands	r2, r7
	adds	r1, r0, r1
	adds	r3, r2, r3
	asrs	r0, r1, #6
	asrs	r3, r3, #6
	movs	r1, r0
	movs	r2, r3
	muls	r1, r0
	muls	r2, r3
	adds	r5, r1, r2
	cmp	r5, r10
	ble	.L2

Es wurde in den Code konvertiert. In der C-Quelle war der Prozess des Verlassens der Schleife mit goto, wenn die Variablen p und q negativ werden, eine Gegenmaßnahme gegen den Multiplikationsüberlauf, der auftreten kann, da die Größe der Variablen im ursprünglichen BASIC-Programm 16 Bit beträgt. ist. Bei der Portierung nach C beträgt die Größe der Variablen 32 Bit, und die Beurteilung des Überlaufs sollte nicht logisch erforderlich sein, sondern wird zum Zweck der getreuen Portierung aus dem BASIC-Programm integriert. Ich war überrascht, dass der Ausgabecode des obigen Compilers diesen Teil durch Optimierung sauber entfernt hatte. [Hinzugefügt 2017.9.3] In der Sprache C wird der Überlauf von Ganzzahlen mit Vorzeichen nicht berücksichtigt, daher der folgende Code

                int r = p / 64; p = r * r; if (p < 0) goto l40;
                int s = q / 64; q = s * s; if (q < 0) goto l40;

Negative Ergebnisse der quadratischen r und s wurden nicht berücksichtigt und wären bei der Optimierung als "nutzlos" entfernt worden.

Außerdem als kurzer Blick

• Flow ist nicht effizient
• Es gibt viele Mov-Anweisungen und es scheint eine nutzlose Zuordnung zu geben
• Langsamer Lesespeicher auf Stapelrahmen in Schleife
• R7 wird verwendet, um die Vorzeichenbits zu maskieren, wenn der vorzeichenbehaftete Wert auf 1/64 reduziert wird, ist jedoch für Befehlskombinationen nicht erforderlich
• Nach dem Dekrementieren des Schleifenzählers wird dieser mit # 0 verglichen, aber der Vergleich selbst ist nutzlos, da sich das Flag mit dem Dekrementieren ändert.

Ich war besorgt über die oben genannten Punkte. Der vorherige Teil

python

	movs	r4, #32
	orrs	r2, r3
	mov	r3, r8
	str	r2, [sp, #4]
	str	r3, [sp]
	movs	r7, r3
.L4:
	asrs	r0, r1, #6
	asrs	r2, r3, #6
	lsrs	r0, r0, #26
	lsrs	r2, r2, #26
	adds	r1, r0, r1
	adds	r3, r2, r3
	asrs	r1, r1, #6
	asrs	r3, r3, #6
	movs	r0, r1
	muls	r0, r3
	muls	r1, r1
	muls	r3, r3
	adds	r5, r1, r3
	cmp	r5, r10
	bgt	1f
	subs	r1, r1, r3
	lsls	r3, r0, #1
	adds	r1, r6, r1
	adds	r3, r7
	subs	r4, r4, #1
	bne	.L4
	b	.L11
1:

Durch Ändern von werden diese Punkte aufgelöst. Das Folgende ist eine Version von mandelbrot.s, die mit dieser Änderung erstellt und in ein BASIC-Programm konvertiert wurde.

text:mandelbrot.gcc.opt.bas

1 ' Mandelbrot set(hand optimized)
2 Z=#C03:Y=#700
3 X=0
4 IFPEEK(Z)=39X=X-1:W=33-PEEK(Z-X):IFW<1V=V<<7-W+W/96*34:POKEY,V>>(X&7):Y=Y+(X&7<7):GOTO4
5 Z=Z+PEEK(Z-1)+4:IFPEEK(Z-3)+PEEK(Z-2)GOTO3
6 CLS:CLT:FORI=1TO100:Z=USR(#700,0):NEXT:LC0,23:?TICK()
10 'Sa NL Ki Sz-eD4I ｦ cP, Um2a#=?""&j""%^y%Chi Hn2aj)%c&n-ji 9bW")q!J;M!$ja%Z{;ACNrcA-r-#n7 ･';3Ig#GmUEr-{DH)a*-Ga"ｩ g1%f-"23 js#Cga)jUQ'ｦ
11 'D'B.#"1UdBra:1#G@!C#:qg!/j$i2gmR*)ｩ ・ 1a"QdEq YO U.?UQvCb|mi'!Yg<Ri%Shuh=!%ー ugm2mUQj;Y!EZ ・<geNry$S!x\Beeindruckend%JC9,<C2!497GQ6;1"!0Q
12 '?P3%U..CDK&5g!U U.$*-4YY}Damit#9""Atsu".Echi

Das Ergebnis ist Es wurde 253. (253-9) / 100 = 2,44 ist die ungefähre Zeit pro Sitzung. Was vor der manuellen Optimierung 2,84 war, ist jetzt 2,44, was ungefähr 16,4% schneller ist. Ich denke, der Effekt war großartig für die Optimierung, die in einem begrenzten Bereich durchgeführt wurde.

Versuchen Sie, kleine Änderungen an der Logik vorzunehmen

Im vorherigen C-Programm wird die Adresse des VRAM für jeden gezeichneten Punkt berechnet. Es gibt vier Punkte in einer Adresse von VRAM, aber es ist sinnlos, dieselbe Adresse viermal zu berechnen. Denken wir also über Verbesserungen nach. Dieser Punkt sollte gemildert werden, indem vier Punkte in derselben VRAM-Adresse nacheinander berechnet werden. Durch Ausnutzung der Tatsache, dass die VRAM-Adressen zusammenhängend sind, kann die VRAM-Adressberechnung selbst weggelassen werden. Das Folgende ist eine Anwendung davon auf das C-Programm.

mandelbrot.c

#include <stdint.h>

int mandelbrot(int16_t arg, uint8_t* ram, const uint8_t* font)
{
    (void)arg; (void)font;
    int n = 32;
    int w = 64, h = 48;
    int a = 2 << 6, b = a * a, c = (3 << 12) / w;
    uint8_t* z = ram + 0x900;
    int v = (-h / 2) * c;
    for (int y = 0; y < h; y += 2) {
        int u = -((w * 3) / 4) * c;
        for (int x = 0; x < w; x += 2) {
            #define mandelbrot2(u, v) ({ \
                int p = u; \
                int q = v; \
                int a = 0; \
                int i = 0; \
                do { \
                    int r = p / 64; p = r * r; \
                    int s = q / 64; q = s * s; \
                    if (p + q < 0 || p + q > b) { \
                        a = 1; \
                        break; \
                    } \
                    p = p - q + u; \
                    q = 2 * r * s + v; \
                } while (++i < n); \
                (a); \
            })
            int k = 0x80;
            if (mandelbrot2(u, v)) {
                k += 1;
            }
            v += c;
            if (mandelbrot2(u, v)) {
                k += 4;
            }
            u += c;
            if (mandelbrot2(u, v)) {
                k += 8;
            }
            v -= c;
            if (mandelbrot2(u, v)) {
                k += 2;
            }
            *z++ = k;
            u += c;
        }
        v += 2 * c;
    }
    return 0;
}

Die VRAM-Adresse wird zuerst eingestellt und nur alle 4 geschriebenen Punkte erhöht. Das Folgende ist eine Zusammenstellung davon mit gcc und einem Programm von BASIC.

mandelbrot.gcc.2.bas

1 ' Mandelbrot set(gcc)
2 Z=#C03:Y=#700
3 X=0
4 IFPEEK(Z)=39X=X-1:W=33-PEEK(Z-X):IFW<1V=V<<7-W+W/96*34:POKEY,V>>(X&7):Y=Y+(X&7<7):GOTO4
5 Z=Z+PEEK(Z-1)+4:IFPEEK(Z-3)+PEEK(Z-2)GOTO3
6 CLS:CLT:FORI=1TO100:Z=USR(#700,0):NEXT:LC0,23:?TICK()
10 'i)¡,KV-eD8 ㆍ S9E"&a3eXc 㽦 CA.!-ngl@j45W!glCH)""--Ao!EUR!apDM)""p"3!Fq 㽹 Bs*)"=&a.y ｧ!I!UU(iOCAED>q}ea 㽬 g22-C./!'a%Oh.Ud{g65U!l ー
11 '!ICH.?ｹ#DD2x5U,-ｦ D.-A#"!0 "`a0U=EU"=CD7;1!I+U:E._OCA*Ö(Sa G9 "eTR"*ｧ!;!?IVs/;9v2q#PU$KC\qB/UgÖ2'C."!fa<㽩;9 o!,!!Chi#!!dB / DA*Set 3:
12 'Rr!#Ka 4Bi,C o#!eaAg;ReAD<)aA"q"#dN1 erfN.!3 s A.;{8l~%)Uu U..qC)%E{9 o!z2j ｧ V.-8!"Damit%!"'dega4 su F.*<-a&Ka Wd18 ー&ｧ%"*!b-U ｦ)agW2!a$A#&'{
13 'B'D+{;!Fcaa VUP8[#2IS;Ugo 2)EQ#X"<'o!*m"4 ")Tuka Q.$?B!;'(=$<1-"":?!g|!H)ｬ"0ceNaT5I$Ao Mücke a%!>ein shi]i2t5V*.LD]8|+:Mg A Z.#;:.ZDG)ｩ p>Mg
14 'xZ Service%Q$~ﾂ ﾂ a<p

Das Ergebnis der Ausführung ist (269-9) / 100 = 2,60, was einer Verbesserung von etwa 9% gegenüber 2,84 vor Änderung der Logik entspricht. Es ist nicht so gut wie die oben beschriebene manuelle Optimierung, aber ich denke, es ist ein kleiner Effekt als einfache Methode. Übrigens, wenn Sie mit Clang bauen, wird das Programm

mandelbrot.clang.2.bas

1 ' Mandelbrot set(clang)
2 Z=#C03:Y=#700
3 X=0
4 IFPEEK(Z)=39X=X-1:W=33-PEEK(Z-X):IFW<1V=V<<7-W+W/96*34:POKEY,V>>(X&7):Y=Y+(X&7<7):GOTO4
5 Z=Z+PEEK(Z-1)+4:IFPEEK(Z-3)+PEEK(Z-2)GOTO3
6 CLS:CLT:FORI=1TO100:Z=USR(#700,0):NEXT:LC0,23:?TICK()
10 'Sa NR\!Ea!"#$!"&Mk"EA*)CFa:"O FCI$1"GAj)7A"1A!Qua&>%GB:1z.i,"""""a･#2&2kE@aP!(-$)Aemg\1"e%g+p a)Aw""49a'q, kR'""!#45),{=a)ｧ#B 0W!
11 '3cTA]Stellen Sie A8a ein$c"e%C+D5i`!¡!/9'1b*"-aB, d!u chiso c&W":IS3.4)W!!0:D'.r,!|Ea]!B!'d%ｩ 9$!!m'i!Anders "]ﾂ A8a$c"e1CCD5i`a¡!/='1r*B-aB, ｦ!u ｩ?c
12 '&W!KiQ3.:IWa!0:Dg/,, ,,.!~Ea]!b!'d"ｧ ”#Q;[)n[#Bedienung!Yq9c%EuTV(q,""",!･!2"2kE;eS$4ﾂ""1uｱSc&ｹ!ElER..9)U!!2:B'/,, ,,.!~Aka 18!%A"ｩ A597Q"
13 'Y#TN1*:eh)"･!s!- -;=Wee!:"2a*mEY"m)'$"E"{L Shi "#!O, U.)""(\ﾂ ﾂ!X@Tasso d Tata`aA!!!

Und das Ergebnis der Ausführung ist Das Ergebnis war (294-9) / 100 = 2,85. Es ist eine Verbesserung gegenüber dem vorherigen Beispiel 2.98 in Clang, aber es ist eine Verbesserung von ungefähr 4%, was nicht so groß ist wie im Fall von gcc.

Assembler

Ich habe das Programm mit dem Assembler geschrieben, basierend auf den Erfahrungen mit manueller Optimierung und Logikänderung.

mandelbrot.s

	.syntax unified
	.cpu cortex-m0
	.thumb

	.macro	mandelbrot2 bit
	mov	r2, r8
	mov	r3, r9
	movs	r4, #n
0:
	asrs	r0, r2, #6
	lsrs	r0, r0, #26
	adds	r2, r2, r0
	asrs	r2, r2, #6
	asrs	r0, r3, #6
	lsrs	r0, r0, #26
	adds	r3, r3, r0
	asrs	r3, r3, #6
	movs	r1, r2
	muls	r1, r3
	muls	r2, r2
	muls	r3, r3
	adds	r0, r2, r3
	cmp	r0, r10
	bgt	9f
	subs	r2, r2, r3
	add	r2, r8
	lsls	r3, r1, #1
	add	r3, r9
	subs	r4, #1
	bne	0b
	subs	r5, #\bit
9:
	.endm

	.text
	.align	1
	.global	mandelbrot
mandelbrot:
	.equiv	vramoffset, 0x900
	.equiv	n, 32
	.equiv	w, 64
	.equiv	h, 48
	.equiv	a, 2<<6
	.equiv	b, a*a
	.equiv	c, (3<<12)/w
	push	{r4, r5, r6, r7, lr}
	mov	r3, r8
	mov	r4, r9
	mov	r5, r10
	mov	r6, r11
	mov	r7, r12
	push	{r3, r4, r5, r6, r7}

	movs	r0, #vramoffset>>4
	lsls	r0, r0, #4
	adds	r6, r0, r1

	movs	r0, #c
	mov	r12, r0
	rsbs	r0, #0
	mov	r14, r0

	movs	r0, #b>>12
	lsls	r0, r0, #12
	mov	r10, r0

	ldr	r7, uend
	ldr	r0, vend
	mov	r11, r0

	ldr	r0, vstart
	mov	r9, r0
yloop:
	ldr	r0, ustart
	mov	r8, r0
xloop:
	movs	r5, #0x8f
	mandelbrot2 1
	add	r9, r12
	mandelbrot2 4
	add	r8, r12
	mandelbrot2 8
	add	r9, r14
	mandelbrot2 2
	add	r8, r12

	strb	r5, [r6]
	adds	r6, #1
	cmp	r7, r8
	bne	xloop

	add	r9, r12
	add	r9, r12
	cmp	r11, r9
	bne	yloop

	pop	{r3, r4, r5, r6, r7}
	mov	r8, r3
	mov	r9, r4
	mov	r10, r5
	mov	r11, r6
	mov	r12, r7
	movs	r0, #0
	pop	{r4, r5, r6, r7, pc}

	.align	2
vstart:
	.word	(-h/2)*c
vend:
	.word	(h/2)*c
ustart:
	.word	-((w*3)/4)*c
uend:
	.word	((w*(4-3))/4)*c

	.end

Durch den Versuch, die Register optimal zu nutzen, müssen im Ausgabecode des C-Compilers keine Daten mehr in vorhandene Stapelrahmen eingefügt werden. Das Folgende ist ein BASIC-Programm.

mandelbrot.asm.1.bas

1 ' Mandelbrot set(asm)
2 Z=#C03:Y=#700
3 X=0
4 IFPEEK(Z)=39X=X-1:W=33-PEEK(Z-X):IFW<1V=V<<7-W+W/96*34:POKEY,V>>(X&7):Y=Y+(X&7<7):GOTO4
5 Z=Z+PEEK(Z-1)+4:IFPEEK(Z-3)+PEEK(Z-2)GOTO3
6 CLS:CLT:FORI=1TO100:Z=USR(#700,0):NEXT:LC0,23:?TICK()
10 'Sa NIUSR-vD8i[<E Ui)!!+9Ra1B)ｧ#+-g#)!!=*-dHq*);9 Soiarh-Schlüssel".03qi ｧ{9aEi%Q!W iR3)ｩ#9!YW9neC1#ich'sBw^!, Af$X;Bs*)l!3*Ka vr!p]5C*-l
11 'D)%j!g!/*'3B-"D.!('ｦ*yeC!Mq E.;- -(q-5)qW Ka E.;B2*Q#N)"?[{1B co aeB2jUR!j1)"""1 ･ E2m%Q!Wu R.<)eA&k.EdNq"cb+'UdE327!Fr!4 LC)?Also Ie3:7g
12 '1*3"-!=3-Ec:ag!/.g4R)e!zBuiV{0A9I2A-iUcC3%{1#]UAD")VY!G[7Für ur=5GN,-Ochi 8jc;cgv2wUV-!1]8}#9""Atsu""1!!!EIN`Tuu!Q!!

Das Ausführungsergebnis ist (215-9) / 100 = 2,06, was das bisher schnellste Ergebnis ist.

Zusammenfassung

Die folgende Tabelle zeigt die obigen Ergebnisse.

Zusammenfassung,

• Im Vergleich zu IchigoJam BASIC sind Maschinensprachenprogramme, die mit C und Assemblern erstellt wurden, sehr schnell.
• Im Vergleich von gcc und clang war gcc in diesem Test hinsichtlich der Ausführungsgeschwindigkeit überlegen.
• Handcodierter Code war in diesem Test besser als von gcc oder clang generierter Code

Das ist es. Beim Nachdenken über die Verbesserung der Ausführungsgeschwindigkeit des Programms

• Logik entwickeln
• Verwenden Sie einen Assembler

Usw. sind ärgerlich, sollten jedoch unter Berücksichtigung des Gleichgewichts zwischen Kosten und Wirkung entschieden werden, die für die Codierung und Wartung des Programms erforderlich sind. Diesmal ist es ein komplettes Spiel, daher werden die Kosten nicht berücksichtigt. Wenn Sie das Programm in einer höheren Sprache wie C schreiben, ist es einfach, die Logik für die Beschleunigung zu entwickeln, und umgekehrt ist es schwierig, die Logik zu ändern, wenn Sie sie einmal im Assembler geschrieben haben, also zunächst C usw. Das Schreiben in einer Hochsprache und das Entwickeln der Logik scheint ein wirksames Mittel zur Optimierung zu sein. Der gcc-Ausgabecode, den ich diesmal gesehen habe, war eindeutig nutzlos. Ich würde gerne weitere Verbesserungen bei gcc und clang erwarten.

Ich habe mir eine weitere Beschleunigung ausgedacht und sie hinzugefügt

Über die Division durch 64, wo die Variablen r und s im C-Programm berechnet werden

python

                int r = p / 64;
                int s = q / 64;

Im gcc-Ausgabecode

python

.L4:
    asrs    r0, r1, #31
    asrs    r2, r3, #31
    ands    r0, r7
    ands    r2, r7
    adds    r1, r0, r1
    adds    r3, r2, r3
    asrs    r0, r1, #6
    asrs    r3, r3, #6

Die Vorzeichenbits der Variablen p und q werden auf 32 Bit erweitert, mit dem Wert von r7 (63) maskiert, zum ursprünglichen Wert addiert und die 6-Bit-Arithmetik nach rechts verschoben. Selbst in der Assembler-Version des Programms ist die Verwendung von Registern unterschiedlich, aber die Idee ist dieselbe.

python

0:
    asrs    r0, r2, #6
    lsrs    r0, r0, #26
    adds    r2, r2, r0
    asrs    r2, r2, #6
    asrs    r0, r3, #6
    lsrs    r0, r0, #26
    adds    r3, r3, r0
    asrs    r3, r3, #6

Dies ist eine Korrektur eines negativen Wertes, der gegen 0 konvergiert, unabhängig davon, ob die Dividende positiv oder negativ ist, wenn der vorzeichenbehaftete Wert durch die Potenz von 2 geteilt wird. Einfache Arithmetik Wenn nur die Rechtsverschiebung verwendet wird, konvergieren positive Werte gegen 0, negative Werte gegen -1, daher ergreifen wir Maßnahmen dagegen. In diesem C-Programm wurde die Größe der Variablen vom ursprünglichen BASIC-Programm von 16 Bit auf 32 Bit geändert, und da es einen Genauigkeitsbereich gibt, beträgt der Wertebereich, der für die Variablen p und q im Programm verwendet werden kann, auf der MSB-Seite 15 Bit. Immer den gleichen Wert haben. Wenn Sie dies verwenden, wird der Teil über dem Programm des vorherigen Assemblers sein

python

0:
    lsrs    r0, r2, #26
    adds    r2, r2, r0
    asrs    r2, r2, #6
    lsrs    r0, r3, #26
    adds    r3, r3, r0
    asrs    r3, r3, #6

Es ist möglich zu schreiben. Das Folgende ist das Ergebnis dieser Änderung und ihrer Konvertierung in ein BASIC-Programm.

text:mandelbrot.asm.2.bas

1 ' Mandelbrot set(asm)
2 Z=#C03:Y=#700
3 X=0
4 IFPEEK(Z)=39X=X-1:W=33-PEEK(Z-X):IFW<1V=V<<7-W+W/96*34:POKEY,V>>(X&7):Y=Y+(X&7<7):GOTO4
5 Z=Z+PEEK(Z-1)+4:IFPEEK(Z-3)+PEEK(Z-2)GOTO3
6 CLS:CLT:FORI=1TO100:Z=USR(#700,0):NEXT:LC0,23:?TICK()
10 'Sa NIUSR-vD8i[<E Ui)!!+9Ra1B)ｧ#+-g#)!!=*-`Hp*);9 Schlüssel iarhUe".03qi ｧ{9aEi$cBeiD9('ｦ*yeC!Mq E.;- -(q-5)qW Ka E.;B2*Q#N)"?\;1*Co ceB2jUR!j1
11 '(%d*1gQ/.g4R)e!zBuiV{0A9I2A-iUcC3%{1#]U Ad")cD3"3A/*'3B-""=<-G ・ 2)"SdJ1 YO U.?aQqCb|n1%eFa*UA%Shoc(""+2%gFre#Ea=3-Ec:aYW9
12 'neC1#ich'sBw^!, Af$X;Bs*)l!3*Ka zr"0]%Bv ""<2 ozwhce ur:UMtD-Dienst. G.)Yu+;ugzrxeQ!b u. u.)""(\ﾂ ﾂ!%a!!$Zﾂ ﾂa"a!!

Dies führte zu (198-9) / 100 = 1,89 (Bildaufnahme weggelassen). Das Folgende ist eine aktualisierte Version der Übersichtstabelle.