Entwickler-Ecke
Algorithmen, Optimierung und Assembler - schnelle Addition
DevilFish - So 28.09.08 19:10
Titel: schnelle Addition
Hallo Leute,
hat jemand eine Ahnung ob es eine Möglichkeit gibt 2 Integer schneller zu addieren als mit inc? (ohne Assembler)
mfg DevilFish
alzaimar - So 28.09.08 19:16
Kann ich mir nicht vorstellen.
wazup - So 28.09.08 19:19
Delete - So 28.09.08 19:21
Das dürfte aber auch nicht schneller sein.
Gausi - So 28.09.08 19:23
Irgendwo hab ich mal gelesen, dass x := x + y und inc(x,y) genau denselben Bytecode erzeugen.
Delete - So 28.09.08 19:24
Ich auch, das war IIRC im Delphi-Treff.
elundril - So 28.09.08 19:26
is ja auch irgendwie verständlich das der compiler solche rechenoperationen auf ein minimum kürzt. warum sollt delphi eine schnelle und eine langsame addition haben, wäre ja ein bisschen unsinnig, oder?
lg elundril
Hidden - So 28.09.08 19:31
Naja.. *2 wird ja afaik auch nicht in shl umgewandelt, oder?^^(belehrt mich bitte eines besseren :lol:)
Edit: Eventuell könntest du den Wertebereich einschränken und mit Byte, etc. arbeiten. Müsste vom Prinzip her ja schneller gehen.
platzwart - So 28.09.08 20:28
weshalb sollte *2 nicht durch shl ersetzt werden? mit bytes sollte es auch nicht schneller gehen, da auf einem 32 bit system immer 32 bits parallel geladen/gespeichert werden ;)
Delete - So 28.09.08 20:32
Dann müsste der Compiler ja überprüfen, ob der Multiplikator eine 2er Potenz ist.
Hidden - So 28.09.08 20:54
 DeddyH hat folgendes geschrieben: |
| Dann müsste der Compiler ja überprüfen, ob der Multiplikator eine 2er Potenz ist. |
Das wäre ja ein entsetzlicher Prüfaufwand :lol:
elundril - Mo 29.09.08 09:01
ja aber beim compilieren wäre es ja egal. immerhin dauert so eine abfrage ja nicht ewig.
Delete - Mo 29.09.08 09:20
Ich wollte damit ausdrücken, dass sich vermutlich niemand die "Mühe" macht, um ein Quentchen mehr Speed herauszuholen, aber ich kann mich auch irren.
Hidden - Mo 29.09.08 09:46
@elundriel: hast du die Smileys deaktiviert oder so?^^
@DeddyH: Es benötigt ja nun wirklich kaum Zeit, und, wenn so etwas ein paar millionen Mal ausgeführt wird..
Um zum Thema zurückzukehren: Eine schnellere Addition ist vermutlich nicht möglich, das ist schon durchoptimiert.
Wozu brauchst du denn eine Schnellere? Wenn sie in einer Schleife läuft, kann man das vielleicht irgendwie zusammenfassen?
mfG,
alzaimar - Mo 29.09.08 09:50
So wie ich das sehe, wird sowohl "x:=x*2" als auch "x := x shl 1" in "x := x+x" kompiliert (D6), oder sehe ich das falsch?
elundril - Mo 29.09.08 09:57
| Hidden hat folgendes geschrieben: |
@elundriel: hast du die Smileys deaktiviert oder so?^^
|
ne, meine antwort war auch eig. auf diesen post bezogen:
| DeddyH hat folgendes geschrieben: |
| Dann müsste der Compiler ja überprüfen, ob der Multiplikator eine 2er Potenz ist. |
und da seh ich beim besten willen kein smilie. ( hab sogar den bildschirm in alle richtungen gedreht, kein smilie! ;-) )
lg elundril
Lossy eX - Mo 29.09.08 09:58
Gausi: Ja habe ich auch. In der CPU Ansicht meines Delphis. ;) Und die Aussage stimmt vollkommen. Das ist gleich. Das Bytecode INC (Assembler) kann nur ein Register erhöhen. Alles andere ist dann immer ADD.
DeddyH: Das kommt meiner Meinung nach immer auf den Einsatz an. Wenn das eine ganz normale Rechnung ist, dann spielt es sicher keine Rolle ob der Code jetzt 0.08 oder 0.02 Millisekunden benötigt. Allerdings wenn diese Stelle 1-10 Mio mal aufgerufen wird oder sehr zeitkritisch ist, dann lohnt es sich mitunter mal zu schauen ob man da nicht evtl. was machen kann.
Multiplikation: Also was Delphi dort teilweise macht ist mitunter spannend. ;)
*2 in bytecode "add eax, eax"
*3 in bytecode "lea eax, [eax+eax*2]"
*4 in bytecode "shl eax, $02"
*5 in bytecode "lea eax, [eax+eax*4]"
*6 in bytecode "add eax, eax; lea eax, [eax+eax*2]" (Aufgeteilt in *2 und *3)
Bei einer konstanten Multiplikation im Code wehrt sich Delphi so lange es geht gegen eine echte Multiplikation. Bei Variable * Variable kann so etwas aber nicht zum Tragen kommen. Dann muss immer multipliziert werden. Denn der Aufwand da etwas zu überprüfen wäre vermutlich größer als die Ersparniss.
Bytes statt Integer: Mitunter kann man da sogar das Gegenteil erreichen von dem was man haben will. Denn die Register sind normal 32 Bit groß und wenn du aber nur einen kleinen Teil davon haben möchtest passiert es schon mal, dass die anderen Bits des Registers gelöscht werden müssen. Außerdem ist der Bytecode zu Integer * Integer kürzer als zu Byte * Byte. Aber wenn es keine extrem kritische Stelle ist macht das vermutlich alles keinen riesigen Unterschied.
Durch die Cachetechnik der CPU werden aber üblicher sowieso ca 16 Bytes (abhängig vom System) aus dem Hauptspeicher in den Cache übertragen. Ob man nun 1 oder 4 Byte haben möchte spielt dabei keine Rolle. Außer es überlappt sich in 2 Cacheblöcken.
DevilFish: Aber um auf deine Frage zu kommen. Was hast du denn genau damit vor? Denn für mich klingt deine Frage schon ein bisschen so als hättest du ein konkretes Problem. Vielleicht solltest du das mal etwas genauer Schildern. Ich denke, wenn du ein konkretes Problem beschleunigen möchtest, dann bringt das viel mehr als nur einen Teil davon beschleunigen zu wollen. Denn das was Delphi in der Regel an Code erzeugt ist schon sehr ausreichend. Häufig hängt es an den Strukturen die man selbst verwendet. ;)
Delete - Mo 29.09.08 10:02
Es ging doch nicht darum, ob ich als Programmierer shl bzw. shr verwende, sondern ob der Compiler dies bei 2er-Potenzen automatisch macht.
DevilFish - Mo 29.09.08 10:26
Also meine Millionenschleife sieht ungefähr so aus, und nach ein par Tests habe ich gemerkt das die Additionen mit inc ziemlich bremsen. Gut aber wies aussieht kann man da wohl nichts machen. Auf jeden Fall danke für die vielen Antworten.
Die Schleife dient übrigens zur verschlüsselung von Daten mittels BlowFish.
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
| Type
T4Bytes = packed record case Integer of
0: (Byte: array[1..4] of Byte);
1: (Total: Cardinal);
end;
TPSBox = Record
PBox : array[0..17] of Cardinal;
SBox : array[0..3,0..255] of Cardinal;
end;
Procedure TForm1.Encrypt;
var Buffer : array[1..512] of T4Byte;
L,R,L1,FL,AnzahlEnrcypr,d,c : Cardinal;
LB : T4Byte;
PSBox : TPSBox;
begin
ErzeugePSBox(PSBOX);
For d := 1 to AnZahlEncrypt do begin
L := Buffer[d*2-1].total;
R := Buffer[d*2].total;
For c := 0 to 15 do
begin
L := L XOR PSBox.PBox[c];
LB.total := L;
FL := 0;
inc(FL,PSBox.SBox[0,LB.Byte[1]]);
inc(FL,PSBox.Sbox[1,LB.Byte[2]]);
FL := FL XOR PSBox.SBox[2,LB.Byte[3]];
inc(FL,PSBox.SBox[3,LB.Byte[4]]);
R := R XOR FL;
L1 := L;
L := R;
R := L1;
end;
L1 := L;
L := R;
R := L1;
R := R XOR PSBox.PBox[16];
L := L XOR PSBox.PBox[17];
Buffer[d*2-1].total := L;
Buffer[d*2].total := R;
end;
end; |
DevilFish
Flamefire - Mo 06.10.08 12:21
dein problem ist nicht das Inc() was sehr schnell ist sondern der Zugriff auf das array
Bzw sogar ein array of
PACKED record
versuch wenigstens das "packed" wegzunehmen, dann ist es schon schneller
außerdem solltest du versuchen, mit pointern statt array-indizes zu arbeiten
3.:
Delphi-Quelltext
1:
2:
| FL := 0;
inc(FL,PSBox.SBox[0,LB.Byte[1]]); |
solltest du ersetzen durch
Delphi-Quelltext
1:
| FL := PSBox.SBox[0,LB.Byte[1]]; |
Sind viele kleine Sachen die bei dir bremsen...
platzwart - Mo 06.10.08 12:32
| Zitat: |
3.:
Delphi-Quelltext 1:
2:
| FL := 0;
inc(FL,PSBox.SBox[0,LB.Byte[1]]); |
solltest du ersetzen durch
Delphi-Quelltext 1:
| FL := PSBox.SBox[0,LB.Byte[1]]; | |
falls das nicht schon der compiler wegoptimiert. ansonsten gebe ich dir recht, es kommt nicht nur auf die operationen an, sondern auch auf den datentyp und wie man mit ihm umgeht.
jaenicke - Mo 06.10.08 15:07
Das ist ja nicht nur diese Zeile, sondern der ganze Block:
DevilFish hat folgendes geschrieben  : |
Delphi-Quelltext 1:
2:
3:
4:
5:
| FL := 0; inc(FL,PSBox.SBox[0,LB.Byte[1]]); inc(FL,PSBox.Sbox[1,LB.Byte[2]]); FL := FL XOR PSBox.SBox[2,LB.Byte[3]]; inc(FL,PSBox.SBox[3,LB.Byte[4]]); | |
Das sind 5 Zuweisungen, 3 Additionen und 1 xor. Warum nicht:
Delphi-Quelltext
1:
2:
| FL := (PSBox.SBox[0,LB.Byte[1]] + PSBox.Sbox[1,LB.Byte[2]]) XOR PSBox.SBox[2,LB.Byte[3]]
+ PSBox.SBox[3,LB.Byte[4]]; |
Wieviel Gewinn das bringt, hab ich mir nicht genauer angeschaut, aber so kann der Compiler die Zwischenergebnisse optimiert speichern und muss die nicht in die Variable packen und wieder herausholen. Inwiefern der Compiler den ursprünglichen Code selbst schon dahingehend optimiert weiß ich nicht.
DevilFish - Mo 06.10.08 20:58
Danke nochmals für die Tips. Ich hab das auch soweit umgesetzt, aber bringt nicht wirklich viel. (ist auch schlecht zu vergleichen wenn die Unterschiede marginal sind)
Ich bin so bei 15Mb/s - 16Mb/s Datenrate mit lesen und schreiben.
Zum vergleich im Leerlauf also ohne die Verschlüsselung komm ich so auf 20Mb/s - 22Mb/s.
Flamefire
| Zitat: |
| außerdem solltest du versuchen, mit pointern statt array-indizes zu arbeiten |
Ich bin erst seit 4 Wochen am programmieren und weiß was ein Pointer ist, aber ich weiß grad nicht wie ich das umsetzen soll. Das würde bedeuten 512 bzw 256*4 +18 Pointer zu haben die jeweils auf ein Element des Array zeigen (und selber nicht als Array deklariert sind). Wenn ich das richtig verstanden habe. Ich wäre über ne kleine Starthilfe erfreut :).
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!