Hi.
Wenn ich mit grossen Zahlen arbeiten muss, kam mir eine Idee, mit der
das richtig elegant funktioniert. Da ich diese Methode dauernd einsetze,
dachte ich mir, ich könnte diese Methode hier mal vostellen. Für alle,
die einfach gerne AVR Assembler programmieren.
Aufgabe: Einen 64-Bit Wert inkrementieren.
Problem: Solche Werte sind üblicherweise im RAM zu Hause. Also müsste
man 8 mal lds + die eigentliche Inkrementierung + 8 mal sts machen. Da
lds und sts jeweils 4 Bytes belegen, kostet so eine einfache
"value++"-Aktion direkt mal 64 Bytes Flash.
Meine Lösung:
1
ldiz RAM_p1_starts
2
sec
3
ldi r25,4
4
0:
5
ld r24,Z
6
adc r24,Gzero
7
st Z+,r24
8
dec r25
9
brne 0b
Der Flashbedarf ist konstant. Es ist egal, ob man einen 32-Bit oder
einen 256-Bit Wert inkrementiert. Gzero enthält den Wert 0. ldiz ist ein
selbsterklärendes Makro.
Nachtrag: Da ich kein C programmiere, kam mir gerade vor Abschicken des
Beitrags die spontane Frage in den Sinn, wie es der Compiler macht?
Vielleicht ist die Idee ja gar nicht so neu... :/
Upsi. Da habe ich den Code aus einem Projekt kopiert, aber da wird nur
ein 32-Bit Wert erhöht. Die Zahl in r25 bestimmt die Anzahl der Bytes.
Korrekt für 64-Bit ist also ldi r25,8. Vielleicht kann das mal ein Mod
kurz ändern.
Guter Tipp. Das brcc baue ich da noch mit ein. Danke. :)
Das elegante an der Methode ist weniger die Schleife, sondern das sec
vor der eigentlichen Schleife.
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.)
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
voidinc64(uint64_t*valp)
2
{
3
32:fc01movwr30,r24
4
(*valp)++;
5
34:2081ldr18,Z
6
36:3181lddr19,Z+1;0x01
7
38:4281lddr20,Z+2;0x02
8
3a:5381lddr21,Z+3;0x03
9
3c:6481lddr22,Z+4;0x04
10
3e:7581lddr23,Z+5;0x05
11
40:8681lddr24,Z+6;0x06
12
42:9781lddr25,Z+7;0x07
13
44:a1e0ldir26,0x01;1
14
46:14d0rcall.+40;0x70<__adddi3_s8>
15
48:2083stZ,r18
16
4a:3183stdZ+1,r19;0x01
17
4c:4283stdZ+2,r20;0x02
18
4e:5383stdZ+3,r21;0x03
19
50:6483stdZ+4,r22;0x04
20
52:7583stdZ+5,r23;0x05
21
54:8683stdZ+6,r24;0x06
22
56:9783stdZ+7,r25;0x07
23
58:0895ret
24
25
uint64_tbla,blub,usw;
26
27
voidtest(void)
28
{
29
inc64(&bla);
30
5a:80e7ldir24,0x70;112
31
5c:90e0ldir25,0x00;0
32
5e:e9dfrcall.-46;0x32<inc64>
33
inc64(&blub);
34
60:88e6ldir24,0x68;104
35
62:90e0ldir25,0x00;0
36
64:e6dfrcall.-52;0x32<inc64>
37
inc64(&usw);
38
66:80e6ldir24,0x60;96
39
68:90e0ldir25,0x00;0
40
6a:e3cfrjmp.-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ß.
Jan schrieb:> Problem: Solche Werte sind üblicherweise im RAM zu Hause. Also müsste> man 8 mal lds + die eigentliche Inkrementierung + 8 mal sts machen. Da> lds und sts jeweils 4 Bytes belegen, kostet so eine einfache> "value++"-Aktion direkt mal 64 Bytes Flash.
Deine Optimierung ist eine Optimierung auf Codesize. Das passt überhaupt
nicht zu dem von dir selbst gewählten Thema des Threads, das suggeriert
nämlich, dass es um eine Optimierung auf Speed gegangen wäre.
Und wenn das das Ziel war, ist die Lösung völlig daneben!
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.
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.
(prx) A. K. schrieb:> Bei CL=0 bleibt es> unverändert. Das ist so ungefähr die dümmstmögliche Art, einen Befehl zu> definieren.
Aber auch dafür wird es vermutlich einen guten Grund gegeben haben, auch
wenn es aus heutiger Sicht eine dumme Wahl war. Und es ist vermutlich
nicht die dringendste Entscheidung, die ein heutiger x86-Architekt
ändern würde.
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.
(prx) A. K. schrieb:> 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.
Die Aussage basiert auf der Erfahrung von mehr als 40 Jahren seit diese
Entscheidung gefällt wurde. Woher sollten sie damals wissen, dass die
Architektur so lange lebt? Woher sollten sie wissen, dass jede
Entscheidung die sie treffen auf Ewigkeit unveränderlich ist?
Prozesorentwickler folgender Generationen hätten das auch ändern können
... wollten sie nur nicht (mit all den Vor- und Nachteilen).
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.
(prx) A. K. schrieb:> 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.
Ich frag mich wie absolut unfähig die Konkurrenz gewesen sein muss, wenn
Intel schon so planlos war. Wieviele Jahre ohne ernste Konkurrenz hat
x86 angehäuft?
>> 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.
Wie gesagt jede Entscheidung hat Vor- und Nachteile. Ich kenne die
Faktoren nicht, die sie bei der Entscheidung abwägen mussten und kann
sie damit nicht als planlos bezeichnen.
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.
Jörg W. schrieb:> 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.
Die Spielregeln waren für alle gleich, oder? Wenn für x86 mehr Gatter
alle Probleme lösen, funktioniert das auch für die Konkurrenz.
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
mh schrieb:> Ich frag mich wie absolut unfähig die Konkurrenz gewesen> sein muss,
???
Dass die Intel-x86-Linie so eine Supernova werden würde,
konnte m.E. am Anfang niemand sehen oder wissen.
Dazu waren als äußere Einflüsse zusätzlich notwendig, dass...
1. ausgerechnet IBM einen relativ preiswerten Kleincomputer
herausbringen würde, der aus verschiedenen Gründen leicht
nachzubauen war,
2. die Hersteller in Fernost ihre Chance erkennen und
massenhaft billige "Clons" des "IBM-PC" herstellen und
als "IBM-kompatibel" vermarkten würden, und
3. Bill Gates die Weltherrschaft mittels "command.com" und
"autoexec.bat" anstreben und erringen würde.
Die anderen Hersteller sind schlicht von der schieren Menge
der "IBM-kompatiblen PCs" überrollt bzw. durch die dadurch
möglichen Kampfpreise zum Verhungern gezwungen worden.
Mit technischer Exzellenz hatte das nix zu tun...
> 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. Das Problem war aber immer, dass das
Gesamtpaket nicht gestimmt hat -- keiner der Konkurrenten
konnte in Preis UND Leistung mithalten (wie auch, ohne die
Massenbasis des x86). Aufgrund der großen Verbreitung war
in den 90ern im Massenmarkt die "Windows-Kompatibilität" der
Plattform auch das entscheidende Fallbeil. Das ändert(e) sich
erst durch die Verbreitung der mobilen Geräte mit Internet-
Zugang.
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?
Thread beobachten
Seitenaufteilung abschalten