Was ist rechnerisch schneller? simple formel

volkard

net schrieb:

potenzieren kann man bestimmt auch so ähnlich. ist nur die frage ob's schneller ist. wahrscheinlich eher nicht.

für x^3 noch nicht, genauso wie für x*3 der trick x+x<<1 noch nicht schneller als x+x+x ist.

Maschi

randa schrieb:

Du bist mir immernoch einen simplen Beweis schuldig. Es ist erstmal eine Behauptung, zu sagen, mit Bitshifts gewinne ich Performance in einem Programm, und dann nichts zur Untermauerung der Aussage hinzuzufügen. Ich will ein Programm sehen, in dem ich einen Frame mit Bitsthifts hinzugewinne. Alles andere disqualifiziert dich selbst.

Witzig, ich programmiere jetzt bestimmt mal eben ein komplettes Demo (besser gesagt 2, sonst fehlt der Vergleich) um dir zu demonstrieren, dass ich Recht habe. So wichtig ist es mir auch nicht. Wenn du lernresistent bist dann ist das deine Sache... Es scheint aber nicht nur meine Erfahrung zu sein, dass Bitshifting Performance bringen kann.

Wenn du den Thread aufmerksam gelesen hättest dann wüsstest du, dass es nur in manchen Fällen Sinn macht. So einen Fall kann man nicht mal eben konstruieren. Man muss Schwachstellen aufdecken, den Profiler befragen wo es hapert und dann überlegen ob man mit geschickten Alternativoperationen Takte sparen kann.

*lol*

Ich würd dich gern später als mein Bit-Shifter-Assi oder so ähnlich einstellen. Bezahlung könnte gut sein. Kommt darauf an wie gut du bist, also ab ran an die Demo.

mfg marcel

Es scheint aber nicht nur meine Erfahrung zu sein, dass Bitshifting Performance bringen kann.

Hast es schon richtig erkannt, trotzdem sollte man nicht auf nicht allg-gültige Aussagen zurückschliessen. Entweder du benutzt Bit-Operatoren (von Anfang an wo es geht) oder du lässt es, da am Ende eines Projekts, ein Quellcode mehrere tausend Zeilen Quellcode enthalten kann und du mit deiner Kinderspielereioptimierung vielleicht 0.00001% Geschwindigkeit herausholen kannst. Was wiederum Zeit in Anspruch nimmt und die Kosten deines Produkts in die höhe treibt. Und ohne vernünftige UNIT-Tests hast du erst recht die Arschkarte.

Cu

Maschi

Wen man keine Ahnung hat ... einfach mal Fresse halten! Ich sprach nie von Anwendungsentwicklung, sondern ausschließlich vom Grafikbereich und da auch nur von Flaschenhälsen. Wenn du mal den Thread lesen würdest, dann würdest du auch erkennen, dass ich irgendwo auch mal gesagt habe, dass Allgemeinaussagen in puncto Optimierung Mist sind.

Maschi schrieb:

Wen man keine Ahnung hat ... einfach mal Fresse halten! Ich sprach nie von Anwendungsentwicklung, sondern ausschließlich vom Grafikbereich und da auch nur von Flaschenhälsen. Wenn du mal den Thread lesen würdest, dann würdest du auch erkennen, dass ich irgendwo auch mal gesagt habe, dass Allgemeinaussagen in puncto Optimierung Mist sind.

unsympathisches arrogantes Arschloch

Maschi

Ich hasse es einfach wenn man mir Sachen unterstellt die ich so nie gesagt habe und wenn Leute nicht bereit sind selber nachzudenken.

Maschi schrieb:

Seher schrieb:

unsympathisches arrogantes Arschloch

Dir würde eine sympathischere Antwort auf "Bit-Shifter-Assi" einfallen? Lass hören: Ich bin bereit ein besserer Mensch zu werden...

bei dir is hopfen und malz verloren. zum glück bist du mit einer arroganten klugscheisser art ein bedauerlicher einzelfall.

volkard

ich bin hier der, der leute beleidigt.
thread für ein weilchen geschlossen.

Assi == Assistent, du solltest mir deswegen keine böswilligkeit unterstellen
Grafikbereich == ist Anwendungsentwicklung, ausser du programmierst controller für gk, etc

randa

Morgen
Schade das der Thread geschlossen wurde, nur weil sich ein paar nicht benehmen konnten. Ich will die Diskussion mal weiterführen, weil ich das interessant finde...

Also Maschi, folgende Sache:
Wie ich dich verstanden hab, hälst du es für sinnvoll, jeden Takt herauszukitzeln bzw überall Bitshifts zu verwenden, wo es geht.

1)Das hilft dir aber nur, wenn du vorher weißt, das es ein Wert ist, der ein vielfaches von zwei ist. das ist selten der Fall. Wenn doch, wie bestimmst du das zur Laufzeit? Alleine eine if-Abfrage "kostet" dich Takte, also kann man das wieder vergessen.
2)Bei konstanten. Das wars aber auch schon. In einem solchen fall multipliziere ich zum Beispiel immer mit 1/Divisor, was ich vorher ausrechne.
3)Warum bringt Taktezählerei nichts? Wenn du einen 2 Ghz Prozessor hast, hast du 2.000.000.000 (2 Milliarden) Takte in der Sekunde. Wenn du hier um 10, 20, oder 100 Takte optimierst, ist das dem Prozessor wurscht. Das ist, als würdest du in einer Anwendung, die 500 MB RAM belegt, um jeden int (4 Byte) kämpfen, damit nicht zuviel Speicher draufgeht. Also sinnlos.
4)Wieviele Divisionen gibts denn Tatsächlich in einer Grafik-Applikation? Sicher einige, aber nicht so viele, das man das signifikant spüren würde, wenn man stattdessen Bitshifts verwenden könnte und würde. Es geht ja letztendlich darum, das wir mit dem Gesunden Menschenverstand am ende auch was davon merken, aber das tun wir nicht.
5)Die Takte, die du meinst zu gewinnen, verlierst du bei der nächstbesten Funktion, die ein einziges int-Argument mehr nimmt => noch sinnloser.
6)Ich habe mal einen Test gemacht, wieviel Performance ein einzelner Bitshift gegen eine einzelne Multiplikation bw. Division mehr bringt.
Test mit 4 Milliarden Schleifendurchläufen a 10 Schleifendurchläufen a 18 Divisionen und 6 Multiplikationen (edit: natürlich die Zahlen usw. gleich gewählt):

Mit Bitshift: 
159.51 sec
Ohne:
181.72 sec

mit Athlon 64 @ 2 Ghz

Das sind etwa 14% mehr Leistung. Bei den wenigen Anwenungsfällen für Bitshifts also nichts. Meineswissens gibt es kein handelsübliches Programm, das nur annähernd so viele Divisionen und Multiplikationen durchführt. Und wenn ja, die paar Sekunden kann dann auch jeder mehr warten.

Es kann in einer High-Level Programmiersprache nicht Sinn sein, um jede Variable zu kämpfen. Das kannst du mit Assembly machen. Fazit also, durch Bitshifts kannst du in C++ Programmen keine Performance gewinnen. Das mag bei Assembly-Programmen bzw. Programmen, die sehr Low-Level sind, anders sein, aber das ist nicht der Bereich der üblichen Programmierung (wie zum Beispiel Grafikprogramme, Spiele usw.).

Edit:

Es scheint aber nicht nur meine Erfahrung zu sein, dass Bitshifting Performance bringen kann.

Du solltest dich nicht auf andere Stützen, ich wollte einen Beweis von dir, da du deine Sache so vehement verteidigt hast.

ethereal

randa schrieb:

3)Warum bringt Taktezählerei nichts? Wenn du einen 2 Ghz Prozessor hast, hast du 2.000.000.000 (2 Milliarden) Takte in der Sekunde. Wenn du hier um 10, 20, oder 100 Takte optimierst, ist das dem Prozessor wurscht. Das ist, als würdest du in einer Anwendung, die 500 MB RAM belegt, um jeden int (4 Byte) kämpfen, damit nicht zuviel Speicher draufgeht. Also sinnlos.

Nicht ganz! Nimm' mal wieder das beliebte Beispiel Grafikprogrammierung. Stell dir vor, du musst bestimmte Pixel zeichnen, die nicht unbedingt aufeinander folgen, so dass eine einfache Inkrementierung des Arrays nicht möglich ist, z.B. so eine Media-Player-Visualisierung. Dann bist du darauf angewiesen, jedes Pixel anzusprechen (Formel siehe einen meiner älteren Beiträge in diesem Thread). Gewinnst du da bei einem Pixel, sagen wir mal, 10 Takte (wahrscheinlich sind's wesentlich mehr), kannst du bei einer hohen Auflösung (1600x1200,1024x786) gut und gern gezwungen sein, z.B. 100.000 Pixel zu zeichnen, wenn nicht mehr (1600x1200 hat 1.920.000 Pixel, da sind 100.000 Pixel ziemlich wenig). Macht schonmal 100.000*10 Takte Unterschied, und das ist doch schonmal eine beachtliche Zahl, oder? Dazu addieren sich z.B. noch die Takte der Threads, die im Hintergrund laufen, und dann kann es wirklich mal dazu kommen, dass deine Anwendung ein Frame (du bist ja immer auf Frames aus) oder mehr langsamer wird. Analoges gilt für Schleifen, bei denen du jeden Durchlauf neu berechnen musst und nicht einfacher aus vorherigen Werten ableiten kannst.

randa

100.000*10=1.000.000 Takte => 0.05% Performance gewonnen, = bei 25 Bilder/s einen Frame gewonnen, geht man davon aus, dass die gesamte Leistung dem Programm zur Verfügung steht (insgesamt wärens mehr).
Dein Beispiel zieht, wenn du mir die Formel zeigst und sichergehen kannst, das alle entsprechenden Operationen durch Bitshifts ersetzt werden können. Wieviel Takte gewonnen werden können, ist außerdem (denke ich mal) Prozessorabhängig, von daher würde ich mit Takten etwas vorsichtig umgehen. Hat der Prozessor ein (oder zwei oder drei...) Megahertz mehr, ist dein Rechenbeispiel wieder nichtig. Du bewegst dich einfach auf zu Prozessornahem Nieveau, um mit einer solchen Rechnung was zu gewinnen.

Außerdem trifft dies nur einen Spezialfall, in der 3D-Grafikprogrammierung indizierst du den Array inkrementell (oder wie auch immer, aber nicht durch divisionen ). Außerdem ist die ganze Bitshift-Sache hauptsächlich für Divisionen gültig, denn bei Mutliplikationen ist der Performanceunterschied viel geringer.

(du bist ja immer auf Frames aus)

Du kannst auch mit Nanosekunden rechnen.

Walli

randa schrieb:

Also Maschi, folgende Sache:
Wie ich dich verstanden hab, hälst du es für sinnvoll, jeden Takt herauszukitzeln bzw überall Bitshifts zu verwenden, wo es geht.

Du kannst echt nicht lesen, oder?

Maschi schrieb:

Ich sprach nie von Anwendungsentwicklung, sondern ausschließlich vom Grafikbereich und da auch nur von Flaschenhälsen.

Btw: Stelle dir doch mal eine Methode in einem Programm vor, die 80% der ganzen Rechenzeit ausmacht. Wenn man da Takte spart dann macht sich das ganz ordentlich bemerkbar...

randa

MaSTaH schrieb:

Du kannst echt nicht lesen, oder?

Das kann ich, doch einmal präsentiert er sich so, einmal so. Ich glaube eher, er weiß selbst nicht was er sagt. Mal sagt er, man kaönne keine Allgemeinaussagen treffen, aber er gibt seine Version so, als ob er die Wahrheit kennt.

btw, wieso so agressiv?

Zu deiner anderen Aussage: Das hat nichts mit meinen Argumenten zur Bitshift-Sache zu tun. Es ist wurscht, ob ich das in einer Funktion oder in 10 berechne. Zu den "gesparten Takten" hab ich mich ja mittlerweile genug ausgelassen, also lies nochmal. Meine Position kennt man, ich bin eher gespannt auf Gegenargumente.

net 0

eigentlich sollte man beim rausholen von speed immer darauf achten, dass die hardware schön ackert. jede softwarelösung ist ist da weit unterlegen. es soll ja noch leute geben, die verwenden auf 'nem pentium eine sinus lookup-table und bemühen nicht den integrierten rechenknecht. auf den ollen 8-bittern, die noch nicht mal mul/div-instructions hatten, hätte z.b. eine simulation dieser rechenarten durch shifts und additionen sicher was gebracht, aber heute nicht mehr. ..und wenn man code optimiert und solche sachen wie instruction cache, pipelining, etc. ausser acht lässt, kann's schnell nach hinten losgehen. so gibt es z.b. prozessoren, die sind bei byte-operationen langsamer als mit 16-bit words. alles fies eben.

btw: manchmal wirds schneller, wenn man zeitintensive prozesse parallelisiert z.b. indem man mehrere threads einsetzt. (ich glaub informatiker sagen 'teile und herrsche' dazu). gerade bei heutigen gui-anwendungen, wo die cpu 99% der zeit herum-idled ist das sinnvoll. aber das ist ein anderes thema...

Ein Gegenargument ist die 80-20 Regel, die du sicherlich kennst. Ich verstehe nicht, was daran so schwer ist. Man kann doch akzeptieren, dass es ein paar wenige Stellen im Code geben kann, wo sich sowas lohnt.
Natürlich war die Idee, zur Laufzeit des zu prüfen, ob man shiften könnte, Müll. Man hat auch nicht immer eine 2er Potzenz. Aber manchmal kann man ja einfach dafür sorgen, dass man eine hat.

Im großen und Ganzen kommt man mit guten Algorithmen und Datenstrukturen sicherlich am weitesten. Vor allem bleibt man damit auch noch am meisten Plattformunabhängig. Shiften ist allerdings auch recht plattformunabhängig, also mit keinerlei Nachteilen verbunden.

randa

Optimizer schrieb:

Ein Gegenargument ist die 80-20 Regel, die du sicherlich kennst. Ich verstehe nicht, was daran so schwer ist. Man kann doch akzeptieren, dass es ein paar wenige Stellen im Code geben kann, wo sich sowas lohnt

Ich habe das oben, bei etherals Bemerkung (die bisher die Überzeugendste war, wenn die Formeln tatsächlich komplett mit Bistshifts opimiert werden können), bereits akzeptiert. Es mag noch ein paar andere Bereiche geben, von denen ich aber glaube, dass sie sehr speziell sind und nichts mit gewöhnlicher Software, wie sie hier von Forumsmitgliedern und auch sonst enwtickelt wird, zu tun haben. Bestimmt gibts auch bestimmte Hardwarenahe Programme, in denen es nötig sein kann.
Beim Rest (beim Großteil) der Fälle sollte man seine Zeit besser in wirkliche Optimierung umsetzen, denn eigentlich reden wir (oder ich? ) hier von ganz normalen Programmen und nicht von Spezialfällen.

volkard

randa schrieb:

Das sind etwa 14% mehr Leistung.

poste mal ein messprogramm in standard-c++ (damit ich nachmessen kann), denn mich verwirrt die these, daß shiften hier 14% mehr speed bringt.

Walli

randa schrieb:

btw, wieso so agressiv?

Ich bin nicht aggressiv. Mich nervt es nur ein wenig, dass du keine Argumente bringst und alles als blöde Bitshifterei abtust. Du stellst hier abenteuerliche Rechnungen auf, die zu 99% deiner Phantasie entspringen. Fakt ist: Leute wie John Carmack und Co. haben bereits eindrucksvoll bewiesen, was Bitshiftereien, inline-asm, loop-unrolling, lookup-tables und sonstige Optimierungen ausmachen "können", wenn man sie denn an den richtigen Stellen einsetzt.

randa schrieb:

Meine Position kennt man, ich bin eher gespannt auf Gegenargumente.

Das ist das Problem... Die ignorierst du.