einzelne Bits schnell lesen / schreiben

[Imhotheb]

Hallo Zusammen,
ich habe mal ein kleines Problem.

Oft benötige ich nur einen boolschen Wert und um es einfacher zu machen verwende ich seit langem die beiden Funktionen im Code. Bisher hatte sie meinen Ansprüchen auch genüge getan. Jetzt habe ich allerdings ein Problem das es zuviel Zeit benötigt. Die benötigte Datenmenge fällt um einiges größer aus als die hier reservierten 3 MB.
Bei diesem Beispiel braucht mein "i7-3930K @ 4,2Ghz" mit PB5.31 x64 ca. 12,5 sek. zum schreiben und 9,6 sek. zum lesen (bei PB5.31 x86 12,5 / 10,7) beides allerdings mit IDE-Debugger... würde bei der zu erwartenden Datenmenge dann 24 Std. zum schreiben benötigen

Ich möchte hier nicht Streiten ob Prozeduren dafür Sinnvoll sind oder nicht ... aber es geht um viele, sehr viele, einzelne Bits die an vielen verschiedenen Stellen im Code gesetzt werden müssen.

Jetzt meine eigentliche Frage ... kann jemand ein paar Tipps/Anregungen geben wie es schneller geht ... ASM wäre vermutlich die schnellste Möglichkeit, doch davon hab' ich keine Ahnung. Liege ich richtig, wenn ich davon ausgehe das Mod() und Pow() am längsten benötigen? Wie könnte man es ohne machen?

Code: Alles auswählen

EnableExplicit

Procedure BitRead(*var, pos)
  If PeekB(*var + Int(pos / 8)) & Int(Pow(2,Mod(pos, 8)))
    ProcedureReturn #True
  Else
    ProcedureReturn #False
  EndIf   
EndProcedure

Procedure BitWrite(*var, pos, value = 1)
  *var + Int(pos / 8)
  If value = #False
    PokeB(*var, PeekB(*var) & ~Int(Pow(2,Mod(pos, 8))))
    ProcedureReturn #False
  ElseIf value = #True
    PokeB(*var, PeekB(*var) | Int(Pow(2,Mod(pos, 8))))
    ProcedureReturn #True
  EndIf
EndProcedure  

#memspace = 3000000
Define *test = AllocateMemory(#memspace, #PB_Memory_NoClear)
Define i.l

Define test1start = ElapsedMilliseconds()

For i = 0 To MemorySize(*test) * 8 - 1
  BitWrite(*test, i)
Next

Define test1endtest2start = ElapsedMilliseconds()

For i = 0 To MemorySize(*test) * 8 - 1 
  BitRead(*test, i)
Next

Define test2end = ElapsedMilliseconds()

MessageRequester("Bit-Test", "Schreiben: " + Str(test1endtest2start - test1start) + " / Lesen: " + Str(test2end - test1endtest2start)) 

Danke schonmal für Eure Antworten

[NicknameFJ]

Schau dir mal an wie ich es gelöst habe. http://purebasic.fr/german/viewtopic.ph ... 01#p329001. Kann man aber sicher auch noch effizienter machen.

Grüße

NicknameFJ


\EDIT:
Ein Makro wäre hier sicher sinnvoll. Gemessen an der Laufzeit der Procedure nimmt die Initialisierung und Stackbereitstellung der Parameter, Aufruf etc. doch sehr viel Zeit in Anspruch.

__________________________________________________
Domain-Link angepasst
04.03.2015
RSBasic

[ts-soft]

@NicknameFJ

Bitte keine Links die auf "forum.purebasic.com" lauten. Immer ersetzen durch "purebasic.fr"
Hier nochmal der richtige Link: http://purebasic.fr/german/viewtopic.ph ... 92#p329001

[NicknameFJ]

@TS-Soft:
Danke für den Hinweis. Mache ich normalerweise auch nicht.

Ich komme gerade (wieder mal nicht) auf die Seite von Purebasic.fr. Daher hatte ich die Seite über den Cache von Google aufgerufen und die wurde da über purebasic.com aufgerufen. Ist mir leider nicht aufgefallen.

NicknameFJ

[NicTheQuick]

Also das kann man schon wesentlich effizienter schreiben:

Code: Alles auswählen

Procedure BitRead(*var.Integer, pos.i)
	*var + pos >> 3
	If *var\i & (1 << (pos & 7))
		ProcedureReturn #True
	Else
		ProcedureReturn #False
	EndIf   
EndProcedure

Procedure BitWrite(*var.Ascii, pos, value = 1)
	*var + pos >> 3
	If value
		*var\a | (1 << (pos & 7))
		ProcedureReturn #True
	Else
		*var\a & ~(1 << (pos & 7))
		ProcedureReturn #False
	EndIf
EndProcedure

Ein "x mod 8" lässt sich durch ein "x & 7" vereinfachen. Ein "x / 8" kann man auch als "x >> 3" schreiben. Integer sind immer schneller als andere Datentypen. Aber beim Schreiben darf man sie nicht verwenden, da man damit über den zulässigen Speicherbereich hinaus schreiben könnte. Oder man macht den Speicherbereich immer 7 Bytes größer als er sein müsste.

[Imhotheb]

PERFECT

DAS habe ich gesucht ... hätte ich mich wohl besser mit Bit-Shift und so beschäftigen sollen

Hier das Ergebnis meiner "Optimierungen" mit den Ideen von NicknameFJ :

Code: Alles auswählen

Procedure BitRead(*var, pos.q)
  ProcedureReturn PeekA(*var + pos / 8) & (1 << pos % 8)
EndProcedure

Procedure SetBit(*var, pos.q)
  pos / 8
  PokeA(*var + pos, PeekA(*var + pos) | (1 << pos % 8 ))
EndProcedure

Procedure ClearBit(*var, pos.q)
  pos / 8
  PokeA(*var + pos, PeekA(*var + pos) & ($FF - (1 << pos % 8 )))
EndProcedure

Procedure BitWrite(*var, pos.q, value = 1)
  If value = #False
    SetBit(*var, pos)
    ProcedureReturn #False
  ElseIf value = #True
    ClearBit(*var,pos)
    ProcedureReturn #True
  EndIf
EndProcedure  

läuft um den Faktor 10 schneller ... das reicht mir eigentlich ... aber wenns noch schneller geht ... immer her damit

[Imhotheb]

werde das von NicTheQuick später testen ... muss jetzt erstmal los

[Thorium]

Schneller wirst du, wenn du dir nen angepassten Algorythmus machst.
Musst du wirklich jedes Bit einzeln setzen? Viel schneller gehts natürlich mit Bitmasken, welche gleich 8, 16, 32 oder 64 bit verarbeiten. Musst dann halt für die spezielle Aufgabe einen speziellen Algo bauen.

Schreib doch mal was genau dein Ziel ist.

[Shardik]

Ich habe vor mehr als 8 Jahren schon einmal ein Beispiel zum Lesen, Setzen und Löschen von Bits in 32-Bit Intel-Assembler gezeigt. Allerdings ist tatsächlich der Overhead des Aufrufs einer Prozedur so hoch, dass es sich für maximale Performance aus Geschwindigkeitsgründen empfiehlt, den Assemblercode in Makros zu packen...

http://www.purebasic.fr/german/viewtopi ... 20&start=2

PS: Ich habe das Beispiel noch einmal getestet und gemerkt, dass auf Grund der Änderung der Hex()-Funktion in aktuelleren PureBasic-Versionen noch das Flag #PB_Long hinzugefügt werden muß. Dies ist der entsprechend überarbeitete Code:

Code: Alles auswählen

Procedure ClearFlag(FlagBit.L)
  !MOV EAX,[ESP+4]
  !BTR DWORD[v_Flags],EAX
EndProcedure


Procedure SetFlag(FlagBit.L)
  !MOV  EAX,[ESP+4]
  !BTS  DWORD[v_Flags],EAX
EndProcedure


Procedure GetFlag(FlagBit.L)
  !PUSH EBX
  !XOR  EAX,EAX
  !MOV  EBX,DWORD[ESP+8]
  !BT   DWORD[v_Flags],EBX
  !JNC  $+3
  !INC  EAX
  !POP  EBX
  ProcedureReturn
EndProcedure


Global Flags.L

Define i.L

Debug "Test ClearFlag() - alle Flags der Reihe nach löschen"
Flags = $FFFFFFFF
Debug "Flags = " + Hex(Flags, #PB_Long)

For i = 0 To 31
  ClearFlag(i)
  Debug "Flags = " + RSet(Hex(Flags, #PB_Long), 8, "0")
Next i

Debug "-----"
Debug "Test SetFlag() - alle Flags der Reihe nach setzen"
Flags = 0
Debug "Flags = " + RSet(Hex(Flags, #PB_Long), 8, "0")

For i = 0 To 31
  SetFlag(i)
  Debug "Flags = " + RSet(Hex(Flags, #PB_Long), 8, "0")
Next i

Debug "-----"
Debug "Test GetFlag() - alle Flags der Reihe nach testen"

Flags = $C0000013

Debug "Flags = " + Hex(Flags, #PB_Long)

For i = 0 To 31
  Debug "Flag " + Str(i) + " = " + Str(GetFlag(i))
Next i

[CSHW89]

NicTheQuick's Variante würde ich dann noch etwas abändern:

Code: Alles auswählen

Structure BitArray
  a.a[0]
EndStructure

Procedure BitRead(*var.BitArray, pos)
   ProcedureReturn Bool(*var\a[pos>>3] & (1 << (pos & 7)))
EndProcedure

Procedure BitWrite(*var.BitArray, pos, value = 1)
   If value
      *var\a[pos>>3] | (1 << (pos & 7))
      ProcedureReturn #True
   Else
      *var\a[pos>>3] & ~(1 << (pos & 7))
      ProcedureReturn #False
   EndIf
EndProcedure

... oder dann als Macro-Variante (dann muss aber gewährleistet sein, dass der Parameter _var_ auch in der aufrufenden Procedure ein Pointer vom Typ BitArray ist:

Code: Alles auswählen

Structure BitArray
  a.a[0]
EndStructure

Macro BitRead(_var_, _pos_)
   Bool(_var_\a[(_pos_)>>3] & (1 << ((_pos_) & 7)))
EndMacro

Macro BitWrite(_var_, _pos_, _value_ = 1)
   If (_value_)
      _var_\a[(_pos_)>>3] | (1 << ((_pos_) & 7))
   Else
      _var_\a[(_pos_)>>3] & ~(1 << ((_pos_) & 7))
   EndIf
EndMacro

lg Kevin