lundi 25 décembre 2017

C++: Performance of std::vector vs std::list

I have the following code to profile std::vector performance vs std::list for various N.

void vectorPerf(size_t n)
{
   std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
   std::vector<size_t> cache;
   for (size_t i = 0; i < n; i++) {
      cache.push_back(i);
   }
   std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();

   auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2-t1).count();

   std::cout << duration << " us." << "\n";

   return;
}

void listPerf(size_t n)
{
   std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
   std::list<size_t> cache;
   for (size_t i = 0; i < n; i++) {
      cache.push_back(i);
   }
   std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();

   auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2-t1).count();

   std::cout << duration << " us." << "\n";

   return;
}

int main(int argc, char** argv)
{

   if (argc != 2) {
      return -1;
   }
   std::stringstream ss(argv[1]);
   size_t n;
   ss >> n;
   vectorPerf(n);
   std::cout << "\n";
   listPerf(n);
   std::cout << "\n";
}

For multiple runs of the same set of N, I get results where the results are consistently of the same order as the numbers below:

N       std::vector  std::list
1000    46           116
2000    85           217
5000    196          575
10000   420          1215
100000  3188         10497
1000000 34489        114330

What I am wondering is how come the performance of std::list is consistently worse then std::vector. For std::vector I would have expected the performance to be amortized O(N), because the internal object underpinning std::vector would need to be resized time to time. Since all I am doing is inserting an element to the end of the list I would have expected std::list to be O(1). So that would suggest that std::list would do better than std::vector but the opposite seems to be true.

I would appreciate if someone can shed some light on why this is happening. I am compiling on MacOS 10.12.6 using g++ on a 2015 MBP.

Thanks.

Aucun commentaire:

Enregistrer un commentaire