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.
113 lines
3.3 KiB
C++
113 lines
3.3 KiB
C++
// Unit test for widelands-0001: FindBobsCallback O(N^2) dedup
|
|
// Simulates the pattern from src/logic/map.cc FindBobsCallback
|
|
// 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>
|
|
|
|
// Simulate Bob pointers as unique integers cast to void*
|
|
using Bob = void;
|
|
|
|
struct FindBobsCallbackBefore {
|
|
std::vector<Bob*>* list_;
|
|
uint32_t found_{0U};
|
|
|
|
void add_bob(Bob* bob) {
|
|
if (list_ != nullptr) {
|
|
// DEFECT: O(N) scan per insertion
|
|
if (std::find(list_->begin(), list_->end(), bob) != list_->end()) {
|
|
return;
|
|
}
|
|
list_->push_back(bob);
|
|
}
|
|
++found_;
|
|
}
|
|
};
|
|
|
|
struct FindBobsCallbackAfter {
|
|
std::vector<Bob*>* list_;
|
|
std::unordered_set<Bob*> seen_;
|
|
uint32_t found_{0U};
|
|
|
|
void add_bob(Bob* bob) {
|
|
if (list_ != nullptr) {
|
|
// FIX: O(1) lookup
|
|
if (seen_.count(bob) != 0) {
|
|
return;
|
|
}
|
|
list_->push_back(bob);
|
|
seen_.insert(bob);
|
|
}
|
|
++found_;
|
|
}
|
|
};
|
|
|
|
int main() {
|
|
// Simulate finding B bobs across fields, with ~50% duplicates
|
|
const int B = 2000;
|
|
|
|
// Create bob pool (half the total insertions, ensuring duplicates)
|
|
std::vector<Bob*> bob_pool;
|
|
for (int i = 0; i < B; ++i) {
|
|
bob_pool.push_back(reinterpret_cast<Bob*>(static_cast<uintptr_t>(i + 1)));
|
|
}
|
|
|
|
// Create insertion sequence: each bob inserted twice (simulating adjacent fields)
|
|
std::vector<Bob*> insertions;
|
|
for (int i = 0; i < B; ++i) {
|
|
insertions.push_back(bob_pool[i]);
|
|
}
|
|
for (int i = 0; i < B; ++i) {
|
|
insertions.push_back(bob_pool[i]);
|
|
}
|
|
|
|
// --- BEFORE (O(N^2)) ---
|
|
std::vector<Bob*> list_before;
|
|
FindBobsCallbackBefore cb_before;
|
|
cb_before.list_ = &list_before;
|
|
|
|
auto t0 = std::chrono::high_resolution_clock::now();
|
|
for (Bob* bob : insertions) {
|
|
cb_before.add_bob(bob);
|
|
}
|
|
auto t1 = std::chrono::high_resolution_clock::now();
|
|
double ms_before = std::chrono::duration<double, std::milli>(t1 - t0).count();
|
|
|
|
// --- AFTER (O(N)) ---
|
|
std::vector<Bob*> list_after;
|
|
FindBobsCallbackAfter cb_after;
|
|
cb_after.list_ = &list_after;
|
|
|
|
auto t2 = std::chrono::high_resolution_clock::now();
|
|
for (Bob* bob : insertions) {
|
|
cb_after.add_bob(bob);
|
|
}
|
|
auto t3 = std::chrono::high_resolution_clock::now();
|
|
double ms_after = std::chrono::duration<double, std::milli>(t3 - t2).count();
|
|
|
|
// Correctness: same results
|
|
assert(list_before.size() == list_after.size());
|
|
assert(list_before.size() == static_cast<size_t>(B));
|
|
assert(cb_before.found_ == cb_after.found_);
|
|
|
|
// Both lists should contain exactly the same bobs
|
|
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("FindBobsCallback dedup (B=%d, %d insertions):\n", B, (int)insertions.size());
|
|
printf(" BEFORE (std::find): %.3f ms\n", ms_before);
|
|
printf(" AFTER (unordered_set): %.3f ms\n", ms_after);
|
|
printf(" Ratio: %.1fx\n", ratio);
|
|
|
|
// Expect meaningful speedup
|
|
assert(ratio > 2.0);
|
|
printf("PASS\n");
|
|
return 0;
|
|
}
|