Bitweiser Zugriff

[Peter Thomassen]

Hallo liebes Forum,

mich interessiert, wie bitweiser Zugriff auf low-level-Ebene ausgeführt wird. Mit PHP schreibt man z.B.

$bit = $foo >> 5 & 1

für das 5. Bit von rechts. PHP sei nur ein Beispiel, in C macht man es wohl ähnlich. Wieviele Schritte führt der Prozessor nun aus?

1.)

• 5 Schritte für den Bitshift
• 1 Schritt für die and-Verknüpfung (oder sind das 32, weil alle Bits verglichen werden?)
  Wegen der Bitverschiebungen hängt die Anzahl der Schritte in diesem Fall vom zu betrachtenden Bit ab.

2.)
Der Compiler erkennt solche Konstrukte und ersetzt sie durch einen direkten Zugriff auf das Bit. Zur Laufzeit ist das also 1 Schritt (unabhängig vom zu betrachtenden Bit).
In welchen Programmiersprachen ist ein solcher direkter Zugriff (entweder per Adressierung im Programmoce oder durch die Compiler-Optimierung) möglich? Ist das überhaupt möglich?

3.)
Hängt die Sache vielleicht vom verwendeten Prozessor ab?

4.)
Gilt vielleicht etwas ganz anderes?

Danke!
Peter

[Der Martin]

Hallo Peter,

mich interessiert, wie bitweiser Zugriff auf low-level-Ebene ausgeführt wird.

das ist eine Operation, die in "Hochsprachen" fast so abgebildet wird, wie sie auf Assemblerebene funktioniert.

Mit PHP schreibt man z.B.

$bit = $foo >> 5 & 1

für das 5. Bit von rechts.

Ja, das ist eine Möglichkeit; wenn man ein Bit testet, ist aber der exakte numerische Wert dieses Bits unerheblich, deswegen wird man in der Regel auf die Shift-Operation verzichten. Schließlich reicht es zu wissen, ob
 $foo & 0x20
ungleich 0 ist.

Wieviele Schritte führt der Prozessor nun aus?

Normalerweise zwei:
 - Operand in ein Register laden
 - UND-Verknüpfung mit Registerinhalt und Konstante
Der dritte Schritt wäre dann schon ein Sprungbefehl, der abhängig davon, ob das Ergebnis der Operation 0 ist, entweder ausgeführt wird oder nicht.

• 5 Schritte für den Bitshift

Nein, selbst wenn man den Shift ausführen würde (was man meist bleiben lässt), ist das bei modernen CPUs nur ein einziger Schritt. Okay, mehrere Arbeitsschritte, aber nur eine Maschineninstruktion.

• 1 Schritt für die and-Verknüpfung (oder sind das 32, weil alle Bits verglichen werden?)

Normalerweise wird eine UND-Verknüpfung mit ALLEN Bits im Register parallel durchgeführt, also je nach Architektur 8, 16, 32 oder gar 64 Bits auf einmal.

Der Compiler erkennt solche Konstrukte und ersetzt sie durch einen direkten Zugriff auf das Bit. Zur Laufzeit ist das also 1 Schritt (unabhängig vom zu betrachtenden Bit).

Viele Compiler sind in der Tat so schlau, diesen Ausdruck zu optimieren.

In welchen Programmiersprachen ist ein solcher direkter Zugriff (entweder per Adressierung im Programmoce oder durch die Compiler-Optimierung) möglich? Ist das überhaupt möglich?

In Assembler auf jeden Fall, aber C ist nahe dran.

Hängt die Sache vielleicht vom verwendeten Prozessor ab?

Ja, natürlich auch. Der legendäre 8bit-Prozessor des C64 (6502 bzw. 6510) konnte zum Beispiel nur um ein Bit pro Befehl schieben. Aber wenn man das sowieso weglässt ...

Schönen Abend noch,
 Martin

[Peter Thomassen]

Hallo Martin,

danke für deine Antwort.

$bit = $foo >> 5 & 1

für das 5. Bit von rechts.

Ja, das ist eine Möglichkeit; wenn man ein Bit testet, ist aber der exakte numerische Wert dieses Bits unerheblich, deswegen wird man in der Regel auf die Shift-Operation verzichten. Schließlich reicht es zu wissen, ob
$foo & 0x20
ungleich 0 ist.

Das klingt in der Tat elegant, allerdings besteht im konkreten Fall die Notwendigkeit, in einer Schleife mehrere Bits zu testen, die an verschiedener Position in verschiedenen Variablen stehen. Diese Fälle lassen sich schlecht explizit angeben.

Nun kann ich 0x20 entweder als Potenz von 2 oder per links-Shift herstellen, oder aber gleich das zu betrachtende Bit nach rechts schieben, wie es das obigen Codebeispiel tut. Oder gibt es hier eine bessere Vorgehensweise?

• 5 Schritte für den Bitshift

Nein, selbst wenn man den Shift ausführen würde (was man meist bleiben lässt), ist das bei modernen CPUs nur ein einziger Schritt. Okay, mehrere Arbeitsschritte, aber nur eine Maschineninstruktion.

Interessieren würde mich der Zeitaufwand. Werden diese Arbeitsschritte parallel oder nacheinander ausgeführt (also Zeitkomplexität O(1) oder O(Bitzahl)? Ich muss zugeben, von Prozessorinterna keine Ahnung zu haben.

Normalerweise wird eine UND-Verknüpfung mit ALLEN Bits im Register parallel durchgeführt, also je nach Architektur 8, 16, 32 oder gar 64 Bits auf einmal.

Also konstanter Zeitaufwand.

Der Compiler erkennt solche Konstrukte und ersetzt sie durch einen direkten Zugriff auf das Bit. Zur Laufzeit ist das also 1 Schritt (unabhängig vom zu betrachtenden Bit).

Viele Compiler sind in der Tat so schlau, diesen Ausdruck zu optimieren.

Das scheint aber im oben beschriebenen Fall nicht möglich, wenn nicht konkret $foo >> 5 geshiftet wird, sondern $foo >> $i oder so.

In welchen Programmiersprachen ist ein solcher direkter Zugriff (entweder per Adressierung im Programmoce oder durch die Compiler-Optimierung) möglich? Ist das überhaupt möglich?

In Assembler auf jeden Fall, aber C ist nahe dran.

Bedeutet das, dass sich in Assembler Bits direkt "per Adresse" auslesen lassen, wie üblicherweise Variablen auch, d.h. ohne es mit 1 zu vergleichen?

Bye,
Peter

[Der Martin]

Hallo Peter,

Schließlich reicht es zu wissen, ob
$foo & 0x20
ungleich 0 ist.

Das klingt in der Tat elegant, allerdings besteht im konkreten Fall die Notwendigkeit, in einer Schleife mehrere Bits zu testen, die an verschiedener Position in verschiedenen Variablen stehen. Diese Fälle lassen sich schlecht explizit angeben.

wenn die Position des abzufragenden Bits schließlich auch noch variabel ist, kommt man fast nicht um eine Schiebeoperation herum - es sei denn, man verfolgt einen tabellenbasierten Ansatz:

$bitmask = Array(0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80);
 ...
 if ($foo & $bitmask[$botposition])
  { ... }

Ich glaube, hier ist PHP wirklich ein schlechtes Beispiel; als Scriptsprache, die erst zur Laufzeit interpretiert wird, sind solche Optimierungen da wohl ein Tropfen im Ozean. Aber in C oder Assembler würde ich diesen Ansatz für zeitkritische Routinen durchaus erwägen. Je nach Rechnerarchitektur kann das tatsächlich schneller sein als die Bitschieberei, denn eine indizierte Adressierung eines Arrays unterstützt jede mir bekannte CPU von sich aus.

Nun kann ich 0x20 entweder als Potenz von 2 oder per links-Shift herstellen, oder aber gleich das zu betrachtende Bit nach rechts schieben, wie es das obigen Codebeispiel tut. Oder gibt es hier eine bessere Vorgehensweise?

Siehe oben. ;-)

Nein, selbst wenn man den Shift ausführen würde (was man meist bleiben lässt), ist das bei modernen CPUs nur ein einziger Schritt.
Interessieren würde mich der Zeitaufwand. Werden diese Arbeitsschritte parallel oder nacheinander ausgeführt (also Zeitkomplexität O(1) oder O(Bitzahl)? Ich muss zugeben, von Prozessorinterna keine Ahnung zu haben.

Das kann man nicht generell für alle Prozessoren sagen. Bei der klassischen Intel-Architektur ist aber der Zeitaufwand für eine Schiebeoperation tatsächlich proportional zur Anzahl der Bitpositionen.

[Optimierung durch Konstanten]
Das scheint aber im oben beschriebenen Fall nicht möglich, wenn nicht konkret $foo >> 5 geshiftet wird, sondern $foo >> $i oder so.

Richtig. Gute Compiler erkennen aber Teilausdrücke, die nur aus Konstanten bestehen, und können aufwendige Terme dadurch oft dennoch etwas vereinfachen, wenn es der Progrmmierer nicht schon getan hat.

In Assembler auf jeden Fall, aber C ist nahe dran.
Bedeutet das, dass sich in Assembler Bits direkt "per Adresse" auslesen lassen, ...

Nein, bei den gängigen CPUs nicht. Die können nur ganze Bytes (Worte, Doppelworte) lesen und dann das gewünschte Bit mit einer UND-Verknüpfung isolieren. Womit wir wieder am Anfang wären. ;-)

Ciao,
 Martin

[Daniel Thoma]

Hallo Martin,

$bitmask = Array(0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80);
if ($foo & $bitmask[$botposition])

Uh, das würde ich dann aber wirklich ausprobieren vorher. Dafür muss der Prozessor ja die Speicherposition ausrechnen (ok, da das Array keine komplexeren Datentypen enthält, ist das nicht besonders schwierig) und erstmal den Wert in ein Register laden. Ist das Array dann nicht schon im Prozessor-Cache hat man wahrscheinlich sowieso schon verloren und selbst wenn würde ich nicht erwarten, dass das schneller geht, als ein Shift. Maximal auf dem von Dir genannten Prozessor mit nur 1-Bit-Shift.

Ich glaube, hier ist PHP wirklich ein schlechtes Beispiel; als Scriptsprache, die erst zur Laufzeit interpretiert wird, sind solche Optimierungen da wohl ein Tropfen im Ozean.

Das sind sie ja sowieso fast überall. In einer Scriptsprache aber natürlich erst recht. Was da wirklich abläuft, ist kaum vorhersagbar.

Nun kann ich 0x20 entweder als Potenz von 2 oder per links-Shift herstellen, oder aber gleich das zu betrachtende Bit nach rechts schieben, wie es das obigen Codebeispiel tut. Oder gibt es hier eine bessere Vorgehensweise?

Hier sollte man wohl noch anmerken: Auf keinen Fall die Variante mit der Potenz nehmen. Potenzieren ist in irgend welchen Bibliotheken implementiert und wird nicht direkt vom Prozessor umgesetzt. Da erkennt ein Compiler nicht mehr, dass sich das nur um eine Shift-Operation handelt, sondern führt mehrere Multiplikationen aus.

Grüße

Daniel

[Der Martin]

Hi Daniel,

$bitmask = Array(0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80);
if ($foo & $bitmask[$botposition])

Uh, das würde ich dann aber wirklich ausprobieren vorher. Dafür muss der Prozessor ja die Speicherposition ausrechnen

in einer Compilersprache wie C oder gar in Assembler nicht. Da ist die *Adresse* einer Variablen konstant - entweder über die gesamte Laufzeit des Programms (globale statische Variablen), oder zumindest während ihrer Lebensdauer (lokale oder dynamisch reservierte Variablen).

Aber nochmal: Optimierungen auf diesem Level lohnen sich wirklich nur bei extrem zeitkritischen Anwendungen, die z.B. millionenfach in einer Schleife durchgenudelt werden. Für die Mehrheit der Anwendungen ist diese Betrachtung rein akademisch.

So long,
 Martin

[Peter Thomassen]

Hallo Martin,

Aber nochmal: Optimierungen auf diesem Level lohnen sich wirklich nur bei extrem zeitkritischen Anwendungen, die z.B. millionenfach in einer Schleife durchgenudelt werden.

Exakt um diesen Fall handelt es sich ;-)

Bye,
Peter

[Daniel Thoma]

Hallo Martin,

in einer Compilersprache wie C oder gar in Assembler nicht. Da ist die *Adresse* einer Variablen konstant - entweder über die gesamte Laufzeit des Programms (globale statische Variablen), oder zumindest während ihrer Lebensdauer (lokale oder dynamisch reservierte Variablen).

Ich meinte auch nicht die Adresse des Arrays sondern die des Feldes darin.
Du hast ja dann in einem Register Deinen Arrayindex stehen und willst nun den Wert haben. Also musst Du irgendwas der Art #Arrayadresse + index * #Datentyplänge rechnen, bzw der Prozessor muss das tun. Wenn die Länge gerade 1 ist, braucht man die Multiplikation nicht. Aber auch eine Addition braucht so viel Schritte wie Bits. (Ok, mit Carry-Lookahead nur logarithmisch viele nicht parallele) Dann musst Du gucken, ob das Ergebnis irgendwo in einen Prozessorcache rumfährt.  Ich weiß nicht mehr so genau, welche Varianten der Implementierung es da gab. Aber ein paar Bits dürfte man schon shiften können, bis man das geladen hat.
Wie lange braucht denn schon so ein LOAD aus dem Cache im Vergleich zu einem 1-Bit-Shift?

Grüße

Daniel

[Der Martin]

Hallo Daniel,

in einer Compilersprache wie C oder gar in Assembler nicht. Da ist die *Adresse* einer Variablen konstant

Du hast ja dann in einem Register Deinen Arrayindex stehen und willst nun den Wert haben. Also musst Du irgendwas der Art #Arrayadresse + index * #Datentyplänge rechnen, bzw der Prozessor muss das tun.

genau so ist es.

Wenn die Länge gerade 1 ist, braucht man die Multiplikation nicht.

Ist dir schon aufgefallen, dass die Größe der elementaren Datentypen in Byte auch immer gerade eine Zweierpotenz ist? Das nutzen die Compiler beim Indizieren von WORD- oder DWORD-Arrays natürlich aus. Daher ist die Indexberechnung richtig fix. Eine Multiplikation braucht's nur, wenn die Arrayelemente selbst komplexe Datentypen mit schräger Größe sind.

Aber auch eine Addition braucht so viel Schritte wie Bits.

Nope. Eine Addition erledigt ein Prozessor üblicherweise in einem einzigen Taktzyklus.

Wie lange braucht denn schon so ein LOAD aus dem Cache im Vergleich zu einem 1-Bit-Shift?

Keine Ahnung. Aber CPU-interne, registerbasierte Operationen sind immer viel schneller als wenn ein Speicherzugriff nötig ist. Selbst bei einem Cache Hit.

Ciao,
 Martin

[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

[Der Martin]

Moin Daniel,

int bitreadshift(int i, int j) {
  return (i & (1 << j)) != 0;
}

wie ich schon Peter gegenüber angedeutet habe, geht es in den meisten Fällen, wo einzelne Bits abgefragt werden, nicht um die tatsächliche Wertigkeit des jeweiligen Bits; daher ist hier der Vergleich !=0 eigentlich sinnfrei (schadet aber auch nicht). Das Funktionsergebnis wird ja im realen Kontext sowieso auf "ungleich Null" abgefragt.

int bitreadarray(int i, int j) {
  return (i & array[j]) != 0;
}

Dito.

Vergessen:

long int time1 = 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 += bitreadshift(i, k);

Okay, hier kommt der numerische Wert doch zum Tragen, das ist aber eine untypische Anwendung für eine Bit-Abfrage.

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

Und dann noch in einer so merkwürdigen Notation.  :-|

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

Hier erkennt man aber, dass der Compiler den Ausdruck umformuliert hat. Was hier in Assembler wirklich formuliert wird, ist  "return ((i>>j) & 1)". Ich finde das bemerkenswert.

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

Auffällig finde ich, dass da bei der Array-Variante anscheinend die AND-Operation wegoptimiert wird.

Keineswegs. Die test-Anweisung ist nämlich ein AND, bei dem das Ergebnis nicht gespeichert wird, gerade für solche Bit-Tests gedacht.

So long,
 Martin

[Daniel Thoma]

Hallo Martin,

wie ich schon Peter gegenüber angedeutet habe, geht es in den meisten Fällen, wo einzelne Bits abgefragt werden, nicht um die tatsächliche Wertigkeit des jeweiligen Bits; daher ist hier der Vergleich !=0 eigentlich sinnfrei (schadet aber auch nicht). Das Funktionsergebnis wird ja im realen Kontext sowieso auf "ungleich Null" abgefragt.

Ja, nur legte er Wert darauf, dass er den Bit-Wert bräuchte. Deswegen habe ich das genau so gemacht.

Vergessen:
     long int time1 = clock() / (CLOCKS_PER_SEC / 1000.0);

Oh ja, ein Fehler beim kopieren in die Antwort.

Und dann noch in einer so merkwürdigen Notation.  :-|

Einfach die Ausgabe von objdump unter Linux, was besseres habe ich nicht zur Hand.

Hier erkennt man aber, dass der Compiler den Ausdruck umformuliert hat. Was hier in Assembler wirklich formuliert wird, ist  "return ((i>>j) & 1)". Ich finde das bemerkenswert.

Ja, das ist mir auch aufgefallen.

Keineswegs. Die test-Anweisung ist nämlich ein AND, bei dem das Ergebnis nicht gespeichert wird, gerade für solche Bit-Tests gedacht.

Ah ok, damit wird das klarer.

Auf einem Sun-Kiste habe ich das auch noch spaßeshalber laufen lassen. (Ultrasparc 3 oder sowas). Da ist shift doppelt so schnell. Zeigt also schön, dass man schon genau wissen muss, für welchen Prozessor man programmiert, wenn man mit sowas anfängt. Könnte natürlich auch sein, dass der gcc für Sparc einfach schlechter optimiert. Das hilft einem aber auch nichts, wenn man nicht wirklich Assembler programmiert.

Grüße

Daniel

[Peter Thomassen]

Hallo Daniel,

wie ich schon Peter gegenüber angedeutet habe, geht es in den meisten Fällen, wo einzelne Bits abgefragt werden, nicht um die tatsächliche Wertigkeit des jeweiligen Bits; daher ist hier der Vergleich !=0 eigentlich sinnfrei (schadet aber auch nicht). Das Funktionsergebnis wird ja im realen Kontext sowieso auf "ungleich Null" abgefragt.
Ja, nur legte er Wert darauf, dass er den Bit-Wert bräuchte. Deswegen habe ich das genau so gemacht.

Mit Bitwert meinte ich eigentlich bloß den Wert des bezeichneten Bits, also einfach 0 oder 1.

Bye,
Peter

[Daniel Thoma]

Hallo Peter,

Mit Bitwert meinte ich eigentlich bloß den Wert des bezeichneten Bits, also einfach 0 oder 1.

Klar ich auch. Ich habe aber erstmal nur einen Wert bestimmt, der 0 ist, wenn das Bit 0 war oder irgend eine Zweierpotenz, wenn das Bit 1 war.
Mit dem != 0 erreiche ich genau, dass ich 0 oder 1 herausbekomme. In C gibt es keinen speziellen Datentyp für Booleans. Das sind einfach die Zahlen 1 für true und 0 für false.

Grüße

Daniel

[Der Martin]

Hallo Daniel,

Mit Bitwert meinte ich eigentlich bloß den Wert des bezeichneten Bits, also einfach 0 oder 1.

das hatte ich auch vermutet, deswegen fand ich dein !=0 überflüssig.

Mit dem != 0 erreiche ich genau, dass ich 0 oder 1 herausbekomme. In C gibt es keinen speziellen Datentyp für Booleans.

Braucht man auch nicht. Alles, was nicht 0 ist, ist true; alles, was numerisch betrachtet 0 ist, ist false. Sogar bei Zeigern gilt NULL als false, jeder andere Zeiger als true (kein Wunder, NULL ist ja nur eine Konstante, die mit #define NULL 0L festgelegt ist).

Das sind einfach die Zahlen 1 für true und 0 für false.

Das sind die Standardwerte. Aber nicht nur die 1 wird als true anerkannt, sondern auch -1, 140567, &main und natürlich die 42.

Schönes Wochenende,
 Martin

[Peter Thomassen]

Hallo ihr zwei,

$bitmask = Array(0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80);
if ($foo & $bitmask[$botposition])
Uh, das würde ich dann aber wirklich ausprobieren vorher. Dafür muss der Prozessor ja die Speicherposition ausrechnen (ok, da das Array keine komplexeren Datentypen enthält, ist das nicht besonders schwierig) und erstmal den Wert in ein Register laden. Ist das Array dann nicht schon im Prozessor-Cache hat man wahrscheinlich sowieso schon verloren und selbst wenn würde ich nicht erwarten, dass das schneller geht, als ein Shift. Maximal auf dem von Dir genannten Prozessor mit nur 1-Bit-Shift.

Hab die Probe aufs Exempel gemacht und festgestellt, dass es mindestens eine Größenordnung langsamer ist. Der Spontantest war mittels PHP, daher nicht besonders repräsentativ, aber ganz zu vernachlässigen ist das sicher nicht.

Ich glaube, hier ist PHP wirklich ein schlechtes Beispiel; als Scriptsprache, die erst zur Laufzeit interpretiert wird, sind solche Optimierungen da wohl ein Tropfen im Ozean.
Das sind sie ja sowieso fast überall. In einer Scriptsprache aber natürlich erst recht. Was da wirklich abläuft, ist kaum vorhersagbar.

Wie eingangs erwähnt war PHP ja nur ein Beispiel :-) Es kommt vielmehr darauf an, wie man in der Theorie schnellstmöglich auf ein Bit zugreift (dessen Position erst zur Laufzeit feststeht).

Nun kann ich 0x20 entweder als Potenz von 2 oder per links-Shift herstellen, oder aber gleich das zu betrachtende Bit nach rechts schieben, wie es das obigen Codebeispiel tut. Oder gibt es hier eine bessere Vorgehensweise?
Hier sollte man wohl noch anmerken: Auf keinen Fall die Variante mit der Potenz nehmen.

Ja, sowieso :-) Habe es nur der Vollständigkeit halber erwähnt.

Potenzieren ist in irgend welchen Bibliotheken implementiert und wird nicht direkt vom Prozessor umgesetzt. Da erkennt ein Compiler nicht mehr, dass sich das nur um eine Shift-Operation handelt, sondern führt mehrere Multiplikationen aus.

Darauf würde ich jetzt nicht schwören. Der Compiler müsste ja nur sehen, ob die Basis 2 ist (oder allgemein eine Potenz davon, d.h. ob die Basis nur ein 1-Bit enthält).

Bye,
Peter

[Vinzenz Mai]

Hallo Peter,

$bitmask = Array(0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80);
if ($foo & $bitmask[$botposition])

Hab die Probe aufs Exempel gemacht und festgestellt, dass es mindestens eine Größenordnung langsamer ist. Der Spontantest war mittels PHP, daher nicht besonders repräsentativ, aber ganz zu vernachlässigen ist das sicher nicht.

mit einer ungeeigneten Sprache. PHP-Arrays sind - soweit ich weiß - verkettete Listen, so dass Du im Gegensatz zu C Deine Zugriffe auf Array-Elemente nicht
in konstanter Zeit erfolgen, sondern O(n) sind. Siehe dazu nochmals Martins Ausführungen.

d.h. bei Programmierung in C hättest eine schnellere Abarbeitung.

Freundliche Grüße

Vinzenz

[Peter Thomassen]

Hallo Vinzenz,

$bitmask = Array(0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80);
if ($foo & $bitmask[$botposition])

Hab die Probe aufs Exempel gemacht und festgestellt, dass es mindestens eine Größenordnung langsamer ist. Der Spontantest war mittels PHP, daher nicht besonders repräsentativ, aber ganz zu vernachlässigen ist das sicher nicht.

mit einer ungeeigneten Sprache. PHP-Arrays sind - soweit ich weiß - verkettete Listen, so dass Du im Gegensatz zu C Deine Zugriffe auf Array-Elemente nicht
in konstanter Zeit erfolgen, sondern O(n) sind.

Der Aufwand, um z.B. auf $bitmask[3] zuzugreifen, ist aber konstant, wenn auch natürlich größer als mit einem echten Array. Ich sehe also bzgl. der Komplexität kein Problem.

Ich habe gerade versucht, etwas über die Array-Implementierung in PHP zu finden. Weißt du, wo man sich das zu Gemüte führen kann?

d.h. bei Programmierung in C hättest eine schnellere Abarbeitung.

Das sowieso.

Bye,
Peter

[Blaubart]

Tach.

Hab die Probe aufs Exempel gemacht und festgestellt, dass es mindestens eine Größenordnung langsamer ist. Der Spontantest war mittels PHP, daher nicht besonders repräsentativ, aber ganz zu vernachlässigen ist das sicher nicht.

mit einer ungeeigneten Sprache. PHP-Arrays sind - soweit ich weiß - verkettete Listen, so dass Du im Gegensatz zu C Deine Zugriffe auf Array-Elemente nicht
in konstanter Zeit erfolgen, sondern O(n) sind.

Nein, als Hashmaps, und damit dann doch wieder O(1). Eine doppelt verkette Liste der Elemente wird bloß jeweils zusätzlich verwaltet, um leichter durch die komplette Sammlung zu laufen, wenn Bedarf dafür besteht.

Als Einstiegspunkt für noch mehr PHP-Spaß: http://de.php.net/internals2.ze1.zendapi#internals2.ze1.zendapi.variables.array

Allerdings stimme ich dir zu, was die Wahl von PHP als Sprache für solche Test angeht ...

[Vinzenz Mai]

Hallo Blaubart,

mit einer ungeeigneten Sprache. PHP-Arrays sind - soweit ich weiß - verkettete Listen, so dass Du im Gegensatz zu C Deine Zugriffe auf Array-Elemente nicht
in konstanter Zeit erfolgen, sondern O(n) sind.

Nein, als Hashmaps, und damit dann doch wieder O(1). Eine doppelt verkette Liste der Elemente wird bloß jeweils zusätzlich verwaltet, um leichter durch die komplette Sammlung zu laufen, wenn Bedarf dafür besteht.

Danke für diese Information ...

Als Einstiegspunkt für noch mehr PHP-Spaß: http://de.php.net/internals2.ze1.zendapi#internals2.ze1.zendapi.variables.array

... und diesen Link. Ich wollte "mein Wissen" auch verifizieren, hab's aber in der Doku nicht gefunden. Jetzt weiß ich es besser.

Freundliche Grüße

Vinzenz

[Ingo Turski]

Hi,

Nein, selbst wenn man den Shift ausführen würde (was man meist bleiben lässt), ist das bei modernen CPUs nur ein einziger Schritt. Okay, mehrere Arbeitsschritte, aber nur eine Maschineninstruktion.

aber auf die Arbeitsschritte kommt es doch an, oder?
Mein Assembler ist zwar arg eingestaubt und war nur beim 6510 (der ja ohnehin nur ASL und LSR kannte) noch zeitgemäß, aber beim 8088 mußte die Anzahl AFAIR noch in cl geladen werden und bei den folgenden 80x86 konte man sie zwar direkt mit angeben, aber benötigt die Ausführung dann nicht auch mehr Takte?

freundliche Grüße
Ingo

[Der Martin]

Hallo Ingo,

Okay, mehrere Arbeitsschritte, aber nur eine Maschineninstruktion.
aber auf die Arbeitsschritte kommt es doch an, oder?

ja, wenn du auf den Zeitbedarf anspielst.

Mein Assembler ist zwar arg eingestaubt und war nur beim 6510 (der ja ohnehin nur ASL und LSR kannte) noch zeitgemäß, ...

Willkommen im Club! ;-)
Diese CPU hab ich sozusagen blind in Assembler programmiert, und es hat mir riesig Spaß gemacht. Ich glaube, 6502-Assembler hätte ich heute noch fast genausogut drauf. Ein bis zwei Tage zum wieder Eingewöhnen, dann klappt das!

aber beim 8088 mußte die Anzahl AFAIR noch in cl geladen werden und bei den folgenden 80x86 konte man sie zwar direkt mit angeben, aber benötigt die Ausführung dann nicht auch mehr Takte?

Doch, sicher. Ich habe das Verzeichnis jetzt nicht zur Hand, die Anzahl der Taktzyklen für den Shift-Befehl beim x86 ist aber k+a+b, wobei k konstant ist (ich meine 2), a die Adressierung des Operanden bedeutet, und b die Zahl der Bitpositionen. Unter anderem deshalb deute ich ja immer wieder an, dass man auf die Shift-Operation meist verzichten kann.

Schönen Abend noch,
 Martin

[Daniel Thoma]

Hallo Peter,

• 5 Schritte für den Bitshift
• 1 Schritt für die and-Verknüpfung (oder sind das 32, weil alle Bits verglichen werden?)

Prozessorinstruktionen werden das wohl 2 sein. Ich habe das mal kurz für x86 nachgeguckt. Dort gibt es Shift-Anweisungen, um mehrere Bits weit zu shiften. Der Prozessor muss da natürlich mehrere Schritte durchführen (Ein Schieberegister mehrmals ein Bit weiter setzen oder sowas). Im Vergleich zu Operationen wie einer Multiplikation ist das aber noch ziemlich einfach.
Die &-Verknüpfung geht auf einen Schlag, um zwei Register bitweise & zu Verknüpfen wird es eine Schaltung geben, die das parallel für alle Bits ausführt.
Evtl. kann man auch ein Schieberegister bauen, das mehrere Bit weit in einem Schritt schieben kann, aber solche Überlegungen sind für's Programmieren uninteressant. Selbst auf Maschinensprachebene geht das "in einem Schritt".

2.)
Der Compiler erkennt solche Konstrukte und ersetzt sie durch einen direkten Zugriff auf das Bit. Zur Laufzeit ist das also 1 Schritt (unabhängig vom zu betrachtenden Bit).

Wenn der Prozessor so ein Kommando hat, könnte er das tun. Ich würde jetzt aber vermuten, dass es so etwas idR. nicht gibt und da normalerweise genau die zwei Kommandos "shift" und "&" beim Prozessor auch ankommen.
Wenn die Argumente des Shifts Konstanten sind, kann es noch sein, dass der Compiler das erkennt, den Shift sofort durchführt und direkt das Ergebnis in den erzeugten Maschinencode schreibt.

3.)
Hängt die Sache vielleicht vom verwendeten Prozessor ab?

Klar, Optimierung hängt immer vom Prozessor ab. Die Prozessoren unterstützen ja unterschiedliche Kommandos und diese auch unterschiedlich effizient. Ich würde aber bei so einfachen Sachen nicht erwarten, dass es da nennenswerte Unterschiede gibt.

Grüße

Daniel

[Daniel Thoma]

Beim Lesen von Martins Anwort ist mir gerade noch aufgefallen, dass Du natürlich wirklich etwas ungewöhnliches tust. Ich hatte das irgendwie übergangen und habe direkt auf Deine Fragen geantwortet.
Üblicherweise wird man statt $foo >> 5 & 1 eher ein $foo & (1 << 5) haben, womit dann der Compiler den Shift wegoptimieren kann. Man kann natürlich direkt das Ergebnis hinschreiben, wie das Martin tut.

[Peter Thomassen]

Hallo nochmal,

Üblicherweise wird man statt $foo >> 5 & 1 eher ein $foo & (1 << 5) haben, womit dann der Compiler den Shift wegoptimieren kann.

Du hast Recht, das ist vielleicht ein klein wenig effizienter. Wie herum das Bit vorschoben wird, ist mir eigentlich egal, es geht ja um den Bitzugriff. Aber danke für den Hinweis :-) Werd's mir merken.

Bye,
Peter

[ritschmanhard]

Hi Peter!

Ist nicht egal.
Das Ergebnis von (a) $x=$foo >> 5 & 1 lautet 1/0, das von (b) $x=$foo & (1 << 5) lautet 32/0...

Allgemein erhältst du mit deiner Anweisung (sei $x,$foo ein word)
a) 4 Befehle:
mov ax, ds:[speicheradresse];
shr ax, 5;
and ax, 1;
mov wordptr ds:[speicheradresse2], ax;

b) 3 Befehle
mov ax, ds:[speicheradresse];
and ax, 32; //Kompileroptimierung berechnet 2^5 ...
mov wordptr ds:[speicheradresse2], ax;

Somit ist "ein klein wenig effizienter" doch ca. 25% (jedoch abhängig von den für die Ausführung benötigten Taktzyklen dauern nicht alle Befehle gleichlang)...

Ideal wäre eine Selbstzuweisung:
$foo = $foo & (1<<5);
Diese (könnte) der Kompiler optimieren zu:
and wordptr ds:[speicheradresse], 32

Grüsse,
Richard

[Der Martin]

Hallo Richard,

zum Zeitbedarf deiner Beispiele:

mov ax, [speicheradresse1] ; das braucht richtig lange (Speicherzugriff)
shr ax, 5                  ; nur wenige Taktzyklen
and ax, 1                  ; dito
mov [speicheradresse2], ax ; und noch ein Zeitfresser

Die wegen der Speicherzugriffe wirklich zeitintensiven Befehle hast du bei deiner Variante b) auch, die spart daher nicht wirklich viel ein. Ich schätze das Einsparpotential auf weniger als 5% pro Schleifenumlauf.

Ideal wäre eine Selbstzuweisung:
Diese (könnte) der Kompiler optimieren zu:
and wordptr ds:[speicheradresse], 32

Richtig, das sind aber immer noch zwei zeitintensive Speicherzugriffe, einmal lesen und einmal schreiben. Also auch hier nur wenig Einsparung.
Okay, der Unterschied ist messbar und vielleicht auch fühlbar, aber bei weitem nicht so groß, wie du ihn darstellst.

Ciao,
 Martin

[Peter Thomassen]

Hallo Daniel!

• 5 Schritte für den Bitshift
• 1 Schritt für die and-Verknüpfung (oder sind das 32, weil alle Bits verglichen werden?)
  Prozessorinstruktionen werden das wohl 2 sein. Ich habe das mal kurz für x86 nachgeguckt. Dort gibt es Shift-Anweisungen, um mehrere Bits weit zu shiften. Der Prozessor muss da natürlich mehrere Schritte durchführen (Ein Schieberegister mehrmals ein Bit weiter setzen oder sowas). Im Vergleich zu Operationen wie einer Multiplikation ist das aber noch ziemlich einfach.

Im konkreten Fall stellen die Bitzugriffe einen wesentlichen Teil der Anweisungen da, sodass die Effizienz der verwendeten Shifts durchaus von Bedeutung ist.

Evtl. kann man auch ein Schieberegister bauen, das mehrere Bit weit in einem Schritt schieben kann, aber solche Überlegungen sind für's Programmieren uninteressant. Selbst auf Maschinensprachebene geht das "in einem Schritt".

Das stimmt, dem Programmierer kann's egal sein. Möglicherweise wäre es aber interessant, ein solches Schieberegister zu haben, wenn man damit enorme Zeitvorteile erzielen kann. Mir geht es ja um die Zeitkomplexität -- kann man also sagen, dass eine Verschiebung über mehrere Positionen in O(1) gelöst werden kann (also unabhängig von der Länge der Zahl)?

2.)
Der Compiler erkennt solche Konstrukte und ersetzt sie durch einen direkten Zugriff auf das Bit. Zur Laufzeit ist das also 1 Schritt (unabhängig vom zu betrachtenden Bit).
Wenn der Prozessor so ein Kommando hat, könnte er das tun. Ich würde jetzt aber vermuten, dass es so etwas idR. nicht gibt und da normalerweise genau die zwei Kommandos "shift" und "&" beim Prozessor auch ankommen.

Ein solches Kommando ist vermutlich einfacher in einen Prozessor zu implementieren als das o.g. Schieberegister ... gibt es solche Prozessoren?

Danke,
Peter

[Daniel Thoma]

Hallo Peter,

Ein solches Kommando ist vermutlich einfacher in einen Prozessor zu implementieren als das o.g. Schieberegister ... gibt es solche Prozessoren?

Keine Ahnung. In den meisten Anwendungen sind wahrscheinlich keine Shift-Operationen das Problem sondern Operationen wie Floatingpoint-Operationen, die viel aufwendiger sind.
Machst Du Dir auch immer Gedanken, wenn Du zwei Zahlen multiplizierst, ob das jetzt O(1) O(n) oder gar O(n²) ist? ;-)

Auf dieser Ebene ist die O-Notation sowieso nicht mehr besonders hilfreich. So lang Deine Argumente beschränkt sind (Du shiftest ja maximal um 31 oder 63 Bit), hast Du immer O(1).
Es kommt also auf den Gesammtalgorithmus an, wie Deine asymptothische Laufzeit aussieht. Wenn es Dir nicht nur um eine rein akademische Diskussion geht, solltest Du Deine Anwendung beschreiben.
Wenn Du wirklich darauf angewiesen bist, die Geschwindigkeit deines Programmes auf dieser ebene zu optimieren, solltest Du erstmal eine compilierte Sprache nehmen und gucken, was das bringt. Das muss nicht C sein, selbst etwas wie Java oder eine .NET-Sprache wäre ein schritt.
Wenn Du wirklich über Prozessorbefehle nachdenken musst (was ich nicht glaube), solltest Du dann zu C oder gar Assembler wechseln.

Grüße

Daniel

[Peter Thomassen]

Hallo Daniel,

Ein solches Kommando ist vermutlich einfacher in einen Prozessor zu implementieren als das o.g. Schieberegister ... gibt es solche Prozessoren?
Keine Ahnung. In den meisten Anwendungen sind wahrscheinlich keine Shift-Operationen das Problem sondern Operationen wie Floatingpoint-Operationen, die viel aufwendiger sind.
Machst Du Dir auch immer Gedanken, wenn Du zwei Zahlen multiplizierst, ob das jetzt O(1) O(n) oder gar O(n²) ist? ;-)

Wenn ich nur multiplizieren würde, wäre mir schon daran gelegen, das möglichst effizient zu tun. Es hat sich wohl auch jemand Gedanken über die Addition gemacht, als er das Carry-Lookahead-Verfahren erfand ;-)

Auf dieser Ebene ist die O-Notation sowieso nicht mehr besonders hilfreich. So lang Deine Argumente beschränkt sind (Du shiftest ja maximal um 31 oder 63 Bit), hast Du immer O(1).

Wieso nun das? Martin schrieb: "Bei der klassischen Intel-Architektur ist aber der Zeitaufwand für eine Schiebeoperation tatsächlich proportional zur Anzahl der Bitpositionen."

Es kommt also auf den Gesammtalgorithmus an, wie Deine asymptothische Laufzeit aussieht. Wenn es Dir nicht nur um eine rein akademische Diskussion geht, solltest Du Deine Anwendung beschreiben.

Hm, ich möchte den Zweck der ganzen Sache gerne noch ein wenig für mich behalten, bis die Sache ein wenig weiter gereift ist. Ich komme mir recht blöd vor, solches hier zu schreiben, weil ich euch damit die Chance nehme, zu verstehen, worum es geht. Ich ahne, dass das ein k.o.-Kriterium für diesen Thread ist :-(

Eigentlich wollte ich aber weder eine akademische Diskussion (die ich sehr interessant finde!) noch eine über die Anwendung anzetteln, sondern einfach die Frage stellen, wie schnell ein einzelnes Bit gezielt gelesen werden kann :-) Daher bleibt die Frage, ob es Prozessoren gibt, die dies mittels eines Kommandos explizit unterstützen.

Wenn Du wirklich darauf angewiesen bist, die Geschwindigkeit deines Programmes auf dieser ebene zu optimieren, solltest Du erstmal eine compilierte Sprache nehmen und gucken, was das bringt. Das muss nicht C sein, selbst etwas wie Java oder eine .NET-Sprache wäre ein schritt.
Wenn Du wirklich über Prozessorbefehle nachdenken musst (was ich nicht glaube), solltest Du dann zu C oder gar Assembler wechseln.

Wie gesagt, der Algorithmus ist noch etwas unausgegoren, deswegen bin ich momentan nicht an einer idealen Implementierung interessiert. Ich wollte vielmehr unabhängig von der verwendeten Programmiersprache ausloten, inwieweit die Bitzugriffe die Laufzeit beeinflussen werden. Meine Überlegungen haben nämlich ergeben, dass die Laufzeit proportional zur Anzahl der Bitzugriffe, und damit natürlich zu deren Laufzeit ist. Dazu wollte ich eben wissen, ob sie in konstanter Zeit stattfinden können.

Sollte es Prozessoren geben, die einen gezielten Bitzugriff in konstanter Zeit erlauben, sollte ich wirklich mal über C mit Inline-Assembler nachdenken. (Die Schwierigkeit ist, dass ich C zwar einigermaßen lesen kann, aber noch nie was C geschrieben habe. Bisher nur PHP und Shell.)

Bye,
Peter

[Der Martin]

Hallo Peter,

Eigentlich wollte ich aber [...] einfach die Frage stellen, wie schnell ein einzelnes Bit gezielt gelesen werden kann :-) Daher bleibt die Frage, ob es Prozessoren gibt, die dies mittels eines Kommandos explizit unterstützen.

da diese Frage direkt oder indirekt jetzt schon mehrfach angesprochen wurde: Die direkte Adressierung von Einzelbits ist mir bisher nur von kleinen Microcontrollern wie etwa der PIC-Familie oder dem 8051 und seinen zahlreichen Derivaten bekannt. Höher entwickelte Prozessoren haben das in der Regel nicht mehr drauf, so dass die den Umweg über die UND-Maskierungen gehen müssen.

Ich wollte vielmehr unabhängig von der verwendeten Programmiersprache ausloten, inwieweit die Bitzugriffe die Laufzeit beeinflussen werden.

Die Programmiersprache hat aber durch ihre grundlegenden Eigenschften einen sehr großen Einfluss auf diesen Aspekt.

Die Schwierigkeit ist, dass ich C zwar einigermaßen lesen kann, aber noch nie was C geschrieben habe.

So wie ich dich anhand deiner bisherigen Fragen und Bemerkungen einschätze, wirst du C lieben (C++ nicht so sehr), und Assembler erst recht!

So long,
 Martin

[Daniel Thoma]

Hallo Peter,

Wieso nun das? Martin schrieb: "Bei der klassischen Intel-Architektur ist aber der Zeitaufwand für eine Schiebeoperation tatsächlich proportional zur Anzahl der Bitpositionen."

Das ist schon richtig. Da ein Prozessor aber nur mit einigen wenigen (im Vergleich zur Unendlichkeit ;) Bits, z.Z. meist 32 oder 64 arbeitet, sind das eben konstant viele Schritte. Also eben O(64) = O(1).
Das kann natürlich bedeuten, dass Dein Programm 64 mal so lang braucht als es auf einem Prozessor brauchen würde, der das in einem Schritt kann. Für die asymptotische Laufzeit macht das aber erstmal keinen unterschied.

Nun kann man natürlich sagen, dass alle direkt unterstützten Datentypen irgendwie beschränkt sind und damit auch das durchlaufen eines integer-indizierten Arrays in konstanter Zeit geht. Der unterschied ist, dass die maximale Shift-weite eben sehr klein ist, ein maximaler Integer Wert aber so groß, dass man ihn für die Analyse von Algorithmen meist als uneingeschränkt betrachten kann/muss.
Daraus ergibt sich dann, dass das Laufzeitverhalten des Shiftbefehls selbst sich nicht auf das asymptotische Laufzeitverhalten Deines Algorithmuses auswirken kann. Das Verhalten muss sich schon aus diesem selbst ergeben. Es kann ja sein, dass 64 Bit viel zu wenig sind und Du irgendwie mit 1MBit-Vektoren arbeiten musst. Da ist natürlich ein Shift wirklich aufwendig. Nur macht den auch nicht mehr der Prozessor für Dich.

Grüße

Daniel

[Peter Thomassen]

Hallo Daniel,

Wieso nun das? Martin schrieb: "Bei der klassischen Intel-Architektur ist aber der Zeitaufwand für eine Schiebeoperation tatsächlich proportional zur Anzahl der Bitpositionen."
Das ist schon richtig. Da ein Prozessor aber nur mit einigen wenigen (im Vergleich zur Unendlichkeit ;) Bits, z.Z. meist 32 oder 64 arbeitet, sind das eben konstant viele Schritte. Also eben O(64) = O(1).

Das hieße, der Zeitaufwand für die Schiebeoperation ist proportional zur Registerbreite. Ich hab Martin aber so verstanden, dass der Aufwand proportional zum Abstand ist, um den man verschieben möchte.

Daraus ergibt sich dann, dass das Laufzeitverhalten des Shiftbefehls selbst sich nicht auf das asymptotische Laufzeitverhalten Deines Algorithmuses auswirken kann. Das Verhalten muss sich schon aus diesem selbst ergeben.

Du meinst also, es dauert genauso lang, Millionen von "foo << 1" durchzuführen wie "foo << 12"? Andernfalls kann das ja eine Auswirkung haben (oder ich habe deine Argumentation nicht verstanden).

Bye,
Peter

[Daniel Thoma]

Hallo Peter,

Das hieße, der Zeitaufwand für die Schiebeoperation ist proportional zur Registerbreite. Ich hab Martin aber so verstanden, dass der Aufwand proportional zum Abstand ist, um den man verschieben möchte.

Ja, aber man kann ja maximal so weit schieben, wie das Register breit ist. Also braucht man maximal 64 Schritte, dann ist das Register leer.

Du meinst also, es dauert genauso lang, Millionen von "foo << 1" durchzuführen wie "foo << 12"? Andernfalls kann das ja eine Auswirkung haben (oder ich habe deine Argumentation nicht verstanden).

Hast Du nicht. Vielleicht weil Dir nicht ganz klar ist, was asymptotische Komplexität oder die O-Notation genau bedeutet.

Angenommen Du hast einen Algorithmus. Der führt irgendwie O(f(n)) Shift-Befehle durch. Ein Shiftbefehl benötigt nun maximal 64 Schritte.
Da 64 * O(f(n)) = O(f(n)) ändert sich am Laufzeitverhalten einfach nix, auch wenn die Befehle bis zu 64 mal so lang brauchen.
Die Argumentation ist einfach, dass sich daraus, ob shift immer 1 Schritt oder bis zu 64 Schritten braucht nur ein Faktor für die Laufzeit ergibt.

So ein Faktor kann natürlich durchaus was ausmachen, schon wenn der Algorithmus nur doppelt so lange braucht, ist das erheblich. Es ist aber oft so, dass man durch einen besseren Algorithmus viel mehr rausholen kann, als dadurch, dass man an irgendwelchen Sachen rumoptimiert, die nur Konstanten beeinflussen.

Grüße

Daniel

[Peter Thomassen]

Hallo Daniel!

Du meinst also, es dauert genauso lang, Millionen von "foo << 1" durchzuführen wie "foo << 12"? Andernfalls kann das ja eine Auswirkung haben (oder ich habe deine Argumentation nicht verstanden).
Hast Du nicht. Vielleicht weil Dir nicht ganz klar ist, was asymptotische Komplexität oder die O-Notation genau bedeutet.

Doch, das ist mir durchaus klar.

Angenommen Du hast einen Algorithmus. Der führt irgendwie O(f(n)) Shift-Befehle durch.

Da ist schon der Haken, ich habe doch nie von einem Algorithmus mit O(f(n)) gesprochen. Als Gegenbeispiel stelle man sich einen Algorithmus vor, dem man ein Array der Länge n und einen Parameter b übergibt. Der Algorithmus soll die Bits aller Arrayelemente um b Positionen verschieben. Ich behaupte nun, die Komplexität ist in diesem Fall O(b * n) gilt, denn b ist ja variabel. Siehst du das nicht auch so?

Bye,
Peter

[Daniel Thoma]

Hallo Peter,

Da ist schon der Haken, ich habe doch nie von einem Algorithmus mit O(f(n)) gesprochen. Als Gegenbeispiel stelle man sich einen Algorithmus vor, dem man ein Array der Länge n und einen Parameter b übergibt. Der Algorithmus soll die Bits aller Arrayelemente um b Positionen verschieben. Ich behaupte nun, die Komplexität ist in diesem Fall O(b * n) gilt, denn b ist ja variabel. Siehst du das nicht auch so?

Sicher, nur hängt das nicht davon ab, wie schnell der Shift-Befehl des Prozessors ist.
Vergleichen wir beide Fälle:
1. Du implementierst diesen Algorithmus mit einem Shift-Befehl, der immer in einem Schritt durchkommt (vermutlich geht besser als logarithmisch nicht, aber nehmen wir das der Einfachheit halber mal an)
Du musst maximal für jedes Element um 63 Bit shiften (wenn man 64 Bit/Element annimmt). Wenn b > 63 ist, dann musst Du die Elemente im Array vertauschen und nur noch b % 64 Bits shiften, also der Anteil, der eben nicht aufgeht.
Das verschieben der Elemente geht wohl in O(n), indem man einfach ein Element an den Platz abrunden(b / 64) setzt. Du kommst also tatsächlich mit O(n) Schritten aus.

2. Du implementierst den Algorithmus mit einem Shift-Befehl, der so viel Schritte braucht, wie geshiftet wird.
Nun es ändert sich nicht viel, außer dass Du für jedes Element bis zu 63 Schritte zum Shiften brauchst.
Statt O(n) Schritten brauchst Du eben 63 * O(n) Schritte. Das ist per Definition eben ebenfalls O(n).

Ich weiß nicht mehr so recht, wie ich es noch genauer ausführen soll ;-)

Meine Aussage ist ja nur, dass das asymptotische Verhalten nicht von der Art des Shift-Befehls auf Prozessorebene abhängt.
Natürlich braucht der Shift für ein beliebig großes Array O(n) Schritte. Natürlich wird es auch schneller, wenn der shift im Prozessor schneller arbeitet. Es bringt aber nichts darüber nachzudenken, wie schnell der Prozessor shiftet, wenn der Algorithmus zum shiften des großen Arrays z.B. so schlecht wäre, dass er ohnehin O(n²) Schritte bräuchte.
Mehr als: "Wenn man Anfängt über Prozessorbefehle nachzudenken, sollte man erstmal einen Schritt zurücktreten und gucken, ob es nicht irgendwie alles viel einfacher geht" wollte ich im Grunde nicht sagen ;-)

Grüße

Daniel