Copy- versus Move-Semantik: Ein paar Zahlen

Viel wurde über die Vorteile der Move- gegenüber der Copy-Semantik schon geschrieben. Anstelle einer teuren copy-Operation kommt eine billige move-Operation zum Einsatz. Doch was heißt das? In diesem Artikel vergleiche ich die Performanz der Copy- mit der Move-Semantik bei den Containern der Standard Template Library (STL).

Bevor ich aber auf die Zahlen eingehe, möchte ich noch ein bisschen Hintergrundwissen vermitteln.

Copy- versus Move-Semantik

Der feine Unterschied der Copy- und der Move-Semantik zur Erzeugung eines neuen Objekts ist es, dass bei der Copy-Semantik die Elemente der Ressource teuer kopiert und bei der Move-Semantik die Elemente der Ressource billig verschoben werden. Das hat zwei weitreichende Konsequenzen.

1. Bei der Copy-Semantik besteht die Gefahr, dass eine std::bad_alloc Ausnahme geworfen wird, falls kein Speicher mehr für das neue Objekt vorhanden ist.
2. Bei der Move-Semantik ist nach der Operation die Quelle der Move-Operation in einem gültigen, aber nicht genauer spezifizierten Zustand ("valid but unspecified state").

Gerade der zweite Punkt lässt sich schön an einem Beispiel mit std::string verdeutlichen.

Zuerst zur klassischen Copy-Semantik.

Copy-Semantik

std::string1("ABCDEF");
std::string str2;
str2= str1;

Nach der copy-Operation besitzen beide Strings str1 und str2 den gleichen Inhalt "ABCDEF". Worin besteht der Unterschied zur Move-Semantik?

Move-Semantik

std::string1("ABCDEF");
std::string str3;
str2= std::move(str1);

Im Gegensatz zur Copy-Semantik besitzt bei der Move-Semantik die Quelle der Operation str1 einen leeren String der Form "". In dem kleinen Codebeispiel habe ich die Move-Semantik explizit mit der Funktion std::move angefordert. Der Compiler wendet die Move-Semantik aber dann automatisch an, wenn er sicher ist, dass die Quelle seiner move-Operation nicht mehr benötigt wird.

Im meiner Performanzbetrachtung werde ich die Move-Semantik mit std::move explizit vom Compiler anfordern. 

Der Performanzunterschied

In diesem Artikel will ich eine naive Position einnehmen und vergleichen, welche Performanzunterschiede zwischen der Copy- und Move-Semantik bei den Containern der STL bestehen. Meine Betrachtung schließt den std::string mit ein. Die assoziativen Container, die mehrere gleiche Schlüssel erlauben, werde ich ignorieren. Darüber hinaus interessiert mich das Performanzverhältnis der vorgestellten Container zwischen der Copy- und Move-Semantik.

Die Randbedingungen

Da in diesem konkreten Unterschied die Performanzunterschiede nicht so drastisch bzgl. der maximal optimierten und nicht optimierten Programmausführung waren, werde ich mich der Einfachheit und Übersichtlichkeit halber auf das maximal optimierte Executable zurückziehen. Zum Einsatz kommt in bekannter Manier der GCC 4.9.2 und der cl.exe, der Bestandteil von Microsoft Visual Studio 2015 ist. Sowohl die Linux als auch die Windows Plattform sind 64bit. Darüber hinaus erzeuge ich 64bit Executables.

Das Programm 

Durch die vielen Container der STL wird das Programm recht länglich.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105

// movePerformance.cpp
 
#include <array>
#include <forward_list>
#include <chrono>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int SIZE = 10000000; 

template <typename T>
void measurePerformance(T& t, const std::string& cont){
  
  std::cout << std::fixed << std::setprecision(10);

  auto begin= std::chrono::system_clock::now();
  T t1(t);
  auto last=  std::chrono::system_clock::now() - begin;
  std::cout << cont << std::endl;
  auto copyTime=  std::chrono::duration<double>(last).count();
  std::cout <<  "    Copy: " << copyTime << " sec" << std::endl;

  begin= std::chrono::system_clock::now();
  T t2(std::move(t));
  last=  std::chrono::system_clock::now() - begin;
  auto moveTime= std::chrono::duration<double>(last).count();
  std::cout <<  "    Move: " << moveTime << " sec" << std::endl;
  
  std::cout << std::setprecision(2);
  std::cout << "    Ratio (copy time/move time): " << (copyTime/moveTime) << std::endl;
  
  std::cout << std::endl;
     
}

int main(){
    
    std::cout << std::endl;
    
    {
      std::array<int,SIZE/1000> myArray;
      measurePerformance(myArray,"std::array<int,SIZE/1000>");   
    }
    
    {
      std::vector<int> myVec(SIZE);
      measurePerformance(myVec,"std::vector<int>(SIZE)");
    }

    {
      std::deque<int>myDec(SIZE);
      measurePerformance(myDec,"std::deque<int>(SIZE)");
    }
    
    {
      std::list<int>myList(SIZE);
      measurePerformance(myList,"std::list<int>(SIZE)");
    }
    
    {
      std::forward_list<int>myForwardList(SIZE);
      measurePerformance(myForwardList,"std::forward_list<int>(SIZE)");
    } 
       
    {
      std::string myString(SIZE,' ');
      measurePerformance(myString,"std::string(SIZE,' ')");
    }
    
    std::vector<int> tmpVec(SIZE);
    std::iota(tmpVec.begin(),tmpVec.end(),0);
    
    {
      std::set<int>mySet(tmpVec.begin(),tmpVec.end());
      measurePerformance(mySet,"std::set<int>");
    }
    
    {
      std::unordered_set<int>myUnorderedSet(tmpVec.begin(),tmpVec.end());
      measurePerformance(myUnorderedSet,"std::unordered_set<int>");
    }
    
    {
      std::map<int,int>myMap;
      for (auto i= 0; i <= SIZE; ++i) myMap[i]= i;
      measurePerformance(myMap,"std::map<int,int>");
    }
    
    {
      std::unordered_map<int,int>myUnorderedMap;
      for (auto i= 0; i <= SIZE; ++i) myUnorderedMap[i]= i;
      measurePerformance(myUnorderedMap,"std::unordered_map<int,int>");
    }  
    
}

Das Ziel des Programms ist es, die Container mit 10 Millionen Elementen per Copy- bzw. Move-Semantik zu initialisieren. Die Performanzmessung findet in dem Funktions-Template measurePerformance (Zeile 21 - 44). Diese Funktion ist über den Typ des Containers und seinen Namen parametrisiert. Mit Hilfe der chrono-Bibliothek messe ich, wie lange die copy-Initialisierung (Zeile 27) und move-Initialisierung (Zeile 34) benötigt. Zum Schluss interessiert mich noch das Zeitverhältnis zwischen der Copy- und Move-Semantik (Zeile 40).

Was passiert in der main-Funktion? Jeden Container lege ich einen lokalen Gültigkeitsbereich an, so dass er automatisch wieder freigegeben wird. So wird myArray (Zeile 51) am Ende seines Gültigkeitsbereichs in Zeile 53 wieder aufgeräumt. Das ist bei der Größe der Container absolut notwendig. Ich habe behauptet, jeder Container besitzt 10 Millionen Elemente. Dies trifft auf alle Container bis auf myArray zu. Da myArray auf dem Stack und nicht auf dem Heap angelegt wird, muss ich seine Größe deutlich reduzieren. Nun aber zu den restlichen Containern. Mit std::vector, std::deque, std::list und std::forward_list folgen in den Zeilen 55 - 73 die restlichen sequentiellen Container. std::string kommt in Zeile 75 - 78 zum Einsatz. Die verbleibenden Container sind die geordneten und ungeordneten assoziativen Container der STL. Eine Besonderheit muss ich natürlich bei den assoziativen Containern beachten. Damit sie alle verschiedene Schlüssel und damit die Länge 10 Millionen besitzen, verwende ich als Schlüssel die Zahlen von 0 bis 9999999. Diese erzeugt mir die std::iota Funktion.

Die Zahlen

Die Ergebnis für std::array sind nicht besonders aussagekräftig. Dies gilt zum einen, da das std::array deutlich kleiner ist, dies gilt zum anderen, da die Zeitdifferenz unter Windows unter der Genauigkeit der Uhr std::system_clock liegt. Die gleiche Aussage gilt für std::forward_list unter Windows.

Welche Erkenntnisse lassen sich aus den Zahlenkolonnen ableiten?

• Sequentielle Container: std::vector ist erfahrungsgemäß der schnellste Container, wenn es um das kopieren oder verschieben geht.
• Sequentielle versus assoziative Container: Die sequentiellen Container lassen sich sowohl unter Linux als auch insbesondere unter Windows schneller kopieren. 
• Copy- versus Move-Semantik: Die Performanzunterschiede zwischne der Copy- und Move-Semantik sind enorm. Dies trifft vor allem auf die assoziativen Container zu.
• std::string: Der std::string unter Linux besitzt ein sehr seltsames Verhalten. Zum einen lässt er sich enorm performant kopieren, zum anderen ist die Move-Semantik nur um den Faktor 16 schneller. Diese Beobachtung wird noch verstärkt, wenn ich das Programm ohne Optimierung ausführe. In diesem Fall schlägt auf meiner Plattform die Move-Semantik die Copy-Semantik nur um den Faktor 1.5. Das steht im starken Gegensatz zu std::string unter Windows. Dort ist die Move-Semantik um den Faktor 15000 schneller als die Copy-Semantik.

Das Rätsel um std::string

Der Unterschied zwischen dem Performanzunterschied der Copy- und Move-Semantik zwischen Linux und Windows ist schnell erklärt. Mein GCC implementiert den std::string nach dem copy-on-write (cow) Prinzip. Das ist aber nicht C++11 standardkonform. Hier folgt wohl schon der cl.exe dem C++11-Standard. Übersetze ich das Programm daher mit dem sehr aktuellen GCC 6.1 und C++11-Standard mit dem Onliner-Compiler auf en.cppreference.com, so verändert sich das Performanzverhalten den std::string deutlich.

Jetzt schlägt die Move-Semantik die Copy-Semantik deutlich.

Wie geht's weiter?

Das war der Motivationsschub für die Move-Semantik. Im nächsten Artikel gehe ich auf die Move-Semantik genauer ein.

Go to Leanpub/cpplibrary "What every professional C++ programmer should know about the C++ standard library".   Hole dir dein E-Book. Unterstütze meinen Blog.