C++: Bitset Addition / Performance Optimieren
URL: https://www.overclockers.at/coding-stuff/c_bitset_addition_performance_optimieren_104394/page_1 - zur Vollversion wechseln!
FMFlash schrieb am 17.01.2004 um 14:23
Da in den Bitsets die Grundrechnungs-Operatoren wie +, - usw nicht implementiert sind aber doch benötigt werden hab ich mich mal daran gemacht einen einfachen Additionsalgorithmus nach den allgemeinen Regeln der Addition in das Template zu basteln:
bitset<_N>& operator+=(const bitset<_N>& _R){
bitset<_N> _S;
unsigned long _pp;
for (unsigned long _p = _Nw; _p < _N; _p++){
if ((test(_p) == 1 && _R[_p] == 1)){
do{
_pp = _p + 1;
(test(_p) == 1 && _R[_p] == 1) ? true : _S[_p] = 0;
((_pp) < _N) ? (_S[_pp] = 1) : false; _p++;
}while(_S[_p] == 1 && (_R[_p] == 1 || test(_p) == 1));
}else{(test(_p) == 1 || _R[_p] == 1) ? _S[_p] = 1 : false;}}
(*this) = _S;
return (*this);
}
Er funktioniert zwar, ist aber klarerweise extrem langsam. Als ersten Ansatz für die Überlegung war es aber recht hilfreich.
Für mehr Geschwindigkeit mussten alle "manuellen" Tätigkeiten weg (schon allein die Zähler bedeuten Additionen innerhalb einer Addition), also Arbeiten nur mit Binären Operatoren.
Dabei herausgekommen ist folgendes:
bitset<_N>& operator+=(const bitset<_N>& _B){
bitset<_N> _C, _D, _E;
_C = (*this); _D = (*this);
_C &= _B; _C <<= 1; _D ^= _B;
while (_C.none()==false){
_E = _C; _C &= _D;
_C <<= 1; _D ^= _E;}
(*this) = _D;
return (*this);
}
Das läuft schon sehr schnell, ist einer Addition auf zb einen normalen int aber immernoch etwas unterlegen.
Jetzt suche ich noch Anregungen und Verbesserungsvorschläge von den Experten zwecks Optimierung (oder einem anderen Konzept?).
tia!
Ringding schrieb am 17.01.2004 um 22:40
Ich hab keine Ahnung, was du da tun willst. Möglicherweise |= nachimplementieren?
EDIT: Oder das:?
to_ulong() + rhs.to_ulong()
FMFlash schrieb am 18.01.2004 um 00:12
Ich hab keine Ahnung, was du da tun willst. Möglicherweise |= nachimplementieren?
EDIT: Oder das:?
to_ulong() + rhs.to_ulong()
Das erste: Nein
Das zweite: Jein - siehe unten
Ich möchte ganz einfach addieren (wie schon gesagt).
| ist ja bereits implementiert, aber damit sind keine arithmetischen Additionen möglich.
Bsp:
bitset<4> a;
a = 10; (1010)
a |= 9; (1001)
Ergibt 1011 = 11 - nicht 19
to_ulong + to_ulong funktioniert auch nur solange man sich in einem Zahlenbereich bewegt in dem man die Rechnung genausogut mit herkömmlichen Variablen rechnen könnte.
Versuch mal auf ein bitset<1024> das Hausnummer bereits 500 Bit nutzt um eine Zahl abzubilden to_ulong() anzuwenden. 
mat schrieb am 18.01.2004 um 04:29
schwierig etwas über deinen code zu sagen, weil ohne genauen definition von bitset kann man sich ja nur denken was deine überladenen operatoren so machen.
vielleicht ein konzeptvorschlag, der (zB) schon implementiert sein könnte: nicht bitweise arbeiten sondern die bitoperationen auf 32bit level durchführen.
Ringding schrieb am 18.01.2004 um 11:02
In ulong-Blöcken zu arbeiten wird wohl am besten sein - beide Operanden in ein ulong-Array konvertieren (müsste mit & und >> recht schnell gehen), in einer simplen Schleife die beiden addieren, nachher wieder zurück ins Bitset mit << und |.
FMFlash schrieb am 18.01.2004 um 17:22
schwierig etwas über deinen code zu sagen, weil ohne genauen definition von bitset kann man sich ja nur denken was deine überladenen operatoren so machen.
Das Bitset ist ein in der C++ STL definiertes Template mit dem sich beliebig lange "Ketten" von Bits verwalten lassen. Damit ist man also nicht auf den Rahmen den die herkömmlichen Datentypen bieten beschränkt.
Der Operator += ist in dem Fall nicht überladen da er per Standard nicht implementiert ist.
Wenn ich so ein Bitset allerdings zur Darstellung einer Zahl verwende statt für zb eine lange liste von Flags fehlen mir die Grundrechenarten -> hier kommt mein Code ins Spiel.
In ulong-Blöcken zu arbeiten wird wohl am besten sein - beide Operanden in ein ulong-Array konvertieren (müsste mit & und >> recht schnell gehen), in einer simplen Schleife die beiden addieren, nachher wieder zurück ins Bitset mit << und |.
Hm, worin liegt da der Geschwindigkeitsvorteil? Der gleiche Additionsalgorithmus den ich jetzt verwende müsste da (neben der Verwaltung des ulong-arrays) mehrmals durchgeführt werden.
Ringding schrieb am 18.01.2004 um 17:53
Hm, worin liegt da der Geschwindigkeitsvorteil?
Dass deine Schleife 32 (oder 64) mal so oft durchlaufen werden muss.
FMFlash schrieb am 18.01.2004 um 18:13
Dass deine Schleife 32 (oder 64) mal so oft durchlaufen werden muss.
"Meine Schleife" ist Teil der Addition und arbeitet nur solange der sog. Carry nicht 0 ist. Das wird ohne einen komplett anderen Ansatz (ich kenne keinen schnelleren) nicht wegzurationalisieren sein.
Addiere ich zb 1 zu einem 1024 Bit langen Bitset mit dem Inhalt 1100 wird diese Schleife kein einziges mal durchlaufen. Bei 1001 + 1 wäre es 1 mal usw, sprich die länge des Bitsets bestimmt lediglich die maximale Anzahl von durchläufen dieser Schleife, nicht die Mindestanzahl!
Ringding schrieb am 18.01.2004 um 19:41
Gut, aber diese Optimierung (abbrechen, wenn nur mehr 0 kommt), kann man mit größeren Worten ja genauso machen.
FMFlash schrieb am 18.01.2004 um 20:34
Gut, aber diese Optimierung (abbrechen, wenn nur mehr 0 kommt), kann man mit größeren Worten ja genauso machen.
Optimierung ist es in dem Sinn ja noch keine, nur eine Regel der Addition.
Ich rechne mal eine einfache Addition nach dem Algorithmus durch, vielleicht wird es dann deutlich:
(Alle Variablen sind vom Typ bitset mit der Länge _N die der Länge des this-bitsets entspricht)
a: 11011
b:+ 00001
c1: 00010 - a&b << 1
d1: 11010 - a^b
- hier beginnt die schleife. wäre c1 jetzt 0, also gibt es keinen "rest", ist die rechnung beendet (bsp 01^10 = 11)
c2: 00100 - c1&d1 << 1
d2: 11000 - c2^d1
c3: 00000 - c2&d2 << 1
d3: 11100 - c3^d2
- schleife bricht ab
ergebnis = 11100
Worin jetzt der Vorteil liegen soll diesen Vorgang auf Teilstücke zu je 32 Bit aufzusplitten leuchtet mir nicht ganz ein.
Ringding schrieb am 19.01.2004 um 00:55
Die Frage kann man jetzt wohl nur noch durch Benchmarking klären. Vielleicht komm ich ja mal dazu.
overclockers.at v4.thecommunity
© all rights reserved by overclockers.at 2000-2025