import java.util.*; /** * Play0001Test: unit test for play-0001 * * Defect: CIopBios::FindIntrHandler() in Source/iop/IopBios.cpp performs a * full linear scan of all m_intrHandlers slots (up to MAX_INTRHANDLER=32) * comparing handler->line == line on every call. HandleInterrupt() calls this * on every pending IOP interrupt — VBLANK, CDROM, DMAC, SPU2, timer lines * fire thousands of times per second during emulation. * * Because IOP interrupt lines are small integers (0x00..0x2D, LINES_MAX=0x2E=46), * a direct array indexed by line number is the correct structure. The fix adds * m_intrHandlerIndex[LINES_MAX] maintained in sync at Register/Release time, * reducing FindIntrHandler from O(H) to O(1) where H = registered handler count. * * Affected file: Source/iop/IopBios.cpp, FindIntrHandler() * Called from: HandleInterrupt() -> FindIntrHandler(line) [hot path] * Frequency: thousands of times per second during normal emulation * Complexity: O(H) -> O(1), H up to MAX_INTRHANDLER=32 */ public class Play0001Test { // Interrupt line constants mirroring Iop::CIntc::LINES static final int LINE_VBLANK = 0x00; static final int LINE_SBUS = 0x01; static final int LINE_CDROM = 0x02; static final int LINE_DMAC = 0x03; static final int LINE_SPU2 = 0x09; static final int LINE_EVBLANK = 0x0B; static final int LINE_SIO2 = 0x11; static final int LINES_MAX = 0x2E; // 46 static final int MAX_HANDLERS = 32; // --- Defective: linear scan over all registered handlers --- static class IntrHandlerDefective { int[] line = new int[MAX_HANDLERS]; boolean[] ok = new boolean[MAX_HANDLERS]; int next = 0; IntrHandlerDefective() { Arrays.fill(line, -1); } int register(int l) { int id = next++; line[id] = l; ok[id] = true; return id; } void release(int id) { ok[id] = false; } // O(H) — the defect int find(int l) { for (int i = 0; i < next; i++) { if (ok[i] && line[i] == l) return i; } return -1; } } // --- Fixed: O(1) direct index by line number --- static class IntrHandlerFixed { int[] line = new int[MAX_HANDLERS]; boolean[] ok = new boolean[MAX_HANDLERS]; int[] idx = new int[LINES_MAX]; // the fix: index by line int next = 0; IntrHandlerFixed() { Arrays.fill(line, -1); Arrays.fill(idx, -1); } int register(int l) { int id = next++; line[id] = l; ok[id] = true; if (l >= 0 && l < LINES_MAX) idx[l] = id; return id; } void release(int id) { ok[id] = false; int l = line[id]; if (l >= 0 && l < LINES_MAX) idx[l] = -1; } // O(1) — the fix int find(int l) { if (l < 0 || l >= LINES_MAX) return -1; int id = idx[l]; if (id == -1 || !ok[id]) return -1; return id; } } static void check(boolean cond, String msg) { if (!cond) throw new AssertionError("FAIL: " + msg); } static void testBasicLookup() { IntrHandlerDefective d = new IntrHandlerDefective(); IntrHandlerFixed f = new IntrHandlerFixed(); d.register(LINE_VBLANK); f.register(LINE_VBLANK); d.register(LINE_CDROM); f.register(LINE_CDROM); d.register(LINE_SPU2); f.register(LINE_SPU2); int idD = d.register(LINE_DMAC); int idF = f.register(LINE_DMAC); check(d.find(LINE_DMAC) == idD, "defective: find LINE_DMAC"); check(f.find(LINE_DMAC) == idF, "fixed: find LINE_DMAC"); check(d.find(0x30) == -1, "defective: unknown line -> -1"); check(f.find(0x30) == -1, "fixed: unknown line -> -1"); System.out.println("PASS testBasicLookup"); } static void testRelease() { IntrHandlerDefective d = new IntrHandlerDefective(); IntrHandlerFixed f = new IntrHandlerFixed(); int idD = d.register(LINE_VBLANK); int idF = f.register(LINE_VBLANK); check(d.find(LINE_VBLANK) == idD, "defective: found before release"); check(f.find(LINE_VBLANK) == idF, "fixed: found before release"); d.release(idD); f.release(idF); check(d.find(LINE_VBLANK) == -1, "defective: not found after release"); check(f.find(LINE_VBLANK) == -1, "fixed: not found after release"); System.out.println("PASS testRelease"); } static void testReregisterAfterRelease() { IntrHandlerFixed f = new IntrHandlerFixed(); int id1 = f.register(LINE_EVBLANK); f.release(id1); int id2 = f.register(LINE_EVBLANK); check(f.find(LINE_EVBLANK) == id2, "fixed: re-register after release"); System.out.println("PASS testReregisterAfterRelease"); } static void testAllKnownLines() { IntrHandlerFixed f = new IntrHandlerFixed(); int[] known = {LINE_VBLANK, LINE_SBUS, LINE_CDROM, LINE_DMAC, 0x04, 0x05, 0x06, LINE_SPU2, LINE_EVBLANK, 0x0D, LINE_SIO2, 0x16}; for (int l : known) f.register(l); for (int l : known) { check(f.find(l) >= 0, "fixed: line 0x" + Integer.toHexString(l) + " must be found"); } System.out.println("PASS testAllKnownLines"); } // Count operations manually to measure algorithmic cost rather than JVM timing // Returns total comparisons performed static long countOpsDefective(int[] registeredLines, int[] queryLines, int N) { long ops = 0; // For each query, defective scans from 0 to hit (or all if miss) for (int i = 0; i < N; i++) { int target = queryLines[i % queryLines.length]; for (int j = 0; j < registeredLines.length; j++) { ops++; if (registeredLines[j] == target) break; } } return ops; } static long countOpsFixed(int[] registeredLines, int[] queryLines, int N) { // Fixed is always exactly 1 array lookup per query return N; } static void testBenchmark() { // Measure algorithmic operation count: defective O(H) vs fixed O(1) int H = 32; int N = 100000; // Query lines that are present in the handler set (worst-case: last element scanned) int[] registeredLines = new int[H]; for (int i = 0; i < H; i++) registeredLines[i] = i % (LINES_MAX - 1); // Query the last registered line (maximum scan distance for defective) int[] queryLines = new int[]{registeredLines[H - 1]}; long defOps = countOpsDefective(registeredLines, queryLines, N); long fixOps = countOpsFixed(registeredLines, queryLines, N); double ratio = (double) defOps / Math.max(fixOps, 1L); System.out.printf("BENCH ops: defective=%d fixed=%d ratio=%.1fx%n", defOps, fixOps, ratio); // Algorithmic ratio must equal H (number of slots scanned per miss-or-last-hit) check(ratio >= (double) H * 0.9, "expected algorithmic ratio >= " + H + "x, got " + String.format("%.1f", ratio) + "x"); // Also do a timing check with a larger dataset IntrHandlerDefective d = new IntrHandlerDefective(); IntrHandlerFixed f = new IntrHandlerFixed(); for (int i = 0; i < H; i++) { d.register(i % (LINES_MAX - 1)); f.register(i % (LINES_MAX - 1)); } // Query last line (worst case for defective) int worstLine = registeredLines[H - 1]; int BIG = 2000000; // Warm-up for (int i = 0; i < 10000; i++) { d.find(worstLine); f.find(worstLine); } long t0 = System.nanoTime(); int sumD = 0; for (int i = 0; i < BIG; i++) sumD += d.find(worstLine); long defNs = System.nanoTime() - t0; long t1 = System.nanoTime(); int sumF = 0; for (int i = 0; i < BIG; i++) sumF += f.find(worstLine); long fixNs = System.nanoTime() - t1; check(sumD == sumF, "bench: result sums must match"); double timeRatio = (double) defNs / Math.max(fixNs, 1L); System.out.printf("BENCH timing: defective=%.2fms fixed=%.2fms ratio=%.1fx%n", defNs / 1e6, fixNs / 1e6, timeRatio); check(timeRatio >= 2.0, "expected >= 2x speedup, got " + String.format("%.1f", timeRatio) + "x"); System.out.println("PASS testBenchmark (algo_ratio=" + String.format("%.0f", ratio) + "x, time_ratio=" + String.format("%.1f", timeRatio) + "x)"); } public static void main(String[] args) { testBasicLookup(); testRelease(); testReregisterAfterRelease(); testAllKnownLines(); testBenchmark(); System.out.println("ALL PASS"); } }