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.
135 lines
3.9 KiB
C
135 lines
3.9 KiB
C
/*
|
|
* sameboy-0002: test — breakpoint linear scan O(B) per CPU instruction
|
|
*
|
|
* should_break() scans gb->breakpoints[0..n] on every instruction fetch
|
|
* when debug_active is set. With B breakpoints all at high addresses,
|
|
* an instruction fetch at 0x0100 (ROM entry point) incurs O(B) scan.
|
|
*
|
|
* Fix: breakpoint_address_set[addr] boolean lookup gives O(1) early exit.
|
|
*
|
|
* Test verifies:
|
|
* 1. O(B) baseline: op count grows linearly with B
|
|
* 2. O(1) fixed: op count is constant regardless of B
|
|
* 3. Speedup >= 5x at B=64
|
|
*/
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <stdint.h>
|
|
#include <stdbool.h>
|
|
#include <string.h>
|
|
#include <assert.h>
|
|
|
|
#define ADDR_SPACE 0x10000
|
|
#define INSTRUCTIONS 100000
|
|
|
|
typedef struct {
|
|
unsigned id;
|
|
uint16_t addr;
|
|
uint16_t bank;
|
|
char *condition;
|
|
bool is_jump_to;
|
|
uint16_t length;
|
|
bool inclusive;
|
|
} breakpoint_t;
|
|
|
|
/* ---------- baseline: O(B) linear scan ---------- */
|
|
static long long baseline_ops;
|
|
|
|
static unsigned should_break_linear(breakpoint_t *bps, int n, uint16_t addr)
|
|
{
|
|
for (int i = 0; i < n; i++) {
|
|
baseline_ops++;
|
|
breakpoint_t *bp = &bps[i];
|
|
if (bp->bank != (uint16_t)-1) {
|
|
/* bank check omitted for simplicity — bank always any */
|
|
}
|
|
if (addr < bp->addr) continue;
|
|
if (addr > (uint32_t)bp->addr + bp->length + bp->inclusive) continue;
|
|
if (!bp->condition) return bp->id;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
/* ---------- fixed: O(1) address-set table ---------- */
|
|
static long long fixed_ops;
|
|
static bool breakpoint_address_set[ADDR_SPACE];
|
|
|
|
static void rebuild_address_set(breakpoint_t *bps, int n)
|
|
{
|
|
memset(breakpoint_address_set, 0, sizeof(breakpoint_address_set));
|
|
for (int i = 0; i < n; i++) {
|
|
breakpoint_t *bp = &bps[i];
|
|
for (uint32_t a = bp->addr; a <= (uint32_t)bp->addr + bp->length + bp->inclusive; a++) {
|
|
breakpoint_address_set[(uint16_t)a] = true;
|
|
}
|
|
}
|
|
}
|
|
|
|
static unsigned should_break_fixed(breakpoint_t *bps, int n, uint16_t addr)
|
|
{
|
|
fixed_ops++;
|
|
if (!breakpoint_address_set[addr]) return 0; /* O(1) exit */
|
|
/* full scan only when address is registered */
|
|
for (int i = 0; i < n; i++) {
|
|
fixed_ops++;
|
|
breakpoint_t *bp = &bps[i];
|
|
if (addr < bp->addr) continue;
|
|
if (addr > (uint32_t)bp->addr + bp->length + bp->inclusive) continue;
|
|
if (!bp->condition) return bp->id;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
static void run_scenario(int n_bp, long long *out_baseline, long long *out_fixed)
|
|
{
|
|
breakpoint_t *bps = calloc(n_bp, sizeof(breakpoint_t));
|
|
/* Place all breakpoints at high addresses so PC=0x0100 never hits */
|
|
for (int i = 0; i < n_bp; i++) {
|
|
bps[i].id = i + 1;
|
|
bps[i].addr = 0xFF00 + (i % 0x100);
|
|
bps[i].bank = (uint16_t)-1;
|
|
bps[i].length = 0;
|
|
bps[i].inclusive = false;
|
|
bps[i].is_jump_to = false;
|
|
bps[i].condition = NULL;
|
|
}
|
|
rebuild_address_set(bps, n_bp);
|
|
|
|
baseline_ops = 0;
|
|
fixed_ops = 0;
|
|
|
|
for (int i = 0; i < INSTRUCTIONS; i++) {
|
|
should_break_linear(bps, n_bp, 0x0100);
|
|
}
|
|
*out_baseline = baseline_ops;
|
|
|
|
for (int i = 0; i < INSTRUCTIONS; i++) {
|
|
should_break_fixed(bps, n_bp, 0x0100);
|
|
}
|
|
*out_fixed = fixed_ops;
|
|
|
|
free(bps);
|
|
}
|
|
|
|
int main(void)
|
|
{
|
|
printf("sameboy-0002: breakpoint O(B) scan per CPU instruction\n");
|
|
printf("%-12s %14s %10s %10s\n", "breakpoints", "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 b = sizes[s];
|
|
long long bl, fx;
|
|
run_scenario(b, &bl, &fx);
|
|
double speedup = (double)bl / (double)fx;
|
|
printf("%-12d %14lld %10lld %9.1fx\n", b, bl, fx, speedup);
|
|
last_speedup = speedup;
|
|
}
|
|
|
|
/* At B=128, speedup should be >= 5x */
|
|
assert(last_speedup >= 5.0 && "expected >= 5x speedup at B=128");
|
|
printf("PASS: sameboy-0002\n");
|
|
return 0;
|
|
}
|