Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C++: Optimizing speed with vector/array?

Tags:

c++

vector

I have a nested for-loop structure and right now I am re-declaring the vector at the start of each iteration:

void function (n1,n2,bound,etc){

    for (int i=0; i<bound; i++){
             vector< vector<long long> > vec(n1, vector<long long>(n2));
             //about three more for-loops here
    }
}

This allows me to "start fresh" each iteration, which works great because my internal operations are largely in the form of vec[a][b] += some value. But I worry that it's slow for large n1 or large n2. I don't know the underlying architecture of vectors/arrays/etc so I am not sure what the fastest way is to handle this situation. Should I use an array instead? Should I clear it differently? Should I handle the logic differently altogether?

EDIT: The vector's size technically does not change each iteration (but it may change based on function parameters). I'm simply trying to clear it/etc so the program is as fast as humanly possible given all other circumstances.

EDIT:

My results of different methods:

Timings (for a sample set of data):
reclaring vector method: 111623 ms
clearing/resizing method: 126451 ms
looping/setting to 0 method: 88686 ms
like image 634
John Smith Avatar asked Apr 13 '12 13:04

John Smith


People also ask

Are C style arrays faster than vectors?

A std::vector can never be faster than an array, as it has (a pointer to the first element of) an array as one of its data members. But the difference in run-time speed is slim and absent in any non-trivial program. One reason for this myth to persist, are examples that compare raw arrays with mis-used std::vectors.

Is vector Push_back slow?

The main reason why push_back is slow is because of multiple reallocation of memory. Every vector has vector::size and vector::capacity. vector::size gives the number of elements in the vector and vector::capacity gives the number of elements vector can store.

Is vector better than array C++?

Vector occupies more memory. Array is memory efficient data structure. Vector takes more time in accessing elements. Array access elements in constant time irrespective of their location as elements are arranged in a contiguous memory allocation.

How much slower are vectors than arrays?

The time difference is 0.333 seconds. Or a difference of 0.000000000333 per array access. Assuming a 2.33 GHz Processor like mine that's 0.7 instruction pipeline stages per array accesses. So the vector looks like it is using one extra instruction per accesses.


1 Answers

I have a clear preference for small scopes (i.e. declaring the variable in the innermost loop if it’s only used there) but for large sizes this could cause a lot of allocations.

So if this loop is a performance problem, try declaring the variable outside the loop and merely clearing it inside the loop – however, this is only advantageous if the (reserved) size of the vector stays identical. If you are resizing the vector, then you get reallocations anyway.

Don’t use a raw array – it doesn’t give you any advantage, and only trouble.

like image 175
Konrad Rudolph Avatar answered Oct 03 '22 03:10

Konrad Rudolph