push_back for vector, deque and lists

Question

I am trying to optimize a C++ routine. The main bottleneck in this routine is the push_back() of a vector of objects. I tried using a deque instead and even tried a list. But strangely (and contrary to theory) deque and list implementations run much slower than the vector counterpart.

In fact even clear() runs much slower for the deque and list implementations than the vector counterpart. In this case too, Vector implementation seems to be the fastest while list implementation is the slowest.

Any pointers?

Note: vector reserve() could have sped the implementation but cannot be done as it is unknown in size.

Thanks.

Answer 1

vector being faster to build or clear than deque or list is to be expected; it's a simpler data structure.

With regard to vector::push_back, it has to do two things:

1. check the vector is big enough to hold the new item.
2. insert the new item.

You can generally speed things up by eliminating step 1 by simply resizing the vector and using operator[] to set items.

UPDATE: Original poster asked for an example. The code below times 128 mega insertions, and outputs

push_back           : 2.04s
reserve & push_back : 1.73s
resize & place      : 0.48s

when compiled and run with g++ -O3 on Debian/Lenny on an old P4 machine.

#include <iostream>
#include <time.h>
#include <vector>

int main(int,char**)
{
  const size_t n=(128<<20);

  const clock_t t0=clock();
  {
    std::vector<unsigned char> a;
    for (size_t i=0;i<n;i++) a.push_back(i);
  }
  const clock_t t1=clock();
  {
    std::vector<unsigned char> a;
    a.reserve(n);
    for (size_t i=0;i<n;i++) a.push_back(i);
  }
  const clock_t t2=clock();
  {
    std::vector<unsigned char> a;
    a.resize(n);
    for (size_t i=0;i<n;i++) a[i]=i;
  }
  const clock_t t3=clock();

  std::cout << "push_back           : " << (t1-t0)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl;
  std::cout << "reserve & push_back : " << (t2-t1)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl;
  std::cout << "resize & place      : " << (t3-t2)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl;

  return 0;  
}