Schnelle Alternativen für Multiplikation mit 2

[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 von Mavarik:

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 von himitsu:

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 von himitsu:

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 von Delphi-Laie:

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 von Luckie:

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