Schnelle Alternativen für Multiplikation mit 2

[Delphi-Laie]

Hallo Delphi-/Pascalfreunde!

Seit Jahren benutze ich die Funktionen succ und pred statt +1 und -1 für Integervariablen, weil ich mal las, daß diese effizienter (=schneller) ausgeführt werden können.

Seit einiger Zeit benutze ich auch shl und shr statt Multiplikationen bzw. Divisionen mit Zweierpotenzen, denn auch diese sollen effizienter bzw. schneller sein.

Nun aber meine Frage: Für die Multiplikation mit 2 kann man statt shl 1 auch Variable+Variable benutzen. Ich vermute, daß auch die Addition schneller als die Multiplikation ist, doch was ist das schnellste: Die Linksverschiebung (shl) oder die Addition? Ich vermute, daß es shl ist. Doch was meint oder wißt Ihr dazu?

[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.

[himitsu]

Zitat:

Zitat von Delphi-Laie (Beitrag 1146174)

Seit Jahren benutze ich die Funktionen succ und pred statt +1 und -1 für Integervariablen, weil ich mal las, daß diese effizienter (=schneller) ausgeführt werden können.

Es gibt auch noch Inc und Dec.

Ja, diese sind theoretisch schneller,
aber nein, praktisch sind sie es dann doch nicht, da der Compiler sowieso schon die +1 zu INC optimiert. (wenn man die Codeoptimierung nicht deaktivert hat)

Zitat:

Zitat von Delphi-Laie (Beitrag 1146174)

Seit einiger Zeit benutze ich auch shl und shr statt Multiplikationen bzw. Divisionen mit Zweierpotenzen, denn auch diese sollen effizienter bzw. schneller sein.

Das Stimmt aber nur für vorzeichenlose Typen.
Bei z.B. dem vorzeichenbehafteten Integer würde dieses das Vorzeichen (-) verstören.

Aber auch hier optimiert der Compiler ein

Delphi-Quellcode:

div 2

und

Delphi-Quellcode:

* 2

über die entsprechenden Schiftoperationen, wenn er es erkennt.

Theoretisch wäre die Addition langsamer als ein Shift und die Multiplication langsamer als eine Addition ... also vom mathematischen Aufwand her,
aber erstmal optimiert der Compiler schon ganz ordentlich und dann verfügen auch nochmal die CPUs/FPUs über entsprechende Optimierungen, um besser/schneller rechnen zu können.

[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.

[Delphi-Laie]

Danke für Eure Antworten!

Zitat:

Zitat von himitsu (Beitrag 1146177)

Zitat:

Zitat von Delphi-Laie (Beitrag 1146174)

Seit Jahren benutze ich die Funktionen succ und pred statt +1 und -1 für Integervariablen, weil ich mal las, daß diese effizienter (=schneller) ausgeführt werden können.

Es gibt auch noch Inc und Dec.

Ja, natürlich, diese sogar ausschließlich, wenn es um dieselbe Variable geht. War in dem Augenblicke nicht gegenwärtig.

[DeddyH]

Wobei Succ() und Pred() als Funktionen mit Call-By-Value-Parametern auch auf Properties anwendbar sind, Inc() und Dec() hingegen nicht. Aber das nur am Rande, hat mit dem Thema nicht viel zu tun.

[Aphton]

Zitat:

Zitat von DeddyH (Beitrag 1146176)

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:

Zitat von DeddyH (Beitrag 1146176)

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

[himitsu]

Im Prinzip hat es DeddyH schon gesagt:
Möglichts "einfachen" Code schreiben, denn der ist besser wartbar
und das ist oftmals eigentlich wichtiger, als eine Nanosekunde weniger zu benötigen.

Der Compiler optimiert dann so Einiges und wenn dann immernoch ein paar Takte zuviel sind, welche unbedingt weg müssen, dann kann man immernoch optimieren.

Wie gesagt, mit SHL muß man aufpassen, da es keinen Pascal-Befehl für ein "signed shift" gibt. (k.A. warum)

PS: Ich hab auch schonmal 'ne ganze Weile dran gesessen und mit Assembler rumoptimiert, mit dem Ergebnis, daß die Codeoptimierung etwa genauso gut war und somit sinnlos Zeit verschwendet wurde, welche wo anderes nötiger gewesen wäre.

[DeddyH]

Und wenn man schon optimiert, dann muss man das auch an den richtigen Stellen tun. Was nützt es mir, wenn mein Programm bei einer einfachen Rechenoperation 2 Taktzyklen einspart, dann aber 2 Millionen Datensätze sequentiell durchsucht?

[Delphi-Laie]

Zitat:

Zitat von Mavarik (Beitrag 1146280)

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

Weil keiner mehr optimiert...

Richtig, Windows ist das beste Beispiel.

Ich hatte noch "das Glück der frühen Geburt", Wordperfect 5, Turbo-Pascal 6.0 (und vorherige Versionen) und Geoworks Ensemble (Versionsnummer nicht mehr geläufig) kennenzulernen. Alle drei waren n.m.W. in Assembler bzw. Maschinencode geschrieben und hinsichtlich Geschwindigkeit und Stabilität einfach exzellent. Bei Geoworks Ensemble hatte man durchaus das Gefühl, vor einem Computer jenseits der PC-Architektur zu sitzen. Auch der Starwriter war sehr schnell und stabil, überlebte und mündete letzlich in das Open Office.

Allerdings gab es damals noch kein präemtives Multitasking, das muß man dem heutigen Windows zugutehalten.

Zitat:

Zitat von himitsu (Beitrag 1146284)

und das ist oftmals eigentlich wichtiger, als eine Nanosekunde weniger zu benötigen.

Wie hier schon erwähnt, die Menge/Masse macht es. Und Windows macht nahezu jeden PC zur Schnecke, wenn es denn will. Lediglich bei den heutigen Mehrkernprozessoren im x-Gigahertz-Bereich habe ich den Eindruck, daß Billys Mannen bei deren Rechengeschwindigkeit mit dem Programmieren ihrer Schnecken- und Zeitlupenroutinen auch nicht mehr hinterherkommen.

[gammatester]

Zitat:

Zitat von himitsu (Beitrag 1146284)

Wie gesagt, mit SHL muß man aufpassen, da es keinen Pascal-Befehl für ein "signed shift" gibt. (k.A. warum)

Nein, shl ist unproblematisch, da sowohl bei shiften als auch bei der Multiplakation die hochsten Bits im Nirvana landen und die Ergebnisse gleich sind (wenn die Checks ausgeschaltet sind).

Problematisch ist shr, da hier offensichtlich auch bei signed Typen der Assemblerbefehl SHR und nicht SAR benutzt wird:

Delphi-Quellcode:

var
  x,y: longint;
begin
  x := -10;
  y := x shr 1;
  writeln(y);
  y := x div 2;
  writeln(y);
end.

Die Ergebnisse sind 2147483643 und -5. Aber selbst SAR ist noch nicht äquivalent zu div, da zwar -10 SAR 1 = -5 ist aber -1 SAR 1 = -1 und -1 div 2 = 0.

[Luckie]

Zitat:

Zitat von Delphi-Laie (Beitrag 1146293)

Ich hatte noch "das Glück der frühen Geburt", Wordperfect 5, Turbo-Pascal 6.0 (und vorherige Versionen) und Geoworks Ensemble (Versionsnummer nicht mehr geläufig) kennenzulernen. Alle drei waren n.m.W. in Assembler bzw. Maschinencode geschrieben und hinsichtlich Geschwindigkeit und Stabilität einfach exzellent. Bei Geoworks Ensemble hatte man durchaus das Gefühl, vor einem Computer jenseits der PC-Architektur zu sitzen. Auch der Starwriter war sehr schnell und stabil, überlebte und mündete letzlich in das Open Office.

Dann vergleich aber mal die Funktionalität uns Usabillity. Da liegen Welten zwischen damals und heute.

Zitat:

Wie hier schon erwähnt, die Menge/Masse macht es. Und Windows macht nahezu jeden PC zur Schnecke, wenn es denn will. Lediglich bei den heutigen Mehrkernprozessoren im x-Gigahertz-Bereich habe ich den Eindruck, daß Billys Mannen bei deren Rechengeschwindigkeit mit dem Programmieren ihrer Schnecken- und Zeitlupenroutinen auch nicht mehr hinterherkommen.

Das ist Unsinn. Ich habe hier XP mit einem etwas älteren Prozessor und ich kann nicht über ein langsames Windows klagen.

Und wie schon gesagt wurde der Flaschenhals ist selten eine nicht optimierte Rechneoperation, sondern meist der Datentransfer über die Hardware oder schlechte Speicherveraltung.

[jaenicke]

Zitat:

Zitat von Luckie (Beitrag 1146303)

Zitat:

Wie hier schon erwähnt, die Menge/Masse macht es. Und Windows macht nahezu jeden PC zur Schnecke, wenn es denn will. Lediglich bei den heutigen Mehrkernprozessoren im x-Gigahertz-Bereich habe ich den Eindruck, daß Billys Mannen bei deren Rechengeschwindigkeit mit dem Programmieren ihrer Schnecken- und Zeitlupenroutinen auch nicht mehr hinterherkommen.

Das ist Unsinn. Ich habe hier XP mit einem etwas älteren Prozessor und ich kann nicht über ein langsames Windows klagen.

Ich habe selbst mit Windows 7 auf einem ca. 10 Jahre alten Medion Laptop keine Geschwindigkeitsprobleme (der RAM ist auf 1,5 GiB aufgerüstet, sonst alles unverändert). Das startet ähnlich schnell wie XP.

[Mavarik]

Zitat:

Zitat von shmia (Beitrag 1146178)

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:

Zitat von NamenLozer (Beitrag 1146314)

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

Delphi-Quellcode:

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

[Delphi-Laie]

Also auch Delphis Ergebnisse können inkonsistent sein, das war mir neu, danke!

Was von beiden ist nun aber der Fehler?

0 - 1 = -1, also mathematisch stimmt das mithin. Ist man sich jedoch gewahr, welchen Bereich eine Bytevariable (oder eine andere integre Variable mit und ohne Vorzeichen) hat, dann erscheinen die 255 konsistent, logisch und "richtig".

[Medium]

Richtig wäre, bei einem vorzeichenlosen Typen, Pred(0) mit einem Ausnahmefehler zu quittieren, auch ohne Bereichsprüfung. Doof dürfte nur, wie immer sein, dass es vermutlich schon hunderte Prgrämmchen gibt, die sich auf die jeweiligen auch z.T. falschen Verhaltensweisen verlassen, und mit einem nachträglichen Fix "kaputt" gingen. Daher wird eher alles bleiben wie es ist, und bestenfalls die Doku ergänzt/korrigiert.

[negaH]

Zitat:

Zitat von himitsu (Beitrag 1146177)

Theoretisch wäre die Addition langsamer als ein Shift und die Multiplication langsamer als eine Addition ... also vom mathematischen Aufwand her,

Bei aktuellen Intel CPUs sollte die Multiplikation mit 2 mit der Additionsmethode performanter sein als mit einem Linksshift per SHL. Das liegt aber nicht an der ALU dieser Chips sondern an den Fähigkeiten der Piplines der CPU. Der ADD Opcode kann besser piplined werden als der SHL Opcode und das heist letzendlich das mit entsprechenden Opcodes vor und nach dieser Addition die CPU eine bessere Auslastung der Piplines ermöglicht als mit dem SHL Opcode und das ist dann der Performacevorteil.

Gruß Hagen