Is std :: vector faster than a simple array?

Question

I just tried comparing std::sort with both std::vector<std::pair<float, unsigned int>> (filled with the push_back operation) and a simple array std::pair<float, unsigned int>> * (highlighted using new ones and then filled one by one). The comparison function simply compares the float parts of the pairs.

Surprisingly, when using 16M values ​​on std :: vector it took only about 1940 ms, and in the array about 2190 ms. Can someone explain how a vector can be faster? Is it due to caching or is it just that the version of the std :: sort array is poorly implemented?

gcc (GCC) 4.4.5 20110214 (Red Hat 4.4.5-6)

Intel(R) Core(TM) i7 CPU 870 @ 2.93GHz - cache size 8192 KB (the computer has two quad-core processors, but I assume that sorting is only single-threaded)

EDIT: Now you can call me dumbass, but when I tried to reproduce the code that I used for measurements (I already deleted the source), I can not reproduce the results - now the array version takes about 1915 + - 5 ms (measured for 32 runs) . I can only swear that three times (manually) I checked the test for 10 measurements with similar results, but this is not strict evidence.

There was probably an error in the source code, the background process seems unacceptable, because I have alternating measurements of vector and massive versions, and the results of the vector are saved and no user is logged in.

Please consider this question closed . Thanks for your efforts.

Answer 1

std::vector<std::pair<float, unsigned int>> (populated with the push_back operation)

All data is stored here, so the memory area is very good.

std::pair<float, unsigned int>> * array (assigned using the new one, and then filled one by one)

This scatters data throughout the memory.

You have set up a very unfair comparison between vector and a simple array. The additional indirection associated with the body of the array will be painful, the lack of terrain will lead to a decrease in cache performance. I am surprised that you do not see a big victory in favor of the adjacent storage.

Answer 2

They will use the same version of sort . These are most likely random processor effects, such as caching or contextual flow switches.

Answer 3

Did you use -O3 to compile the code?

If not, do it. All other test results are meaningless, especially for template code.

Have you run a test many times?

This is to prevent things like interrupts and caching from having a significant impact on your result.

Do not use floating point comparisons or arithmetic for tests. The results are highly dependent on the compiler, platform, compiler options, etc.

How were your test data created?

The time required by most sorting algorithms varies depending on the sorting of the input data.

What time measurement method did you use? Clock cycles? Timer?

In any case, test records that provide reliable results are not as simple as they might seem at first glance. Do not use a benchmark to determine which code is for your problem.