97 lines
2.5 KiB
C++
97 lines
2.5 KiB
C++
// cemu-0001: LatteTextureViewVk::list_descriptorSets vector -> unordered_set
|
|
// Tests that AddDescriptorSetReference is O(1) amortized, not O(D).
|
|
|
|
#include <cassert>
|
|
#include <unordered_set>
|
|
#include <vector>
|
|
#include <chrono>
|
|
#include <cstdio>
|
|
|
|
// Simulates the original defect: std::vector with linear scan for uniqueness
|
|
struct DefectRef {
|
|
std::vector<int*> refs;
|
|
|
|
void add(int* p) {
|
|
for (auto* r : refs)
|
|
if (r == p) return;
|
|
refs.push_back(p);
|
|
}
|
|
|
|
void remove(int* p) {
|
|
refs.erase(std::remove(refs.begin(), refs.end(), p), refs.end());
|
|
}
|
|
};
|
|
|
|
// Fixed implementation: unordered_set, O(1) amortized
|
|
struct FixedRef {
|
|
std::unordered_set<int*> refs;
|
|
|
|
void add(int* p) {
|
|
refs.insert(p);
|
|
}
|
|
|
|
void remove(int* p) {
|
|
refs.erase(p);
|
|
}
|
|
};
|
|
|
|
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() {
|
|
// Correctness test: both implementations maintain unique set
|
|
DefectRef defect;
|
|
FixedRef fixed;
|
|
|
|
const int N = 500;
|
|
int ptrs[N];
|
|
for (int i = 0; i < N; i++) {
|
|
defect.add(&ptrs[i]);
|
|
fixed.add(&ptrs[i]);
|
|
}
|
|
// Duplicate add should not grow the collection
|
|
for (int i = 0; i < N; i++) {
|
|
defect.add(&ptrs[i]);
|
|
fixed.add(&ptrs[i]);
|
|
}
|
|
assert(defect.refs.size() == N);
|
|
assert(fixed.refs.size() == N);
|
|
|
|
// Remove half
|
|
for (int i = 0; i < N / 2; i++) {
|
|
defect.remove(&ptrs[i]);
|
|
fixed.remove(&ptrs[i]);
|
|
}
|
|
assert(defect.refs.size() == N / 2);
|
|
assert(fixed.refs.size() == N / 2);
|
|
|
|
// Performance: add D = 1000 unique pointers to each, measure time
|
|
const int D = 1000;
|
|
int ds_ptrs[D];
|
|
|
|
DefectRef defect2;
|
|
auto t_defect = bench_ns([&]() {
|
|
for (int i = 0; i < D; i++)
|
|
defect2.add(&ds_ptrs[i]);
|
|
});
|
|
|
|
FixedRef fixed2;
|
|
auto t_fixed = bench_ns([&]() {
|
|
for (int i = 0; i < D; i++)
|
|
fixed2.add(&ds_ptrs[i]);
|
|
});
|
|
|
|
double ratio = (double)t_defect / (double)t_fixed;
|
|
printf("cemu-0001: defect=%lldns fixed=%lldns ratio=%.1fx (D=%d)\n",
|
|
(long long)t_defect, (long long)t_fixed, ratio, D);
|
|
|
|
// Fixed should be significantly faster for large D
|
|
assert(ratio > 2.0 && "Fixed implementation not measurably faster — check test");
|
|
|
|
printf("cemu-0001: PASS\n");
|
|
return 0;
|
|
}
|