ch16/bench.cpp127 lines
// bench.cpp: container costs on station data (companion repository)
// Build: g++ -std=c++20 -O2 -Wall -Wextra -Werror -o bench bench.cpp
#include <algorithm>
#include <chrono>
#include <cstdio>
#include <deque>
#include <list>
#include <malloc.h>
#include <map>
#include <random>
#include <string>
#include <unordered_map>
#include <vector>
#include "reading.hpp"
using Clock = std::chrono::steady_clock;
static volatile double sink;
// Runs setup() untimed, then op() timed; repeats; returns the median ms.
template <typename Setup, typename Op>
double median_ms(Setup setup, Op op, int reps = 7) {
std::vector<double> t;
for (int i = 0; i < reps; ++i) {
auto state = setup();
auto a = Clock::now();
op(state);
auto b = Clock::now();
t.push_back(std::chrono::duration<double, std::milli>(b - a).count());
}
std::sort(t.begin(), t.end());
return t[t.size() / 2];
}
std::vector<stn::Reading> make_day(std::size_t n, unsigned seed) {
std::mt19937 rng(seed);
std::uniform_real_distribution<double> v(-5.0, 35.0);
std::vector<stn::Reading> rs;
rs.reserve(n);
for (std::size_t i = 0; i < n; ++i) {
std::uint8_t f = (i % 20 == 3) ? 0 : 3; // 5% invalid
rs.push_back({static_cast<std::uint32_t>(1001 + i % 4),
static_cast<std::int64_t>(60 * (i / 4)), v(rng), f});
}
return rs;
}
static bool invalid(const stn::Reading& r) { return !(r.flags & stn::FLAG_VALID); }
template <typename C>
double sum_values(const C& c) {
double s = 0;
for (const auto& r : c) s += r.value;
return s;
}
static size_t heap_in_use() {
struct mallinfo2 m = mallinfo2();
return m.uordblks + m.hblkhd;
}
template <typename C>
void traversal_row(const char* name, const std::vector<stn::Reading>& src) {
size_t before = heap_in_use();
C* c = new C(src.begin(), src.end());
size_t after = heap_in_use();
double ms = median_ms([&] { return 0; }, [&](int) { sink = sum_values(*c); });
std::printf(" %-22s %8.2f ms %6.1f B/reading\n", name, ms,
double(after - before) / double(src.size()));
delete c;
}
static void traversal(std::size_t n) {
auto day = make_day(n, 42);
std::printf("== traversal: sum %zu values\n", n);
traversal_row<std::vector<stn::Reading>>("vector", day);
traversal_row<std::deque<stn::Reading>>("deque", day);
traversal_row<std::list<stn::Reading>>("list (built in order)", day);
std::list<stn::Reading> l(day.begin(), day.end());
l.sort([](const stn::Reading& a, const stn::Reading& b) { return a.value < b.value; });
double ms = median_ms([&] { return 0; }, [&](int) { sink = sum_values(l); });
std::printf(" %-22s %8.2f ms\n", "list (after l.sort())", ms);
// map keyed by time and sensor: node-based, sorted
std::map<std::pair<std::int64_t, std::uint32_t>, stn::Reading>* m;
size_t before = heap_in_use();
m = new std::map<std::pair<std::int64_t, std::uint32_t>, stn::Reading>;
for (const auto& r : day) m->emplace(std::pair{r.time_s, r.sensor_id}, r);
size_t after = heap_in_use();
ms = median_ms([&] { return 0; }, [&](int) {
double s = 0;
for (const auto& kv : *m) s += kv.second.value;
sink = s;
});
std::printf(" %-22s %8.2f ms %6.1f B/reading\n", "map<(time,id),Reading>", ms,
double(after - before) / double(n));
delete m;
}
static void filtering(std::size_t n) {
auto day = make_day(n, 42);
std::printf("== filter: remove the 5%% invalid from %zu\n", n);
double ms = median_ms([&] { return day; },
[](std::vector<stn::Reading>& v) { std::erase_if(v, invalid); });
std::printf(" %-28s %9.2f ms\n", "vector std::erase_if", ms);
ms = median_ms([&] { return std::list<stn::Reading>(day.begin(), day.end()); },
[](std::list<stn::Reading>& l) { l.remove_if(invalid); });
std::printf(" %-28s %9.2f ms\n", "list remove_if", ms);
ms = median_ms([&] { return std::deque<stn::Reading>(day.begin(), day.end()); },
[](std::deque<stn::Reading>& d) { std::erase_if(d, invalid); });
std::printf(" %-28s %9.2f ms\n", "deque std::erase_if", ms);
if (n <= 200'000) {
ms = median_ms([&] { return day; }, [](std::vector<stn::Reading>& v) {
for (auto it = v.begin(); it != v.end();) {
if (invalid(*it)) it = v.erase(it); else ++it;
}
}, 3);
std::printf(" %-28s %9.2f ms\n", "vector it = erase(it) loop", ms);
}
}
int main(int argc, char** argv) {
std::string what = argc > 1 ? argv[1] : "all";
if (what == "all" || what == "traverse") traversal(1'000'000);
if (what == "all" || what == "filter") {
for (std::size_t n : {10'000u, 100'000u, 1'000'000u}) filtering(n);
}
return 0;
}
ch16/case_sim.cpp22 lines
#include <cstdio>
#include <vector>
#include <random>
#include "reading.hpp"
#include "filter.hpp"
int main() {
std::mt19937 rng(16);
std::uniform_real_distribution<double> v(52.0, 71.0);
std::vector<stn::Reading> rs;
int bad = 0;
for (int m = 0; m < 1440; ++m) {
bool storm = (m >= 600 && m < 720);
bool invalid = storm ? (rng() % 3 != 0) : (rng() % 40 == 0);
if (invalid) ++bad;
rs.push_back({1002, 60LL*m, invalid ? -99.0 : v(rng), static_cast<std::uint8_t>(invalid ? 0 : 3)});
}
std::size_t valid = rs.size() - bad;
stn::drop_invalid(rs);
int left_bad = 0; double mn = 1e9, sum = 0;
for (auto& r : rs) { if (!(r.flags & 1)) ++left_bad; if (r.value < mn) mn = r.value; sum += r.value; }
std::printf("invalid %d, expected kept %zu, kept %zu, invalid left %d, min %.1f mean %.1f\n", bad, valid, rs.size(), left_bad, mn, sum/rs.size());
}
ch16/filter.hpp25 lines
// filter.hpp: the module under test (Writer's first version)
#ifndef STN_FILTER_HPP
#define STN_FILTER_HPP
#include <vector>
#include "reading.hpp"
namespace stn {
// Removes every reading whose VALID bit is clear.
// Keeps the order of the readings that remain.
inline void drop_invalid(std::vector<Reading>& rs) {
#ifdef USE_FIXED
std::erase_if(rs, [](const Reading& r) {
return (r.flags & FLAG_VALID) == 0;
});
#else
for (auto& r : rs) {
if (!(r.flags & FLAG_VALID)) {
auto pos = rs.begin() + (&r - rs.data());
rs.erase(pos);
}
}
#endif
}
} // namespace stn
#endif
ch16/max_concept.cpp22 lines
// max_concept.cpp: the same call, with a C++20 concept
#include <concepts>
#include <vector>
#include "reading.hpp"
template <std::totally_ordered T>
T max_of(const std::vector<T>& v) {
T best = v[0];
for (const T& x : v) {
if (best < x) {
best = x;
}
}
return best;
}
int main(void) {
std::vector<stn::Reading> rs = {{1001, 60, 21.75, 3},
{1001, 120, 22.00, 3}};
stn::Reading hottest = max_of(rs);
return hottest.sensor_id == 1001 ? 0 : 1;
}
ch16/max_err.cpp21 lines
// max_err.cpp: asking max_of for something it cannot do
#include <vector>
#include "reading.hpp"
template <typename T>
T max_of(const std::vector<T>& v) {
T best = v[0];
for (const T& x : v) {
if (best < x) {
best = x;
}
}
return best;
}
int main(void) {
std::vector<stn::Reading> rs = {{1001, 60, 21.75, 3},
{1001, 120, 22.00, 3}};
stn::Reading hottest = max_of(rs);
return hottest.sensor_id == 1001 ? 0 : 1;
}
ch16/reading.hpp16 lines
// reading.hpp: the station record used in this chapter
#ifndef STN_READING_HPP
#define STN_READING_HPP
#include <cstdint>
namespace stn {
struct Reading {
std::uint32_t sensor_id; // e.g. 1001
std::int64_t time_s; // seconds since start
double value; // in the sensor's unit
std::uint8_t flags; // bit 0 VALID, bit 3 OUT_OF_RANGE
};
inline constexpr std::uint8_t FLAG_VALID = 0x01;
inline constexpr std::uint8_t FLAG_OUT_OF_RANGE = 0x08;
} // namespace stn
#endif
ch16/search.cpp93 lines
// search.cpp: PA6 baseline, lookups by sensor ID (companion repository)
// Build: g++ -std=c++20 -O2 -Wall -Wextra -Werror -o search search.cpp
#include <algorithm>
#include <chrono>
#include <cstdio>
#include <map>
#include <numeric>
#include <random>
#include <unordered_map>
#include <vector>
#include "reading.hpp"
using Clock = std::chrono::steady_clock;
static volatile double sink;
// Binary search on a vector sorted by sensor_id.
// Returns a borrowed pointer, valid until `sorted` is modified,
// or nullptr if no reading has this id.
using Table = std::vector<stn::Reading>;
const stn::Reading* find_sorted(const Table& sorted,
std::uint32_t id) {
auto it = std::lower_bound(sorted.begin(), sorted.end(), id,
[](const stn::Reading& r, std::uint32_t key) {
return r.sensor_id < key;
});
if (it == sorted.end() || it->sensor_id != id) {
return nullptr;
}
return &*it;
}
template <typename F>
double median_ns_per(F f, std::size_t k, int reps = 5) {
std::vector<double> t;
for (int i = 0; i < reps; ++i) {
auto a = Clock::now(); f(); auto b = Clock::now();
t.push_back(std::chrono::duration<double, std::nano>(b - a).count() / double(k));
}
std::sort(t.begin(), t.end());
return t[t.size() / 2];
}
int main() {
std::printf("%9s %12s %12s %12s %12s\n", "n", "linear", "sorted+bin", "std::map", "unordered");
for (std::size_t n : {1'000u, 10'000u, 100'000u, 1'000'000u}) {
std::mt19937 rng(42);
std::vector<std::uint32_t> ids(n);
std::iota(ids.begin(), ids.end(), 2001u);
std::shuffle(ids.begin(), ids.end(), rng);
std::vector<stn::Reading> table;
for (std::size_t i = 0; i < n; ++i) table.push_back({ids[i], 60, 20.0 + double(i % 10), 3});
const std::size_t k = 1000;
std::vector<std::uint32_t> keys(k);
std::uniform_int_distribution<std::size_t> pick(0, n - 1);
for (auto& key : keys) key = ids[pick(rng)];
double lin = median_ns_per([&] {
double s = 0;
for (auto key : keys) {
auto it = std::find_if(table.begin(), table.end(),
[key](const stn::Reading& r) { return r.sensor_id == key; });
s += it->value;
}
sink = s;
}, k);
auto sorted = table;
std::sort(sorted.begin(), sorted.end(),
[](const stn::Reading& a, const stn::Reading& b) { return a.sensor_id < b.sensor_id; });
double bin = median_ns_per([&] {
double s = 0;
for (auto key : keys) {
s += find_sorted(sorted, key)->value;
}
sink = s;
}, k);
std::map<std::uint32_t, stn::Reading> m;
std::unordered_map<std::uint32_t, stn::Reading> um;
for (const auto& r : table) { m.emplace(r.sensor_id, r); um.emplace(r.sensor_id, r); }
double tm = median_ns_per([&] {
double s = 0;
for (auto key : keys) s += m.find(key)->second.value;
sink = s;
}, k);
double tu = median_ns_per([&] {
double s = 0;
for (auto key : keys) s += um.find(key)->second.value;
sink = s;
}, k);
std::printf("%9zu %10.0f ns %10.0f ns %10.0f ns %10.0f ns\n", n, lin, bin, tm, tu);
}
return 0;
}