I just ran a quick analysis on the performance of various STL containers on simple data insertion. The result was not exactly what I expected so I’d like to share it with you.
What was performed was sequential insertions of 50,000,000 (50 million) unique pointer values into various STL containers, either by push_back or insert, depending on which method is supported by the container. I ran the test on openSUSE 11.2, with g++ 4.4.1, with the compiler options of -std=c++0x -Os -g. The -std=c++0x flag is necessary in order to use std::unordered_set.
Anyway, here is the result I observed:
I was fully aware of the set containers being slower than list and vector on insertion, due to the internal structure of set being more elaborate than those of list or vector, and this test confirms my knowledge. However, I was not aware of such wide gap between list and vector. Also, the difference between unreserved and reserved vector was not as wide as I would have expected. (For the sake of completeness, a reserved vector is an instance of vector whose internal array size is pre-allocated in advance in order to avoid re-allocation.) My belief has always been that reserving vector in advance improves performance on data insertion, which it does, but I was expecting a wider gap between the two. So, the result I see here is a bit unexpected.
In case you want to re-run this test on your own environment, here is the code I used to measure the containers’ performance:
#include <vector> #include <unordered_set> #include <set> #include <list> #include <stdio.h> #include <string> #include <sys/time.h> using namespace std; namespace { class StackPrinter { public: explicit StackPrinter(const char* msg) : msMsg(msg) { fprintf(stdout, "%s: --begin\n", msMsg.c_str()); mfStartTime = getTime(); } ~StackPrinter() { double fEndTime = getTime(); fprintf(stdout, "%s: --end (duration: %g sec)\n", msMsg.c_str(), (fEndTime-mfStartTime)); } void printTime(int line) const { double fEndTime = getTime(); fprintf(stdout, "%s: --(%d) (duration: %g sec)\n", msMsg.c_str(), line, (fEndTime-mfStartTime)); } private: double getTime() const { timeval tv; gettimeofday(&tv, NULL); return tv.tv_sec + tv.tv_usec / 1000000.0; } ::std::string msMsg; double mfStartTime; }; } int main() { size_t store_size = 50000000; { StackPrinter __stack_printer__("vector non-reserved"); string* ptr = 0x00000000; vector<void*> store; for (size_t i = 0; i < store_size; ++i) store.push_back(ptr++); } { StackPrinter __stack_printer__("vector reserved"); string* ptr = 0x00000000; vector<void*> store; store.reserve(store_size); for (size_t i = 0; i < store_size; ++i) store.push_back(ptr++); } { StackPrinter __stack_printer__("list"); string* ptr = 0x00000000; list<void*> store; for (size_t i = 0; i < store_size; ++i) store.push_back(ptr++); } { StackPrinter __stack_printer__("set"); string* ptr = 0x00000000; set<void*> store; for (size_t i = 0; i < store_size; ++i) store.insert(ptr++); } { StackPrinter __stack_printer__("unordered set"); string* ptr = 0x00000000; unordered_set<void*> store; for (size_t i = 0; i < store_size; ++i) store.insert(ptr++); } }
