russell@unturf.com
1326aeefec
Scanned 1509 C# files in OpenRA (C# RTS game engine, Command & Conquer style). MOAD-0001 (CWE-407): CLEAN. Exceptionally well-optimized. FrozenSet<string> for config type checks, HashSet<Actor/CPos> for membership, binary search in TraitDictionary, CellLayer bounds checks. Only List.Contains on small bounded collections (<50 items). MOAD-0002 (Intertangle): CLEAN. Trait-based ECS architecture. No god objects. MOAD-0003 (Leaked Context): CLEAN. Single ThreadLocal for diagnostics only. MOAD-0004 (CWE-312): CLEAN. Only public identifiers logged, no secrets. MOAD-0005 (Thundering Herd): CLEAN. Single-threaded game logic, proper lock() on multi-threaded subsystems.
86 lines
2.9 KiB
C++
86 lines
2.9 KiB
C++
// Unit test for widelands-0003: cleanup_playerimmovables_area burnlist O(N^2)
|
|
// Simulates the pattern from src/logic/editor_game_base.cc
|
|
// Demonstrates O(N^2) with std::find vs O(N) with unordered_set
|
|
|
|
#include <algorithm>
|
|
#include <cassert>
|
|
#include <chrono>
|
|
#include <cstdint>
|
|
#include <cstdio>
|
|
#include <unordered_set>
|
|
#include <vector>
|
|
|
|
using PlayerImmovable = void;
|
|
|
|
// BEFORE: O(N^2)
|
|
void build_burnlist_before(const std::vector<PlayerImmovable*>& immovables,
|
|
std::vector<PlayerImmovable*>& burnlist) {
|
|
for (PlayerImmovable* imm : immovables) {
|
|
if (std::find(burnlist.begin(), burnlist.end(), imm) == burnlist.end()) {
|
|
burnlist.push_back(imm);
|
|
}
|
|
}
|
|
}
|
|
|
|
// AFTER: O(N)
|
|
void build_burnlist_after(const std::vector<PlayerImmovable*>& immovables,
|
|
std::vector<PlayerImmovable*>& burnlist) {
|
|
std::unordered_set<PlayerImmovable*> burnset;
|
|
for (PlayerImmovable* imm : immovables) {
|
|
if (burnset.insert(imm).second) {
|
|
burnlist.push_back(imm);
|
|
}
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
const int N = 2000;
|
|
|
|
// Create pool of unique immovables
|
|
std::vector<PlayerImmovable*> pool;
|
|
for (int i = 0; i < N; ++i) {
|
|
pool.push_back(reinterpret_cast<PlayerImmovable*>(static_cast<uintptr_t>(i + 1)));
|
|
}
|
|
|
|
// Create input with ~2x duplicates (simulating overlapping field scans)
|
|
std::vector<PlayerImmovable*> immovables;
|
|
for (int i = 0; i < N; ++i) {
|
|
immovables.push_back(pool[i]);
|
|
}
|
|
for (int i = 0; i < N; ++i) {
|
|
immovables.push_back(pool[i]);
|
|
}
|
|
|
|
// --- BEFORE ---
|
|
std::vector<PlayerImmovable*> burnlist_before;
|
|
auto t0 = std::chrono::high_resolution_clock::now();
|
|
build_burnlist_before(immovables, burnlist_before);
|
|
auto t1 = std::chrono::high_resolution_clock::now();
|
|
double ms_before = std::chrono::duration<double, std::milli>(t1 - t0).count();
|
|
|
|
// --- AFTER ---
|
|
std::vector<PlayerImmovable*> burnlist_after;
|
|
auto t2 = std::chrono::high_resolution_clock::now();
|
|
build_burnlist_after(immovables, burnlist_after);
|
|
auto t3 = std::chrono::high_resolution_clock::now();
|
|
double ms_after = std::chrono::duration<double, std::milli>(t3 - t2).count();
|
|
|
|
// Correctness
|
|
assert(burnlist_before.size() == burnlist_after.size());
|
|
assert(burnlist_before.size() == static_cast<size_t>(N));
|
|
|
|
std::sort(burnlist_before.begin(), burnlist_before.end());
|
|
std::sort(burnlist_after.begin(), burnlist_after.end());
|
|
assert(burnlist_before == burnlist_after);
|
|
|
|
double ratio = ms_before / ms_after;
|
|
printf("cleanup_playerimmovables_area burnlist dedup (N=%d, %d entries):\n",
|
|
N, (int)immovables.size());
|
|
printf(" BEFORE (std::find): %.3f ms\n", ms_before);
|
|
printf(" AFTER (unordered_set): %.3f ms\n", ms_after);
|
|
printf(" Ratio: %.1fx\n", ratio);
|
|
|
|
assert(ratio > 2.0);
|
|
printf("PASS\n");
|
|
return 0;
|
|
}
|