Optimierungen an Modulo
-
Erste Frage:
Ein Modulo ist im Assembler ja dasselbe wie eine Division, nur dass der Wert aus einem anderen Register genommen wird. Wie siehts aus in folgendem Stück Code:
int a = 42; int b = a / 10; int c = a % 10;
Angenommen, der Compiler berechnet hier die Berechnungen nicht zur Compilezeit weg (Oder a steht erst zur Laufzeit fest), wird hier im Assembler zu einer Division optimiert?
Zweite Frage:
Teilbarkeiten lassen sich ja oft einfach feststellen, wie zum Beispiel Teilbar von 2 (1er bit auf 0). Ich weiß nicht, ob sich andere Teilbarkeits Regeln, vor allem kompliziertere, wie die Teilbarkeit durch 11, einfach aufs Binärsystem übertragen lassen, aber wird hier von den Compilern optimiert?
-
Dein Compiler hat mit sehr großer Wahrscheinlichkeit ein ASM Listing generieren.
Da kannst du selber nachschauen.Prinzipiell würde ich aber beide Optimierungen von meinem Compiler erwarten.
-
Das lässt sich generell so nicht beantworten, weil im Standard nix dazu festgelegt ist. Die Compilerhersteller können hier rumoptimieren wie sie wollen, solange die Sematik die gleiche bleibt.
Am besten guckst du dir einfach mal den erzeugten ASM-Code von deinem Compiler mit deinen benutzen Optimierungseinstellungen an.Edit: War zu lahm.
-
Visual Studio 2010:
int b = a / 10; 00C416C3 mov eax,66666667h 00C416C8 imul dword ptr [esp+4] 00C416CC sar edx,2 00C416CF mov ecx,edx 00C416D1 shr ecx,1Fh 00C416D4 add ecx,edx int c = b % 10; 00C416D6 mov eax,66666667h 00C416DB imul ecx 00C416DD sar edx,2 00C416E0 mov eax,edx 00C416E2 shr eax,1Fh 00C416E5 add eax,edx 00C416E7 lea edx,[eax+eax*4] 00C416EA add edx,edx 00C416EC sub ecx,edx
-
Auch wenn du so ein bisschen zu den C++-Puristen zählst, die C-Bibliothek sollte man nicht vergessen:
http://www.cplusplus.com/reference/clibrary/cstdlib/div/
Das wird garantiert optimiert, dazu ist es da.In der C-Biliothek gibt es so manche Schätzchen.
edit: In diesem Fall würde ich jedoch davon ausgehen, dass ein Compiler das heutzutage erkennt. Es ist relativ offensichtlich, wie das zu optimieren ist. Die genannte Funktion zählt eher zu der Sorte die man gebraucht hat, als die Compiler noch nicht so gut waren.
-
314159265358979 schrieb:
Zweite Frage:
Teilbarkeiten lassen sich ja oft einfach feststellen, wie zum Beispiel Teilbar von 2 (1er bit auf 0). Ich weiß nicht, ob sich andere Teilbarkeits Regeln, vor allem kompliziertere, wie die Teilbarkeit durch 11, einfach aufs Binärsystem übertragen lassen, aber wird hier von den Compilern optimiert?
Die Regeln gelten in jedem Positionssystem sinngemäß (kannst du dir induktiv leicht herleiten):
In einem Zahlensystem Zur Basis B, kann die Teilbarhkeit durch B-1 anhand der Quersumme, die durch B+1 anhand der alternierenden Quersumme getestet werden. Gleiches gilt für die Teiler von B-1 und B+1.
Die Teilbarkeit durch 2 kann folglich in einem System mit ungerader Basis sowohl an der einfachen als auch an der alternierenden Quersumme erkannt werden.
-
cooky451 schrieb:
Visual Studio 2010:
int b = a / 10; 00C416C3 mov eax,66666667h 00C416C8 imul dword ptr [esp+4] 00C416CC sar edx,2 00C416CF mov ecx,edx 00C416D1 shr ecx,1Fh 00C416D4 add ecx,edx int c = b % 10; 00C416D6 mov eax,66666667h 00C416DB imul ecx 00C416DD sar edx,2 00C416E0 mov eax,edx 00C416E2 shr eax,1Fh 00C416E5 add eax,edx 00C416E7 lea edx,[eax+eax*4] 00C416EA add edx,edx 00C416EC sub ecx,edx
Wenn ich das richtig sehe (Bin kein ASM Experte) hat VS hier nicht optimiert?
camper schrieb:
Die Regeln gelten in jedem Positionssystem sinngemäß (kannst du dir induktiv leicht herleiten):
In einem Zahlensystem Zur Basis B, kann die Teilbarhkeit durch B-1 anhand der Quersumme, die durch B+1 anhand der alternierenden Quersumme getestet werden. Gleiches gilt für die Teiler von B-1 und B+1.
Die Teilbarkeit durch 2 kann folglich in einem System mit ungerader Basis sowohl an der einfachen als auch an der alternierenden Quersumme erkannt werden.Wieder was gelernt. Kann man auch allgemeine Teilbarkeitsregeln für jede beliebige Zahl in jedem beliebigen Zahlensystem aufstellen?
-
Die Teilbarkeitsregelnbeiträge habe ich dorthin http://www.c-plusplus.net/forum/290591 geschubst.
-
@cooky451:
Du hast falsch abgetippt (int c = b % 10;
gibt's in der Frage von 314 nicht).
Und ist das "Release" Code, mita = Konstante
, oder vielleicht mita = rand()
um das Wegoptimieren zu unterdrücken?Interessant wäre für mich z.B. ob der Compiler schlau genug ist für
#include <iostream> int main() { int a = 42; int b = a / 10; int c = a % 10; std::cout << b << ", " << c << "\n"; }
Kann er alles wegoptimieren, und Konstanten ausgeben?
#include <iostream> #include <cstdlib> #include <ctime> int main() { std::srand(std::time(0)); int a = rand(); int b = a / 10; int c = a % 10; std::cout << b << ", " << c << "\n"; }
Checkt er dass er nur 1x div (bzw. den div-ersatzcode) braucht, oder rechnet er für / und % doppelt?
(Ich bin mir ziemlich sicher dass er in beiden Fällen schlau genug ist, aber habs nicht ausprobiert)
-
hustbaer schrieb:
Kann er alles wegoptimieren, und Konstanten ausgeben?
Nur mit G++ getestet, der macht es, was ich auch sehr überraschend gefunden hätte, wenn nicht. Dazu ist ein Compiler da.
Checkt er dass er nur 1x div (bzw. den div-ersatzcode) braucht, oder rechnet er für / und % doppelt?
Gute Frage, mein Assembler ist nicht gut genug dafür . Ich vermute schon.
-
hustbaer schrieb:
@cooky451:
Du hast falsch abgetippt (int c = b % 10;
gibt's in der Frage von 314 nicht).
Und ist das "Release" Code, mita = Konstante
, oder vielleicht mita = rand()
um das Wegoptimieren zu unterdrücken?Mein Post wurde wohl versehentlich verschoben:
cooky451 schrieb:
314159265358979 schrieb:
Dann hat cookie sich wohl vertippt
Jau, ärgerlich. Hätte eigentlich sofort auffallen sollen, verdammt.
int b = a / 10; int c = a % 10; 008616C3 mov ecx,dword ptr [esp+4] 008616C7 mov eax,66666667h 008616CC imul ecx 008616CE sar edx,2 008616D1 mov eax,edx 008616D3 shr eax,1Fh 008616D6 add eax,edx 008616D8 lea edx,[eax+eax*4] 008616DB add edx,edx 008616DD sub ecx,edx
-
Ah, in den anderen Fred hab ich nicht geguckt.
D.h. er ...
* multipliziert statt zu dividieren
* check dass er "c = a - 10 * b" rechnen kann
* rechnet "10 * b" als "2 * (b + 4 * b)" mit nur zwei instructions (lea+add)Sehr schön.
Und ich nehme an du hast für die Initialisierung von a keine Konstante genommen, ja?
-
hustbaer schrieb:
Und ich nehme an du hast für die Initialisierung von a keine Konstante genommen, ja?
Nein, dann haut er alles raus. Habe einfach eine Zahl von cin gelesen.