I'm studying C++ using Strostrup's book, solving this exercise problem:
Measure the time (§26.6.1) it takes to allocate 10,000 objects of random sizes in the [1000:0)-byte range using new; then measure the time it takes to deallocate them using delete. Do this twice, once deallocating in the reverse order of allocation and once deallocating in random order. Then, do the equivalent for allocating 10,000 objects of size 500 bytes from a pool and freeing them. Then, do the equivalent of allocating 10,000 objects of random sizes in the [1000:0)-byte range on a stack and then free them (in reverse order). Compare the measurements. Do each measurement at least three times to make sure the results are consistent.
And here is my code:
#include <array>
#include <algorithm>
#include <chrono>
#include <iostream>
#include <numeric>
#include <vector>
#include <random>
#include <memory_resource>
int main() {
constexpr size_t N = 1'000;
constexpr size_t SZ = 1'000;
constexpr size_t trials = 1;
std::mt19937 gen(std::random_device{}());
std::uniform_int_distribution<> sz(1, SZ);
std::array<char*, N> arr {0};
std::chrono::duration<int, std::micro> dt1 {0};
// allocate random size, deallocate in reverse order
for (size_t t = 0; t < trials; t++) {
auto t1 = std::chrono::steady_clock::now();
for (size_t i = 0; i < N; i++) {
arr[i] = new char[sz(gen)];
}
for (size_t i = N - 1; i < N; i--) {
delete arr[i];
}
auto t2 = std::chrono::steady_clock::now();
dt1 += std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1);
}
std::cout << dt1.count() / trials << "us\n";
std::vector<int> v (N);
std::iota(v.begin(), v.end(), 0);
std::shuffle(v.begin(), v.end(), gen);
std::chrono::duration<int, std::micro> dt2 {0};
// allocate random size, deallocate in random order
for (size_t t = 0; t < trials; t++) {
auto t1 = std::chrono::steady_clock::now();
for (size_t i = 0; i < N; i++) {
arr[i] = new char[sz(gen)];
}
for (size_t i = 0; i < N; i++) {
delete arr[v[i]];
}
auto t2 = std::chrono::steady_clock::now();
dt2 += std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1);
}
std::cout << dt2.count() / trials << "us\n";
std::pmr::unsynchronized_pool_resource pool;
std::array<std::pmr::vector<std::byte>, N> arr2;
std::chrono::duration<int, std::micro> dt3 {0};
// allocate fixed size in a pool, deallocate in reversed order
for (size_t t = 0; t < trials; t++) {
auto t1 = std::chrono::steady_clock::now();
for (size_t i = 0; i < N; i++) {
arr2[i] = std::pmr::vector<std::byte>(500, &pool);
}
for (size_t i = N - 1; i < N; i--) {
arr2[i].clear();
}
auto t2 = std::chrono::steady_clock::now();
dt3 += std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1);
}
std::cout << dt3.count() / trials << "us\n";
std::chrono::duration<int, std::micro> dt4 {0};
// allocate fixed size in a pool, deallocate in random order
for (size_t t = 0; t < trials; t++) {
auto t1 = std::chrono::steady_clock::now();
for (size_t i = 0; i < N; i++) {
arr2[i] = std::pmr::vector<std::byte>(500, &pool);
}
for (size_t i = 0; i < N; i++) {
arr2[v[i]].clear();
}
auto t2 = std::chrono::steady_clock::now();
dt4 += std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1);
}
std::cout << dt4.count() / trials << "us\n";
std::array<std::byte, N * SZ> buf;
std::chrono::duration<int, std::micro> dt5 {0};
// allocate random size in a stack, deallocate in reversed order
for (size_t t = 0; t < trials; t++) {
std::pmr::monotonic_buffer_resource pool2 {buf.data(), buf.size()};
auto t1 = std::chrono::steady_clock::now();
for (size_t i = 0; i < N; i++) {
arr2[i] = std::pmr::vector<std::byte>(sz(gen), &pool2);
}
auto t2 = std::chrono::steady_clock::now();
dt5 += std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1);
}
std::cout << dt5.count() / trials << "us\n";
}
Here is the typical output, in my machine, using trials = 1 and compiled with -O3 in gcc 9.1:
901us
137us
637us
210us
1018us
So I've initially concluded that "Wow, deallocating in reverse order is way slower than deallocating in random order! This would be a lesson from this exercise."
But, this turned out to be incorrect. As I increased the number of trials for making an averaged (=consistent) benchmark, a weird thing happened:
Setting trials = 30 gives:
233us
206us
348us
226us
365us
Setting trials = 1'000 gives:
167us
154us
221us
195us
194us
So when I allocate/deallocate over and over again, deallocating in reverse order doesn't become particularly slower than deallocating in random order!
Why does this weird thing happen? Why is it slow to deallocating in reverse order for the first time?