java-topology/defects/pcsx2-0001/test/PatchReloadEnabledListsTest.java

import java.util.*;

/**
 * Unit test for PCSX2 pcsx2-0001: Patch::ReloadEnabledLists and EnablePatches
 * use std::find on std::vector for membership checks inside loops, giving O(N^2).
 *
 * Four sites in ReloadEnabledLists:
 *   1. disabled_patches lookup O(E*D)
 *   2. prev_enabled_cheats lookup O(C*P)
 *   3. prev_enabled_patches lookup O(P*P)
 *   4. EnablePatches enable_list lookup O(G*E)
 *
 * Fix: convert lookup vectors to HashSet for O(1) membership.
 *
 * Defect file: pcsx2/Patch.cpp  lines 616, 630, 637, 651
 */
public class PatchReloadEnabledListsTest {

    // --- Defective: linear scan on list ---
    static List<String> reloadEnabledListsDefective(
            List<String> enabledPatches,
            List<String> disabledPatches,
            List<String> prevEnabledPatches) {

        // Filter disabled patches: O(E*D) with list.contains
        List<String> filtered = new ArrayList<>();
        for (String patch : enabledPatches) {
            if (!disabledPatches.contains(patch)) {  // O(D) scan per patch
                filtered.add(patch);
            }
        }

        // Find newly enabled: O(F*P) with list.contains
        List<String> justEnabled = new ArrayList<>();
        for (String p : filtered) {
            if (!prevEnabledPatches.contains(p)) {  // O(P) scan per patch
                justEnabled.add(p);
            }
        }
        return justEnabled;
    }

    // --- Fixed: hash set for O(1) lookups ---
    static List<String> reloadEnabledListsFixed(
            List<String> enabledPatches,
            List<String> disabledPatches,
            List<String> prevEnabledPatches) {

        Set<String> disabledSet = new HashSet<>(disabledPatches);
        Set<String> prevSet = new HashSet<>(prevEnabledPatches);

        List<String> filtered = new ArrayList<>();
        for (String patch : enabledPatches) {
            if (!disabledSet.contains(patch)) {  // O(1)
                filtered.add(patch);
            }
        }

        List<String> justEnabled = new ArrayList<>();
        for (String p : filtered) {
            if (!prevSet.contains(p)) {  // O(1)
                justEnabled.add(p);
            }
        }
        return justEnabled;
    }

    // --- EnablePatches defective: O(G*E) ---
    static int enablePatchesDefective(List<String> patchGroups, List<String> enableList) {
        int count = 0;
        for (String name : patchGroups) {
            if (!name.isEmpty() && !enableList.contains(name))  // O(E) per group
                continue;
            count++;
        }
        return count;
    }

    // --- EnablePatches fixed: O(G+E) ---
    static int enablePatchesFixed(List<String> patchGroups, List<String> enableList) {
        Set<String> enableSet = new HashSet<>(enableList);
        int count = 0;
        for (String name : patchGroups) {
            if (!name.isEmpty() && !enableSet.contains(name))  // O(1)
                continue;
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int N = 500;

        // Build test data
        List<String> enabled = new ArrayList<>();
        List<String> disabled = new ArrayList<>();
        List<String> prevEnabled = new ArrayList<>();
        List<String> patchGroups = new ArrayList<>();
        List<String> enableList = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            String name = "patch_" + i;
            enabled.add(name);
            patchGroups.add(name);
            enableList.add(name);
            if (i % 5 == 0) disabled.add(name);
            if (i < N / 2) prevEnabled.add(name);
        }

        // Correctness check
        List<String> resultDef = reloadEnabledListsDefective(enabled, disabled, prevEnabled);
        List<String> resultFix = reloadEnabledListsFixed(enabled, disabled, prevEnabled);
        assert resultDef.equals(resultFix) : "ReloadEnabledLists mismatch";

        int countDef = enablePatchesDefective(patchGroups, enableList);
        int countFix = enablePatchesFixed(patchGroups, enableList);
        assert countDef == countFix : "EnablePatches mismatch";

        // Warm up
        for (int i = 0; i < 200; i++) {
            reloadEnabledListsDefective(enabled, disabled, prevEnabled);
            reloadEnabledListsFixed(enabled, disabled, prevEnabled);
        }

        // Benchmark ReloadEnabledLists
        int ITER = 2000;
        long t0 = System.nanoTime();
        for (int i = 0; i < ITER; i++) {
            reloadEnabledListsDefective(enabled, disabled, prevEnabled);
        }
        long defectNs = System.nanoTime() - t0;

        t0 = System.nanoTime();
        for (int i = 0; i < ITER; i++) {
            reloadEnabledListsFixed(enabled, disabled, prevEnabled);
        }
        long fixedNs = System.nanoTime() - t0;

        double ratio = (double) defectNs / fixedNs;
        System.out.printf("ReloadEnabledLists  N=%d  defect=%.1fms  fixed=%.1fms  ratio=%.1fx%n",
                N, defectNs / 1e6, fixedNs / 1e6, ratio);

        // Benchmark EnablePatches
        t0 = System.nanoTime();
        for (int i = 0; i < ITER; i++) {
            enablePatchesDefective(patchGroups, enableList);
        }
        long epDefNs = System.nanoTime() - t0;

        t0 = System.nanoTime();
        for (int i = 0; i < ITER; i++) {
            enablePatchesFixed(patchGroups, enableList);
        }
        long epFixNs = System.nanoTime() - t0;

        double epRatio = (double) epDefNs / epFixNs;
        System.out.printf("EnablePatches       N=%d  defect=%.1fms  fixed=%.1fms  ratio=%.1fx%n",
                N, epDefNs / 1e6, epFixNs / 1e6, epRatio);

        assert ratio > 2.0 : "Expected >2x speedup for ReloadEnabledLists, got " + ratio;
        assert epRatio > 2.0 : "Expected >2x speedup for EnablePatches, got " + epRatio;

        System.out.println("PASS");
    }
}