Verwendet einen Vektor boolescher Werte langsamer als ein dynamisches Bitset?
Ich habe gerade von Boosts dynamischem Bitset gehört, und ich habe mich gefragt, ob es sich lohnt die Schwierigkeiten. Kann ich stattdessen einfach Vektor von booleschen Werten verwenden?
Sehr viel hängt davon ab, mit wie vielen booleschen Werten Sie arbeiten.
Sowohl bitset als auch vector<bool> verwenden normalerweise eine gepackte Darstellung, bei der ein Boolescher Wert nur als einzelnes Bit gespeichert wird.
Auf der einen Seite führt dies zu einem Overhead in Form von Bitmanipulation, um auf einen einzelnen Wert zuzugreifen.
Andererseits bedeutet das auch, dass viel mehr Boolesche Werte in Ihren Cache passen.
Wenn Sie eine Menge Boolesche Werte verwenden (z. B. wenn Sie ein Sieb von Eratosthenes implementieren), werden mehr von ihnen im Cache fast immer einen Nettogewinn erzielen. Die Verringerung des Speicherverbrauchs wird Ihnen viel mehr bringen, als die Bit-Manipulation verliert.
Die meisten Argumente gegen std::vector<bool> kommen auf die Tatsache zurück, dass es kein Standardcontainer ist (d. h. es erfüllt nicht die Anforderungen für einen Container). IMO, dies ist meist eine Frage der Erwartungen - da es vector sagt, erwarten viele Leute, dass es ein Container ist (andere Arten von Vektoren sind), und sie reagieren oft negativ auf die Tatsache, dass vector<bool> kein a ist Container.
Wenn Sie den Vektor so verwenden, dass er wirklich ein Container ist, dann möchten Sie wahrscheinlich eine andere Kombination verwenden - entweder deque<bool> oder vector<char> kann gut funktionieren. Denken Sie , bevor Sie das tun - es gibt eine Menge (lausiger, IMO) Rat, der vector<bool> im Allgemeinen vermieden werden sollte, mit wenig oder keiner Erklärung, warum es überhaupt vermieden werden sollte, oder unter welchen Umständen es einen wirklichen Unterschied für dich macht.
Ja, es gibt Situationen, in denen etwas anderes besser funktioniert. Wenn Sie in einer dieser Situationen sind, ist es eine gute Idee, etwas anderes zu verwenden. Aber stellen Sie sicher, dass Sie wirklich in einer dieser Situationen sind. Jeder, der Ihnen beispielsweise sagt, dass "Herb sagt, Sie sollten vector<char> verwenden", ohne eine Menge Erklärung über die damit verbundenen Kompromisse, sollte nicht vertraut werden.
Lassen Sie uns ein echtes Beispiel geben. Da es in den Kommentaren erwähnt wurde, betrachten wir das Sieb von Eratosthenes:
%Vor% Wir haben ein ausreichend großes Array verwendet, von dem wir erwarten können, dass ein großer Teil davon den Hauptspeicher belegt. Ich habe mich auch ein wenig bemüht, um sicherzustellen, dass die einzige -Ding, die zwischen einem Aufruf und dem anderen wechselt, die Verwendung von vector<char> vs. vector<bool> ist. Hier sind einige Ergebnisse. Zuerst mit VC ++ 2015:
... dann die Zeit mit g ++ 5.1:
%Vor% Offensichtlich gewinnt die vector<bool> in beiden Fällen - um etwa 15% mit VC ++ und über 30% mit gcc. Beachten Sie auch, dass ich in diesem Fall die Größe so gewählt habe, dass vector<char> in einem sehr günstigen Licht angezeigt wird. Wenn ich zum Beispiel number von 100000000 auf 10000000 reduziere, wird die Zeitdifferenz viel größer:
Obwohl ich nicht viel Arbeit zur Bestätigung geleistet habe, würde ich annehmen, dass in diesem Fall die Version, die vector<bool> verwendet, genügend Speicherplatz speichert, damit das Array vollständig in den Cache passt, während vector<char> ist groß genug, um den Cache zu überlaufen, und viel Hauptspeicherzugriff einbeziehen.
Normalerweise sollten Sie std::vector<bool> vermeiden, da es sich nicht um einen Standardcontainer handelt. Es ist eine gepackte Version, also bricht es einige wertvolle Garantien, die normalerweise von einem vector gegeben werden. Eine gültige Alternative wäre die Verwendung von std::vector<char> , was Herb Sutter empfiehlt.
Sie können mehr darüber in seinem GotW zu diesem Thema lesen.
Aktualisierung:
Wie bereits erwähnt, kann vector<bool> mit gutem Ergebnis verwendet werden, da eine gepackte Darstellung die Lokalität großer Datenmengen verbessert. Je nach den Umständen ist es sehr wahrscheinlich die schnellste Alternative. Allerdings würde ich es immer noch nicht standardmäßig empfehlen, da es viele der Versprechen bricht, die von std::vector erstellt wurden, und das Packen ist ein Kompromiss zwischen Geschwindigkeit und Speicher, der sowohl in der Geschwindigkeit als auch im Gedächtnis von Vorteil sein kann.
Wenn Sie es verwenden möchten, würde ich dies tun, nachdem Sie es für Ihre Anwendung mit vector<char> gemessen haben. Selbst dann würde ich empfehlen, ein typedef zu verwenden, um über einen Namen darauf zu verweisen, der nicht die Garantien zu machen scheint, die er nicht hält.
Es scheint, dass die Größe eines dynamischen Bitsets nicht geändert werden kann: "Die Klasse dynamic_bitset ist nahezu identisch mit der Klasse std :: bitset. Der Unterschied besteht darin, dass die Größe des dynamic_bitset (die Anzahl der Bits) zur Laufzeit während der Erstellung eines dynamic_bitset-Objekts angegeben wird, während die Größe einer std :: Bitset wird bei der Kompilierung über einen Integer-Template-Parameter angegeben. " (aus Ссылка ) Daher sollte es etwas schneller sein, da es etwas weniger Overhead als ein Vektor haben wird, aber Sie verlieren die Fähigkeit, Elemente einzufügen.
UPDATE : Ich stelle nur fest, dass OP nach vector<bool> vs bitset gefragt hat und meine Antwort beantwortet die Frage nicht, aber ich denke, ich sollte es verlassen, wenn Sie nach
vector<bool> ist furchtbar langsam. Zumindest auf meinem Arch Linux System (Sie können wahrscheinlich eine bessere Implementierung oder so etwas bekommen ... aber ich war wirklich überrascht). Wenn jemand irgendwelche Vorschläge hat, warum das so langsam ist, bin ich ganz Ohr! (Sorry für den stumpfen Anfang, hier ist der professionellere Teil.)
Ich habe zwei Implementierungen des SOE geschrieben, und die 'close to metal' C-Implementierung ist zehnmal schneller. sievec.c ist die C-Implementierung und sievestl.cpp ist die C ++ - Implementierung. Ich habe gerade kompiliert mit make (nur implizite Regeln, kein Makefile): und die Ergebnisse waren 1,4 sec für die C-Version und 12 sec für die C ++ / STL-Version :
und
%Vor% sievec.c lautet wie folgt:
sievestl.cpp lautet wie folgt: