Ackermann

Ackermann macht’s möglich (28.1.2019)

Die Ackermann-Funktion[1] (AF) ist eine stark rekursive Funktion und wird deshalb häufig für CPU-Tests bezüglich Verwendung des Arbeitsspeichers (insbesondere des Stacks) und der benötigten Ausführungszeit herangezogen.

Deshalb soll die AF nach einigen Vorbemerkungen auch hier (neben ein paar weiteren Programmen) verwendet werden, um die Leistungsfähigkeit von s’AVR auf den 8-bit-AVR zu überprüfen.

Auf eine Erklärung der mathematischen Hintergründe möchte ich an dieser Stelle verzichten, denn hierzu gibt es unendlich viele Abhandlungen in Büchern, Skripten und im WWW.

Auf vielen CPUs

Da mich die AF schon immer fasziniert hat seit ich mit Computern, µProzessoren und µControllern zu tun habe, hatte ich früh damit angefangen, die AF selbst zu programmieren - natürlich immer mit dem Bestreben, ein möglichst schnelles Programm für eine bestimmte CPU zu schreiben bzw. um verschiedene CPUs und verschiedene Programmiersprachen vergleichen zu können.

Anfangs waren es die CPUs Z80 und 68000, mit denen ich beruflich zu tun hatte. Ein ebenso µP/µC-infizierter Freund hatte zur gleichen Zeit die AF mit meinem Assemblerprogramm-Vorschlag auf seinem kleinen MC6802-System getestet - mit einer interessanten Feststellung (wie wir weiter unten noch sehen werden).

Schnell kamen weitere CPUs bzw. Rechner dazu, die ich "beackert" hatte.

Da der CPU-Takt natürlich nicht immer derselbe war, habe ich schließlich die Ausführungszeit der AF für einen sinnvollen Vergleich auf eine einheitliche Größe umgerechnet und einen Ackermann-Index (AI) eingeführt, der praktischerweise wie folgt definiert ist:

AI = (Ausführungszeit/msec * CPU-Frequenz/MHz) / AF(x, y)

Die "Maßeinheit" des Ackermann-Index ist eigentlich msec * MHz, genaugenommen aber dimensionslos, da die Ausführungszeit auf die CPU-Zykluszeit bezogen ist.
Die Division durch AF(x, y) hält den Index in Grenzen[4].

Zum Vergleichen verschiedener CPUs/Rechner, Programmiersprachen und Betriebssysteme muss man also immer dieselben Parameter x und y von AF(x, y) verwenden und sinnvollerweise neben der Ausführungszeit auch den CPU-Takt, die Speicherausstattung, etc. erfassen. Der daraus bestimmte AI ist dann eine ziemlich gute Vergleichsaussage, wobei jeweils der kleinere Wert gewinnt.

Meine Windows-Referenz

Ende 1999 hatte ich damit angefangen, mit dem inzwischen steinalten Delphi-5 (mit dem auch s’AVR erstellt ist, was aber kein Nachteil sein muss) in Pascal ein Windows-Programm zuschreiben, das nicht nur die AF berechnet (das ist eine leichte Übung), sondern bei Bedarf auch die Rekursionstiefe grafisch darstellt, so dass man eine Vorstellung davon hat, was im Stack des CPU-Systems so vor sich geht.

Da die Grafikausgabe sehr zeitintensiv ist, muss man sie zur Bestimmung der tatsächlichen Ausführungszeit der AF natürlich abschalten! Mit Grafik heißt es deshalb auch "Zeichenzeit" statt "Rechenzeit".

Im Laufe der Zeit sind noch einige Extras dazugekommen, wie z.B. die Ausgabe der Anzahl der Funktionsaufrufe und der maximalen Rekursionstiefe, die ein Hinweis auf den Stack-Bedarf ist.

Und so schaut das Ergebnis einer Berechnung von AF(3, 8) mit Grafikausgabe aktuell auf meinem Windows-10-PC (mit i5-CPU) aus:

AF(3,8) mit Grafik

Man könnte sich die vom Programm ausgegebene Grafik[2] im unteren (größeren) Bereich des Programm-Fensters beim gezeigten Beispiel als 3D-Vorhang vorstellen, der bei größeren AF-Parametern langsam zugezogen wird (und je nach AF-Parameter auch sehr unterschiedlich ausschaut).

Auf dem Programmfenster steht auch gleich die Definition der Ackermann-Funktion.
Und statt stolzen 58 sec Zeichenzeit wären es ohne Grafikausgabe bei AF(3, 8) nur noch 15 msec Rechenzeit (bei vollständig rekursiver Berechnung)!

Bei sehr kleinen AF-Parametern sind es eher bunte und schnell (hier < 1 sec) wachsende Eiszapfen in 2D:

AF(3,2) mit Grafik

Bei diesem Beispiel sieht man sehr schön das stetige Ab-und-Auf im Stack, bis schließlich nach Erreichen der maximalen Stack-Tiefe das Ergebnis am Ende des letzten Aufstiegs zur Verfügung steht (das aber nicht in der Grafik erkennbar ist, sondern separat als AF(3|2) = 29 ausgegeben wird).

Mit den angegebenen Pixeleinheiten könnte man bei diesem Beispiel sogar die Zahl der Funktionsaufrufe und die Rekursionstiefe aus der Grafik ablesen, wenn auch etwas mühsam. Deshalb werden diese Werte inzwischen vom Programm gezählt und unten in der Statuszeile ausgegeben.

Damit der interessierte Leser eigene AF-Untersuchungen anstellen kann (so er einen schnellen PC oder viel Zeit hat), stelle ich mein Windows-Programm bei Bedarf gerne zur Verfügung.

Eine Übersicht

Bevor es ans Eingemachte geht, zunächst ganz unabhängig von jeglicher CPU und Programmiersprache eine Tabelle mit diversen AF-Ergebnissen von zweckmäßigen Parametern x und y, der Anzahl der zugehörigen Funktionsaufrufe und der maximalen Rekursionstiefe (also dem letzten Peak vor dem AF-Ergebnis), jeweils für die vollständig rekursive Berechnung:

x

y

AF(x, y)

dto. in HEX

Funktionsaufrufe

Rekursionstiefe

4

1

65.533

0FFFD

2_862_984_010

65.536

4

0

13

0000D

107

16

3

16

524.285

7FFFD

183_249_316_583

524.287

3

15

262.141

3FFFD

45_811_673_828

262.143

3

14

131.069

1FFFD

11_452_590_817

131.071

3

13

65.533

0FFFD

2_862_983_902

65.535

3

12

32.765

07FFD

715_664_091

32.767

3

11

16.381

03FFD

178_875_096

16.383

3

10

8.189

01FFD

44_698_325

8.191

3

9

4.093

00FFD

11_164_370

4.095

3

8

2.045

007FD

2_785_999

2.047

3

7

1.021

003FD

693_964

1.023

3

6

509

001FD

172_233

511

3

5

253

000FD

42_438

255

3

4

125

0007D

10_307

127

3

3

61

0003D

2_432

63

3

2

29

0001D

541

31

3

1

13

0000D

106

15

3

0

5

00005

15

7


Die Anzahl der Funktionsaufrufe[5] und der maximalen Rekursionstiefe dieser Tabelle wurden vom Programm gefunden und in die Tabelle übertragen.

Nach (sehr) langem Suchen habe ich auch eine ziemlich komplexe Formel zur Berechnung der Anzahl der Funktionsaufrufe für AF(3, y) und deren clevere Herleitung[3] gefunden:

Anzahl der AF-Funktionsaufrufe = (128 * 4^y −120 * 2^y + 9*×*y + 37)/3

Eine Verifizierung mit dieser Formel bestätigt exakt die vom Programm gefundenen Werte (immerhin)!

Ein Versuch, diese Formel aus den Tabellenwerten herzuleiten, kann nur scheitern.

nach oben


Auf die Plätze ...

Nach der langen Vorrede sollen nun Zahlenwerte sprechen, die über die Jahre mehr oder weniger vollständig gesammelt und in einer umfangreichen Tabelle zusammengefasst wurden.

Ein Auszug mit den wichtigsten Spalten soll hier gezeigt werden:

AF

Ergebnis

CPU

Sprache

MHz

Zeit/sec

AI/(MHz*ms)

Kommentar

AF(4,1)

65.533

i3 M380, 4 Cores

Delphi 5

2.530,00

20,571

794

Ergebnisse ähnlich AF(3, 13)

AF(4,1)

65.533

i5-3550, 4 Cores

Delphi 5

3.500,00

11,890

635

256 KB L1 Cache, 1 MB L2 Cache, 6 MB L3 Cache, WIN10

AF(4,1)

65.533

AMD-K3

Delphi 5

350,00

232,550

1.242

WIN98 SE, 256 MB SDRAM

 

 

 

 

 

 

 

 

AF(3,16)

524.285

i3 M380, 4 Cores

Delphi 5

2.530,00

1.351,914

6.524

WIN7

AF(3,16)

524.285

i5-3550, 4 Cores

Delphi 5

3.500,00

764,897

5.106

256 KB L1 Cache, 1 MB L2 Cache, 6 MB L3 Cache, WIN10

AF(3,16)

524.285

AMD-K3

Delphi 5

350,00

23.856,010

15.926

WIN98 SE, 256 MB SDRAM

 

 

 

 

 

 

 

 

AF(3,15)

262.141

i3 M380, 4 Cores

Delphi 5

2.530,00

330,084

3.186

WIN7

AF(3,15)

262.141

i5-3550, 4 Cores

Delphi 5

3.500,00

190,826

2.548

256 KB L1 Cache, 1 MB L2 Cache, 6 MB L3 Cache, WIN10

AF(3,15)

262.141

AMD-K3

Delphi 5

350,00

5.366,530

7.165

WIN98 SE, 256 MB SDRAM

 

 

 

 

 

 

 

 

AF(3,14)

131.069

i3 M380, 4 Cores

Delphi 5

2.530,00

82,302

1.589

WIN7

AF(3,14)

131.069

i5-3550, 4 Cores

Delphi 5

3.500,00

47,640

1.272

256 KB L1 Cache, 1 MB L2 Cache, 6 MB L3 Cache, WIN10

AF(3,14)

131.069

AMD-K3

Delphi 5

350,00

1.120,370

2.992

WIN98 SE, 256 MB SDRAM

 

 

 

 

 

 

 

 

AF(3,13)

65.533

i3 M380, 4 Cores

Delphi 5

2.530,00

20,513

792

WIN7

AF(3,13)

65.533

i5-3550, 4 Cores

Delphi 5

3.500,00

11,907

636

256 KB L1 Cache, 1 MB L2 Cache, 6 MB L3 Cache, WIN10

AF(3,13)

65.533

Pentium III

Delphi 5

500,00

134,790

1.028

 

AF(3,13)

65.533

AMD-K3

Delphi 5

350,00

232,720

1.243

WIN98 SE, 256 MB SDRAM

 

 

 

 

 

 

 

 

AF(3,12)

32.765

i3 M380, 4 Cores

Delphi 5

2.530,00

5,100

394

WIN7

AF(3,12)

32.765

i5-3550, 4 Cores

Delphi 5

3.500,00

2,969

317

256 KB L1 Cache, 1 MB L2 Cache, 6 MB L3 Cache, WIN10

AF(3,12)

32.765

AMD-K3

Delphi 5

350,00

53,600

573

WIN98 SE, 256 MB SDRAM

 

 

 

 

 

 

 

 

AF(3,11)

16.381

i3 M380, 4 Cores

Delphi 5

2.530,00

1,279

198

WIN7

AF(3,11)

16.381

i5-3550, 4 Cores

Delphi 5

3.500,00

0,750

160

256 KB L1 Cache, 1 MB L2 Cache, 6 MB L3 Cache, WIN10

AF(3,11)

16.381

AMD-K3

Delphi 5

350,00

12,470

266

WIN98 SE, 256 MB SDRAM

AF(3,11)

16.381

IDT79R3081

IDT/c 5.1

33,00

128,000

258

16k/4k I/D Cache

AF(3,11)

16.381

IDT79R3081

IDT/c 5.1

33,00

125,000

252

8k/8k I/D Cache

 

 

 

 

 

 

 

 

AF(3,10)

8.189

i3 M380, 4 Cores

Delphi 5

2.530,00

0,312

96

WIN7

AF(3,10)

8.189

i5-3550, 4 Cores

Delphi 5

3.500,00

0,187

80

WIN10

AF(3,10)

8.189

AMD-K3

Delphi 5

350,00

2,860

122

WIN98 SE, 256 MB SDRAM

AF(3,10)

8.189

IDT79R3052

Assembler

33,00

135,000

544

uncached

AF(3,10)

8.189

IDT79R3052

IDT/c

33,00

235,000

947

uncached

AF(3,10)

8.189

IDT79R3081

IDT/c 5.1

33,00

29,000

117

8k/8k I/D Cache

AF(3,10)

8.189

IDT79R3081

IDT/c 5.1

33,00

31,000

125

16k/4k I/D Cache

AF(3,10)

8.189

IDT79R3000A

Assembler

25,00

41,800

128

64k/64k I/D Cache, cc -O4

AF(3,10)

8.189

MK68200

Assembler

4,00

385,500

188

 

AF(3,10)

8.189

68HC11

Assembler

2,46

418,000

125

512 B internal + 32+2 KB SRAM

 

 

 

 

 

 

 

 

AF(3,9)

4.093

i3 M380, 4 Cores

Delphi 5

2.530,00

0,078

48,2

WIN7

AF(3,9)

4.093

i5-3550, 4 Cores

Delphi 5

3.500,00

0,047

40,2

WIN10

AF(3,9)

4.093

AMD-K3

Delphi 5

350,00

0,500

42,8

WIN98 SE, 256 MB SDRAM

AF(3,9)

4.093

ATmega1284

s'AVR

18,00

8,060

35,4

s'AVR and AVR assembler

AF(3,9)

4.093

IDT79R3000A

Assembler

25,00

7,900

48,3

64k/64k I/D Cache, cc -O4

AF(3,9)

4.093

IDT79R3052

Assembler

33,00

34,000

274,1

uncached

AF(3,9)

4.093

IDT79R3052

IDT/c

33,00

58,800

474,1

uncached

AF(3,9)

4.093

IDT79R3081

IDT/c 5.1

33,00

7,000

56,4

16k/4k I/D Cache

AF(3,9)

4.093

8080

Assembler

2,00

361,800

176,8

 

AF(3,9)

4.093

80286

Quick C

12,00

132,000

387,0

opt full, stack check off

AF(3,9)

4.093

80486DX-33

Quick C

33,00

11,000

88,7

opt full, stack check off

AF(3,9)

4.093

MK68200

Assembler

4,00

96,280

94,1

 

AF(3,9)

4.093

68HC11

Assembler

2,46

104,950

63,0

512 B internal + 32+2 KB SRAM

 

 

 

 

 

 

 

 

AF(3,8)

2.045

i3 M380, 4 Cores

Delphi 5

2.530,00

0,021

26,0

WIN7

AF(3,8)

2.045

i5-3550, 4 Cores

Delphi 5

3.500,00

0,015

25,7

WIN10

AF(3,8)

2.045

AMD-K3

Delphi 5

350,00

0,110

18,8

WIN98 SE, 256 MB SDRAM

AF(3,8)

2.045

ATmega1284

s'AVR

18,00

2,010

17,7

s'AVR and AVR assembler

AF(3,8)

2.045

80286

Quick C

12,00

34,000

199,5

opt full, stack check off

AF(3,8)

2.045

8080

Assembler

2,00

90,600

88,6

 

AF(3,8)

2.045

Z80

Assembler

2,50

54,900

67,1

 

AF(3,8)

2.045

Z80

Assembler

4,00

34,400

67,3

 

AF(3,8)

2.045

MK68200

Assembler

4,00

25,030

49,0

 

AF(3,8)

2.045

68HC11

Assembler

2,46

26,600

32,0

512 B internal + 32+2 KB SRAM

 

 

 

 

 

 

 

 

AF(3,7)

1.021

ATmega1284

s'AVR

18,00

0,501

8,8

s'AVR and AVR assembler

AF(3,7)

1.021

8080

Assembler

2,00

25,800

50,5

 

AF(3,7)

1.021

Z80

Assembler

2,50

13,900

34,0

 

AF(3,7)

1.021

MK68200

Assembler

4,00

5,980

23,4

 

AF(3,7)

1.021

6802

Assembler

1,00

18,000

17,6

 

AF(3,7)

1.021

68HC11

Assembler

2,46

6,520

15,7

512 B internal + 32+2 KB SRAM

AF(3,7)

1.021

68000

Assembler

8,00

5,600

43,9

move.w

AF(3,7)

1.021

80286

Quick C

12,00

8,000

94,0

opt full, stack check off

 

 

 

 

 

 

 

 

AF(3,6)

509

ATmega1284

s'AVR

18,00

0,124

4,4

s'AVR and AVR assembler

AF(3,6)

509

ATmega328

s'AVR

16,00

0,140

4,4

s'AVR and AVR assembler

AF(3,6)

509

ATmega328

Arduino C

16,00

0,260

8,2

avr-gc++ compiler, Option -Os, int/int

AF(3,6)

509

ATmega328

Arduino C

16,00

0,205

6,4

avr-gc++ compiler, Option -Os, byte/int

AF(3,6)

509

ATmega328

avr gcc

16,00

0,237

7,4

avr-gcc compiler, Option -O, uint8_fast/int

AF(3,6)

509

8080

Assembler

2,00

5,800

22,8

 

AF(3,6)

509

Z80

Assembler

2,50

3,600

17,7

 

AF(3,6)

509

MK68200

Assembler

4,00

1,460

11,5

 

AF(3,6)

509

6802

Assembler

1,00

5,000

9,8

 

AF(3,6)

509

68HC11

Assembler

2,46

1,610

7,8

512 B internal + 32+2 KB SRAM

AF(3,6)

509

68000

Assembler

8,00

1,500

23,6

move.w

AF(3,6)

509

80286

Quick C

12,00

2,000

47,2

opt full, stack check off

 

 

 

 

 

 

 

 

AF(3,5)

253

ATmega1284

s'AVR

18,00

0,031

2,2

s'AVR and AVR assembler

AF(3,5)

253

ATmega328

s'AVR

16,00

0,035

2,2

s'AVR and AVR assembler

AF(3,5)

253

ATmega328

Arduino C

16,00

0,064

4,0

avr-gc++ compiler, Option -Os, int/int

AF(3,5)

253

ATmega328

Arduino C

16,00

0,051

3,2

avr-gc++ compiler, Option -Os, byte/int

AF(3,5)

253

ATmega328

avr gcc

16,00

0,058

3,7

avr-gcc compiler, Option -O, uint8_fast/int

AF(3,5)

253

8080

Assembler

2,00

1,600

12,6

 

AF(3,5)

253

Z80

Assembler

2,00

1,000

7,9

 

AF(3,5)

253

MK68200

Assembler

4,00

0,370

5,8

 

AF(3,5)

253

6802

Assembler

1,00

1,000

4,0

 

AF(3,5)

253

68HC11

Assembler

2,46

0,397

3,9

512 B internal + 32+2 KB SRAM

AF(3,5)

253

80286

Quick C

12,00

1,000

47,4

opt full, stack check off


Der Sieger aus jeder AF(3, y)-Gruppe ist jeweils grün markiert, die Nächstplatzierten orange.

Gelbe Werte waren mit der Armbanduhr "geschätzt" und wurden für den 6802 durch den codekompatiblen 68HC11 neuerdings per Scope genauer gemessen (genau genommen sollte sich für beide derselbe AI ergeben).

Erkenntnisse

  • 6802/68HC11 waren in meiner Liste lange die AF-Sieger bis die RISC-Prozessoren von MIPS auf den Markt kamen, sind aber trotz CISC-Architektur heute je nach AF-Parameter immer noch auf den vorderen Rängen mit dabei.
  • Die 8-Bit-AVR können bei der AF absolut mit großen RISC-CPUs mithalten, wobei modernere Compiler für letztere vermutlich bessere Ergebnisse zeigen als der Code meines alten Delphi-5, der aber angeblich schneller ist, als Code neuerer Delphi-Versionen.

    Vielleicht kann das jemand von meinen Lesern durch eigene Untersuchungen bestätigen?
  • Im Vergleich zu Arduino C (kompiliert mit Arduino-Tools) und avr gcc (kompiliert mit Atmel Studio) zeigt s’AVR auf denselben AVR-CPUs deutlich bessere Ergebnisse, siehe AF(3, 5) und AF(3, 6).
  • Bis einschließlich AF(3, 9) sind die 8-bit-AVR-CPUs in Kombination mit s’AVR schneller als andere von mir untersuchte CPUs und Programmiersprachen.

 

Ich bin gespannt auf Kommentare und freue mich über AF-Ergebnisse (auch mit anderen CPUs) meiner Leser.

nach oben


Quellprogramme

Zur Diskussion der Ergebnisse oder für eigene Untersuchungen durch meine Leser möchte ich nachfolgend den von mir verwendeten Quellcode zur Verfügung stellen.

Mein Delphi-Programm setzt die oben gezeigten AF-Definitionen direkt in Pascal um:

    function AF(x,y: longword): longword; register;    // no extras, full speed!
    begin
         if x = 0 then af := y+1
         else if y = 0 then af := af(x-1, 1)
         else af := af(x-1, af(x,y-1));
    end;

Die Rechenzeit wird mittels Differenz der Windows-Systemvariablen "now" vor und nach dem AF-Aufruf bestimmt.

Für Arduino lautet die AF-Routine in C wie folgt:

    int ackermann(byte m, int n)    // m can be byte (short n would be same as int n)
    {
            if (!m) return n + 1;
            if (!n) return ackermann(m - 1, 1);
            return ackermann(m - 1, ackermann(m, n - 1));
    }

Für eine genaue Messung der Rechenzeit per Scope mit einem ATmega328 wird an LED13 ein Trigger-Signal ausgegeben und die AF(3, 6) [mehr lässt der Stack nicht zu] in einer Endlosschleife ausgeführt:

    void loop()
    {
            byte m; int n;
            digitalWrite(led13, LOW);
            ackermann(3, 6);
            digitalWrite(led13, HIGH);
            delay(1); // 1 ms
    }

Hier der vollständige C-Code aus Atmel Studio (wobei ich bei den Ergebnissen keinen Unterschied zwischen GCC und GPP feststellen konnte):

    #define F_CPU 16000000UL             // 16 MHz
    #include <avr/io.h>
    #include <util/delay.h>

    #define LED_ONPORTB |= (1 << PORTB5)
    #define LED_OFFPORTB &= ~(1 << PORTB5)
    #define LED_TOGGLEPINB |= (1 << PINB5)

    int ackermann(uint_fast8_t m, int n)
    {
            if (!m) return n + 1;
            if (!n) return ackermann(m - 1, 1);
            return ackermann(m - 1, ackermann(m, n - 1));
    }

    int main(void)
    {
            DDRB |= (1 << DDB5);        // Port B, Bit 5 is output

            while(1)
            {
                    LED_OFF;
                    ackermann(3, 6);    // AF(3, 6)
                    LED_ON;
                    _delay_ms(1);       // short HIGH pulse for the scope (1 ms)
            }
    }

Und per s’AVR wird die eigentliche AF-Routine kaum aufwendiger, nämlich ebenso mit nur zwei einfachen IF-Abfragen:

    AF:              ; Ackermann function AF(x, y)

                     ; where x = xl = R26, y = yh:yl = R29:R28, result in yh:yl

       IF xl == #0   ; check x ? 0

           adiw y,1  ; AF(0, 1) = y+1

           ret       ; the only and final return within AF

       ENDI

       adiw y,0      ; to check y ? 0

       IF NZ         ; testing for y <> 0 (NZ) first speeds up for larger y values

           sbiw y,1  ; y := y - 1

           push xl

           rcall AF  ; recursive call AF(x, y-1), result in yh:yl

           pop  xl

           subi xl,1 ; x := x - 1

           rjmp AF   ; recursive call,

                     ; same as rcall AF(x-1, AF(x, y-1)) | ret (tail call)

       ENDI          ; all other cases must be AF(x, 0) = AF(x-1, 1)

       subi xl,1     ; x := x - 1

       ldi  yl,1     ; y := 1 (additional clr yh is not required

                     ; as yh:yl was zero before)

       rjmp AF       ; recursive call, same as rcall AF(x-1, 1) | ret (tail call)

Zum genauen Messen der Rechenzeit wird ebenfalls ein Trigger-Signal in einer Endlosschleife verwendet (hier mit 100 ms Verzögerung zum Messen längerer Rechenzeiten für AF(3, 9) mit dem ATmega1284, der 16 kByte SRAM für den Stack zur Verfügung hat):

       LOOP                   ; loop AF to measure the time by scope

           mov   xl,AFX       ; get AF parameter X

           mov   yl,AFYL      ; get AF parameter YL

           mov   yh,AFYH      ; get AF parameter YH

           cbi   PORTC,0      ; pin off, trigger scope on falling edge

           rcall AF

           sbi   PORTC,0      ; pin on, measure time on rising edge

           rcall delay100ms

       ENDL

Die in diesem AF-Code verwendeten Tail-Calls sind ein gängiger Assembler-Optimierungstrick, der auch von den genannten C-Compilern verwendet wird.

Die C-Compiler verwenden noch ein paar weitere Tricks. So wird bei Register R1 immer der Inhalt 0 vorausgesetzt und von beiden C-Compilern verwendet (nicht so von s’AVR).

Dennoch ist der von s’AVR erzeugte Code mit 30 Bytes deutlich kompakter (und entsprechend schneller) als jener der C-Compiler, die 48 Bytes (Arduino C) bzw. 56 Bytes (avr gcc) für die eigentliche AF-Routine benötigen.

Die von den C-Compilern erzeugten Assembler-Listings auf Anhieb zu verstehen, ist allerdings schon eine Herausforderung ...

Interessant ist vielleicht noch, dass 6802/68HC11 (8-bit-CISC-CPUs) nur 22 Bytes Programmspeicher und der MK68200 (16-bit-CISC-CPU) bereits 36 Bytes für den AF-Code in Assembler-Sprache benötigen.

Fazit

s’AVR erzeugt sehr effektiven und schnellen Programm-Code und muss einen Vergleich mit AVR-C-Compilern nicht scheuen - gute AVR-Assembler-Kenntnisse beim Schreiben der s’AVR-Programme vorausgesetzt.

Die Ackermann-Funktion ist zwar eine sehr einfache (wenn auch rechenintensive) Funktion, ich erwarte bei komplexeren AVR-Programmen unter Verwendung von s’AVR aber eine ähnlich gute Effizienz im Vergleich mit AVR-C-Compilern.

nach oben


[1] Genau genommen ist hier eine vereinfachte Variante genannt Ackermann-Péter-Funktion gemeint.

[2] Die Grafik von AF(3,8) ist Bestandteil des Programmfensters rechts oben. Sie wurde allerdings auf einem älteren Bildschirm mit anderer Auflösung erstellt.

[3] Diese Studie ist ursprünglich vom April 1975 (!):

https://www.researchgate.net/publication/226959069_Ackermann%27s_function

An weiteren Stellen im WWW finden sich andere Formeln für die Anzahl der Funktionsaufrufe der Ackermann-Funktion (teilweise auch mit Tippfehlern von anderen Quellen übernommen), die sehr viel größere Werte ergeben, als jene von B. A. Wichmann und von mir gefundene.

Auch bezüglich der maximalen Rekursionstiefe (siehe obige Tabelle) gibt es widersprüchliche Aussagen.
Offensichtlich ist sie bei AF(3,y) um zwei größer als AF(3,y) und bei AF(4,y) ist sie um drei größer als AF(4,y).

[4] Mit einem zusätzlichen Faktor 2^(10-y) würde der Index für alle AF(3, y) überwiegend konstant bleiben.

[5] Mit Unterstrich statt Tausenderpunkt (oder Leerzeichen), damit (manche) Browser keine Telefonnummern oder IP-Adressen daraus machen.