russell@unturf.com
f46f7c9588
sameboy-0001: test_watchpoint() O(W) linear scan per GB memory read/write. Every call to GB_read_memory / GB_write_memory scans all watchpoints when n_watchpoints > 0. Fix: watchpoint_address_flags[0x10000] lookup table gives O(1) early exit; 128x speedup at W=128. sameboy-0002: should_break() O(B) linear scan per CPU instruction fetch. GB_debugger_run() calls should_break() every instruction when debug_active. Fix: breakpoint_address_set[0x10000] boolean table gives O(1) early exit; 128x speedup at B=128. MOAD-0002: CLEAN, gb struct passed explicitly, no shared global state. MOAD-0003: CLEAN, __thread only used for local string formatting buffers. MOAD-0004: CLEAN, no network credentials logged. MOAD-0005: CLEAN, no unsynchronized cache patterns found.
137 lines
4.3 KiB
C
137 lines
4.3 KiB
C
/*
|
|
* sameboy-0001: test — watchpoint linear scan O(W) per memory access
|
|
*
|
|
* Simulates the test_watchpoint() hot path. With W watchpoints, every
|
|
* GB_read_memory / GB_write_memory call scans all W watchpoints.
|
|
* Fix: watchpoint_address_flags[addr] lookup table gives O(1) early exit.
|
|
*
|
|
* Test verifies:
|
|
* 1. O(W) baseline: op count grows linearly with W
|
|
* 2. O(1) fixed: op count is constant regardless of W
|
|
* 3. Speedup >= 5x at W=64
|
|
*/
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <stdint.h>
|
|
#include <string.h>
|
|
#include <assert.h>
|
|
#include <time.h>
|
|
|
|
#define WATCHPOINT_READ 1
|
|
#define WATCHPOINT_WRITE 2
|
|
#define ADDR_SPACE 0x10000
|
|
#define MEM_ACCESSES 100000
|
|
|
|
/* Simulate the watchpoint struct */
|
|
typedef struct {
|
|
unsigned id;
|
|
uint16_t addr;
|
|
uint16_t bank;
|
|
uint8_t flags;
|
|
uint16_t length;
|
|
int inclusive;
|
|
char *condition;
|
|
} watchpoint_t;
|
|
|
|
/* ---------- baseline: O(W) linear scan ---------- */
|
|
static long long baseline_ops;
|
|
|
|
static void test_watchpoint_linear(watchpoint_t *wps, int n, uint16_t addr, uint8_t flags)
|
|
{
|
|
for (int i = 0; i < n; i++) {
|
|
baseline_ops++;
|
|
watchpoint_t *wp = &wps[i];
|
|
if (wp->bank != (uint16_t)-1) continue; /* any-bank */
|
|
if (!(wp->flags & flags)) continue;
|
|
if (addr < wp->addr) continue;
|
|
if (addr > (uint32_t)wp->addr + wp->length + wp->inclusive) continue;
|
|
/* would fire, but we only measure cost */
|
|
break;
|
|
}
|
|
}
|
|
|
|
/* ---------- fixed: O(1) address-flag table ---------- */
|
|
static long long fixed_ops;
|
|
static uint8_t watchpoint_address_flags[ADDR_SPACE];
|
|
|
|
static void rebuild_flags(watchpoint_t *wps, int n)
|
|
{
|
|
memset(watchpoint_address_flags, 0, sizeof(watchpoint_address_flags));
|
|
for (int i = 0; i < n; i++) {
|
|
watchpoint_t *wp = &wps[i];
|
|
for (uint32_t a = wp->addr; a <= (uint32_t)wp->addr + wp->length + wp->inclusive; a++) {
|
|
watchpoint_address_flags[(uint16_t)a] |= wp->flags;
|
|
}
|
|
}
|
|
}
|
|
|
|
static void test_watchpoint_fixed(watchpoint_t *wps, int n, uint16_t addr, uint8_t flags)
|
|
{
|
|
fixed_ops++;
|
|
if (!(watchpoint_address_flags[addr] & flags)) return; /* O(1) exit */
|
|
/* full scan only when address is actually covered */
|
|
for (int i = 0; i < n; i++) {
|
|
fixed_ops++;
|
|
watchpoint_t *wp = &wps[i];
|
|
if (wp->bank != (uint16_t)-1) continue;
|
|
if (!(wp->flags & flags)) continue;
|
|
if (addr < wp->addr) continue;
|
|
if (addr > (uint32_t)wp->addr + wp->length + wp->inclusive) continue;
|
|
break;
|
|
}
|
|
}
|
|
|
|
static void run_scenario(int n_watchpoints, long long *out_baseline, long long *out_fixed)
|
|
{
|
|
watchpoint_t *wps = calloc(n_watchpoints, sizeof(watchpoint_t));
|
|
/* Place all watchpoints at high addresses so accesses to 0x8000 never hit */
|
|
for (int i = 0; i < n_watchpoints; i++) {
|
|
wps[i].id = i + 1;
|
|
wps[i].addr = 0xFF00 + (i % 0x100);
|
|
wps[i].bank = (uint16_t)-1; /* any */
|
|
wps[i].flags = WATCHPOINT_READ | WATCHPOINT_WRITE;
|
|
wps[i].length = 0;
|
|
wps[i].inclusive = 0;
|
|
wps[i].condition = NULL;
|
|
}
|
|
rebuild_flags(wps, n_watchpoints);
|
|
|
|
baseline_ops = 0;
|
|
fixed_ops = 0;
|
|
|
|
/* Simulate MEM_ACCESSES to address 0x8000 (not covered by any watchpoint) */
|
|
for (int a = 0; a < MEM_ACCESSES; a++) {
|
|
test_watchpoint_linear(wps, n_watchpoints, 0x8000, WATCHPOINT_READ);
|
|
}
|
|
*out_baseline = baseline_ops;
|
|
|
|
for (int a = 0; a < MEM_ACCESSES; a++) {
|
|
test_watchpoint_fixed(wps, n_watchpoints, 0x8000, WATCHPOINT_READ);
|
|
}
|
|
*out_fixed = fixed_ops;
|
|
|
|
free(wps);
|
|
}
|
|
|
|
int main(void)
|
|
{
|
|
printf("sameboy-0001: watchpoint O(W) scan per memory access\n");
|
|
printf("%-12s %14s %10s %10s\n", "watchpoints", "baseline_ops", "fixed_ops", "speedup");
|
|
|
|
int sizes[] = {4, 16, 32, 64, 128};
|
|
double last_speedup = 0;
|
|
for (int s = 0; s < (int)(sizeof(sizes)/sizeof(sizes[0])); s++) {
|
|
int w = sizes[s];
|
|
long long bl, fx;
|
|
run_scenario(w, &bl, &fx);
|
|
double speedup = (double)bl / (double)fx;
|
|
printf("%-12d %14lld %10lld %9.1fx\n", w, bl, fx, speedup);
|
|
last_speedup = speedup;
|
|
}
|
|
|
|
/* At W=64, speedup should be >= 5x */
|
|
assert(last_speedup >= 5.0 && "expected >= 5x speedup at W=128");
|
|
printf("PASS: sameboy-0001\n");
|
|
return 0;
|
|
}
|