russell@unturf.com
dbc058c155
naev-0001: map.c Dijkstra/A* pathfinding uses linked-list open/closed sets with O(V) A_in() membership test and O(V) A_lowest() extract-min per iteration, making full pathfinding O(V^2 + E*V). Fix: array-indexed visited flags for O(1) membership, sorted-insert open list for O(1) extract-min. 102.5x at V=500 (Naev has 538 star systems). HIGH. naev-0002: tech.c tech_addGroupItemPrice() dedup scans growing output array linearly per item O(I*N) when building outfit/ship/commodity lists from tech groups. Fix: hash set for O(1) amortized dedup. 333x at N=1000. MEDIUM. MOAD-0002 (Intertangle): global stacks are standard C game engine pattern, subsystems largely independent. CLEAN. MOAD-0003 (Leaked Context): single thread_local in Rust RNG only. CLEAN. MOAD-0004 (Logged Secret): no credentials in single-player game. CLEAN. MOAD-0005 (Thundering Herd): single-threaded gameplay logic. CLEAN. 2/2 PASS, 2 defects.
102 lines
3.7 KiB
C++
102 lines
3.7 KiB
C++
// Unit test for freeorion-0001: CheckResearchProgress costs_times linear scan O(Q*T + T*T)
|
|
// Demonstrates that building an unordered_map for O(1) lookup eliminates quadratic scaling.
|
|
|
|
#include <cassert>
|
|
#include <chrono>
|
|
#include <iostream>
|
|
#include <string>
|
|
#include <string_view>
|
|
#include <tuple>
|
|
#include <unordered_map>
|
|
#include <vector>
|
|
|
|
// -----------------------------------------------------------------------
|
|
// DEFECT (original): linear scan of costs_times vector per tech lookup
|
|
// -----------------------------------------------------------------------
|
|
static double __attribute__((noinline)) lookup_linear(
|
|
const std::vector<std::tuple<std::string_view, double, int>>& costs_times,
|
|
const std::vector<std::string>& tech_names)
|
|
{
|
|
volatile double sum = 0.0;
|
|
for (const auto& tech_name : tech_names) {
|
|
for (const auto& [name, cost, time] : costs_times) {
|
|
if (name == tech_name) {
|
|
sum = sum + cost;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
return sum;
|
|
}
|
|
|
|
// -----------------------------------------------------------------------
|
|
// FIX (patched): build hash map once, O(1) lookup per tech
|
|
// -----------------------------------------------------------------------
|
|
static double __attribute__((noinline)) lookup_hashmap(
|
|
const std::vector<std::tuple<std::string_view, double, int>>& costs_times,
|
|
const std::vector<std::string>& tech_names)
|
|
{
|
|
std::unordered_map<std::string_view, std::pair<double, int>> costs_map;
|
|
costs_map.reserve(costs_times.size());
|
|
for (const auto& [name, cost, time] : costs_times)
|
|
costs_map.emplace(name, std::pair{cost, time});
|
|
|
|
volatile double sum = 0.0;
|
|
for (const auto& tech_name : tech_names) {
|
|
auto it = costs_map.find(tech_name);
|
|
if (it != costs_map.end())
|
|
sum = sum + it->second.first;
|
|
}
|
|
return sum;
|
|
}
|
|
|
|
int main() {
|
|
// Simulate a tech tree with T techs
|
|
constexpr int T = 2000;
|
|
|
|
std::vector<std::string> tech_names;
|
|
tech_names.reserve(T);
|
|
std::vector<std::tuple<std::string_view, double, int>> costs_times;
|
|
costs_times.reserve(T);
|
|
|
|
for (int i = 0; i < T; ++i) {
|
|
tech_names.push_back("TECH_" + std::to_string(i));
|
|
}
|
|
// Build costs_times with string_views into tech_names
|
|
for (int i = 0; i < T; ++i) {
|
|
costs_times.emplace_back(std::string_view(tech_names[i]), static_cast<double>(i + 1), 1);
|
|
}
|
|
|
|
// Correctness check
|
|
double linear_sum = lookup_linear(costs_times, tech_names);
|
|
double hashmap_sum = lookup_hashmap(costs_times, tech_names);
|
|
assert(linear_sum == hashmap_sum);
|
|
|
|
// Benchmark: linear (defect)
|
|
auto t0 = std::chrono::high_resolution_clock::now();
|
|
constexpr int ITERS = 20;
|
|
for (int r = 0; r < ITERS; ++r)
|
|
lookup_linear(costs_times, tech_names);
|
|
auto t1 = std::chrono::high_resolution_clock::now();
|
|
|
|
// Benchmark: hashmap (fix)
|
|
for (int r = 0; r < ITERS; ++r)
|
|
lookup_hashmap(costs_times, tech_names);
|
|
auto t2 = std::chrono::high_resolution_clock::now();
|
|
|
|
auto linear_us = std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();
|
|
auto hashmap_us = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
|
|
|
|
double ratio = (hashmap_us > 0) ? static_cast<double>(linear_us) / hashmap_us : 999.0;
|
|
|
|
std::cout << "T=" << T << " techs, " << ITERS << " iterations" << std::endl;
|
|
std::cout << "linear (defect): " << linear_us << " us" << std::endl;
|
|
std::cout << "hashmap (fix): " << hashmap_us << " us" << std::endl;
|
|
std::cout << "ratio: " << ratio << "x" << std::endl;
|
|
|
|
// At T=2000, expect at least 10x speedup
|
|
assert(ratio > 5.0 && "Expected significant speedup from hashmap lookup");
|
|
|
|
std::cout << "PASS" << std::endl;
|
|
return 0;
|
|
}
|