Bitweiser Zugriff

[Daniel Thoma]

Hallo Martin,

So ich hab jetzt meine C-Kenntnisse zusammengekratzt und das jetzt mal doch implementiert:

  
#include <stdio.h>  
#include <stdlib.h>  
#include <time.h>  
  
int array[32];  
  
int bitreadshift(int i, int j) {  
  return (i & (1 << j)) != 0;  
}  
  
int bitreadarray(int i, int j) {  
  return (i & array[j]) != 0;  
}  
  
int main() {  
  int count = 100000000;  
  
  int i = rand();  
  int x = 0;  
  for (int j = 0; j < 32; ++j) {  
    array[j] = 1 << j;  
  }  
  
  for (int j = 0; j < count; ++j) {  
    /* int k = 1 + (int) (31.0 * (rand() / (RAND_MAX + 1.0))); */  
    for (int k = 0; k < 32; ++k) {  
      x += bitreadshift(i, k);  
    }  
  }  
  long int time2 = clock() / (CLOCKS_PER_SEC / 1000.0);  
  for (int j = 0; j < count; ++j) {  
    /* int k = 1 + (int) (31.0 * (rand() / (RAND_MAX + 1.0))); */  
    for (int k = 0; k < 32; ++k) {  
      x += bitreadarray(i, k);  
    }  
  }  
  long int time3 = clock() / (CLOCKS_PER_SEC / 1000.0);  
  
  printf("Shift: %d\n", time2 - time1);  
  printf("Array: %d\n", time3 - time2);  
  printf("%d\n", x);  
}  

Das aufsummieren der Bits habe ich drin, weil ich irgendwas machen muss, damit mir der Compiler nicht den Code wegoptimiert, dessen Ergebnisse ich sowieso nicht brauche ;-)

Für die misstrauischen habe ich das auch mal disassembliert:

  
080483e0 <bitreadshift>:  
 80483e0:       55                      push   %ebp  
 80483e1:       89 e5                   mov    %esp,%ebp  
 80483e3:       8b 45 08                mov    0x8(%ebp),%eax  
 80483e6:       8b 4d 0c                mov    0xc(%ebp),%ecx  
 80483e9:       5d                      pop    %ebp  
 80483ea:       d3 f8                   sar    %cl,%eax  
 80483ec:       83 e0 01                and    $0x1,%eax  
 80483ef:       c3                      ret  
  
080483f0 <bitreadarray>:  
 80483f0:       55                      push   %ebp  
 80483f1:       89 e5                   mov    %esp,%ebp  
 80483f3:       8b 45 0c                mov    0xc(%ebp),%eax  
 80483f6:       8b 55 08                mov    0x8(%ebp),%edx  
 80483f9:       5d                      pop    %ebp  
 80483fa:       85 14 85 a0 97 04 08    test   %edx,0x80497a0(,%eax,4)  
 8048401:       0f 95 c0                setne  %al  
 8048404:       0f b6 c0                movzbl %al,%eax  
 8048407:       c3                      ret  
 8048408:       90                      nop  
 8048409:       8d b4 26 00 00 00 00    lea    0x0(%esi),%esi  

Auffällig finde ich, dass da bei der Array-Variante anscheinend die AND-Operation wegoptimiert wird. Ohne die Befehle nachzulesen, weiß ich nicht, was da genau passiert ;-)
Die Funktionen werden inlined, das was tatsächlich ausgeführt wird, sieht also nochmal etwas anders aus. Nur findet man da durch das ganze umsortieren der Befehle fast nichts mehr wieder.

Auf meinem Athlon 64 geben sich die beiden Varianten nicht viel.
Compiliert habe ich das ganze mit gcc -std=C99 -O3 -o test test.c
Mit O1 schneidet die Array-Variante deutlich schlechter ab. (Faktor 1.5 oder so). Aber auch die Shift-Variante braucht da dopplet so lang obwohl sich da der erzeugte Maschinencode kaum unterscheidet (nur Anordnung der Befehle, was natürlich einiges ausmachen kann).

Ich bin mit etwas Recherche auf den Barrel Shifter gestoßen. Damit sollte shiften ähnlich wie addieren in log(Bits) Schritten gehen. Irgendwo dort stand, dass Intelprozessoren das mal hatten, der Pentium 4 aber nicht mehr. Wie das nun bei aktuellen Prozessoren aussieht, bleibt noch herauszufinden...

Grüße

Daniel