The client's gap closing before a frame raise (0x764EB0) walks the whole frame list once per empty level and per moved level; with a large addon set one raise took 150-975 ms (panels, StaticPopup, MirrorTimer, addon windows). Replaced with one walk that gives the same levels, counts and list order, checked against a port of the client's code in tests/test_framelevel.cpp. Switch: framelevel=0. Lua: DucielPerf_GetFrameLevelStats(). Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
273 lines
10 KiB
C++
273 lines
10 KiB
C++
// Test for one-pass frame-level compaction (src/modules/framelevel_core.h).
|
|
// A fake CSimpleTop (frame list, per-strata level counts, per-level lists of
|
|
// shown frames) is compacted twice: by reference(), a literal port of the
|
|
// client's 0x764EB0, and by Compactor::compact(). Every frame's level, every
|
|
// strata's level count and the order of frames inside every level list must
|
|
// match. Also: the fallback when a shown frame is missing from the frame
|
|
// list, and the cost (frame-list nodes visited) of both.
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
#include <algorithm>
|
|
#include <chrono>
|
|
#include <vector>
|
|
|
|
#include "../src/modules/framelevel_core.h"
|
|
|
|
struct F {
|
|
int id;
|
|
int strata;
|
|
uint32_t level;
|
|
bool shown;
|
|
F *next; // frame list
|
|
};
|
|
|
|
struct World {
|
|
std::vector<F> frames;
|
|
F *head = nullptr;
|
|
uint32_t count[8] = {};
|
|
std::vector<std::vector<int>> lists[8]; // shown frame ids per level
|
|
uint64_t visits = 0, set_calls = 0;
|
|
|
|
void ensure(int s, uint32_t lvl) {
|
|
if (lists[s].size() <= lvl) lists[s].resize(lvl + 1);
|
|
}
|
|
void setLevel(F *f, uint32_t lvl) {
|
|
set_calls++;
|
|
if (f->shown) {
|
|
auto &from = lists[f->strata][f->level];
|
|
from.erase(std::find(from.begin(), from.end(), f->id));
|
|
ensure(f->strata, lvl);
|
|
lists[f->strata][lvl].push_back(f->id);
|
|
}
|
|
f->level = lvl;
|
|
}
|
|
void relink() { // frames vector must not reallocate after this
|
|
head = nullptr;
|
|
for (size_t i = frames.size(); i-- > 0;) {
|
|
frames[i].next = head;
|
|
head = &frames[i];
|
|
}
|
|
}
|
|
};
|
|
|
|
struct TestApi {
|
|
typedef World *Top;
|
|
typedef F *Frame;
|
|
static uint32_t count(Top t, int s) { return t->count[s]; }
|
|
static void setCount(Top t, int s, uint32_t n) { t->count[s] = n; }
|
|
static bool listUsed(Top t, int s, uint32_t lvl) { return lvl < t->lists[s].size() && !t->lists[s][lvl].empty(); }
|
|
static Frame first(Top t) {
|
|
if (t->head) t->visits++;
|
|
return t->head;
|
|
}
|
|
static Frame next(Top t, Frame f) {
|
|
if (f->next) t->visits++;
|
|
return f->next;
|
|
}
|
|
static int strata(Frame f) { return f->strata; }
|
|
static uint32_t level(Frame f) { return f->level; }
|
|
static void setLevel(Frame f, uint32_t lvl);
|
|
static void *grow(void *p, size_t bytes) { return realloc(p, bytes); }
|
|
};
|
|
static World *g_world; // world being changed by setLevel
|
|
void TestApi::setLevel(Frame f, uint32_t lvl) { g_world->setLevel(f, lvl); }
|
|
|
|
// Literal port of the client's 0x764EB0 (see perf_framelevel.cpp).
|
|
static void reference(World *w, int s) {
|
|
uint32_t n = w->count[s];
|
|
uint32_t edi = 0, ebx = n;
|
|
int64_t edx = -1;
|
|
auto anyFrame = [&](uint32_t lvl) {
|
|
for (F *f = TestApi::first(w); f; f = TestApi::next(w, f))
|
|
if (f->strata == s && f->level == lvl) return true;
|
|
return false;
|
|
};
|
|
while (edi < ebx) {
|
|
bool used = TestApi::listUsed(w, s, edi) || anyFrame(edi);
|
|
if (!used) {
|
|
if (edx < 0) edx = edi;
|
|
edi++;
|
|
continue;
|
|
}
|
|
if (edx < 0) {
|
|
edi++;
|
|
continue;
|
|
}
|
|
uint32_t shift = edi - (uint32_t)edx;
|
|
for (uint32_t j = edi; j < ebx; j++)
|
|
for (F *f = TestApi::first(w); f; f = TestApi::next(w, f))
|
|
if (f->strata == s && f->level == j) w->setLevel(f, j - shift);
|
|
ebx -= shift;
|
|
edx = -1;
|
|
}
|
|
w->count[s] = edx >= 0 ? (uint32_t)edx : ebx;
|
|
}
|
|
|
|
static uint32_t g_seed = 4242;
|
|
static uint32_t rnd(uint32_t n) {
|
|
g_seed = g_seed * 1103515245u + 12345u;
|
|
return (g_seed >> 8) % n;
|
|
}
|
|
|
|
static int g_failures;
|
|
static void check(const char *what, bool ok) {
|
|
printf(" %-66s %s\n", what, ok ? "ok" : "FAIL");
|
|
if (!ok) g_failures++;
|
|
}
|
|
|
|
// Random world: nframes frames over 8 strata; strata `s` gets `levels`
|
|
// levels with gaps (density in %), a few frames at or above the count.
|
|
static World makeWorld(int nframes, int s, uint32_t levels, int density) {
|
|
World w;
|
|
w.frames.reserve(nframes);
|
|
std::vector<uint8_t> level_used(levels);
|
|
for (uint32_t l = 0; l < levels; l++) level_used[l] = rnd(100) < (uint32_t)density;
|
|
for (int i = 0; i < nframes; i++) {
|
|
F f{};
|
|
f.id = i;
|
|
f.strata = rnd(3) == 0 ? s : (int)rnd(8);
|
|
uint32_t cnt = f.strata == s ? levels : 1 + rnd(20);
|
|
if (f.strata == s) {
|
|
uint32_t l = rnd(levels + 3); // a few beyond the count
|
|
for (int tries = 0; l < levels && !level_used[l] && tries < 8; tries++) l = rnd(levels);
|
|
f.level = l;
|
|
} else {
|
|
f.level = rnd(cnt);
|
|
}
|
|
f.shown = rnd(3) != 0;
|
|
w.frames.push_back(f);
|
|
}
|
|
// Shuffle the list order (creation order is not level order).
|
|
for (int i = nframes - 1; i > 0; i--) std::swap(w.frames[i], w.frames[rnd(i + 1)]);
|
|
w.relink();
|
|
for (int st = 0; st < 8; st++) w.count[st] = st == s ? levels : 20;
|
|
for (F &f : w.frames) {
|
|
w.ensure(f.strata, std::max(f.level, w.count[f.strata]));
|
|
if (f.shown) w.lists[f.strata][f.level].push_back(f.id);
|
|
}
|
|
return w;
|
|
}
|
|
|
|
static bool same(const World &a, const World &b) {
|
|
for (size_t i = 0; i < a.frames.size(); i++)
|
|
if (a.frames[i].level != b.frames[i].level) return false;
|
|
for (int s = 0; s < 8; s++) {
|
|
if (a.count[s] != b.count[s]) return false;
|
|
size_t n = std::max(a.lists[s].size(), b.lists[s].size());
|
|
for (size_t l = 0; l < n; l++) {
|
|
static const std::vector<int> empty;
|
|
const auto &x = l < a.lists[s].size() ? a.lists[s][l] : empty;
|
|
const auto &y = l < b.lists[s].size() ? b.lists[s][l] : empty;
|
|
if (x != y) return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
// Copy a world (re-pointing the frame list into the copy).
|
|
static World copyWorld(const World &w) {
|
|
World c;
|
|
c.frames = w.frames;
|
|
c.frames.reserve(w.frames.size());
|
|
for (size_t i = 0; i < w.frames.size(); i++)
|
|
c.frames[i].next = w.frames[i].next ? &c.frames[w.frames[i].next - w.frames.data()] : nullptr;
|
|
c.head = w.head ? &c.frames[w.head - w.frames.data()] : nullptr;
|
|
memcpy(c.count, w.count, sizeof c.count);
|
|
for (int s = 0; s < 8; s++) c.lists[s] = w.lists[s];
|
|
return c;
|
|
}
|
|
|
|
int main() {
|
|
printf("test_framelevel\n");
|
|
framelevel::Compactor<TestApi> comp;
|
|
|
|
// Randomized equivalence.
|
|
int cases = 0, mismatches = 0, changed = 0;
|
|
uint64_t ref_visits = 0, new_visits = 0;
|
|
for (int iter = 0; iter < 3000; iter++) {
|
|
int nframes = 1 + rnd(iter < 2500 ? 120 : 1500);
|
|
int s = rnd(8);
|
|
uint32_t levels = rnd(iter % 10 == 0 ? 3 : 60);
|
|
int density = 5 + rnd(95);
|
|
World base = makeWorld(nframes, s, levels, density);
|
|
World a = copyWorld(base), b = copyWorld(base);
|
|
g_world = &a;
|
|
reference(&a, s);
|
|
g_world = &b;
|
|
bool done = comp.compact(&b, s);
|
|
cases++;
|
|
if (!done || !same(a, b)) {
|
|
if (mismatches++ < 3)
|
|
printf(" mismatch: iter %d frames %d strata %d levels %u density %d done %d\n", iter, nframes, s,
|
|
levels, density, done);
|
|
}
|
|
if (a.set_calls) changed++;
|
|
ref_visits += a.visits;
|
|
new_visits += b.visits;
|
|
}
|
|
char line[160];
|
|
snprintf(line, sizeof line, "%d random worlds: same levels, counts and list order (%d changed)", cases, changed);
|
|
check(line, mismatches == 0);
|
|
snprintf(line, sizeof line, "frame-list nodes visited: client %llu, one-pass %llu",
|
|
(unsigned long long)ref_visits, (unsigned long long)new_visits);
|
|
check(line, new_visits <= ref_visits);
|
|
|
|
// Hand-made case from the analysis: levels {0, 5, 7} of 8 -> the client
|
|
// gives {0, 1, 3} and count 4 (it does not re-check the moved range).
|
|
{
|
|
World w;
|
|
w.frames.reserve(3);
|
|
uint32_t lv[3] = {0, 5, 7};
|
|
for (int i = 0; i < 3; i++) w.frames.push_back(F{i, 2, lv[i], true, nullptr});
|
|
w.relink();
|
|
w.count[2] = 8;
|
|
w.lists[2].resize(8);
|
|
for (F &f : w.frames) w.lists[2][f.level].push_back(f.id);
|
|
World r = copyWorld(w);
|
|
g_world = &r;
|
|
reference(&r, 2);
|
|
g_world = &w;
|
|
comp.compact(&w, 2);
|
|
bool ok = same(r, w) && w.frames[1].level == 1 && w.frames[2].level == 3 && w.count[2] == 4;
|
|
check("levels {0,5,7} of 8 -> {0,1,3}, count 4 (as the client)", ok);
|
|
}
|
|
|
|
// Fallback: a shown frame in a level list but not in the frame list.
|
|
{
|
|
World w = makeWorld(50, 3, 10, 50);
|
|
w.lists[3][9].push_back(999); // nobody at level 9 in the frame list? make sure
|
|
bool in_list = false;
|
|
for (F &f : w.frames)
|
|
if (f.strata == 3 && f.level == 9) in_list = true;
|
|
World before = copyWorld(w);
|
|
g_world = &w;
|
|
uint64_t fb = comp.fallbacks;
|
|
bool done = comp.compact(&w, 3);
|
|
check("shown frame missing from the frame list -> client's code, nothing changed",
|
|
in_list ? done : (!done && comp.fallbacks == fb + 1 && same(before, w)));
|
|
}
|
|
|
|
// Cost on a raid-sized UI: 30000 frames, 150 levels, raise-like gaps.
|
|
{
|
|
World base = makeWorld(30000, 4, 150, 70);
|
|
World a = copyWorld(base), b = copyWorld(base);
|
|
g_world = &a;
|
|
auto t0 = std::chrono::steady_clock::now();
|
|
reference(&a, 4);
|
|
auto t1 = std::chrono::steady_clock::now();
|
|
g_world = &b;
|
|
comp.compact(&b, 4);
|
|
auto t2 = std::chrono::steady_clock::now();
|
|
double ms_ref = std::chrono::duration<double, std::milli>(t1 - t0).count();
|
|
double ms_new = std::chrono::duration<double, std::milli>(t2 - t1).count();
|
|
snprintf(line, sizeof line, "30000 frames, 150 levels: client %.1f ms (%llu nodes), one-pass %.2f ms (%llu)",
|
|
ms_ref, (unsigned long long)a.visits, ms_new, (unsigned long long)b.visits);
|
|
check(line, same(a, b) && ms_new < ms_ref);
|
|
}
|
|
|
|
printf(g_failures ? "test_framelevel: %d FAILED\n" : "test_framelevel: all passed\n", g_failures);
|
|
return g_failures ? 1 : 0;
|
|
}
|