einzelne Bits schnell lesen / schreiben

Imhotheb · Beitrag von **Imhotheb** » 05.03.2015 23:44

Thorium hat geschrieben: Musst du wirklich jedes Bit einzeln setzen?
Schreib doch mal was genau dein Ziel ist.

Ja, leider ... muss jedes Bit einzeln setzen ... langer (Un-)Sinn, kurze Erklärung:
ich bekomme von einer externen Lib (Eine Art Wrapper-DLL für eine spezielle I/O Karte) ein Bit mit Zeitstempel.
Es werden Signale von 128 externen MicroControllern mit je ca. 500 Sensoren (nur Ja/Nein) gesendet.
Diese Daten muss ich Sortieren und da auch viel Parallel gearbeitet wird (Threads), muss jedes Bit einzeln geschrieben werden.
Könnte sie auch in einem Puffer sammeln, aber da hätte ich das gleiche Problem.
Das ganze geht teilweise über ein paar Stunden ... brauche dafür dann auch geschätzt 30 GB RAM.

Habe mich jetzt Entschieden, doch Makros zu benutzen, auch wenn ich versuche sie zu meiden. Für meinen Geschmack etwas zu Fehleranfällig.
Wollte sie als "Funktionsersatz" schreiben, mit halbwegs vernünftigem Rückgabewert (deshalb das Bool() macht auch kaum einen Unterschied bei der Geschwindigkeit). Scheinbar ist der Overhead von Proceduren für diese Aufgabe doch zu groß. Mit Makros läuft es noch um einiges schneller.

BitWrite wäre ohne "If, Else" ganz gut ... aber da gibt es ein kleines Problem. Es funktioniert zwar so, ABER ... ich kann nur Konstanten angeben.

CSHW89 hat geschrieben:... 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

Wieso das BitArray? Kann man nicht einfach einen Pointer "hochzählen" ... steht auch so in der Hilfe. Und bei dem Beispielcode unten funktionierts auch.

?

Folgenden Code habe ich jetzt "Zusammengetragen":

Code: Alles auswählen

EnableExplicit
DisableDebugger

Macro SetBit(_ptr_, _pos_)
 Bool(PokeB(_ptr_ + _pos_ >> 3, PeekB(_ptr_ + _pos_ >> 3) | 1 << (_pos_ & 7)))  
EndMacro  

Macro ClearBit(_ptr_, _pos_)   
  Bool(PokeB(_ptr_ + _pos_ >> 3, PeekB(_ptr_ + _pos_ >> 3) & ~(1 << (_pos_ & 7))))
EndMacro
  
Macro ToggleBit(_ptr_, _pos_)
  Bool(PokeB(_ptr_ + _pos_ >> 3, PeekB(_ptr_ + _pos_ >> 3) ! (1 << (_pos_ & 7)))) 
EndMacro

Macro GetBit(_ptr_, _pos_) 
  Bool(PeekB(_ptr_ + _pos_ >> 3) & 1 << (_pos_ & 7))
EndMacro

Macro WriteBit(_ptr_, _pos_, _value_ = 1)   
  Bool(PokeB(_ptr_ + _pos_ >> 3, PeekB(_ptr_ + _pos_ >> 3) | (PeekB(_ptr_ + _pos_ >> 3) ! (-_value_ ! PeekB(_ptr_ + _pos_ >> 3)) & (1 << (_pos_ & 7)))))
EndMacro

Macro ReadBit(_ptr_, _pos_) ; ein WriteBit braucht ein ReadBit ;-)
  GetBit(_ptr_, _pos_)
EndMacro

#memspace = 1000000
Define *test = AllocateMemory(#memspace)
Define i
Define test1start = ElapsedMilliseconds()

For i = 0 To MemorySize(*test) * 8 - 1
  ;SetBit(*test, i)
  ;If Mod(i,2) : ToggleBit(*test, i) : EndIf
  WriteBit(*test, i, i % 2)	; "Ausdruck ist zu komplex (CPU-Register reichen nicht). Bitte splitten SIe ihn" o.O
Next

Define test1endtest2start = ElapsedMilliseconds()

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

Define test2end = ElapsedMilliseconds()
MessageRequester("Bit-Test", "MBit Gesamt: " + StrF(MemorySize(*test) * 8 / 1000000) + Chr(13) + "Schreiben: " + Str(test1endtest2start - test1start) + " ms" + Chr(13) + "Lesen: " + Str(test2end - test1endtest2start) + " ms"+ Chr(13) + "BitRW/s: " + Str(MemorySize(*test) * 8 / (test2end - test1start) * 1000))

CSHW89 · Beitrag von **CSHW89** » 06.03.2015 14:08

Ja es funktioniert. Du rufst allerdings wieder zwei Proceduren auf: PeekB und PokeB. Mit dem BitArray ist das dann nicht nötig. Ich muss aber sagen, ich dachte eigentlich es würde mehr ausmachen. Ich hab mal ein kleinen Test geschrieben:

Code: Alles auswählen

EnableExplicit
DisableDebugger

Structure BitArray
  a.a[0]
EndStructure

Procedure nic(*var.Ascii, pos)
  *var + pos >> 3
  *var\a | (1 << (pos & 7))
EndProcedure

Macro imho(_ptr_, _pos_)
 Bool(PokeB(_ptr_ + _pos_ >> 3, PeekB(_ptr_ + _pos_ >> 3) | 1 << (_pos_ & 7))) 
EndMacro 

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


#memspace = 10000000
Define *test.BitArray = AllocateMemory(#memspace)
Define i

Define test1start = ElapsedMilliseconds()
For i = 0 To MemorySize(*test) * 8 - 1
  nic(*test, i)
Next
Define test1end = ElapsedMilliseconds()

Define test2start = ElapsedMilliseconds()
For i = 0 To MemorySize(*test) * 8 - 1
  imho(*test, i)
Next
Define test2end = ElapsedMilliseconds()

Define test3start = ElapsedMilliseconds()
For i = 0 To MemorySize(*test) * 8 - 1
  cshw89(*test, i)
Next
Define test3end = ElapsedMilliseconds()


MessageRequester("Bit-Test",
                 "nic: "    + Str(test1end - test1start) + " ms" +Chr(10)+
                 "imho: "   + Str(test2end - test2start) + " ms" +Chr(10)+
                 "cshw89: " + Str(test3end - test3start) + " ms")

Ausgabe bei mir ist:

Code: Alles auswählen

nic: 1646 ms
imho: 1581 ms
cshw89: 1451 ms

Also die Version mit dem BitArray ist nochmal etwas schneller, aber nicht sehr viel.

lg Kevin

Thorium · Beitrag von **Thorium** » 06.03.2015 14:29

Imhotheb hat geschrieben: Ja, leider ... muss jedes Bit einzeln setzen ... langer (Un-)Sinn, kurze Erklärung:
ich bekomme von einer externen Lib (Eine Art Wrapper-DLL für eine spezielle I/O Karte) ein Bit mit Zeitstempel.
Es werden Signale von 128 externen MicroControllern mit je ca. 500 Sensoren (nur Ja/Nein) gesendet.
Diese Daten muss ich Sortieren und da auch viel Parallel gearbeitet wird (Threads), muss jedes Bit einzeln geschrieben werden.
Könnte sie auch in einem Puffer sammeln, aber da hätte ich das gleiche Problem.
Das ganze geht teilweise über ein paar Stunden ... brauche dafür dann auch geschätzt 30 GB RAM.

Um sie sortieren zu können müssen sie doch sowieso gepuffert werden, oder?
Aber naja, wenn du immer nur ein Bit mit Zeitstempel bekommst, lässt sich da wirklich nicht so viel machen, wenns nur um die Sortierung geht.

Imhotheb · Beitrag von **Imhotheb** » 06.03.2015 16:29

CSHW89 hat geschrieben: Ich hab mal ein kleinen Test geschrieben

Ausgabe bei mir:

nic: 801
imho: 839
cshw89: 703

bleibt mir nur

... das ich mit Poke und Peek ja auch Proceduren aufrufe habe ich gar nicht bedacht ... verstehe das jetzt auch mit dem BitArray ... dachte erst das war so eine Art Schutz damit ich nicht zu weit mit dem Pointer springe oder über das Ende schreibe.
Werde sehen, was sich am Ende des Projekts am besten bewährt hat, aber schneller ist vermutlich hier auch besser

Thorium hat geschrieben:Um sie sortieren zu können müssen sie doch sowieso gepuffert werden, oder?

ja, natürlich ... es ist natürlich nicht "nur" die Sortierung in der Reihenfolge ... das ist auch nicht das Problem ... nur muss das alles relativ schnell geschehen ... die weitere Verarbeitung kann dann auch etwas länger dauern
So ein "Paket" von der I/O Karte sieht in etwa so aus: 4 Byte Länge ... die ersten 3 Byte sind die Zeit und Reihenfolge etc. im letzten Byte sind die linken 7 Bit weitere Daten, aber für mich nicht relevant ... das letzte Bit ist das was ich dann speichern muss

Hat noch jemand eine Idee wegen dem WriteBit? ... ist jetzt nicht sooo wichtig, würde aber gerne ein "If, Else" Konstrukt vermeiden ... werde versuchen das mal so umzusetzten das ich direkt in den Speicher schreibe, ohne Poke und Peek ... sollte dann ja vielleicht funktionieren ... mal sehen
Bin zwar schon einige Zeit unterwegs mit PureBasic und anderen Sprachen (QBasic, VB,teilweise auch C und C++) aber einzelne Bits und die logischen Operatoren habe ich immer irgendwie gemieden

Sei's drum ... irgendwann muss man ja mal

Thorium · Beitrag von **Thorium** » 06.03.2015 17:02

Imhotheb hat geschrieben: Hat noch jemand eine Idee wegen dem WriteBit? ... ist jetzt nicht sooo wichtig, würde mir aber gerne ein "If, Else" Konstrukt vermeiden ... werde versuchen das mal so umzusetzten das ich direkt in den Speicher schreibe, ohne Poke und Peek ... sollte dann ja vielleicht funktionieren ... mal sehen

Du initialisierst den Puffer mit Nullen und das Problem ist gelöst.

Code: Alles auswählen

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

Das initialisieren des Speichers mit Nullen geht um einiges schneller als bei jedem eine Prüfung durchzuführen. Da wird jedesmal ein Branch generiert, der jede Menge Zeit benötigt.

7x7 · Beitrag von **7x7** » 06.03.2015 17:05

Code: Alles auswählen

EnableASM

Macro MACRO_BitSet(VAR,NR)
	MOV ebx, dword[v_#NR]
	BTS dword[v_#VAR], ebx
EndMacro

Macro MACRO_BitReset(VAR,NR)
	MOV ebx, dword[v_#NR]
	BTR dword[v_#VAR], ebx
EndMacro

Macro MACRO_BitTest(VAR,NR,DESTINATION)
	MOV dword[v_#DESTINATION], 0
	MOV ebx, dword[v_#NR]
	BT  dword[v_#VAR], ebx
	ADC dword[v_#DESTINATION],0
EndMacro

;----------------------------------------

; Bits setzen
a=0
For x=0 To 31
	MACRO_BitSet(a,x)
	Debug a
Next x
Debug "------"

; Bits löschen
For x=0 To 31
	MACRO_BitReset(a,x)
	Debug a
Next x
Debug "------"

; Bits testen
a=%10101010101010101010101010101010
For x=0 To 31
	MACRO_BitTest(a,x,b)
	Debug b
Next x

7x7 · Beitrag von **7x7** » 08.03.2015 17:54

@Imhotheb

Ich denke, mein unten stehender Code trifft dein Problem besser als mein oben geposteter.

Code: Alles auswählen

EnableASM

Macro MACRO32_BitFieldAdress(POINTER,BITNR)
	MOV ECX, dword[p_#POINTER]
	MOV EBX, dword[v_#BITNR]
	MOV EDX, EBX
	SHR EBX, 5
	SHL EBX, 2
	ADD ECX, EBX
	SHL EBX, 3
	SUB EDX, EBX
EndMacro

Macro MACRO32_BitSet(POINTER,BITNR)
	MACRO32_BitFieldAdress(POINTER,BITNR)
	BTS dword[ECX], EDX
EndMacro

Macro MACRO32_BitReset(POINTER,BITNR)
	MACRO32_BitFieldAdress(POINTER,BITNR)
	BTR dword[ECX], EDX
EndMacro

Macro MACRO32_BitTest(POINTER,BITNR,DESTINATION)
	MACRO32_BitFieldAdress(POINTER,BITNR)
	MOV dword[v_#DESTINATION], 0
	BT  dword[ECX], EDX
	ADC dword[v_#DESTINATION], 0
EndMacro

;------------------------------------------------


; dein Test-Programm:


#memspace = 3000000
Define *adr = AllocateMemory(#memspace, #PB_Memory_NoClear)	;"*test" ersetzt wegen EnableASM: TEST wäre ein ASM-Befehl
Define i.l, Result.l

Define test1start = ElapsedMilliseconds()

For i = 0 To MemorySize(*adr) * 8 - 1
	;BitWrite(*adr, i)
	
	MACRO32_BitReset(adr,i)				; wenn du ein Bit setzen möchtest -> dann MACRO32_BitSet()
									       	; der Pointer "adr" wird ohne Stern(*) übergeben!
Next


Define test1endtest2start = ElapsedMilliseconds()

For i = 0 To MemorySize(*Adr) * 8 - 1 
	;BitRead(*adr, i)
	MACRO32_BitTest(adr,i,Result)		; das Ergebnis würde in Result stehen
Next

Define test2end = ElapsedMilliseconds()

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

Um die volle Wirkung auszukosten: Debugger ausschalten nicht vergessen!

Imhotheb · Beitrag von **Imhotheb** » 08.03.2015 19:14

erstmal vielen Dank für die vielen Beiträge

hab einige Stunden erfolglos damit verbracht das erste Beispiel von 7x7 irgendwie so hinzubekommen wie ich es gerne hätte ... 7x7 war dann aber schneller ... und ich hab auch nicht wirklich Ahnung von ASM ... dachte zuerst ich müsste nur den Pointer schieben, aber das war ganz daneben ... egal

Habe jetzt mal das ASM-Makro mit aufgenommen in den Test:

EDIT: habe den Code nochmal geändert, wegen "TEST"

Code: Alles auswählen

EnableExplicit
EnableASM

DisableDebugger

Structure BitArray
  a.a[0]
EndStructure

Procedure nic(*var.Ascii, pos)
  *var + pos >> 3
  *var\a | (1 << (pos & 7))
EndProcedure

Macro imho(_ptr_, _pos_)
 Bool(PokeB(_ptr_ + _pos_ >> 3, PeekB(_ptr_ + _pos_ >> 3) | 1 << (_pos_ & 7)))
EndMacro

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

Macro MACRO32_BitFieldAdress(POINTER,BITNR)
   MOV ECX, dword[p_#POINTER]
   MOV EBX, dword[v_#BITNR]
   MOV EDX, EBX
   SHR EBX, 5
   SHL EBX, 2
   ADD ECX, EBX
   SHL EBX, 3
   SUB EDX, EBX
 EndMacro
 
Macro ASM_7x7(POINTER,BITNR)
  MACRO32_BitFieldAdress(POINTER,BITNR)
   BTS dword[ECX], EDX
EndMacro


#memspace = 10000000
Define *newtest.BitArray = AllocateMemory(#memspace)
Define i

Define test1start = ElapsedMilliseconds()
For i = 0 To MemorySize(*newtest) * 8 - 1
  nic(*newtest, i)
Next
Define test1end = ElapsedMilliseconds()

Define test2start = ElapsedMilliseconds()
For i = 0 To MemorySize(*newtest) * 8 - 1
  imho(*newtest, i)
Next
Define test2end = ElapsedMilliseconds()

Define test3start = ElapsedMilliseconds()
For i = 0 To MemorySize(*newtest) * 8 - 1
  cshw89(*newtest, i)
Next
Define test3end = ElapsedMilliseconds()

Define test4start = ElapsedMilliseconds()
For i = 0 To MemorySize(*newtest) * 8 - 1
  ASM_7x7(newtest, i)
Next
Define test4end = ElapsedMilliseconds()


MessageRequester("Bit-Test",
                 "nic: "    + Str(test1end - test1start) + " ms" +Chr(10)+
                 "imho: "   + Str(test2end - test2start) + " ms" +Chr(10)+
                 "cshw89: " + Str(test3end - test3start) + " ms" +Chr(10)+
                 "7x7: "    + Str(test4end - test4start) + " ms")

hier mein Ergebnis:
nic: 828
imho: 782
cshw89: 715
7x7: 576

Werde das nochmal nativ unter Linux probieren ... ist ja letztlich auch das OS wo sich dann alles abspielt.
Habe bei den Tests festgestellt das es unter Linux nochmals etwas schneller geht ... zumindest in einer VM sind es folgende Werte:
nic: 419
imho: 420
cshw89: 311
7x7: 309

PureBoard

einzelne Bits schnell lesen / schreiben

Re: einzelne Bits schnell lesen / schreiben

Re: einzelne Bits schnell lesen / schreiben

Re: einzelne Bits schnell lesen / schreiben

Re: einzelne Bits schnell lesen / schreiben

Re: einzelne Bits schnell lesen / schreiben

Re: einzelne Bits schnell lesen / schreiben

Re: einzelne Bits schnell lesen / schreiben

Re: einzelne Bits schnell lesen / schreiben