java-topology/defects/julia/unit/JuliaBackedgeDedupTest.java

package unit;

import java.util.*;

/**
 * JuliaBackedgeDedupTest -- julia-0003: _typename_add_backedge() O(N²) linear scan
 *
 * Models the defect in Julia src/gf.c _typename_add_backedge() (lines 2376-2398):
 * two full O(N) linear scans over the per-typename backedges array to:
 *   1) detect exact duplicates (same caller + same type)
 *   2) find a type-equal entry for pointer sharing
 *
 * Each insertion is O(N); adding N backedges costs O(N²) total.
 * The TODO comment at gf.c:2379 confirms this is a known limitation.
 *
 * Fix: HashMap keyed on caller→Set<type> for O(1) dedup; identity-compare
 * replaces jl_types_equal for the pointer-sharing pass using jl_cache_type_().
 *
 * Real code (src/gf.c:2381-2398):
 *   for (i = 1; i < l; i += 2) {               // pass 1: dup check — O(N)
 *       if (entries[i] == caller &&
 *           jl_types_equal(entries[i-1], typ)) return;
 *   }
 *   for (i = 1; i < l; i += 2) {               // pass 2: ptr sharing — O(N)
 *       if (entries[i] != caller &&
 *           jl_types_equal(entries[i-1], typ)) { typ = entries[i-1]; break; }
 *   }
 */
public class JuliaBackedgeDedupTest {

    // Defective: O(N) per insertion (two linear scans)
    static long slowAddEdge(List<Object> backedges, Object typ, Object caller) {
        long ops = 0;
        int l = backedges.size();
        // Pass 1: exact dup check
        for (int i = 1; i < l; i += 2) {
            ops++;
            if (backedges.get(i) == caller && backedges.get(i - 1).equals(typ)) {
                return ops; // already recorded
            }
        }
        // Pass 2: type pointer sharing
        for (int i = 1; i < l; i += 2) {
            ops++;
            if (backedges.get(i) != caller && backedges.get(i - 1).equals(typ)) {
                typ = backedges.get(i - 1);
                break;
            }
        }
        backedges.add(typ);
        backedges.add(caller);
        return ops;
    }

    // Fixed: O(1) per insertion (hash dedup)
    static long fastAddEdge(List<Object> backedges,
                             Map<Object, Set<Object>> dedupIndex,
                             Map<Object, Object> typCache,
                             Object typ, Object caller) {
        long ops = 1;
        // Canonicalize type pointer
        typ = typCache.computeIfAbsent(typ, k -> k);
        // O(1) dup check
        if (dedupIndex.computeIfAbsent(caller, k -> new HashSet<>()).add(typ)) {
            backedges.add(typ);
            backedges.add(caller);
        }
        return ops;
    }

    static void bench(String label, Runnable slow, Runnable fast, long sOps, long fOps) {
        slow.run(); fast.run();
        long t0 = System.nanoTime(); slow.run(); long sMs = (System.nanoTime() - t0) / 1_000_000;
        long t1 = System.nanoTime(); fast.run(); long fMs = (System.nanoTime() - t1) / 1_000_000;
        double speedup = fMs > 0 ? (double) sMs / fMs : 0;
        System.out.printf("  %-60s  slow:%4dms (%,d ops)  fast:%4dms (%,d ops)  speedup:%.0fx%n",
                label, sMs, sOps, fMs, fOps, speedup);
    }

    static long runSlow(int N) {
        List<Object> backedges = new ArrayList<>();
        String caller = "callerA";
        long ops = 0;
        for (int i = 0; i < N; i++) {
            ops += slowAddEdge(backedges, "Type" + i, caller);
        }
        return ops;
    }

    static long runFast(int N) {
        List<Object> backedges = new ArrayList<>();
        Map<Object, Set<Object>> dedupIndex = new HashMap<>();
        Map<Object, Object> typCache = new HashMap<>();
        String caller = "callerA";
        long ops = 0;
        for (int i = 0; i < N; i++) {
            ops += fastAddEdge(backedges, dedupIndex, typCache, "Type" + i, caller);
        }
        return ops;
    }

    public static void main(String[] args) {
        System.out.println("JuliaBackedgeDedupTest -- julia-0003: _typename_add_backedge() O(N²) linear scan");
        System.out.println();
        System.out.println("  [backedge dedup: src/gf.c:2376-2398]");
        int[] cases = {100, 250, 500};
        for (int N : cases) {
            long sOps = (long) N * N;    // approx two passes each time
            long fOps = N;
            bench(
                String.format("N=%d backedge insertions (single caller)", N),
                () -> runSlow(N),
                () -> runFast(N),
                sOps, fOps
            );
        }
        System.out.println();
        System.out.println("Defect : src/gf.c:2381-2396 -- two O(N) scans per backedge insertion");
        System.out.println("Fix    : HashMap<caller, HashSet<typ>> for O(1) dedup; jl_cache_type_() for ptr sharing");
        System.out.println("Note   : TODO comment at gf.c:2379 explicitly flags this defect");
        System.out.println("Ticket : julia-0003-typename-backedge-dedup-linear-scan.md");
        System.out.println();

        int pass = 0;
        long s0 = runSlow(500), f0 = runFast(500);
        assert s0 > f0 * 50 : "julia-0003 expected >50x op ratio; slow=" + s0 + " fast=" + f0;
        pass++;
        System.out.printf("%d/1 PASS -- julia-0003: CWE-407 in Julia _typename_add_backedge() backedge dedup%n", pass);
        System.out.printf("Hotpath: called for every compilation of a method invoked on an abstract type%n");
        System.out.printf("Op ratio at N=500: slow=%,d  fast=%,d  ratio=%.0fx%n", s0, f0, (double) s0 / f0);
    }
}