java-topology/defects/aria2-0001/test/Aria2DhtPeerAnnounceTest.java

import java.util.*;

/**
 * Unit test for aria2-0001: DHTPeerAnnounceEntry::addPeerAddrEntry peerAddrEntries_ O(P^2) scan.
 *
 * aria2's DHT layer maintains a per-infohash list of peers that have announced themselves via
 * DHT GET_PEERS. For each new announce, addPeerAddrEntry() scans the entire peerAddrEntries_
 * vector with std::find to check if the (ip, port) pair is already known:
 *
 *   auto i = std::find(peerAddrEntries_.begin(), peerAddrEntries_.end(), entry);
 *   if (i == peerAddrEntries_.end()) peerAddrEntries_.push_back(entry);
 *   else (*i).notifyUpdate();
 *
 * std::find on std::vector<PeerAddrEntry> is O(P) where P = current number of peers.
 * Inserting P unique peers costs O(1)+O(2)+...+O(P) = O(P^2) total.
 * There is no cap on peerAddrEntries_ size, so P grows freely during a download session.
 *
 * Fix: replace vector + std::find with std::unordered_map<string, PeerAddrEntry>
 * keyed by "ip:port". addPeerAddrEntry becomes O(1) amortized.
 *
 * This test models the pattern in Java using ArrayList.contains vs HashMap.containsKey:
 *   - Defect: ArrayList.contains(entry) before add  → O(P^2) total
 *   - Fix:    HashMap.put(key, entry)               → O(P) amortized total
 */
public class Aria2DhtPeerAnnounceTest {

    static final class PeerKey {
        final String ip;
        final int port;

        PeerKey(String ip, int port) { this.ip = ip; this.port = port; }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof PeerKey)) return false;
            PeerKey p = (PeerKey) o;
            return port == p.port && ip.equals(p.ip);
        }

        @Override
        public int hashCode() { return Objects.hash(ip, port); }
    }

    // --- Defect: vector + std::find equivalent ---
    // Simulates: for each peer, scan entire list for (ip==entry.ip && port==entry.port)
    static int buildDefect(List<PeerKey> incomingPeers) {
        List<PeerKey> stored = new ArrayList<>();
        for (PeerKey entry : incomingPeers) {
            if (!stored.contains(entry)) {   // O(|stored|) — the defect
                stored.add(entry);
            }
            // else: update timestamp (omitted, same cost path)
        }
        return stored.size();
    }

    // --- Fix: unordered_map equivalent ---
    static int buildFixed(List<PeerKey> incomingPeers) {
        Set<PeerKey> stored = new HashSet<>();
        for (PeerKey entry : incomingPeers) {
            stored.add(entry);               // O(1) amortized — the fix
        }
        return stored.size();
    }

    /** Build P unique PeerKey objects simulating distinct IP:port announcers. */
    static List<PeerKey> buildPeers(int P) {
        List<PeerKey> peers = new ArrayList<>(P);
        for (int i = 0; i < P; i++) {
            String ip = "10." + ((i >> 16) & 0xFF) + "." + ((i >> 8) & 0xFF) + "." + (i & 0xFF);
            peers.add(new PeerKey(ip, 6881 + (i % 10000)));
        }
        return peers;
    }

    public static void main(String[] args) {
        // --- Correctness check ---
        int smallP = 20;
        List<PeerKey> smallPeers = buildPeers(smallP);
        int defectSize = buildDefect(smallPeers);
        int fixedSize  = buildFixed(smallPeers);
        assert defectSize == smallP : "Defect: expected " + smallP + " peers, got " + defectSize;
        assert fixedSize  == smallP : "Fixed:  expected " + smallP + " peers, got " + fixedSize;
        System.out.println("Correctness OK: P=" + smallP
                + " defect.size=" + defectSize + " fixed.size=" + fixedSize);

        // --- Performance benchmark ---
        // P=3000 peers (popular torrent with active DHT swarm).
        // Each peer announces once. Total cost: defect=O(P^2)=9M comparisons, fix=O(P)=3000.
        int P = 3000;
        int reps = 20;
        List<PeerKey> peers = buildPeers(P);

        // Correctness at full scale
        assert buildDefect(peers) == P : "Full-scale correctness: defect size mismatch";
        assert buildFixed(peers)  == P : "Full-scale correctness: fixed size mismatch";

        // Warmup
        for (int w = 0; w < 3; w++) {
            buildDefect(peers);
            buildFixed(peers);
        }

        long t0 = System.nanoTime();
        for (int r = 0; r < reps; r++) buildDefect(peers);
        long defectNs = System.nanoTime() - t0;

        long t1 = System.nanoTime();
        for (int r = 0; r < reps; r++) buildFixed(peers);
        long fixedNs = System.nanoTime() - t1;

        double ratio = (double) defectNs / fixedNs;
        System.out.printf("DHT peer announce dedup: P=%d peers reps=%d%n", P, reps);
        System.out.printf("  Defect (ArrayList.contains O(P^2)): %,d ns%n", defectNs);
        System.out.printf("  Fix    (HashSet.add     O(P)):      %,d ns%n", fixedNs);
        System.out.printf("  speedup: %.1fx%n", ratio);

        assert ratio > 3.0 : "Expected >3x speedup, got " + ratio;
        System.out.println("PASS");
    }
}