push_back() vs push_front() in deque.

push_back() vs push_front() in deque.

I took a quick look at the source code for libstdc++, but I couldn't really figure out a concrete version one would be faster than the other. In the source code, deques start empty, so push_front allocates a block at the front and push_back allocates a block at the back. However, I think this should be basically the same speed.

For testing on my own, I wrote the following program:

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 100000;
constexpr int T = 10000000;
deque<int> dq[N];

// hi 1
int main() {
        mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	for (int i = 0; i < T; i++) {
	    int idx = uniform_int_distribution(0, N - 1)(rng);
	    dq[idx] = {};
	    dq[idx].push_back(i);
            // dq[idx].push_front(i);
	}
	
	long long sum = 0;
	
	for (auto &d : dq) {
	    if (!d.empty()) {
	        sum += d[0];
	    }
	}
	
	cout << sum << '\n';
	return 0;
}

Running this with push_back five times, the times I get are: - 374ms - 358ms - 358ms - 358ms - 436ms

With push_front, I get: - 514ms - 483ms - 436ms - 405ms - 529ms

(I also modified some other comment to produce new runs for each program)

So it seems like with this program, push_front was worse.

Running locally, I get:

> for ((i=0; i<5; i++)); do time ./back; done
989994166783
./back  2.23s user 0.04s system 99% cpu 2.291 total
990005476889
./back  2.04s user 0.03s system 99% cpu 2.086 total
990020568957
./back  2.02s user 0.03s system 99% cpu 2.064 total
990011175274
./back  2.04s user 0.04s system 99% cpu 2.086 total
990024430012
./back  2.03s user 0.03s system 99% cpu 2.072 total

> for ((i=0; i<5; i++)); do time ./front; done
990027252540
./front  2.38s user 0.08s system 89% cpu 2.758 total
989990156039
./front  2.17s user 0.07s system 99% cpu 2.251 total
990023081202
./front  2.15s user 0.07s system 99% cpu 2.234 total
989990367124
./front  2.15s user 0.07s system 99% cpu 2.231 total
989984050663
./front  2.16s user 0.07s system 99% cpu 2.243 total

So it looks like push_back is better locally as well, so maybe in general its better to use push_back, but I don't really know why this is true after looking at the source code.