IPC 2014

Bitoperationen – Heute noch aktuell?

Beim programmieren einer Onlinezeitung bin ich eher zufällig über Bitoperationen gestolpert. Bitoperationen sind mathematische Operationen , die früher in der hardwarenahen Programmierung eingesetzt wurden. Heute existieren diese Operatoren zwar noch in (fast) allen Programmiersprachen, aber kaum jemand verwendet sie noch. Deshalb untersuche ich, ob das an mangelnder Perfomance liegen könnte.

Welche Operationen untersuche ich

Ich untersuche nur: Schiebeoperationen, Inkrement und Dekrement

Schiebeoperationen:

Mit Schiebeoperationen können Multiplikation mit bzw. Division durch 2er-Potenzen effektiv berechnet werden.

echo 9 << 3; // 9*2^3 = 72
echo 72 >> 3; // 72/2^3 = 9

Inkrement und Dekrement

Mit Inkrement und Dekrement kann man zu einer Variable eins addieren bzw. subtrahieren.

Natürlich gibt es aber auch noch weitere Bitoperationen.

Mein Testscript:

$durchläufe=2000000;
 
echo '<h1>Verschiebeoperationen</h1><br />';
$t_ref=microtime(true);
for ($x=1;$x<=$durchläufe;$x++)
  {
  $c=(9 * 8);	  
  }
$t_ref=microtime(true)-$t_ref;
echo 'Zeit "* 8": '.($t_ref).' s (100 %)<br />';flush();
 
$t1 = microtime(true);
for ($x=1;$x<=$durchläufe;$x++)
  {
  $c=(9 << 3);	  
  }
$t1=microtime(true)-$t1;
echo 'Zeit "<< 3": '.($t1).' s ('.round(100/$t_ref*$t1).'%)<br />';flush();
echo '<br />';
 
$t_ref=microtime(true);
for ($x=1;$x<=$durchläufe;$x++)
  {
  $c=(72 / 8);	  
  }
$t_ref=microtime(true)-$t_ref;
echo 'Zeit "/ 8": '.($t_ref).' s (100 %)<br />';flush();
 
$t1 = microtime(true);
for ($x=1;$x<=$durchläufe;$x++)
  {
  $c=(72 >> 3);	  
  }
$t1=microtime(true)-$t1;
echo 'Zeit ">> 3": '.($t1).' s ('.round(100/$t_ref*$t1).'%)<br />';flush();
echo '<hr />';
 
echo '<h1>Inkrement</h1><br />';
$c=0;
$t_ref=microtime(true);
for ($x=1;$x<=$durchläufe;$x++)
  {
  $c=$c+1;	  
  }
$t_ref=microtime(true)-$t_ref;
echo 'Zeit "x=x+1": '.($t_ref).' s (100 %)<br />';flush();
 
$c=$durchläufe;
$t1 = microtime(true);
for ($x=1;$x<=$durchläufe;$x++)
  {
  $c++;	  
  }
$t1=microtime(true)-$t1;
echo 'Zeit "x++": '.($t1).' s ('.round(100/$t_ref*$t1).'%)<br />';flush();
echo '<hr />';
 
echo '<h1>Dekrement</h1><br />';
$c=0;
$t_ref=microtime(true);
for ($x=1;$x<=$durchläufe;$x++)
  {
  $c=$c+1;	  
  }
$t_ref=microtime(true)-$t_ref;
echo 'Zeit "x=x-1": '.($t_ref).' s (100 %)<br />';flush();
 
$c=$durchläufe;
$t1 = microtime(true);
for ($x=1;$x<=$durchläufe;$x++)
  {
  $c++;	  
  }
$t1=microtime(true)-$t1;
echo 'Zeit "x--": '.($t1).' s ('.round(100/$t_ref*$t1).'%)<br />';flush();
echo '<hr />';

Ergebnis

Bei mir sind die Zeitunterschiede bei Inkrement und Dekrement sehr gering (+-2%).
Die Unterschiede bei den Verschiebeoperationen sind bei mir aber zwischen 30 und 50% deutlich spürbar.

Was haltet ihr davon? Nutzt ihr heute noch Bitoperationen? Oder sind sie euch zu kompliziert?

Ergänzung von Jan Hoersch:
Habe grad die Frage durchgecheckt, ob das Vertauschen von Variabeln über Bitoperationen schneller ist :)
Nach ein Paar kleinen Durchläufen hab ich nun ein Ergebnis für das Vertauschen von Variabeln über Bitoperationen. Und ich kann schonmal sagen…es lohnt sich sowas von nicht.
Vorallem für größere Texte fangen die Bitoperationen an zu stottern und erschreckend große Zeiten auszugeben, wobei sich das normale Vertauschen über eine zusätzliche Temp-Variable fast nicht auf die Zeit auswirkt.
Für C kann ich bisher nichts sagen, aber in PHP lohnt es sich nicht.
Das angehängte Skript hat aus 10 Durchläufen einen Mittelwert errechnet, zusätzlich inkrementiert es die Anzahl der Buchstaben, die es zu vertauschen gilt. Aber die Zeiten und der Graph denke ich sprechen für sich selber :)

Das Skript hat diese Ausführungszeiten benötigt. Übersichtlich als Graph ausgegeben sieht das Ganze so aus:
Vergleich Variablentausch über Bitoperation
Vielen Dank an Jan für den kleinen Zusatztest!




7 Kommentare bisher »

  1. Tobias sagt

    am 18. August 2010 @ 06:26

    Also ich nutze ab und zu auch Bitoperationen, nicht nur in PHP, aber auch nur dann wenn es eine performancekritische Applikation ist, ansonsten sieht das denke ich einfach zu komplitiert aus. Es muss ja auch noch lesbar bleiben…

  2. Daniel sagt

    am 18. August 2010 @ 06:55

    Ich frage mich, ob man Inkrementierer und Dekrementierer wirklich als Bitopertion sehen sollte, oder einfach als Abkürzung. Auch wenn es die Befehle auch auf Assembler-Ebene gibt, handelt es sich eigentlich "nur" um eine Addition von 1 oder -1. Auf Hardware-Ebene ist irgendwie ja alles eine (oder mehrere) Bitoperation ;-)
    ++ und — sind natürlich überhaupt nicht wegzudenken, die kommen in so gut wie jeder unausgerollten For-Schleife vor. Auch sonst verwende ich sie gern. Gab es nicht auch mal einen Benschmark in dem ++$i und $i++ vergleichen wurden? In C soll es ja angeblich einen kleinen Unterschied machen ;-)

    Bitoperationen wie das Shifting habe ich in PHP wohl noch nie verwendet. Es ist aber interessant zu sehen, dass es Vorteile gibt und in Zukunft werde ich bei Zeitkritischen Aufgaben jetzt versuchen darauf zu achten.

  3. Lars sagt

    am 18. August 2010 @ 08:30

    Seit wann ist denn In-/Dekrement eine Bitoperation?
    "x++" ist doch einzig und alleine eine Kurzform für "x=x+1". Natürlich kriegt man daher keine Performance-Unterschiede, weil intern das gleiche gemacht wird.

  4. Uli sagt

    am 18. August 2010 @ 09:22

    Ich benutze (in C) bitmäßiges XOR gerne noch zum Austausch von Variableninhalten, so spare ich mir eine Puffervariable.

    a = a ^ b;
    b = a ^ b;
    a = a ^ b;

    Ob das performanter ist hab' ich, ehrlich gesagt, noch nie ausprobiert, sollte aber ein wenig bringen…

  5. Daniel sagt

    am 18. August 2010 @ 10:24

    Uli: Irgendwie fürchte ich, dass 3 Zuweisungen + 3 XOR teurer ist als 3 Zuweisungen + 1 neue Variable. Könnte man natürlich mal messen. Nett anzuschauen ist es allemal :-) Diese Schreibweise find ich ja noch niedlicher: a=a^(b=(a=a^b)^b) ;-)

  6. anderer jan sagt

    am 18. August 2010 @ 12:58

    Bitoperationen sind nach wie vor wichtig. ich verwende sie immer noch bei performancekritischen angelegenheiten…aber inkrement und dekrement seh ich jetzt auch nicht als bitoperation an…
    mein liebling ist immer noch:
    c = ((a>>1)&0x7f7f7f00)+((b>>1)&0x7f7f7f00)+(a&b&0×01010100)+((a&0xff)|(b&0xff));
    mischen von 2 farben in rgba form :)
    dadurch spart man sich ne schleife

    zu dem anderen…das mit dem umtauschen…ja…ich hab grad nen test laufen gehabt…es hat viel mehr vorteile die extra variable zu verwenden :)
    ich mach gleich ein paar charts dazu…gimme a minute

  7. hauke sagt

    am 18. August 2010 @ 14:15

    @Daniel: Dann gibt's aber Ärger mit theoretisch standardkonformen C. Man darf nämlich eigentlich keine Variable mehrfach zwischen 2 Sequent Points ändern, deswegen ist auch sowas wie a = a++ ziemlich böse. ;)

    Jan, das RGB-Ding ist cool. Danke, ich glaube, das merk ich mir!

    Und allgemein, Bitoperationen sind wichtig. Man braucht sie nicht oft, aber ich finde sie hier und da wirklich nützlich.

Komentar RSS · TrackBack URI

Hinterlasse einen Kommentar

Name: (erforderlich)

eMail: (erforderlich)

Website:

Kommentar: