java-topology/defects/janusgraph/unit/JanusGraphTest.java

package unit;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

/**
 * janusgraph-0001: MultiCondition extends ArrayList — O(C²) condition dedup
 *
 * Simulates JanusGraph's MultiCondition.contains() / QueryUtil.addConstraint()
 * pattern where conditions are stored in an ArrayList but membership is tested
 * with contains() before each add().
 *
 * Slow path: ArrayList-backed condition set (as in MultiCondition).
 * Fast path: HashSet-backed condition set (proposed fix).
 *
 * Each "condition" (PredicateCondition) is a unique Integer-keyed object.
 * We count equals() calls to measure O(C²) vs O(C) growth.
 */
public class JanusGraphTest {

    static int slowEqOps = 0;
    static int fastEqOps = 0;

    static class SlowCondition {
        final int id;
        SlowCondition(int id) { this.id = id; }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof SlowCondition)) return false;
            slowEqOps++;
            return this.id == ((SlowCondition) o).id;
        }

        @Override
        public int hashCode() {
            // Deliberately return constant to simulate broken hash — worst-case
            // for HashSet (though that's not what we're testing here; this tests
            // the ArrayList path which never uses hashCode).
            return 42;
        }
    }

    static class FastCondition {
        final int id;
        FastCondition(int id) { this.id = id; }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof FastCondition)) return false;
            fastEqOps++;
            return this.id == ((FastCondition) o).id;
        }

        @Override
        public int hashCode() {
            return id;  // proper hash — O(1) HashSet lookup
        }
    }

    /**
     * Defective path: ArrayList-backed MultiCondition.
     * addConstraint() pattern: if (!conditions.contains(pc)) conditions.add(pc)
     * O(i) scan for the i-th unique item => O(C^2) total.
     */
    static void slowPath(int n) {
        List<SlowCondition> conditions = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            SlowCondition pc = new SlowCondition(i);
            if (!conditions.contains(pc)) {
                conditions.add(pc);
            }
        }
        // Second pass: try adding duplicates (all present — full scan each time)
        for (int i = 0; i < n; i++) {
            SlowCondition pc = new SlowCondition(i);
            if (!conditions.contains(pc)) {
                conditions.add(pc);
            }
        }
    }

    /**
     * Fixed path: HashSet-backed condition set with preserved insertion order.
     * contains() is O(1) regardless of set size.
     */
    static void fastPath(int n) {
        Set<FastCondition> conditionSet = new LinkedHashSet<>();
        for (int i = 0; i < n; i++) {
            FastCondition pc = new FastCondition(i);
            conditionSet.add(pc);  // Set.add() deduplicates with O(1) contains check
        }
        // Second pass: duplicates — O(1) per add, idempotent
        for (int i = 0; i < n; i++) {
            conditionSet.add(new FastCondition(i));
        }
    }

    public static void main(String[] args) {
        int N = 400;
        int PASSES = 3;

        // Warm up
        slowPath(10);
        fastPath(10);
        slowEqOps = 0;
        fastEqOps = 0;

        // Measure
        for (int p = 0; p < PASSES; p++) {
            slowPath(N);
            fastPath(N);
        }

        // slow: first-pass adds N unique items, i-th add scans i existing => N*(N-1)/2
        //       second-pass each of N items scans full N => N*N
        //       per call total: ~1.5*N^2; for PASSES calls: ~1.5*N^2*PASSES
        long expectedSlowMin = (long)(N * N / 4);      // conservative lower bound
        // fast: proper hash, each add/lookup is O(1), ~0 equals() for distinct ids
        long expectedFastMax = (long)(N * PASSES * 4); // generous upper bound

        System.out.println("N=" + N + "  PASSES=" + PASSES);
        System.out.println("slow equals ops   : " + slowEqOps + " (expected >=" + expectedSlowMin + ")");
        System.out.println("fast equals ops   : " + fastEqOps + " (expected <=" + expectedFastMax + ")");

        int passed = 0;
        int total = 0;

        total++;
        if (slowEqOps >= expectedSlowMin) {
            System.out.println("PASS 1/" + total + ": slow path O(n^2) confirmed (ops=" + slowEqOps + " >= " + expectedSlowMin + ")");
            passed++;
        } else {
            System.out.println("FAIL 1/" + total + ": slow ops=" + slowEqOps + " < expected " + expectedSlowMin);
        }

        total++;
        if (fastEqOps <= expectedFastMax) {
            System.out.println("PASS 2/" + total + ": fast path O(1) confirmed (ops=" + fastEqOps + " <= " + expectedFastMax + ")");
            passed++;
        } else {
            System.out.println("FAIL 2/" + total + ": fast ops=" + fastEqOps + " > expected " + expectedFastMax);
        }

        total++;
        boolean ratioOk = fastEqOps == 0 || slowEqOps >= fastEqOps * 10;
        if (ratioOk) {
            System.out.println("PASS 3/" + total + ": speedup ratio slow/fast = " +
                (fastEqOps == 0 ? "inf" : (slowEqOps / fastEqOps)) + "x (expected >=10x)");
            passed++;
        } else {
            System.out.println("FAIL 3/" + total + ": ratio too small: slow=" + slowEqOps + " fast=" + fastEqOps);
        }

        System.out.println(passed + "/" + total + " PASS");
        if (passed != total) System.exit(1);
    }
}