Warum ist std::deque so viel langsamer als std::vector?



  • Über einen std::vector ist viel schneller als über eine std::deque zu iterieren. Aber ich verstehe nicht wieso.

    Es heisst ja, bei einem vector<> liegt der Speicher direkt hintereinander und ist deshalb sehr cache efficient. Bei einer deque<> sind es mehrere Chunks, und wegen den Sprüngen zwischen diesen Chunks ist es langsamer.

    Aaaber, das Betriebssystem gibt dem vector auch nicht den Speicher hintereinander. Das vergibt Memory Pages à 4 KB, und beim drüberiterieren muss zwischen diesen hin und her gesprungen werden, weil der Prozessor nichts darüber weiss. Eine deque nimmt Chunks à 4 KB und muss deshalb nicht mehr und nicht weniger im Speicher hin und her springen als ein vector.

    Gut, eine deque hat etwas Verwaltungsoverhead und muss Adressen umrechnen (aber das OS genauso), aber das dürfte doch nicht so einen Unterschied machen ... oder doch?



  • dequorator schrieb:

    Eine deque nimmt Chunks à 4 KB und muss deshalb nicht mehr und nicht weniger im Speicher hin und her springen als ein vector.

    wie kommst du darauf?



  • Bevor wir überhaupt irgendwas diskutieren, sag uns, wie du "langsamer" gemessen hast.



  • Die Chunks die eine deque nimmt sind echt mini. Nen paar 100 bytes oder so.



  • Solange es keine page-faults gibt, werden bei vector die Frames durch den Prozessor bestimmt, also in Hardware und deutlich schneller.
    Bei deque muss der iterator zur richtigen Stelle springen und ich weiß nicht, wie er das genau macht, aber mir fällt keine Implementierungsmöglichkeit ein, bei der nicht bei jedem Schritt wieder überprüft werden muss, ob man sich am Ende des Segments befindet.
    Außerdem holt deque sich nicht immer 4 KB chunks, sondern oft genug Speicher für eine bestimmte Anzahl an Elementen (z.B. für 512).

    Außerdem ist deque bei komplizierten Tpen noch nicht einmal langsamer.

    Lies dir DAS und DAS mal durch.



  • Welchen physischen Speicher der Vektor kriegt, ist üblicherweise ziemlich egal; die Übersetzung von virtueller in physische Adresse macht in einem PC die CPU in Hardware. (nebenbei: Wenn du wissen willst, warum Intel heute Desktop-CPUs rausbringt, die trotz 64-Bit-Architektur nur 32GB physischen Speicher adressieren können, ist der Mechanismus, wie das funktioniert, das, was du nachschlagen willst. Stichwort: TLB)

    Cachefreundlich ist eine std::deque aber auch: Die Chunks dürften in der Regel deutlich breiter sein als eine Cacheline. Der Unterschied wird sich hier im Wesentlichen daraus ergeben, dass ein Vektor auf einem x86 mit einer Instruktion (lea) einen Wert aus dem Vektor ziehen kann respektive beim Iterieren einfach einen Zeiger hochzählt, während eine std::deque einen zweistufigen Lookup machen respektive beim Hochzählen des Zeigers immer prüfen muss, ob sie gerade aus dem Chunk herausgelaufen ist.



  • Der Compiler kann es beim vector auch noch besser optimieren. Ich habe es mal beim Visual Studio 10 ausprobiert.
    C++-Code:

    sum = std::accumulate( begin(container), end(container), 0 );
    

    'container' ist einmal ein vector und einmal eine deque jeweils mit 100000 Elementen (Typ int).

    Maschinencode bei vector (nur die innerste Schleife):

    00401804  add         ebx,dword ptr [eax]    // <=========== ADD
    00401806  add         eax,4
    00401809  cmp         eax,esi  
    0040180B  jne         mach<std::vector<int,std::allocator<int> > >+144h (401804h)
    

    und der bei deque:

    00401A55  mov         ebx,dword ptr [ebp-10h]  
    00401A58  mov         eax,ecx  
    00401A5A  mov         edx,ecx  
    00401A5C  shr         eax,2  
    00401A5F  and         edx,3  
    00401A62  cmp         ebx,eax  
    00401A64  ja          $LN190+30h (401A68h)  
    00401A66  sub         eax,ebx  
    00401A68  mov         ebx,dword ptr [ebp-14h]  
    00401A6B  mov         eax,dword ptr [ebx+eax*4]  
    00401A6E  add         esi,dword ptr [eax+edx*4]   // <===== ADD
    00401A71  inc         ecx  
    00401A72  cmp         ecx,edi  
    00401A74  jne         $LN190+1Dh (401A55h)
    

    das sind 14 Maschinencode-Aufrufe gegenüber 4 beim vector. Selbst das Addieren an sich geschieht bei der deque über eine Indirektion mehr, benötigt also sicher mindestens einen Taktzyklus mehr.

    Ergebnis: die ints im vector werden 3mal so schnell addiert, wie die in der deque.

    Gruß
    Werner



  • Hab ich neulich auch erst getestet. So'n deque-Iterator ist schon komplizierter. Das Iterieren kann man aber trotzdem beschleunigen, wenn man Implementierungsdetails ausnutzt. Nur, weil's mich interessierte, hatte ich das mal gebenchmarkt, also, ein eigenes for_each für deque-Iteratoren gebaut, was wieder viel flotter war. Hier die speziellere for_each-Funktion für deque-Iteratoren aus libstd++

    template<class T, class Ref, class Ptr, class Fun>
    Fun deque_for_each(std::_Deque_iterator<T,Ref,Ptr> beg,
                       std::_Deque_iterator<T,Ref,Ptr> end, Fun fun)
    {
    	while (beg != end) {
    		Ptr segment_end = (beg._M_node != end._M_node) ? beg._M_last : end._M_cur;
    		do {
    			fun(*beg);
    			++(beg._M_cur);
    		} while (beg._M_cur != segment_end);
    		--(beg._M_cur); // let the iterator itself handle
    		++beg;          // the jump to the next node
    	}
    	return fun;
    }
    

    Ja, ist nicht portabel, weiß ich. Die Neugier war aber groß genug.



  • aber in der standardbibliothek könnte man sowas (als speziellere Überladung von std::for_each) ja eigentlich einbauen ... für eine höhere QoI. Nur leider gibt's ja noch viele andere Algorithmen, die auch iterieren wollen. Der Witz der Iteratoren ist ja gerade, dass man die Algorithmen nur 1mal generisch schreiben muss. Ein bisschen unbefriedigend, so eine for_each-Extrawurst für deque.



  • Vielen Dank für die tollen Antworten!


Log in to reply