Smart Zeiger Umbruch Strafe. Memoisierung mit std :: map

Question

Ich bin gerade mitten in einem Projekt, in dem Leistung von entscheidender Bedeutung ist. Im Folgenden sind einige der Fragen, die ich zu diesem Thema hatte.

Question1

Mein Projekt umfasst viele boost::shared_ptr .Ich weiß, auf der Flucht gemeinsamen Zeiger zu schaffen mit boost::make_shared langsam ist, da es eine Menge Aufwand ist, wie es verfolgen, muss references.I wissen wollte, was passiert, wenn Die Boost-Shared-Pointer sind bereits erstellt, dann hätten diese beiden Anweisungen die gleiche Performance oder wäre eine schneller als die andere. Wenn die regulären Zeiger schneller sind und ich bereits Zeiger freigegeben habe, welche Optionen habe ich, um eine Methode aufzurufen, auf die der gemeinsame Zeiger zeigt?

statement1: sharedptr->someMethod(); //here the pointer is a shared ptr created by boost::make_shared 
statement2: regularptr->someMethod(); //here the pointer is a regular one made with new 

Frage 2

Ich habe eine Instanz Methode (n), die sich schnell, die ein std::vector<std::string> auf den Stapel jedes Mal erzeugt aufgerufen wird. Ich beschloss, diesen Vektorzeiger in einer statischen std :: map (d. H.) std::map<std::String,std::vector<std::string>*> zu speichern. Wenn ein Vektor in der Map für den Schlüssel nicht existiert (was der Name der Methode sein könnte). Die gültige Vektoradresse wird erstellt und zur Karte hinzugefügt. Meine Frage lautet: "Es lohnt sich, eine Karte nach einer Vektoradresse zu suchen und eine gültige Adresse zurückzugeben, anstatt nur eine auf dem Stapel zu erstellen wie std::vector<std::string> somevector. Ich hätte auch gerne eine Idee die Leistung von std::map finden

Irgendwelche Ideen diese Bedenken in Bezug auf geschätzt würde

Answer 1

Antwort Q # 1

Wenn die regulären Zeiger schneller sind, und ich habe bereits freigegebenen Zeiger Welche Möglichkeiten habe ich haben, um ein Verfahren, das die freigegebenen Zeiger anrufen?

operator-> innerhalb boost::shared_ptrhas assertion:

typename boost::detail::sp_member_access<T>::type operator->() const 
{ 
    BOOST_ASSERT(px != 0); 
    return px; 
} 

So, zunächst sicher sein, dass Sie NDEBUG definiert haben (in der Regel in Version baut es automatisch geschieht):

#define NDEBUG 

---

Ich habe Assembler Vergleich zwischen Dereferenzierung vongemachtund Rohzeiger:

template<int tag,typename T> 
NOINLINE void test(const T &p) 
{ 
    volatile auto anti_opti=0; 
    ASM_MARKER<tag+0>(); 
    anti_opti = p->data; 
    anti_opti = p->data; 
    ASM_MARKER<tag+1>(); 
    (void)anti_opti; 
} 

---

test<1000>(new Foo); 

ASM Code von test wenn T ist Foo* ist (keine Angst, ich diff unten haben):

_Z4testILi1000EP3FooEvRKT0_: 
.LFB4088: 
.cfi_startproc 
pushq %rbx 
.cfi_def_cfa_offset 16 
.cfi_offset 3, -16 
movq %rdi, %rbx 
subq $16, %rsp 
.cfi_def_cfa_offset 32 
movl $0, 12(%rsp) 
call _Z10ASM_MARKERILi1000EEvv 
movq (%rbx), %rax 
movl (%rax), %eax 
movl %eax, 12(%rsp) 
movl %eax, 12(%rsp) 
call _Z10ASM_MARKERILi1001EEvv 
movl 12(%rsp), %eax 
addq $16, %rsp 
.cfi_def_cfa_offset 16 
popq %rbx 
.cfi_def_cfa_offset 8 
ret 
.cfi_endproc 

---

test<2000>(boost::make_shared<Foo>()); 

ASM Code von test wenn T ist boost::shared_ptr<Foo>:

_Z4testILi2000EN5boost10shared_ptrI3FooEEEvRKT0_: 
.LFB4090: 
.cfi_startproc 
pushq %rbx 
.cfi_def_cfa_offset 16 
.cfi_offset 3, -16 
movq %rdi, %rbx 
subq $16, %rsp 
.cfi_def_cfa_offset 32 
movl $0, 12(%rsp) 
call _Z10ASM_MARKERILi2000EEvv 
movq (%rbx), %rax 
movl (%rax), %eax 
movl %eax, 12(%rsp) 
movl %eax, 12(%rsp) 
call _Z10ASM_MARKERILi2001EEvv 
movl 12(%rsp), %eax 
addq $16, %rsp 
.cfi_def_cfa_offset 16 
popq %rbx 
.cfi_def_cfa_offset 8 
ret 
.cfi_endproc 

---

Hier Ausgabe von diff -U 0 foo_p.asm shared_ptr_foo_p.asm Befehl:

--- foo_p.asm Fri Apr 12 10:38:05 2013 
+++ shared_ptr_foo_p.asm  Fri Apr 12 10:37:52 2013 
@@ -1,2 +1,2 @@ 
-_Z4testILi1000EP3FooEvRKT0_: 
-.LFB4088: 
+_Z4testILi2000EN5boost10shared_ptrI3FooEEEvRKT0_: 
+.LFB4090: 
@@ -11 +11 @@ 
-call _Z10ASM_MARKERILi1000EEvv 
+call _Z10ASM_MARKERILi2000EEvv 
@@ -16 +16 @@ 
-call _Z10ASM_MARKERILi1001EEvv 
+call _Z10ASM_MARKERILi2001EEvv 

Wie Sie sehen können, Unterschied nur in Funktionssignatur ist, und tag nicht -Typ Vorlage Argument Wert, Rest des Codes ist IDENTICAL.

---

Im Allgemeinen - shared_ptr ist sehr teuer - es ist die Referenzzählung zwischen Threads synchronisiert (in der Regel über atomare Operationen). Wenn Sie stattdessen boost::intrusive_ptr verwenden würden, können Sie Ihre eigene increment/decrement ohne Thread-Synchronisierung implementieren, was die Referenzzählung beschleunigen würde.

Wenn Sie es sich leisten können, unique_ptr zu verwenden oder Semantik zu verschieben (über Boost.Move oder C++ 11) - dann wird es keine Referenzzählung geben - es wäre noch schneller.

LIVE DEMO WITH ASM OUTPUT

#define NDEBUG 

#include <boost/make_shared.hpp> 
#include <boost/shared_ptr.hpp> 

#define NOINLINE __attribute__ ((noinline)) 

template<int> 
NOINLINE void ASM_MARKER() 
{ 
    volatile auto anti_opti = 11; 
    (void)anti_opti; 
} 

struct Foo 
{ 
    int data; 
}; 

template<int tag,typename T> 
NOINLINE void test(const T &p) 
{ 
    volatile auto anti_opti=0; 
    ASM_MARKER<tag+0>(); 
    anti_opti = p->data; 
    anti_opti = p->data; 
    ASM_MARKER<tag+1>(); 
    (void)anti_opti; 
} 

int main() 
{ 
    { 
     auto p = new Foo; 
     test<1000>(p); 
     delete p; 
    } 
    { 
     test<2000>(boost::make_shared<Foo>()); 
    } 
} 

Antwort Q # 2

Ich habe eine Instanz Methode (n), die schnell aufgerufen wird, die ein std :: vector auf dem Stapel jedes Mal erstellt.

Im Allgemeinen ist es ratsam, die Kapazität von vector wiederzuverwenden, um teure Neuzuweisungen zu vermeiden.Zum Beispiel ist es besser, zu ersetzen:

{ 
    for(/*...*/) 
    { 
     std::vector<value> temp; 
     // do work on temp 
    } 
} 

mit:

{ 
    std::vector<value> temp; 
    for(/*...*/) 
    { 
     // do work on temp 
     temp.clear(); 
    } 
} 

---

Aber sieht aus wie durch std::map<std::string,std::vector<std::string>*> geben Sie versuchen, irgendeine Art von memoization perfom.

Wie bereits vorgeschlagen, statt std::map die hat O (ln (N)) Lookup/fügen Sie boost::unordered_map/std::unordered_map zu verwenden, können versuchen, die O (1) Durchschnitt und O (N) hat worst Case-Komplexität für Lookup/Einfügung, und bessere Lokalität/Compactess (Cache-freundlich).

Auch COSIDER versuchen Boost.Flyweight:

Flyweights sind kleine Behandlungsklassen ständigen Zugriff auf gemeinsam genutzten Daten gewähren, damit für die Verwaltung großer Mengen von Einheiten innerhalb einer angemessenen Speichergrenzen zu ermöglichen. Boost.Flyweight macht es einfach, diese allgemeine Programmiersprache zu verwenden, indem die Klassenvorlage flyweight, die als ein Drop-in-Ersatz für const T dient.

Answer 2

Für Question1:..

Hauptleistungsgewinn bei einer Architektur Design achived werden kann, Algorithmus verwendet, und während geringe Bedenken sind auch wichtig nur wenn highlevel Design stark ist Lass uns zu deiner Frage kommen, regulärer Zeiger ausführen Diese ist höher als shared_ptr. Aber die Menge an Overhead, die Sie nicht shared_ptr verwenden, ist auch mehr, was die Kosten für die Pflege von Code in längeren Lauf erhöht. Redundante Objekterzeugung und -zerstörung muss in performancekritischen Anwendungen vermieden werden. In solchen Fällen spielt shared_ptr eine wichtige Rolle, die beim gemeinsamen Verwenden gemeinsamer Objekte über Threads spielt, indem der Overhead der Freigabe der Ressourcen reduziert wird. ja Shared Pointer verbraucht mehr Zeit als reguläre Zeiger wegen Refcount, Zuweisung (Objekt, Zähler, Deleter) usw. Sie können shared_ptr schneller machen, indem Sie unnötige Kopie von ihnen verhindern.Verwenden Sie es als ref (shared_ptr const &). Darüber hinaus brauchen Sie keine geteilten Ressourcen über Threads verwenden Sie nicht shared_ptr und normale ptr wird bessere Ergebnisse in diesen Fällen geben.

Frage 2

Wenn Sie wollen, Wiederverwendung Pool von shared_ptr verwenden Objekte, die Sie besser in Objektpool-Design-Pattern Ansatz aussehen kann. http://en.wikipedia.org/wiki/Object_pool_pattern

Answer 3

Q1: Gerade bei der Umsetzung:

T * operator->() const // never throws 
{ 
    BOOST_ASSERT(px != 0); 
    return px; 
} 

Offensichtlich ist es eine Membervariable zurückkehrt und nichts auf der Fliege zu berechnen, so dass die Leistung so schnell sein wird, einen einfachen Zeiger (vorbehaltlich als dereferencing Die üblichen Macken der Compiler-Optimierung/Leistung eines nicht optimierten Builds können immer erwartet werden, um zu saugen - keine Überlegung wert.

Q2: „. Es lohnt sich ein map für eine vector Adresse suchen und wieder eine gültige Adresse Rückkehr nur über einen auf dem Stapel wie std::vector<std::string> somevector Schaffung möchte ich auch eine Idee, auf die Leistung von std::map::find“

Ob es sich lohnt, es auf die Menge der Daten abhängt, die in der vector kopiert werden müssen, und in geringerem Ausmaß die Anzahl der Knoten in der map, die Länge der gemeinsamen Präfixe in den Schlüsseln werden etc verglichen .. Als immer, wenn es dich interessiert, Benchmark. Im Allgemeinen würde ich jedoch erwarten, dass die Antwort Ja ist, wenn die Vektoren eine signifikante Menge an Daten enthalten (oder dass sich die Daten nur langsam regenerieren). std::map ist ein Balance-Binärbaum, so erwarten Sie im Allgemeinen Lookups in O (log2N), wobei N die aktuelle Anzahl der Elemente ist (d. H. size()).

Sie könnten auch eine Hash-Tabelle verwenden - das gibt O (1), die für eine große Anzahl von Elementen schneller ist, aber es ist unmöglich zu sagen, wo der Schwellenwert ist. Die Leistung hängt immer noch davon ab, wie teuer die Hash-Funktion ist, die Sie für Ihre Schlüssel verwenden (einige Hash-Implementierungen wie Microsofts std::hash enthalten nur maximal 10 Zeichen entlang der gehashten Zeichenkette, also gibt es eine obere Grenze für die Zeit, aber massiv mehr Kollisionspotenzial)), Hashtabellenkollisionshandhabungsansätze (z. B. Verschiebungslisten zum Suchen alternativer Buckets vs. alternative Hashfunktionen vs. aus Buckets gekettete Container) und die Kollisionsanfälligkeit selbst.

Answer 4

Frage 1:

Ich benutze Zeiger in meinem Projekt geteilt ausgiebig, aber ich möchte nicht shared_ptr<T> verwenden. Es erfordert ein Heap-Objekt, das separat von T selbst zugewiesen wird, so dass der Speicherzuordnungsaufwand verdoppelt wird und die Speichernutzung um einen Betrag zunimmt, der von der Implementierung Ihrer Laufzeitbibliothek abhängt. intrusive_ptr ist effizienter, aber es ist ein Schlüsselproblem, das mich ärgert, und das Funktionsaufruf ist:

void Foo(intrusive_ptr<T> x) {...} 

jedes Mal, wenn Foo aufrufen, müssen die Referenzzählung des Parameters x mit einem relativ teuren Atomschritt erhöht werden und dann auf dem Weg nach unten dekrementiert. Dies ist jedoch redundant, da Sie normalerweise davon ausgehen können, dass der Anrufer bereits einen Verweis auf x hat und dass der Verweis für die Dauer des Anrufs gültig ist. Es gibt verschiedene Möglichkeiten, dass der Aufrufer nicht bereits eine Referenz hat, aber es ist nicht schwer, den Code so zu schreiben, dass die Referenz des Aufrufers immer gültig ist.

Daher bevorzuge ich meine eigene Smart-Pointer-Klasse, die die gleiche wie intrusive_ptr ist, außer dass es implizit in und von T * konvertiert. Dann erkläre ich immer meine Methoden Ebene Zeiger zu nehmen, die Vermeidung unnötiger Referenzzählung:

void Foo(T* x) {...} 

Dieser Ansatz bewährt hat sich gut in meinem Projekt zu arbeiten, aber um ehrlich zu sein, habe ich eigentlich nie den Unterschied in der Leistung gemessen macht.

Verwenden Sie vorzugsweise auch auto_ptr (C++ 03) oder unique_ptr (C++ 11), wenn möglich.

Frage 2:

Ich verstehe nicht, warum Sie mit einem std denken :: map. Zuallererst wird hash_map schneller (solange es nicht die VC++ Dinkumware-Implementierung in VS2008/2010, details in here somewhere ist), und zweitens, wenn Sie nur einen Vektor pro Methode benötigen, warum nicht eine statische Variable vom Typ verwenden?

Wenn Sie bei jedem Aufruf der Methode den Vektor in einer Hashtabelle nachschlagen müssen, ist es wahrscheinlich, dass Sie im Vergleich zum Erstellen eines neuen Vektors nur wenig oder gar keine Zeit sparen. Wenn Sie den Vektor in einer std :: map nachschlagen, dauert es noch länger.