104 lines
3.4 KiB
C++
104 lines
3.4 KiB
C++
// cemu-0002: GraphicPack2 FILTER_SETTINGS format/tilemode list membership O(F) -> O(1)
|
|
// Per-texture-creation std::find in active graphic pack rules replaced with unordered_set lookup.
|
|
|
|
#include <cassert>
|
|
#include <vector>
|
|
#include <unordered_set>
|
|
#include <chrono>
|
|
#include <cstdio>
|
|
|
|
// Simulates defect: vector + std::find membership check, called per texture creation
|
|
struct DefectFilter {
|
|
std::vector<int> format_whitelist;
|
|
std::vector<int> tilemode_whitelist;
|
|
|
|
bool matches(int format, int tilemode) const {
|
|
if (!format_whitelist.empty()) {
|
|
if (std::find(format_whitelist.begin(), format_whitelist.end(), format)
|
|
== format_whitelist.end())
|
|
return false;
|
|
}
|
|
if (!tilemode_whitelist.empty()) {
|
|
if (std::find(tilemode_whitelist.begin(), tilemode_whitelist.end(), tilemode)
|
|
== tilemode_whitelist.end())
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
};
|
|
|
|
// Fixed: unordered_set membership, O(1) per lookup
|
|
struct FixedFilter {
|
|
std::unordered_set<int> format_whitelist;
|
|
std::unordered_set<int> tilemode_whitelist;
|
|
|
|
bool matches(int format, int tilemode) const {
|
|
if (!format_whitelist.empty()) {
|
|
if (format_whitelist.find(format) == format_whitelist.end())
|
|
return false;
|
|
}
|
|
if (!tilemode_whitelist.empty()) {
|
|
if (tilemode_whitelist.find(tilemode) == tilemode_whitelist.end())
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
};
|
|
|
|
static long long bench_ns(auto fn) {
|
|
auto t0 = std::chrono::steady_clock::now();
|
|
fn();
|
|
auto t1 = std::chrono::steady_clock::now();
|
|
return std::chrono::duration_cast<std::chrono::nanoseconds>(t1 - t0).count();
|
|
}
|
|
|
|
int main() {
|
|
// Build filters with F = 200 format entries and T = 50 tilemode entries
|
|
// (large texture packs may enumerate many formats and tile modes)
|
|
const int F = 200;
|
|
const int T = 50;
|
|
const int TEXTURES = 10000; // simulate 10k texture creations
|
|
|
|
DefectFilter defect;
|
|
FixedFilter fixed;
|
|
|
|
for (int i = 0; i < F; i++) {
|
|
defect.format_whitelist.push_back(i * 3 + 1); // scattered to avoid trivial branch pred
|
|
fixed.format_whitelist.insert(i * 3 + 1);
|
|
}
|
|
for (int i = 0; i < T; i++) {
|
|
defect.tilemode_whitelist.push_back(i * 5 + 2);
|
|
fixed.tilemode_whitelist.insert(i * 5 + 2);
|
|
}
|
|
|
|
// Correctness: both should agree on membership
|
|
for (int f = 0; f < F * 4; f++) {
|
|
for (int t = 0; t < T * 6; t++) {
|
|
bool d = defect.matches(f, t);
|
|
bool x = fixed.matches(f, t);
|
|
assert(d == x && "mismatch between defect and fixed");
|
|
}
|
|
}
|
|
|
|
// Performance: TEXTURES texture lookups, scattered format/tilemode queries
|
|
volatile bool sink = false;
|
|
|
|
auto t_defect = bench_ns([&]() {
|
|
for (int i = 0; i < TEXTURES; i++)
|
|
sink ^= defect.matches(i % (F * 4), i % (T * 6));
|
|
});
|
|
|
|
auto t_fixed = bench_ns([&]() {
|
|
for (int i = 0; i < TEXTURES; i++)
|
|
sink ^= fixed.matches(i % (F * 4), i % (T * 6));
|
|
});
|
|
|
|
double ratio = (double)t_defect / (double)t_fixed;
|
|
printf("cemu-0002: defect=%lldns fixed=%lldns ratio=%.1fx (F=%d T=%d textures=%d)\n",
|
|
(long long)t_defect, (long long)t_fixed, ratio, F, T, TEXTURES);
|
|
|
|
assert(ratio > 1.5 && "Fixed implementation not measurably faster — check test");
|
|
|
|
printf("cemu-0002: PASS\n");
|
|
return 0;
|
|
}
|