Schnelle Alternativen für Multiplikation mit 2

[DeddyH]

Wenn man Ahnung davon hat (ich habe sie nicht), dann kann man sich die verschiedenen Varianten ja einmal im resultierenden Assembler-Code ansehen. Allerdings denke ich, dass, wenn überhaupt Geschwindigkeitsunterschiede bestehen sollten, diese wahrscheinlich allenfalls marginal sind. Wichtiger ist es IMO, dass der Code lesbar und nachvollziehbar (und somit auch leicht wartbar) ist. Wenn man also mit Bitmasken hantiert, dann ist das Bitshifting in diesem Kontext logisch. In anderen Zusammenhängen könnte es den Betrachter (das ist man im Zweifel selbst nach ein paar Monaten) nur verwirren.

[shmia]

Multiplikationen und Divisionen mit den Konstanten 2,4,8,16,... werden vom Delphi Compiler automatisch in einen Links- oder Rechtshift übersetzt.

Delphi-Quellcode:

x := x * 256;
x := x shl 8;

Man kann sich also die Shift-Operationen hier sparen.
Was anderes ist es, wenn erst während der Laufzeit der Multiplikator oder Divisor feststeht.
Dann macht eine Shiftoperation natürlich Sinn.

[Mavarik]

Zitat von shmia:

Multiplikationen und Divisionen mit den Konstanten 2,4,8,16,... werden vom Delphi Compiler automatisch in einen Links- oder Rechtshift übersetzt.

Delphi-Quellcode:

x := x * 256;
x := x shl 8;

Man kann sich also die Shift-Operationen hier sparen.
Was anderes ist es, wenn erst während der Laufzeit der Multiplikator oder Divisor feststeht.
Dann macht eine Shiftoperation natürlich Sinn.

Theorie und Praxis...

Delphi-Quellcode:

Aus: A := A * 8; wird

Add ebx,ebx
Add ebx,ebx
Add ebx,ebx

Aus: A := A div 2; wird

mov ecx,2
mov eax,ebx
cdq
idev ecx
mov ebx,eax

Mavarik

[Namenloser]

Wieso macht der Compiler das? Alignment? Ich hab’s mal getestet, und es ist (auf meinem Core 2) sowohl langsamer als die echte Multiplikation als auch das Shifting:

Code:

Add, Add, Add: 1435
Shl: 421
IMul: 1264

(das ganze sind Millisekunden für jeweils 1 000 000 000 Durchläufe)

[Mavarik]

Zitat von NamenLozer:

Wieso macht der Compiler das?

Habe aufgegeben eine Antwort auf diese Frage zu suchen...

Mavarik

[Delphi-Laie]

Ich erlaube mir, dieses leicht angetagte Thema noch einmal aufzuwärmen.

Der (bzw. die) Delphicompiler optmiert (optimieren) also in mehrerlei Hinsicht. Da dieses Forum auch ein Lazarusforum ist: Vermutlich stecken im Freepascalcompiler bzw. in Lazarus noch mehr Optmierungspotential. Doch Vorsicht bei den Eliminationen mit vermeintlich oder tatsächlich schnelleren Alternativen: Die Ergebnisse sind nicht immer denen in/mit Delphi gleich und können auch inkonsistent sein, siehe http://bugs.freepascal.org/view.php?id=20853.

[gammatester]

Wenn überhaupt ist der sog. "Freepascal-Bug" ein Delphi-Bug: pred und succ sollten den gleichen Ergebnistyp haben wie das Argument. FreePascal, BorlandPascal und VirtualPascal machen das auch, nur Delphi in seiner unendlichen Weisheit definiert
function Pred(X: Ordinal): Integer; und behauptet dann noch frech:

Zitat:

The result, of the same type as X, is the predecessor of X.

(Quelle: http://docwiki.embarcadero.com/Libraries/en/System.Pred) Mit folgendem Programm

Delphi-Quellcode:

{$Q-,R-}
var
  b,c: byte;
begin
  b := 0;
  c := pred(b);
  writeln(c:6, pred(b):6);
end.

liefern FPC, BP7 und VP2.1 jeweils 255 255, die Delphi-Versionen D2 .. D12 allerdings 255 -1

[Aphton]

Zitat von DeddyH:

Wenn man Ahnung davon hat (ich habe sie nicht), dann kann man sich die verschiedenen Varianten ja einmal im resultierenden Assembler-Code ansehen.

Klar

Zitat von DeddyH:

Allerdings denke ich, dass, wenn überhaupt Geschwindigkeitsunterschiede bestehen sollten, diese wahrscheinlich allenfalls marginal sind. Wichtiger ist es IMO, dass der Code lesbar und nachvollziehbar (und somit auch leicht wartbar) ist.

Jain. Kommt auf das Einsatzgebiet an. Wenn es hochperformant sein soll, dann spielt es natürlich eine Rolle.
Bei solchen Unklarheiten wende ich Trick #17 an -> einen Geschwindigkeitstest machen.
Da sieht man dann anschließend, welche Variante schneller ist (am eigenen Rechner)

[DeddyH]

Wobei so ein Test aber auch nur dann aussagefähig ist, solange unter exakt gleichen Bedingungen verglichen wird.

[Mavarik]

Warum ist alles langsammer als früher obwohl die Rechner 100x schneller geworden sind?

Weil keiner mehr optimiert...

Früher hab ich mit der Z80 Bibel von Rodnay Zaks für jede - wichtige - Routine die Taktzüglen zusammen addiert um zu schauen, ob ich nicht mit anderen Befehlen 2 oder 3 sparen kann.

Also warum nicht shl verwenden... Dann bist Du Dir sicher das es aus so benutzt wird... Falls der Compiler es anders sieht!

Mavarik