CODEWITHSUNDEEP
c++performancevectorc++17
Sam Hammamy
Sam Hammamy

Reputation: 11017

C++ Why is an uninitialized Vector's insert as fast as push_back and assignment?

In an attempt to understand how Vectors behave, I coded the following three toy examples:

  1. vector_using_assignment.cc: Initialize a vector to 1,000,000 and assign its elements in a for loop
// 1. vector_using_assignment
#include <iostream>
#include <vector>

int main(int argc, char *argv[]) {
  int N = *argv[1];
  std::vector<int> V(N);
  for (int i =0; i < N; i++) {
      V[i] = i;
  }  
}
$ g++ -O0 -std=c++17 vector_using_assignment.cc -o vector_using_assignment
$ time ./vector_using_assignment 1000000
real    0m0.004s
user    0m0.003s
sys     0m0.001s
  1. vector_using_push_back.cc: Create an empty vector and then assign its elements in a for loop using the push_back method
// 2. vector_using_push_back.cc
#include <iostream>
#include <vector>
int main(int argc, char *argv[]) {
  int N = *argv[1];
  std::vector<int> V;
  for (int i =0; i < N; i++) {
      V.push_back(i);
  }    
}
$ g++ -O0 -std=c++17 vector_using_push_back.cc -o vector_using_push_back
$ time ./vector_using_push_back 1000000
real    0m0.004s
user    0m0.004s
sys     0m0.000s
  1. vector_using_insert.cc Create an empty vector and then assign its elements in a for loop using the insert method
// 3. vector_using_insert.cc
#include <iostream>
#include <vector>
int main(int argc, char *argv[]) {
  int N = *argv[1];
  std::vector<int> V;
  for (int i =0; i < N; i++) {
  V.insert(V.begin(), N - i - 1);
  }
}
$ g++ -O0 -std=c++17 vector_using_insert.cc -o vector_using_insert
$ time ./vector_using_insert 1000000
  real  0m0.004s
  user  0m0.003s
  sys   0m0.001s

As you can see, all methods are exactly equal. My understanding is that push_back is linear in complexity (when size < capacity). This is clearly no the case in this example. Shouldn't the insert method be linear also?

My guesses are that:

  1. c++17 is doing some optimization even though I turned off optimization?
  2. My machine has 2 CPU's with I think 20 cores each, and 32G RAM, so this is making behave differently to what I am thinking? I tried 100,000,000 but still saw no changes

What am I doing wrong here?

Upvotes: 0

Views: 303

Answers (1)

Sam Hammamy
Sam Hammamy

Reputation: 11017

As expected, there was a bug in how I convert the stdin arg to int. The correct way is:

int N = atoi(argv[1]);
std::cout << "N = " << N << std::endl;

Now I see some real differences:

$ time ./vector_using_push_back 1000000000
N = 1000000000

real    0m20.139s
user    0m16.437s
sys 0m3.701s

$ time ./vector_using_assignment 1000000000
N = 1000000000

real    0m7.530s
user    0m6.005s
sys 0m1.525s

$ time ./vector_using_insert 1000000000
N = 1000000000
# I gave up after a couple of min

Upvotes: 0

Related Questions