Bit Twiddling Hacks

[milan1612]

http://graphics.stanford.edu/~seander/bithacks.html
Ein sehr interessanter Artikel - auch für die die (so wie ich) keine Ahnung haben
was man mit ein paar Tricks und den 'bitweisen' Operatoren alles anstellen kann.
Wer auch nur ein bisschen Englisch kann sollte sich das mal anschauen, die
Beispiele sind zwar in C, aber doch recht einfach auf Purebasic zu übertragen.

[AND51]

Cool, dank für den Link!

Dazu ein paar Fragen.
Ein paar Terme enthalten Multiplikationen, z. B.

Code: Alles auswählen

int v;      // we want to find the sign of v
int sign;   // the result goes here 

// CHAR_BIT is the number of bits per byte (normally 8).
sign = -(v < 0);  // if v < 0 then -1, else 0. 
// or, to avoid branching on CPUs with flag registers (IA32):
sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));
// or, for one less instruction (but not portable):
sign = v >> (sizeof(int) * CHAR_BIT - 1); 

(siehe letzte Zeile)
Ich halte Multiplikationen für langsamer als Bitoperationen, stimmt das? Und überhaupt, wäre es nicht besser/schneller, mit If zu prüfen, ob eine Variable kleiner ist, um dann -1 oder 0 zurückzugeben?

Oder was genau ist der Sinn der Seite? Einfach nur, um zu zeigen, wie's kürzer geht oder geht's auch um die Performance?

[milan1612]

Ich bin zwar bei diesem Thema absolut kein Profi, aber ich würde aus Erfahrung sagen
dass bitweise Operationen grundsätzlich schneller sind als - na wie nennt man
denn 'normale' mathematische Operationen?.
Aber ich denke dass Vergleichsoperationen noch einen Tick langsamer sind als alles andere.
Bin gespannt ob sich hier noch ein Profi dazu äußert...

[AND51]

Aber ich denke dass Vergleichsoperationen noch einen Tick langsamer sind als alles andere.

Ich frage mich eigentlich nur, ob Bitoperationen oder vergleichsoperationen (bei IF) schneller sind.

Ein bisschen weiß ich von ASM, das es da verschiedene Sprungbefehle gibt, ich glaube, z. B. "JNE" ("springe, wenn ungleich"). Da man mit ASM ja dem Prozessor schon ziemlich nah kommt, würde ich schätzen, dass Bit- und Vergleichsoperationen etwa gleich schnell oder ltzeres etwas schneller ist.

Was mich auch mal interessieren würde, sind die Vergleichsoperatoren <= und >= langsamer als < und > ? Kennt sich da wer genauer aus?

[Kaeru Gaman]

(sizeof(int) * CHAR_BIT - 1)

sizeof(int) liefert die größe einer Integer in Chars
CHAR_BIT ist die Anzahl Bits in einem Char
-1 sorgt dafür, dass es eins weniger ist.

für PB liefert SizeOf(Long) die größe eines Long in Byte,
der Multiplikator wäre also einfach eine literale 8
SizeOf(Long) * 8 -1 ist 31
wenn man das vorzeichenbit um 31 nach rechts schiebt,
bekommt man 0 für positiv und 1 für negativ.
wenn man 1 und -1 haben will, muss man noch 1-2*sign rechnen.

[ZeHa]

Da es sich aber um drei Konstanten handelt (sizeof, CHAR_BIT, -1), wird das eh zur Compilezeit berechnet und als ein einziger, fertiger Wert in den Maschinencode eingefügt.

Was mich auch mal interessieren würde, sind die Vergleichsoperatoren <= und >= langsamer als < und > ? Kennt sich da wer genauer aus?

Wie Du schon selbst sagtest, gibt es verschiedene Sprungbefehle, unter anderem z.B. auch JBE (Jump if Below or Equal), sprich, allein für <= und < gibt es auf Deinem Prozessor bereits zwei verschiedene Operationen (nämlich JBE und JB).

[AND51]

//Edit:

Ja okay, dann ist das in meinem Codebeispiel also ein fester Wert, der ja vom Compiler vorher evaluiert wird.
OK und wie ist das nun mit den ASM-Sprungbefehlen? Dann gibt es halt 2 verschiene Sprungbefehle.

Aber die Frage ist doch: Wo habe ich mehr Aufwand?
Wenn ich gucken muss, ob x gleich oder kleiner als y ist?
Wenn ich nur gucken müsste, ob x kleiner als y dann wäre doch

Code: Alles auswählen

If x < 30
    Debug "OK"
EndIf

besser als

Code: Alles auswählen

If x <= 29
    Debug "OK"
EndIf

da ich mir doch einen Arbeitsschritt spare, oder?

[Kaeru Gaman]

ich weiß es nicht.

ich weiß nur, dass Vergleiche in PB verdammt schnell sind.
in PB lohnt es sich eher mal ein If statt einer Formel zu verwenden.
in C und anderen sprachen ist es oft genau umgekehrt.

letztendlich ist das auch Problemspezifisch, also wie komplex deine Formel oder dein If ist,
und auch in welcher reihenfolge dein If-Konstrukt aufgebaut ist.
eine speziell Problem angepasste Formel-If-Kombination ist oft am effektivsten.

im zweifel mal alle möglichen konstruktionen in nen speedtest packen.

PS:
> sind die Vergleichsoperatoren <= und >= langsamer als < und > ?
ich würde mal raten, dass das garnicht feststeht, sondern von beiden zu verarbeitenden werten abhängt....

[Andreas_S]

//Edit:

Ja okay, dann ist das in meinem Codebeispiel also ein fester Wert, der ja vom Compiler vorher evaluiert wird.
OK und wie ist das nun mit den ASM-Sprungbefehlen? Dann gibt es halt 2 verschiene Sprungbefehle.

Aber die Frage ist doch: Wo habe ich mehr Aufwand?
Wenn ich gucken muss, ob x gleich oder kleiner als y ist?
Wenn ich nur gucken müsste, ob x kleiner als y dann wäre doch

Code: Alles auswählen

If x < 30
    Debug "OK"
EndIf

besser als

Code: Alles auswählen

If x <= 29
    Debug "OK"
EndIf

da ich mir doch einen Arbeitsschritt spare, oder?

Wo sparst du hier einen Arbeitsschritt?

Du weist ja nicht ob der prozessor hier das mit einem Streich macht oder +1 rechnet...


EDIT:

>> ich weiß nur, dass Vergleiche in PB verdammt schnell sind.
>> in PB lohnt es sich eher mal ein If statt einer Formel zu verwenden.
>> in C und anderen sprachen ist es oft genau umgekehrt.

?
Warum sollte PB hier von anderen Sprachen abweichen?
Ich denke dass alle Sprachen gerade bei solchen grundlegenden Befehlen mit der Geschwindigkeit gleich sind...

[ZeHa]

Dafür sind die zwei Sprungbefehle doch da! Es gibt sogar noch viel mehr Sprungbefehle.

Die erste Operation lautet CMP (compare). Das heißt, hier findet der Vergleich statt, und der Prozessor setzt sich intern ein paar Flags anhand des Ergebnisses.

Danach kommt erst der Sprungbefehl. JB (jump if below), JBE (jump if below or equal), JA (jump if above), JAE (jump if above or equal), JE (jump if equal), JNE (jump if not equal), usw., und dieser wird anhand der gesetzten Flags ausgewertet. Die eigentliche Vergleichsoperation dauert also gleich lang.

Ob die einzelnen Sprungbefehle evtl. unterschiedlich lang benötigen, wage ich dabei zu bezweifeln, aber hier bin ich mir nicht 100%ig sicher. Es ist aber anzunehmen daß jeder Sprungbefehl gleich lang benötigt.