russell@unturf.com
223ccb3fee
0ad-0001 CCmpObstructionManager dirty shapes vector+std::find O(N*D) HIGH 4.1x 0ad-0002 CCmpRangeManager m_ModifiedEntities vector+std::find O(E*M) HIGH 25.8x 0ad-0003 CCmpTemplateManager FindUsedTemplates vector+std::find O(T^2) MEDIUM 5.9x 0ad-0004 XmppClient+NetServer lobby auth token logged verbatim CWE-312 MEDIUM MOAD-0002 (Intertangle): g_ globals are deliberate single-thread game arch, CLEAN MOAD-0003 (Leaked Context): thread_local properly scoped, CLEAN MOAD-0005 (Thundering Herd): single-threaded sim, no cache stampede, CLEAN 4/4 unit tests PASS, UNDF 956-959
89 lines
3.1 KiB
C++
89 lines
3.1 KiB
C++
// Unit test for 0ad-0003: CCmpTemplateManager::FindUsedTemplates dedup
|
|
// Verifies that unordered_set-based dedup matches vector-based behavior
|
|
// and demonstrates O(T^2) -> O(T) improvement.
|
|
|
|
#include <vector>
|
|
#include <unordered_set>
|
|
#include <algorithm>
|
|
#include <string>
|
|
#include <chrono>
|
|
#include <cstdio>
|
|
#include <cstdint>
|
|
#include <cassert>
|
|
#include <map>
|
|
|
|
using entity_id_t = uint32_t;
|
|
|
|
// --- BEFORE: vector + std::find ---
|
|
std::vector<std::string> FindUsedTemplatesBefore(const std::map<entity_id_t, std::string>& latestTemplates) {
|
|
std::vector<std::string> usedTemplates;
|
|
for (const auto& p : latestTemplates)
|
|
if (std::find(usedTemplates.begin(), usedTemplates.end(), p.second) == usedTemplates.end())
|
|
usedTemplates.push_back(p.second);
|
|
return usedTemplates;
|
|
}
|
|
|
|
// --- AFTER: unordered_set ---
|
|
std::vector<std::string> FindUsedTemplatesAfter(const std::map<entity_id_t, std::string>& latestTemplates) {
|
|
std::unordered_set<std::string> seen;
|
|
for (const auto& p : latestTemplates)
|
|
seen.insert(p.second);
|
|
return std::vector<std::string>(seen.begin(), seen.end());
|
|
}
|
|
|
|
void test_correctness() {
|
|
std::map<entity_id_t, std::string> templates;
|
|
// 500 entities using 50 unique templates (typical RTS: many units, few template types)
|
|
for (entity_id_t i = 0; i < 500; ++i)
|
|
templates[i] = "template_" + std::to_string(i % 50);
|
|
|
|
auto before = FindUsedTemplatesBefore(templates);
|
|
auto after = FindUsedTemplatesAfter(templates);
|
|
|
|
// Same size
|
|
assert(before.size() == after.size());
|
|
assert(before.size() == 50);
|
|
|
|
// Same contents (order may differ)
|
|
std::unordered_set<std::string> beforeSet(before.begin(), before.end());
|
|
std::unordered_set<std::string> afterSet(after.begin(), after.end());
|
|
assert(beforeSet == afterSet);
|
|
|
|
printf("PASS correctness: %zu unique templates from %zu entities\n", after.size(), templates.size());
|
|
}
|
|
|
|
void test_performance() {
|
|
const int ENTITIES = 2000;
|
|
const int UNIQUE_TEMPLATES = 100;
|
|
|
|
std::map<entity_id_t, std::string> templates;
|
|
for (int i = 0; i < ENTITIES; ++i)
|
|
templates[i] = "units/athen/infantry_spearman_" + std::to_string(i % UNIQUE_TEMPLATES);
|
|
|
|
// BEFORE
|
|
auto t0 = std::chrono::high_resolution_clock::now();
|
|
auto before = FindUsedTemplatesBefore(templates);
|
|
auto t1 = std::chrono::high_resolution_clock::now();
|
|
|
|
// AFTER
|
|
auto t2 = std::chrono::high_resolution_clock::now();
|
|
auto after = FindUsedTemplatesAfter(templates);
|
|
auto t3 = std::chrono::high_resolution_clock::now();
|
|
|
|
assert(before.size() == after.size());
|
|
|
|
double before_us = std::chrono::duration<double, std::micro>(t1 - t0).count();
|
|
double after_us = std::chrono::duration<double, std::micro>(t3 - t2).count();
|
|
double ratio = before_us / after_us;
|
|
|
|
printf("PASS performance: before=%.0fus after=%.0fus ratio=%.1fx (E=%d, T=%d)\n",
|
|
before_us, after_us, ratio, ENTITIES, UNIQUE_TEMPLATES);
|
|
assert(ratio > 1.5 && "Expected at least 1.5x speedup");
|
|
}
|
|
|
|
int main() {
|
|
test_correctness();
|
|
test_performance();
|
|
printf("ALL TESTS PASSED\n");
|
|
return 0;
|
|
}
|