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.
89 lines
2.8 KiB
C++
89 lines
2.8 KiB
C++
// Unit test for widelands-0002: find_reachable_immovables_unique O(N^2) dedup
|
|
// Simulates the pattern from src/logic/map.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 BaseImmovable = void;
|
|
|
|
struct ImmovableFound {
|
|
BaseImmovable* object;
|
|
};
|
|
|
|
// BEFORE: O(N^2)
|
|
void dedup_before(const std::vector<ImmovableFound>& duplist, std::vector<BaseImmovable*>& list) {
|
|
for (const ImmovableFound& imm_found : duplist) {
|
|
BaseImmovable* obj = imm_found.object;
|
|
if (std::find(list.begin(), list.end(), obj) == list.end()) {
|
|
list.push_back(obj);
|
|
}
|
|
}
|
|
}
|
|
|
|
// AFTER: O(N)
|
|
void dedup_after(const std::vector<ImmovableFound>& duplist, std::vector<BaseImmovable*>& list) {
|
|
std::unordered_set<BaseImmovable*> seen;
|
|
for (const ImmovableFound& imm_found : duplist) {
|
|
BaseImmovable* obj = imm_found.object;
|
|
if (seen.insert(obj).second) {
|
|
list.push_back(obj);
|
|
}
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
const int N = 2000;
|
|
|
|
// Create pool of unique immovables
|
|
std::vector<BaseImmovable*> pool;
|
|
for (int i = 0; i < N; ++i) {
|
|
pool.push_back(reinterpret_cast<BaseImmovable*>(static_cast<uintptr_t>(i + 1)));
|
|
}
|
|
|
|
// Create duplist with ~2x duplicates
|
|
std::vector<ImmovableFound> duplist;
|
|
for (int i = 0; i < N; ++i) {
|
|
duplist.push_back({pool[i]});
|
|
}
|
|
for (int i = 0; i < N; ++i) {
|
|
duplist.push_back({pool[i]});
|
|
}
|
|
|
|
// --- BEFORE ---
|
|
std::vector<BaseImmovable*> list_before;
|
|
auto t0 = std::chrono::high_resolution_clock::now();
|
|
dedup_before(duplist, list_before);
|
|
auto t1 = std::chrono::high_resolution_clock::now();
|
|
double ms_before = std::chrono::duration<double, std::milli>(t1 - t0).count();
|
|
|
|
// --- AFTER ---
|
|
std::vector<BaseImmovable*> list_after;
|
|
auto t2 = std::chrono::high_resolution_clock::now();
|
|
dedup_after(duplist, list_after);
|
|
auto t3 = std::chrono::high_resolution_clock::now();
|
|
double ms_after = std::chrono::duration<double, std::milli>(t3 - t2).count();
|
|
|
|
// Correctness
|
|
assert(list_before.size() == list_after.size());
|
|
assert(list_before.size() == static_cast<size_t>(N));
|
|
|
|
std::sort(list_before.begin(), list_before.end());
|
|
std::sort(list_after.begin(), list_after.end());
|
|
assert(list_before == list_after);
|
|
|
|
double ratio = ms_before / ms_after;
|
|
printf("find_reachable_immovables_unique dedup (N=%d, %d entries):\n", N, (int)duplist.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;
|
|
}
|