Kleiner AVR Trick zum schnellen Inkrementen grosser Zahlen

Herzlichen Glückwunsch! Du hast die Schleife zum 1024ten Mal 
wiederentdeckt!

Und wenn Du die Schleife abbrichst, wenn nach ADC das Carry-Flag nicht 
gesetzt ist, sparst Du auch noch CPU-Zyklen.

Jan schrieb:
> sec

>   0:

Bitte, was macht sec? Und was bedeutet 0: ?
Gruß Rainer

sec = SEt Carry
0: Sprungmarke für brne 0b
0b: springe zu Marke 0 zurück (back)

Rainer V. schrieb:
> Bitte, was macht sec?

Setzt das Carry-Flag.

> Und was bedeutet 0: ?

Das nennt man ein Label.

Jan schrieb:
> die spontane Frage in den Sinn, wie es der Compiler macht?

Der geht davon aus, dass die Zahl in Registern vorliegt und ruft eine 
Hilfsfunktion dafür auf:

1

$ avr-objdump -d _adddi3_s8.o 

2

3

_adddi3_s8.o:     file format elf32-avr

4

5

6

Disassembly of section .text.libgcc:

7

8

00000000 <__adddi3_s8>:

9

   0:   00 24           eor     r0, r0

10

   2:   a7 fd           sbrc    r26, 7

11

   4:   00 94           com     r0

12

   6:   2a 0f           add     r18, r26

13

   8:   30 1d           adc     r19, r0

14

   a:   40 1d           adc     r20, r0

15

   c:   50 1d           adc     r21, r0

16

   e:   60 1d           adc     r22, r0

17

  10:   70 1d           adc     r23, r0

18

  12:   80 1d           adc     r24, r0

19

  14:   90 1d           adc     r25, r0

20

  16:   08 95           ret

r18 … r25 enthalten dabei die 64-Bit-Zahl, r26 den Summanden. (Daher 
auch _s8 im Namen.)

Danke und sorry...hab' mir eben auf der eigenen Leitung gestanden....
Rainer

Jan schrieb:
> Da
> lds und sts jeweils 4 Bytes belegen, kostet so eine einfache
> "value++"-Aktion direkt mal 64 Bytes Flash.

So macht man es ja auch nicht. Wird diese Funktion mehrmals benötigt, 
schreibt man es als Unterfunktion und übergibt nur die Adresse der 
Variablen:

1

void inc64( uint64_t* valp)

2

{

3

  32:  fc 01         movw  r30, r24

4

  (*valp)++;

5

  34:  20 81         ld  r18, Z

6

  36:  31 81         ldd  r19, Z+1  ; 0x01

7

  38:  42 81         ldd  r20, Z+2  ; 0x02

8

  3a:  53 81         ldd  r21, Z+3  ; 0x03

9

  3c:  64 81         ldd  r22, Z+4  ; 0x04

10

  3e:  75 81         ldd  r23, Z+5  ; 0x05

11

  40:  86 81         ldd  r24, Z+6  ; 0x06

12

  42:  97 81         ldd  r25, Z+7  ; 0x07

13

  44:  a1 e0         ldi  r26, 0x01  ; 1

14

  46:  14 d0         rcall  .+40       ; 0x70 <__adddi3_s8>

15

  48:  20 83         st  Z, r18

16

  4a:  31 83         std  Z+1, r19  ; 0x01

17

  4c:  42 83         std  Z+2, r20  ; 0x02

18

  4e:  53 83         std  Z+3, r21  ; 0x03

19

  50:  64 83         std  Z+4, r22  ; 0x04

20

  52:  75 83         std  Z+5, r23  ; 0x05

21

  54:  86 83         std  Z+6, r24  ; 0x06

22

  56:  97 83         std  Z+7, r25  ; 0x07

23

  58:  08 95         ret

24

25

uint64_t bla, blub, usw;

26

27

void test(void)

28

{

29

  inc64(&bla);

30

  5a:  80 e7         ldi  r24, 0x70  ; 112

31

  5c:  90 e0         ldi  r25, 0x00  ; 0

32

  5e:  e9 df         rcall  .-46       ; 0x32 <inc64>

33

  inc64(&blub);

34

  60:  88 e6         ldi  r24, 0x68  ; 104

35

  62:  90 e0         ldi  r25, 0x00  ; 0

36

  64:  e6 df         rcall  .-52       ; 0x32 <inc64>

37

  inc64(&usw);

38

  66:  80 e6         ldi  r24, 0x60  ; 96

39

  68:  90 e0         ldi  r25, 0x00  ; 0

40

  6a:  e3 cf         rjmp  .-58       ; 0x32 <inc64>

In der Regel überlege ich ab 2 Vorkommen einer Codesequenz, ob ich 
daraus eine Funktion machen kann.
Ich hasse Codewiederholungen, da man dann auch wiederholt Fehler machen 
kann bzw. sie an mehreren Stellen beseitigen muß.

>eine Optimierung auf Speed
Das wird's wohl sein!

Falk B. schrieb:

> Herzlichen Glückwunsch! Du hast die Schleife zum 1024ten Mal
> wiederentdeckt!

Nunja, bald ist wieder Weihnachten. Da werden viele Schleifen benötigt.

Was ihr euch immer um sowas streitet. Deswegen poste ich hier so ungerne 
Codefetzen. Es ist immer die Frage worauf man den Code optimiert. Wenn 
man genug Flash hat, sind die einzelnen LDS/ADC/STS-Befehle schneller 
als die Verpackung in eine Schleife. Wenn man nicht genug Flash hat, 
nimmt man eben die Schleife und opfert ein wenig CPU-Zeit.

Jörg W. schrieb:
> Der geht davon aus, dass die Zahl in Registern vorliegt und ruft eine
> Hilfsfunktion dafür auf:

Obwohl ich mich ja schon blamiert habe, wage ich zu sagen, genau so 
würde ich das auch Programmieren. Dabei interessiert mich erst mal 
überhaupt nicht, ob die Zahl nun im Ram, Flash oder EEProm liegt. 
Gerechnet wird in den CPU-Registern und wenn es Interrupts geben kann, 
dann muß halt der ganze Registersatz gerettet werden. Zumindest aus 
dieser Sicht kann ich dann auch keinen Trick erkennen...
Trotzdem Danke...vielleicht werden die Ideen ja doch noch spannend.
Gruß Rainer

Ben B. schrieb:
> Deswegen poste ich hier so ungerne Codefetzen.

Ich bin mal mutig ...
Wenn es um Performance geht und nur inkrementiert werden muss:
Dies dürfte wohl die schnellste Lösung sein.
65535 von 65536 Aufrufen sind in jeweils 10 Takten erledigt.

1

:

2

ldiz    RAM_p1_starts

3

CALL    inc64

4

:

5

:

6

7

inc64:  LD    R24, Z

8

        LDD   R25, Z+1

9

        ADIW  R25:24, 1

10

        ST    Z+, R24

11

        ST    Z+, R25

12

        BRCC  inc64x

13

14

        LD    R24, Z

15

        LDD   R25, Z+1

16

        ADIW  R25:24, 1

17

        ST    Z+, R24

18

        ST    Z+, R25

19

        BRCC  inc64x

20

21

        LD    R24, Z

22

        LDD   R25, Z+1

23

        ADIW  R25:24, 1

24

        ST    Z+, R24

25

        ST    Z+, R25

26

        BRCC  inc64x

27

28

        LD    R24, Z

29

        LDD   R25, Z+1

30

        ADIW  R25:24, 1

31

        ST    Z+, R24

32

        ST    Z+, R25

33

        (BRCS  behandlung_bei_ueberlauf)

34

35

inc64x: RET

Etwas kurzes habe ich auch noch:

1

:

2

ldiz    RAM_p1_starts

3

CALL    inc64

4

:

5

:

6

7

inc64:  SEC

8

        CALL  inc641

9

inc641: CALL  inc642

10

inc642: BRCC  inc64x

11

        LD    R24, Z

12

        LDD   R25, Z+1

13

        ADIW  R25:24, 1

14

        ST    Z+, R24

15

        ST    Z+, R25

16

inc64x: RET

;-)


Gruß
Jobst

Moby schrieb:
> Wo sich solche Rechnungen häufen: Einen 32Bit  Controller benutzen!

Nein.

Wenn der Controller zu langsam ist, und das wegen solcher Rechnungen, 
benutzt man besser einen mit breiterer ALU. Z.B. einen 32-Bitter.

Arithmetik die breiter ist als die ALU gab es schon immer und wird es 
immer geben (Stichwort: Kryptographie). Deswegen hat die ALU auch 
immer[1] ein Carry-Flag oder eine Entsprechung.


[1] oder gibt es Ausnahmen? Ich kenne keine, aber ich würde mich auch 
nicht als Kenner historischer oder seltsamer Architekturen bezeichen

Irgendwie würde das keinen Sinn machen. Das Carry-Flag ist ja auch kein 
Muss, sondern es wird von der Hardware zur Verfügung gestellt und es ist 
Sache des Programmierers, ob er's benutzt oder nicht.

Axel S. schrieb:
> [1] oder gibt es Ausnahmen? Ich kenne keine, aber ich würde mich auch
> nicht als Kenner historischer oder seltsamer Architekturen bezeichen

MIPS gehört zu den Ausnahmen und ist weder historisch noch seltsam. 
Historisch wäre beispielsweise DEC Alpha.

Bei tiefem Pipelining oder superskalarer Implementierung ist ein 
Statusregister ausgesprochen aufwändig zu implementieren, von 
Out-of-Order ganz zu schweigen. Architekturen, die solche Thematik 
eingepreist haben, lassen das manchmal weg. Die sind dann Kandidaten für 
alternative Lösungen von Mehrwort-Arithmetik.

https://yarchive.net/comp/carry_bit.html

Axel S. schrieb:
> [1] oder gibt es Ausnahmen? Ich kenne keine, aber ich würde mich auch
> nicht als Kenner historischer oder seltsamer Architekturen bezeichen

NB: Besonders perfide ist eine Architektur, bei denen aus dem Befehl 
selbst nicht hervorgeht, ob das Carry-Bit ein Ergebnis des Befehls ist, 
oder unverändert bleiben soll. Etwa die sowohl historische als auch 
seltsame x86 Architektur bei den Rotate-Befehlen: Bei CL=0 bleibt es 
unverändert. Das ist so ungefähr die dümmstmögliche Art, einen Befehl zu 
definieren.

Der Zirkus, den man in Implementierungen aufführen muss, um damit sauber 
umzugehen, kann wirklich sehenswert sein. AMDs K5 führte solche Befehle 
spekulativ aus, wie bedingte Sprungbefehle, in der Annahme von CL!=0. 
War dann doch CL=0, wurde der Befehl abgebrochen und neu aufgesetzt.

mh schrieb:
> Aber auch dafür wird es vermutlich einen guten Grund gegeben haben

Nicht wirklich. Das ist einfach nur das, was dabei rauskommt, wenn man 
den Befehl bitweise in der Schleife ausführt (Microcode). Und nicht im 
Traum auf die Idee kommt, dass es nach der ersten 8086/8088 Generation 
noch weitere geben könnte. Hätte man das C Bit für CL=0 als undefiniert 
deklariert, wäre die Hardware die gleiche geblieben und den Nachfolgern 
wäre der Zirkus erspart geblieben.

Jedenfalls hat das bei Intel Tradition. Auch bei der Definition der 
Segmentierung des protected Mode beim 286 hat Intel nicht weiter als bis 
zum nächsten Laternenpfahl gedacht, worüber seither Generationen von 
Prozessorentwicklern ausgiebigst fluchen. Das gehörte beispielsweise zu 
den Gründen, weshalb der Pentium Pro bei Win9x keinen Stich machte, der 
Pentium MMX besser abschnitt.

mh schrieb:
> Die Aussage basiert auf der Erfahrung von mehr als 40 Jahren seit diese
> Entscheidung gefällt wurde.

Diese Planlosigkeit hat die Performance aller segmentiert arbeitenden 
Betriebssysteme auf x86 behindert, oder den Aufwand beträchtlich erhöht 
(ab Pentium II). Spätestens beim 486 dürfte Intel sich bereits in den 
Hintern gebissen haben, also schon wenige Jahre später.

> Prozesorentwickler folgender Generationen hätten das auch ändern können

Und hätten damit die heilige Kuh "Kompatibilität" geschlachtet. Nö, 
statt dessen wurde aufwändiges Snooping implementiert, um Modifikationen 
der Segment-Deskriptoren im Speicher zu erkennen.

(prx) A. K. schrieb:
> Axel S. schrieb:
>> [1] oder gibt es Ausnahmen? Ich kenne keine, aber ich würde mich auch
>> nicht als Kenner historischer oder seltsamer Architekturen bezeichen
>
> MIPS gehört zu den Ausnahmen und ist weder historisch noch seltsam.

Da habe ich mir ja ein Ei gelegt. MIPS ist ja geradezu mainstreamig.

> Bei tiefem Pipelining oder superskalarer Implementierung ist ein
> Statusregister ausgesprochen aufwändig zu implementieren, von
> Out-of-Order ganz zu schweigen.

Ja gut, verkettete Operationen gibt es abseits der ALU-Flags ja auch 
genug. Da ist dann halt nix mehr mit out-of-order. Es sei denn, man 
versteht das als Warnung a'la "Elevator Out Of Order" :)


(prx) A. K. schrieb:
> NB: Besonders perfide ist eine Architektur, bei denen aus dem Befehl
> selbst nicht hervorgeht, ob das Carry-Bit ein Ergebnis des Befehls ist,
> oder unverändert bleiben soll. Etwa die sowohl historische als auch
> seltsame x86 Architektur bei den Rotate-Befehlen

Ja gut. x86 gewinnt den Sonderpreis für Seltsamkeit. Das ist da 
sozusagen Programm. Weil du ja auf das Usenet verweist, ein 
Signaturspruch den ich eine Weile verwendet habe, kommt mir da in den 
Sinn:

> Das ist halt der Unterschied: Unix ist ein Betriebssystem mit Tradition,
> die anderen sind einfach von sich aus unlogisch. -- Anselm Lingnau

x86 ist einfach von sich aus unlogisch, inkonsistent, seltsam. Aber 
wenigstens hat die ALU ein Carry-Flag. Es ist also nicht seltsam im 
ursprünglichen Sinn.

Axel S. schrieb:
> Ja gut, verkettete Operationen gibt es abseits der ALU-Flags ja auch
> genug. Da ist dann halt nix mehr mit out-of-order. Es sei denn, man
> versteht das als Warnung a'la "Elevator Out Of Order" :)

Die Reduktion der Performance durch die Abhängigkeiten sind (meist) 
weniger das Problem, als vielmehr der Aufwand, sie überhaupt zu 
festzustellen und die zu Inhalte verwalten. Eine OoO Implementierung von 
x86 hat nicht nur Renaming der Integer-Register an der Backe, sondern 
muss dies auch noch mit (meist) 3 verschiedenen Teile der Statusflags 
tun. Das erhöht den Aufwand erheblich.

Das "meist" bezieht sich auf den Pentium 4, bei dem Intel sich die 
Arbeit drastisch vereinfachte. Alle Teile eines Integers sind ein 
einziges Objekt, egal ob AL, AH und der Rest von EAX. Und alle 
Statusbits sind ein einziges Objekt. Damit handelte Intel sich einen 
Rattenschwanz von Scheinabhängigkeiten ein, weil ein Befehl, der 
irgendein Statusflag setzte, alle anderen mit durchreichen musste.

Das klingt harmloser als es ist:

1

l1: adc eax, [ebx,esi*4]

2

    dec esi

3

    jns l1

DEC interessiert sich nicht für das C-Flag, weder rein noch raus, 
weshalb die in der Latenz sehr kritischen Ladeoperationen weit vor den 
Additionen durchgeführt werden können. Mehrere voneinander getrennte 
Dataflows, der tiefere Sinn von OoO. Der P4 koppelt diese jedoch. Mit 
drastischen Folgen.

Da der P4 das C-Flag der Addition durch die DEC Operation durchschleust, 
von der ADC nun ebenso abhängt, serialisiert sich der Code weitestgehend 
und die Latenz des Speicherzugriffs schlägt voll durch. Nicht mehr 1 
Takt pro Iteration, wie bei anderen x86, sondern Latenz+2 Takte.

mh schrieb:
> Ich frag mich wie absolut unfähig die Konkurrenz gewesen sein muss, wenn
> Intel schon so planlos war.

Die wurde an die Wand gespielt. Solange der Strom aus der Steckdose kam, 
konnte man halt Gatter ohne Ende an die Front werfen. Ironie der 
Geschichte, dass mittlerweile Acorn ja inzwischen letztlich das erreicht 
hat, womit sie eigentlich vor 30+ Jahren direkt gegen Intel angetreten 
waren: die omnipräsente Plattform zu sein.

mh schrieb:
> Die Spielregeln waren für alle gleich, oder?

Nö, es gibt ja noch sowas wie Marktmacht eines Quasi-Monopolisten.

mh schrieb:
> Ich kenne die Faktoren nicht, die sie bei der Entscheidung
> abwägen mussten

Es hat offensichtlich keinerlei Abwägung stattgefunden, es fand keine 
Entscheidung statt, weil man nicht darüber nachdachte. Man hat exakt das 
Verhalten in die Referenz geschrieben, das bei der Implementierung 
implizit rauskam.

Beim ROR/C-Problem hätte es ausgereicht, statt CF=unchanged bei CL=0 in 
die Doku CF=undefined reinzuschreiben. Das hätte nicht einmal 
nennenswert Druckerschwärze gekostet.

Bei den Segment-Descriptoren hätte es ausgereicht, einen sowieso als NOP 
ausgeführten Befehl als etwas ähnlich wie "clear descriptor cache" zu 
deklarieren. Auch hier hätte sich an der Hardware mangels eines echten 
Caches reinweg nichts geändert, nur wäre diesmal ein wenig Doku fällig 
gewesen.

Sollte x86 nicht Assemblerlevel kompatibel zum 8080 sein? Soweit ich 
mich erinnere, gab's dafür extra einen Converter. Das Problem historisch 
also mindestens schon beim 8080/85 liegen.

Abdul K. schrieb:
> Sollte x86 nicht Assemblerlevel kompatibel zum 8080 sein? Soweit ich
> mich erinnere, gab's dafür extra einen Converter. Das Problem historisch
> also mindestens schon beim 8080/85 liegen.

8080 hat nur Rotates um exakt 1 Bit. Das Problem tritt nur bei Rotates 
auf, deren Anzahl Bits nicht per Befehl bekannt ist, sondern im Register 
steht, inklusive 0.

(prx) A. K. schrieb:
> Alle Teile eines Integers

Korrektur: Alle Teile eines Integer-Registers

Abdul K. schrieb:
> Sollte x86 nicht Assemblerlevel kompatibel zum 8080 sein?

Naja, x86 ist 16 Bit, der 8080 ist 8 Bit ... was meinst Du?

Der Z80 ist aber aus dem 8080 entstanden und hat zusätzliche Kommandos.


Gruß
Jobst

Jobst M. schrieb:
> Naja, x86 ist 16 Bit, der 8080 ist 8 Bit ... was meinst Du?

Die 8088/86 waren so gebaut, dass sich alle alten 8080-Befehle gut darin 
umsetzen liessen.

Dieser Vorgabe verdankt x86 beispielsweise die Befehle LAHF und SAHF.

Egon D. schrieb:
>> Wieviele Jahre ohne ernste Konkurrenz hat x86 angehäuft?
>
> M.E. gar keine.
> Traditionell gab es u.a. die 68'000er-Serie; später kamen
> der PowerPC und DEC Alpha; die sind m.E. alle technisch
> gediegener als x86

Wobei man zu Intels Ehrenrettung sagen muß, daß sie auch "ordentliche" 
Architekturen konnten. Z.B. i860 oder i960. Sie sind vom Erfolg des x86 
einfach überrannt worden und mußten nachher kompatibel zu allen seinen 
Macken bleiben. Alle ihre Versuche, aus dem x86 Markt auszubrechen und 
mit anderen Architekturen Fuß zu fassen (i860, Itanium) sind 
gescheitert.

Und es lag nicht an technischen Unzulänglichkeiten. Die Kompatibilität 
zum Alten (vulgo: die Trägheit der Massen) war einfach stärker. Aus dem 
gleichen Grund wird uns C als Programmiersprache auch "ewig" erhalten 
bleiben. Trotz der (manchmal besseren) Konkurrenz.

Axel S. schrieb:
> Wobei man zu Intels Ehrenrettung sagen muß, daß sie auch "ordentliche"
> Architekturen konnten.

Durchaus. Die erkennt man mühelos daran, dass sie tot sind. ;-)
Dem MCS-96 als Nachfolger des nur für kurze Lebensdauer konzipierten 
8051 erging es nicht besser.

Ob man das doch sehr spezielle an den Programmierer durchgereichte 
Pipelining des 860 allerdings wirklich als "ordentlich" bezeichnen kann?