java-topology/defects/citra-0001/test/CitraTest.java

import java.util.*;

/**
 * CitraTest -- MOAD-0001 (CWE-407) regression test for citra-0001.
 *
 * Defect: RasterizerCache page_table stored surfaces as std::vector<SurfaceId>
 * per page. UnregisterSurface called std::find (O(S)) for each of P pages the
 * surface spans, giving O(P * S) per eviction where S = number of overlapping
 * surfaces on a shared page. Total over all S surfaces: O(P * S^2).
 *
 * Fix: Replace std::vector<SurfaceId> with std::unordered_set<SurfaceId>
 * so that find and erase are O(1), reducing total to O(P * S).
 *
 * This test models the same access pattern in Java using primitive int arrays
 * (no boxing overhead) to approximate the C++ unboxed SurfaceId (uint32_t)
 * performance characteristics.
 */
public class CitraTest {

    // ---- Defective: int[] per page, linear scan to find and remove ----
    // Simulates std::vector<SurfaceId> with std::find + erase O(S) per page

    static long benchVector(int S, int P) {
        // pageVec[p][0] = current count, pageVec[p][1..S] = surface ids
        int[][] pageVec = new int[P][S + 1];
        for (int[] pv : pageVec) pv[0] = 0;

        // Register all S surfaces on all P pages (simulate RegisterSurface)
        for (int i = 0; i < S; i++) {
            for (int p = 0; p < P; p++) {
                pageVec[p][++pageVec[p][0]] = i;
            }
        }

        long t0 = System.nanoTime();
        // Unregister all surfaces: O(S) find per page per surface = O(P * S^2) total
        for (int i = 0; i < S; i++) {
            for (int p = 0; p < P; p++) {
                int count = pageVec[p][0];
                for (int k = 1; k <= count; k++) {
                    if (pageVec[p][k] == i) {
                        // swap-with-last erase (order-independent, same as vector erase)
                        pageVec[p][k] = pageVec[p][count];
                        pageVec[p][0]--;
                        break;
                    }
                }
            }
        }
        return System.nanoTime() - t0;
    }

    // ---- Fixed: BitSet per page, O(1) set/clear ----
    // Simulates std::unordered_set<SurfaceId> with O(1) insert and erase

    static long benchSet(int S, int P) {
        BitSet[] pageSet = new BitSet[P];
        for (int p = 0; p < P; p++) pageSet[p] = new BitSet(S);

        // Register all S surfaces on all P pages
        for (int i = 0; i < S; i++) {
            for (int p = 0; p < P; p++) {
                pageSet[p].set(i);
            }
        }

        long t0 = System.nanoTime();
        // Unregister all surfaces: O(1) per page per surface = O(P * S) total
        for (int i = 0; i < S; i++) {
            for (int p = 0; p < P; p++) {
                pageSet[p].clear(i);
            }
        }
        return System.nanoTime() - t0;
    }

    public static void main(String[] args) {
        // S = overlapping surfaces on same page (texture cache at busy scene transition)
        // P = pages per surface (256x256 RGBA texture on 4KB pages = 64 pages)
        final int S = 500;
        final int P = 64;
        final int WARMUP = 5;
        final int RUNS = 10;

        System.out.println("citra-0001: RasterizerCache page_table surfaces O(P*S^2) -> O(P*S)");
        System.out.printf("S=%d overlapping surfaces, P=%d pages per surface%n", S, P);
        System.out.println();

        long defectTotal = 0;
        for (int r = 0; r < WARMUP + RUNS; r++) {
            long elapsed = benchVector(S, P);
            if (r >= WARMUP) defectTotal += elapsed;
        }
        double defectMs = defectTotal / 1e6 / RUNS;

        long fixedTotal = 0;
        for (int r = 0; r < WARMUP + RUNS; r++) {
            long elapsed = benchSet(S, P);
            if (r >= WARMUP) fixedTotal += elapsed;
        }
        double fixedMs = fixedTotal / 1e6 / RUNS;

        double ratio = defectMs / fixedMs;
        System.out.printf("Defective (vector linear-scan unregister): %.3f ms%n", defectMs);
        System.out.printf("Fixed     (bitset O(1) unregister):        %.3f ms%n", fixedMs);
        System.out.printf("Speedup:                                   %.1fx%n", ratio);
        System.out.println();

        // Correctness: after all unregisters, page entries should be empty
        int[][] verifyVec = new int[P][3];
        for (int[] pv : verifyVec) pv[0] = 0;
        verifyVec[0][++verifyVec[0][0]] = 42;
        // Linear remove of 42
        int found = -1;
        for (int k = 1; k <= verifyVec[0][0]; k++) {
            if (verifyVec[0][k] == 42) { found = k; break; }
        }
        if (found < 0) throw new AssertionError("correctness: 42 not found");
        verifyVec[0][found] = verifyVec[0][verifyVec[0][0]--];
        if (verifyVec[0][0] != 0) throw new AssertionError("correctness: count should be 0 after remove");

        BitSet verifySet = new BitSet(100);
        verifySet.set(42);
        verifySet.clear(42);
        if (verifySet.get(42)) throw new AssertionError("correctness: bitset should be empty");
        // Double-clear is idempotent (no error) - same as unordered_set erase returns count
        verifySet.clear(42);

        System.out.println("All correctness assertions PASS");

        if (ratio < 2.0) {
            System.err.printf("FAIL: speedup %.1fx less than expected minimum 2x at S=%d%n",
                              ratio, S);
            System.exit(1);
        } else {
            System.out.printf("PASS: %.1fx speedup >= 2x minimum%n", ratio);
        }
    }
}