Aktuelle Zeit: 27.01.2020 12:00

Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]




Ein neues Thema erstellen Auf das Thema antworten  [ 18 Beiträge ]  Gehe zu Seite 1, 2  Nächste
Autor Nachricht
 Betreff des Beitrags: einzelne Bits schnell lesen / schreiben
BeitragVerfasst: 04.03.2015 13:04 
Offline
Benutzeravatar

Registriert: 10.10.2014 13:14
Wohnort: Wolfenbüttel
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 :lurk: :coderselixir: :lurk: :coderselixir:

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:
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

_________________
weil einfach einfach einfach ist ... mach' ich es anders


Zuletzt geändert von Imhotheb am 04.03.2015 13:44, insgesamt 1-mal geändert.

Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: einzelne Bits schnell lesen / schreiben
BeitragVerfasst: 04.03.2015 13:36 
Offline
Benutzeravatar

Registriert: 03.06.2007 14:36
Wohnort: Von der Sonne aus gesehen der dritte Planet
Schau dir mal an wie ich es gelöst habe. http://purebasic.fr/german/viewtopic.php?f=3&t=28758&p=329001#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

_________________
PS: Alle im Text enthaltenen Schreibfehler sind beabsichtigt und dienen der Belustigung aller

Bild


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: einzelne Bits schnell lesen / schreiben
BeitragVerfasst: 04.03.2015 13:51 
Offline
Benutzeravatar

Registriert: 08.09.2004 00:57
Wohnort: Berlin
@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

_________________
PureBasic 5.71 | SpiderBasic 2.30 | Windows 10 Pro (x64) | Linux Mint 19.3 (x64)
Nutella hat nur sehr wenig Vitamine. Deswegen muss man davon relativ viel essen.
Bild


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: einzelne Bits schnell lesen / schreiben
BeitragVerfasst: 04.03.2015 13:57 
Offline
Benutzeravatar

Registriert: 03.06.2007 14:36
Wohnort: Von der Sonne aus gesehen der dritte Planet
@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

_________________
PS: Alle im Text enthaltenen Schreibfehler sind beabsichtigt und dienen der Belustigung aller

Bild


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: einzelne Bits schnell lesen / schreiben
BeitragVerfasst: 04.03.2015 14:04 
Offline
Ein Admin
Benutzeravatar

Registriert: 29.08.2004 20:20
Wohnort: Saarbrücken
Also das kann man schon wesentlich effizienter schreiben:
Code:
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.

_________________
Ubuntu Gnome 19.04 LTS x64, PureBasic 5.71 x64 (außerdem 4.41, 4.50, 4.61, 5.00, 5.10, 5.11, 5.21, 5.22, 5.30, 5.31, 5.40, 5.50, 5.60)
"Die deutsche Rechtschreibung ist Freeware, du darfst sie kostenlos nutzen – Aber sie ist nicht Open Source, d. h. du darfst sie nicht verändern oder in veränderter Form veröffentlichen."


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: einzelne Bits schnell lesen / schreiben
BeitragVerfasst: 04.03.2015 14:11 
Offline
Benutzeravatar

Registriert: 10.10.2014 13:14
Wohnort: Wolfenbüttel
PERFECT :allright:

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 :twisted: :

Code:
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

_________________
weil einfach einfach einfach ist ... mach' ich es anders


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: einzelne Bits schnell lesen / schreiben
BeitragVerfasst: 04.03.2015 14:13 
Offline
Benutzeravatar

Registriert: 10.10.2014 13:14
Wohnort: Wolfenbüttel
werde das von NicTheQuick später testen ... muss jetzt erstmal los

_________________
weil einfach einfach einfach ist ... mach' ich es anders


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: einzelne Bits schnell lesen / schreiben
BeitragVerfasst: 04.03.2015 15:15 
Offline
Benutzeravatar

Registriert: 12.06.2005 11:15
Wohnort: Germany
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.

_________________
Zu mir kommen behinderte Delphine um mit mir zu schwimmen.

Wir fordern mehr Aufmerksamkeit für umfallende Reissäcke! Bild


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: einzelne Bits schnell lesen / schreiben
BeitragVerfasst: 04.03.2015 15:59 
Offline
Benutzeravatar

Registriert: 25.01.2005 12:19
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... :wink:

http://www.purebasic.fr/german/viewtopic.php?f=8&t=11820&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:
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


Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: einzelne Bits schnell lesen / schreiben
BeitragVerfasst: 05.03.2015 00:56 
Offline
Benutzeravatar

Registriert: 14.12.2008 12:22
NicTheQuick's Variante würde ich dann noch etwas abändern:
Code:
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:
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

_________________
Bild Bild Bild
http://www.jasik.de - Windows Hilfe Seite

padawan hat geschrieben:
Ich liebe diese von hinten über die Brust ins Auge Lösungen


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 18 Beiträge ]  Gehe zu Seite 1, 2  Nächste

Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 3 Gäste


Sie dürfen keine neuen Themen in diesem Forum erstellen.
Sie dürfen keine Antworten zu Themen in diesem Forum erstellen.
Sie dürfen Ihre Beiträge in diesem Forum nicht ändern.
Sie dürfen Ihre Beiträge in diesem Forum nicht löschen.

Suche nach:
Gehe zu:  

 


Powered by phpBB © 2008 phpBB Group | Deutsche Übersetzung durch phpBB.de
subSilver+ theme by Canver Software, sponsor Sanal Modifiye