Optimieren von Multiplikation mit Potenz von 2 ?

[Dirty Oerti]

Achso

Der Ausschnitt kommt, wie vllcht schon erraten, aus meinem Kernelcode.
Und zwar aus der Funktion, die ein nicht gesetztes Bit einer Bitmap (entspricht freiem Speicherframe) sucht.

Dazu gehe ich folgendermaßen vor:

Ich überprüfe jeweils 4-Byte-Blöcke (32 Bit), ob ein Bit nicht gesetzt ist.

Code: Alles auswählen

if(*address!=0xFFFFFFFF) { //...

Habe ich einen Block gefunden, dann überprüfe ich die einzelnen Bits, um herauszufinden, welches Bit denn nun nicht gesetzt ist.
Am Ende gebe ich die Nummer des Bits in der GESAMTEN Bitmap zurück.(entspricht Nummer des Frames)

Habe ich vorher 20 4-Byte-Blöcke (also 20 mal 32 Bit durchsucht) durchsucht und im 21. ist das 4. Bit ungesetzt, dann berechnet sich die Nummer so:

Code: Alles auswählen

(20 *32) + 4

Da diese " * 32" immer vorkommen dachte ich mir, das könnte ich versuchen zu optimieren.

Ich nehme 4-Byte-Blocks, weil das die größte Datenmenge ist, die eine 32-Bit CPU auf einmal verarbeiten kann.
Würde ich jedes Bit einzeln überprüfen, wäre das ganze ganz schön langsam...

[Xin]

Da diese " * 32" immer vorkommen dachte ich mir, das könnte ich versuchen zu optimieren.

Ich nehme 4-Byte-Blocks, weil das die größte Datenmenge ist, die eine 32-Bit CPU auf einmal verarbeiten kann.

Sowas dachte ich mir schon, daher habe ich gefragt.

Du weißt aber, dass CPUs Bytezugriffe machen und keine Bitzugriffe? ;-P
Um 32 Bit weiter zu kommen, muss -> 4 <- Byte weiter gehen: <<2, nicht <<5.

[Dirty Oerti]

Da diese " * 32" immer vorkommen dachte ich mir, das könnte ich versuchen zu optimieren.

Ich nehme 4-Byte-Blocks, weil das die größte Datenmenge ist, die eine 32-Bit CPU auf einmal verarbeiten kann.

Sowas dachte ich mir schon, daher habe ich gefragt.

Du weißt aber, dass CPUs Bytezugriffe machen und keine Bitzugriffe? ;-P
Um 32 Bit weiter zu kommen, muss -> 4 <- Byte weiter gehen: <<2, nicht <<5.

Hm...heißt es nicht "Bitoperatoren" ?
Also soweit ich weiß (und es funktioniert ja auch) macht das

Code: Alles auswählen

(1)<<1

aus der 1 eine 2, es wird um ein Bit nach links verschoben.

Ich denke du hast außerdem das "=" übersehen

Code: Alles auswählen

countb<<=5;

Heißt im Endeffekt countb wird um 32 erhöht.
Um den nächsten 4-Byte-Block anzusteuern mach ich das so:

Code: Alles auswählen

unsigned int *tmp = STARTADRESSE;
// (...)
tmp++;//Nächste 4 Byte

Und so ist es denk ich mal auch richtig

[Xin]

Da diese " * 32" immer vorkommen dachte ich mir, das könnte ich versuchen zu optimieren.

Ich nehme 4-Byte-Blocks, weil das die größte Datenmenge ist, die eine 32-Bit CPU auf einmal verarbeiten kann.

Sowas dachte ich mir schon, daher habe ich gefragt.

Du weißt aber, dass CPUs Bytezugriffe machen und keine Bitzugriffe? ;-P
Um 32 Bit weiter zu kommen, muss -> 4 <- Byte weiter gehen: <<2, nicht <<5.

Hm...heißt es nicht "Bitoperatoren" ?

Doch, weil es mit Bits arbeitet.

Deine Annahme, wie es funktioniert ist vollkommen richtig.

Ich denke du hast außerdem das "=" übersehen

Code: Alles auswählen

countb<<=5;

Heißt im Endeffekt countb wird um 32 erhöht.

Nein. Es multipliziert countb mit 32.

Um den nächsten 4-Byte-Block anzusteuern mach ich das so:

Code: Alles auswählen

unsigned int *tmp = STARTADRESSE;
// (...)
tmp++;//Nächste 4 Byte

Und so ist es denk ich mal auch richtig

tmp++ addiert 4 Byte auf tmp, das funktioniert richtig. Nur verstehe ich immernoch nicht, warum Du etwas mit 32 multiplizierst. Die Operation ist ungewöhnlich, daher vermute(!) ich, dass sie nicht die ist, die Du tun willst. Ich kenne aber auch nur Codefragmente.

[Dirty Oerti]

Ok...

Hm...heißt es nicht "Bitoperatoren" ?

Das sollte einen Hauch von Sarkasmus mit sich bringen

Deine Annahme, wie es funktioniert ist vollkommen richtig.

Ist mir bewusst.

Nein. Es multipliziert countb mit 32.

Meinte ich, tschuldigung

Ich versuche es mal an einem anderen Beispiel zu erklären:
Ein Array.
Ein 2 Dimensionaler Array.

Sagen wir von der Größe [5][3].
Heißt wir haben 5 mal einen Block von 3 Werten.
Nehmen wir an, Wert = Bit.

Nun suchen wir ein Bit/einen Wert gleich 0.
Dazu überprüfen wir zunächst den ersten "3-Werte-Block", stellen fest, dass dort alle Wert ungleich 0 sind
(im echten Code ist das EIN Vergleich, da alle 3 Werte, bzw im Code eben 32 (Bit), auf einmal angesprochen werden können)

Heißt wir überprüfen den nächsten Block.
Sagen wir, der 4. Wert in diesem 2. Block ist gleich 0.
Nun haben wir unseren gesuchten Wert gefunden.

Jetzt nehmen wir an, wir möchten diesen Wert adressieren.
Nur eben nicht per [1][3] (2. Block, 4.Wert)
Sondern mit einer Zahl.

Wie machen wir das?
Nunja:

(ANZAHL ELEMENTE PRO BLOCK * Block) + Wert

Im Beispiel also (5*1)+3 = 8


Im Code oben sind es nunmal 32 Bits und nicht 5 Werte.
Deswegen nehme ich die Nummer des Blocks (countb) mit der Anzahl der Werte/Bits pro Block mal.
Damit bekomme ich eine einzelne Nummer, mit der ich dann das Bit (das für einen Frame steht) eindeutig adressieren kann.

Ok?

Die Operation ist ungewöhnlich, daher vermute(!) ich, dass sie nicht die ist, die Du tun willst. Ich kenne aber auch nur Codefragmente.

Es ist genau die Operation, die ich tun möchte

Der ganze Code ist hier zu finden: http://proggen.org/viewtopic.php?p=2606#p2606
Es ist die Funktion find_first_free()
Sie durchsucht eine Bitmap in 32Bit-Schritten (liest immer 32 Bit und prüft, ob alle gesetzt)
Wenn sie einen 32Bit-Block findet, in dem nicht alle Bits gesetzt sind, werden noch die einzelnen Bits überprüft, um herauszufinden, welches Bit denn nun nicht gesetzt ist.
Dann Nr. des 32-Bit-Blocks*32 + Nr des Bits im Block ergibt absoulute Bitnummer.
Die wiederrum steht in dem speziellen Fall für die Nummer der (Unter)Bitmap.
Diese wird daraufhin genauso wie oben durchsucht.
Das hier gefundene, freie Bit bezeichnet dann aber die Nummer des Frames in der (Unter)Bitmap.
Um die absolute Nummer zu erhalten nehme ich die Nr der (Unter)Bitmap mal der Anzahl Frames in einer Bitmap plus die Nummer des Frames in der Bitmap.
Und schon habe ich die absolute Framenummer.

[Xin]

Hab diesen Thread noch in meiner Todo-List - noch aktuell?

[Dirty Oerti]

Hab diesen Thread noch in meiner Todo-List - noch aktuell?

Nicht wirklich.
Hab noch ein paar Aspekte, an denen ich nicht weiß, was schneller ist.
Aber das muss erstmal noch warten.