Files
DucielPerf/tests/test_framelevel.cpp
DucielandClaude Opus 5.5 338bdb5159 One-pass frame-level compaction: no more freezes when showing toplevel frames (0.8.0)
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>
2026-11-16 21:14:57 +01:00

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;
}