russell@unturf.com
4641c3c60f
bzflag-0001: bz_EventHandler::HasEvent() std::find on HandledEvents vector called per-handler per-event-fire in callEvents hot path. O(E*H). Fix: std::bitset<bz_eLastEvent>. HIGH, 8.4x speedup. bzflag-0002: AccessControlList ban/hostBan/idBan std::find on growing ban vector for dedup. O(B^2) during merge() of master ban list. Fix: parallel unordered_set index. MEDIUM, 17x speedup. bzflag-0003: parsePermissionString customPerms std::find dedup O(W*C). Fix: std::set shadow for dedup. LOW-MEDIUM, 5.1x speedup. MOAD-0004: bzfs.cxx:4732 logs auth token verbatim at debug level 1 (logDebugMessage with player token). Noted, not patched (debug only). MOAD-0002 (intertangle): global mutable state typical for 1993 C++ game server, not a clean god-object coupling defect. MOAD-0003 (leaked context): no thread_local usage found. CLEAN. MOAD-0005 (thundering herd): single-threaded server, no cache races. CLEAN.
108 lines
3.2 KiB
C++
108 lines
3.2 KiB
C++
// Unit test for bzflag-0003: parsePermissionString customPerms dedup O(W*C)
|
|
//
|
|
// Defect: parsePermissionString uses std::find on customPerms vector to
|
|
// check for duplicates when adding custom permissions. When a group file
|
|
// has many custom permissions, this is O(W*C) per parse call.
|
|
//
|
|
// Fix: Use a std::set<std::string> shadow for O(log C) dedup lookups.
|
|
|
|
#include <vector>
|
|
#include <set>
|
|
#include <string>
|
|
#include <algorithm>
|
|
#include <cassert>
|
|
#include <chrono>
|
|
#include <cstdio>
|
|
|
|
// BEFORE: vector find dedup
|
|
struct PermInfoBefore {
|
|
std::vector<std::string> customPerms;
|
|
|
|
void addCustomPerm(const std::string &word) {
|
|
if (std::find(customPerms.begin(), customPerms.end(), word) == customPerms.end())
|
|
customPerms.push_back(word);
|
|
}
|
|
};
|
|
|
|
// AFTER: set-backed dedup
|
|
struct PermInfoAfter {
|
|
std::vector<std::string> customPerms;
|
|
std::set<std::string> customPermsSeen;
|
|
|
|
void addCustomPerm(const std::string &word) {
|
|
if (customPermsSeen.find(word) == customPermsSeen.end()) {
|
|
customPermsSeen.insert(word);
|
|
customPerms.push_back(word);
|
|
}
|
|
}
|
|
};
|
|
|
|
void test_correctness() {
|
|
PermInfoAfter info;
|
|
|
|
info.addCustomPerm("CUSTOM_KICK");
|
|
info.addCustomPerm("CUSTOM_BAN");
|
|
info.addCustomPerm("CUSTOM_MUTE");
|
|
assert(info.customPerms.size() == 3);
|
|
|
|
// Duplicate should not be added
|
|
info.addCustomPerm("CUSTOM_KICK");
|
|
assert(info.customPerms.size() == 3);
|
|
|
|
// Order preserved
|
|
assert(info.customPerms[0] == "CUSTOM_KICK");
|
|
assert(info.customPerms[1] == "CUSTOM_BAN");
|
|
assert(info.customPerms[2] == "CUSTOM_MUTE");
|
|
|
|
printf("PASS: correctness\n");
|
|
}
|
|
|
|
void test_performance() {
|
|
const int NUM_PERMS = 2000;
|
|
|
|
// Generate unique perm names
|
|
std::vector<std::string> perms;
|
|
for (int i = 0; i < NUM_PERMS; i++)
|
|
perms.push_back("CUSTOM_PERM_" + std::to_string(i));
|
|
|
|
// Benchmark BEFORE
|
|
PermInfoBefore before;
|
|
auto t0 = std::chrono::high_resolution_clock::now();
|
|
for (int round = 0; round < 10; round++) {
|
|
before.customPerms.clear();
|
|
for (auto &p : perms)
|
|
before.addCustomPerm(p);
|
|
}
|
|
auto t1 = std::chrono::high_resolution_clock::now();
|
|
double before_ms = std::chrono::duration<double, std::milli>(t1 - t0).count();
|
|
|
|
// Benchmark AFTER
|
|
PermInfoAfter after;
|
|
auto t2 = std::chrono::high_resolution_clock::now();
|
|
for (int round = 0; round < 10; round++) {
|
|
after.customPerms.clear();
|
|
after.customPermsSeen.clear();
|
|
for (auto &p : perms)
|
|
after.addCustomPerm(p);
|
|
}
|
|
auto t3 = std::chrono::high_resolution_clock::now();
|
|
double after_ms = std::chrono::duration<double, std::milli>(t3 - t2).count();
|
|
|
|
assert(before.customPerms.size() == (size_t)NUM_PERMS);
|
|
assert(after.customPerms.size() == (size_t)NUM_PERMS);
|
|
|
|
double ratio = before_ms / after_ms;
|
|
printf("BEFORE: %.1f ms (%d perms)\n", before_ms, NUM_PERMS);
|
|
printf("AFTER: %.1f ms (%d perms)\n", after_ms, NUM_PERMS);
|
|
printf("Ratio: %.1fx speedup\n", ratio);
|
|
|
|
assert(ratio > 3.0 && "Expected at least 3x speedup from set dedup");
|
|
printf("PASS: performance (%.1fx)\n", ratio);
|
|
}
|
|
|
|
int main() {
|
|
test_correctness();
|
|
test_performance();
|
|
printf("ALL TESTS PASSED\n");
|
|
return 0;
|
|
}
|