-2

For example we have a series of numbers [0, 1, 2, ... N]
We need to line them up in reverse order [N, ... 2, 1, 0]
Is it better to use an array or a vector?
If we use a vector then use "swap" or use buffer?

Using "swap":

for (int i = 0; i < NUMBS / 2; i++)
        std::swap(vec[i], vec[(NUMBS - 1) - i]);

Using buffer:

int buf;
for (int i = 0; i < NUMBS / 2; i++) {
    buf = vec[i];
    vec[i] = vec[(NUMBS - 1) - i];
    vec[(NUMBS - 1) - i] = buf;
}

I wrote a little code that demonstrates that an array is faster at this task than a vector:

#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
#include <cmath>

#define NUMBS 20000000

std::vector<int> vec;
int arr[NUMBS];

float timeVswap;
float timeVbuf;
float timeAbuf;

class Timer {
private:
    using clock_t = std::chrono::high_resolution_clock;
    using second_t = std::chrono::duration<double, std::ratio<1> >;

    std::chrono::time_point<clock_t> m_beg;

public:
    Timer() : m_beg(clock_t::now()) {
    }

    void reset() {
        m_beg = clock_t::now();
    }

    double elapsed() const {
        return std::chrono::duration_cast<second_t>(clock_t::now() - m_beg).count();
    }
};

void Vswap() {
    Timer t;
    t.reset();

    for (int i = 0; i < NUMBS / 2; i++)
        std::swap(vec[i], vec[(NUMBS - 1) - i]);

    timeVswap = t.elapsed();
}

void Vbuf() {
    Timer t;
    t.reset();

    int buf;
    for (int i = 0; i < NUMBS / 2; i++) {
        buf = vec[i];
        vec[i] = vec[(NUMBS - 1) - i];
        vec[(NUMBS - 1) - i] = buf;
    }

    timeVbuf = t.elapsed();
}

void Abuf() {
    Timer t;
    t.reset();

    int buf;
    for (int i = 0; i < NUMBS / 2; i++) {
        buf = arr[i];
        arr[i] = arr[(NUMBS - 1) - i];
        arr[(NUMBS - 1) - i] = buf;
    }

    timeAbuf = t.elapsed();
}

int main() {
    Timer t;

    for (int i = 0; i < NUMBS; i++) {
        vec.push_back(i);
        arr[i] = i;
    }

    Vswap();
    Vbuf();
    Abuf();

    std::cout << "Time for vector (swap):   " << timeVswap << " sec.\n";
    std::cout << "Time for vector (buf):    " << timeVbuf << " sec.\n";
    std::cout << "------------------------------------\n";
    std::cout << "Time for array (buf):     " << timeAbuf << " sec.\n";
    std::cout << "\n";
    std::cout << "array is faster: " << floorf(100 - timeAbuf / timeVbuf * 100) << " %\n";

    return 0;
}

I got results like this:

image

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
Serhii Oleksenko
  • 1
  • 1
  • 3
    As ever with benchmarking questions, what optimization flags are you compiling with? – Nathan Pierson May 06 '21 at 18:24
  • "*Is it better to use an array or a vector?*" - measure for yourself and see which is faster for your use-case. "*If we use a vector then use "swap" or use buffer?*" - consider using [`std::reverse()`](https://en.cppreference.com/w/cpp/algorithm/reverse) instead, eg: `std::reverse(vec.begin(), vec.end()); ... std::reverse(arr, arr+NUMBS);` – Remy Lebeau May 06 '21 at 18:24
  • 1
    look here what happens when you turn on optimizations: https://godbolt.org/z/nczx3j1ej. Though, note that the results are not that meaningful, because the compiler will probably optimize away most calculations in your code, you need to use the result to make sure that doesnt happen. Micro benchmarking isnt that easy unfortunately – 463035818_is_not_an_ai May 06 '21 at 18:27
  • 1
    `array is faster: -2 %` :) – 463035818_is_not_an_ai May 06 '21 at 18:28
  • Note: `high_resolution_clock` is... troublesome. [Even it's creator recommends that you not use it](https://stackoverflow.com/a/37440647/4581301). – user4581301 May 06 '21 at 18:29
  • In this case, yes std :: reverse () is a good solution, but if you need to swap even cells with odd cells? – Serhii Oleksenko May 06 '21 at 18:29
  • There may be a bit of a slow-down with `vector` here due to resizing. You can get rid of that by preallocating `vec` with `reserve` to make a fair comparison since you know the maximum size ahead of time. – user4581301 May 06 '21 at 18:31

1 Answers1

1

С++ why is an array at least 32% faster than a vector?

It is not.

You did not turn on compiler optimizations hence your results are not representative for how std::vector comares to array in a real application.

After turning on optimizations with gcc via -O3 I got output:

array is faster: -2 %

On another run:

Time for vector (swap):   0.0100716 sec.
Time for vector (buf):    0.00857671 sec.
------------------------------------
Time for array (buf):     0.00842298 sec.

array is faster: 1 %

Note that the absolute times are tiny. This hints at the compiler realizing that it has no observable effect when it doesn't actually do any swapping or reversing of neither the vector nor the array. You have to use the results of the calculations to make sure the compiler does not optimize away what you actually want to measure.

463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185