5

I was looking at the new chrono library (C++11) and trying to use it. I wrote the two following programs:

vector.cpp

#include <iostream>
#include <vector>
#include <chrono>

int main()
{
    std::vector<double> vector(1000000, 0.);

    auto start = std::chrono::high_resolution_clock::now();
    for(int i(0); i < vector.size(); i++)
    {
        vector[i] += 1.;
    }
    auto end = std::chrono::high_resolution_clock::now();

    std::cout << "Elapsed time: " << std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count() << " milliseconds" << std::endl;

    return 0;
}

array.cpp

#include <iostream>
#include <array>
#include <algorithm>
#include <chrono>

int main()
{
    std::array<double, 1000000> array;

    std::fill(array.begin(), array.end(), 0.);

    auto start = std::chrono::high_resolution_clock::now();
    for(int i(0); i < array.size(); i++)
    {
        array[i] += 1.;
    }
    auto end = std::chrono::high_resolution_clock::now();

    std::cout << "Elapsed time: " << std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count() << " milliseconds" << std::endl;

    return 0;
}

I obtained 9 millisecond for the array program and 12 milliseconds for the vector program. The std::vector seems about 33% slower than the std::array. I'm doing it right? Why this difference?

Ps: I'm using GCC 4.7, Mac OS X 10.7.

g++-mp-4.7 -std=c++11 vector.cpp -o vector
g++-mp-4.7 -std=c++11 array.cpp -o array
Improve this question
10
  • 3
    Change to for(int i(0), iMax( vector.size() ); i < iMax; i++). Commented Aug 25, 2012 at 10:09
  • Did you run it enough times to ensure your times are statistically accurate? - 3ms difference in 1 run might not be meaningful. Commented Aug 25, 2012 at 10:11
  • 1
    @R.M., to make sure that you are not doing any extra work on every iteration - you should do it for both versions. Commented Aug 25, 2012 at 10:13
  • 2
    As an aside, you don need std::fill to zero the array, you can initialize it like this std::array<double, 1000000> array{}. Commented Aug 25, 2012 at 10:20
  • 9
    You should also switch on optimization, otherwise the exercise it completely academic. Commented Aug 25, 2012 at 10:23

3 Answers 3

Reset to default
10

I changed your code to this:

std::array<double, 1000000> array;

double total = 0;
std::fill(array.begin(), array.end(), 0.);

for (unsigned j = 0; j < 1000; ++j)
{
    auto start = std::chrono::high_resolution_clock::now();

    for (unsigned i = 0; i < array.size(); i++)
    {
        array[i] += 1.;
    }

    auto end = std::chrono::high_resolution_clock::now();
    total = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
}

std::cout << total << " for Array." << std::endl;

std::vector<double> vector(1000000, 0.);
total = 0;

for (unsigned j = 0; j < 1000; ++j)
{
    auto start = std::chrono::high_resolution_clock::now();

    for (unsigned i = 0; i < vector.size(); i++)
    {
        vector[i] += 1.;
    }

    auto end = std::chrono::high_resolution_clock::now();
    total = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
}

std::cout << total << " for Vector." << std::endl;

My results using -O3:

8123 for Array.
8117 for Vector.

Seems to me that both are equally fast.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I confirm your results (with the O3 option): 3005 for Array. 3018 for Vector. For 10000 cycles: 30103 for Array. 30082 for Vector.
2

The numbers are meaningless without enabling optimizations. Most likely the repeated calls to size() make the difference in your case.

Improve this answer

Comments

1

A std::array has a size known at compile time, so the memory will most likely be allocated on the stack.

A std::vector uses std::allocator (which probably uses `new to allocate memory from the free store (aka the heap) at runtime).

I would say 30% is normal for heap vs stack allocation.

EDIT: Running this a couple of times (not the most scientific measurement, I know) on liveworkspace.org (std::vector and std::array), I get 8 vs 10 ms. As all allocations are indeed outside the measurement, I would naively conclude that accessing the heap is slower than accessing stack memory. I wouldn't be surprised if this is generally true, as there is an extra indirection in the case of the heap.

Improve this answer

3 Comments

All allocation happens outside the timing window.
It is clearly not allocating 1M doubles on the stack - guess again.
@lucas1024 so you think std::array knows about anything else than the stack?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.