c++ - Vector vs Array Performance -

in thread started discussion vectors , arrays, in largely playing devil's advocate, push buttons. however, during course of this, stumbled onto test case has me little perplexed, , have real discussion it, on "abuse" i'm getting playing devil's advocate, starting real discussion on thread impossible. however, particular example has me intrigued, , cannot explain myself satisfactorily.

the discussion general performance of vector vs arrays, ignoring dynamic elements. ex: continually using push_back() in vector going slow down. we're assuming vector , array pre-populated data. example presented, , subsequently modified individual in thread, following:

#include <iostream> #include <vector> #include <type_traits> using namespace std;  const int array_size = 500000000;  // http://stackoverflow.com/a/15975738/500104 template <class t> class no_init_allocator { public:     typedef t value_type;      no_init_allocator() noexcept {}     template <class u>         no_init_allocator(const no_init_allocator<u>&) noexcept {}     t* allocate(std::size_t n)         {return static_cast<t*>(::operator new(n * sizeof(t)));}     void deallocate(t* p, std::size_t) noexcept         {::operator delete(static_cast<void*>(p));}     template <class u>         void construct(u*) noexcept         {             // libstdc++ doesn't know 'is_trivially_default_constructible', still has old names             static_assert(is_trivially_default_constructible<u>::value,             "this allocator can used trivally default constructible types");         }     template <class u, class a0, class... args>         void construct(u* up, a0&& a0, args&&... args) noexcept         {             ::new(up) u(std::forward<a0>(a0), std::forward<args>(args)...);         } };  int main() {     srand(5);  //i use same seed, need random distribution.     vector<char, no_init_allocator<char>> chararray(array_size);     //char* chararray = new char[array_size];     for(int = 0; < array_size; i++) {         chararray[i] = (char)((i%26) + 48) ;     }      for(int = 0; < array_size; i++) {         chararray[i] = chararray[rand() % array_size];     } } 

when run on machine, following terminal output. first run vector line uncommented, second array line uncommented. used highest level of optimization, give vector best chance of success. below results, first 2 runs array line uncommented, second 2 vector line.

//array run # 1 clang++ -std=c++11 -stdlib=libc++ -o3 some.cpp -o b.out && time ./b.out  real    0m20.287s user    0m20.068s sys 0m0.175s  //array run # 2 clang++ -std=c++11 -stdlib=libc++ -o3 some.cpp -o b.out && time ./b.out  real    0m21.504s user    0m21.267s sys 0m0.192s  //vector run # 1 clang++ -std=c++11 -stdlib=libc++ -o3 some.cpp -o b.out && time ./b.out  real    0m28.513s user    0m28.292s sys 0m0.178s  //vector run # 2 clang++ -std=c++11 -stdlib=libc++ -o3 some.cpp -o b.out && time ./b.out  real    0m28.607s user    0m28.391s sys 0m0.178s 

that arrays outperform vectors not surprise me, however, difference on order of 50% surprises me much, expect negligible, , feel nature of test case me obscuring nature of results. when run test on array sizes smaller, performance differences dissipate dramatically.

my explanation:

the additional implementation instructions vector causing vector instructions align in memory poorly, perhaps on example, split @ bad point on 2 different "blocks". causing memory jump , forth between levels of cache vs data cache vs instruction cache more expect. suspect llvm compiler may exaggerating weaknesses, , optimizing poorly, due of newer c++11 elements, though have no reason either of these explanations besides hypothesis , conjecture.

i interested if a: can replicate results , b: if has better explanation how computer running particular benchmark , why vector dramatically underperforming arrays in instance.

my set up: http://www.newegg.com/product/product.aspx?item=n82e16834100226

i can guarantee llvm infact misoptimize std::vector (if in fact optimising @ all), @ least of right now. not correctly inline many of function calls involved. better performance gcc.