251 lines
11 KiB
Java
251 lines
11 KiB
Java
package unit;
|
||
|
||
import java.util.*;
|
||
|
||
/**
|
||
* Unit test for opencv-0001: tvUpdateConfictMap O(C²×G) → O(C+G)
|
||
*
|
||
* Simulates OpenCV DNN TimVX graphConflictMap update (recursive DFS):
|
||
* Defective: std::find on vector<int> for conflict membership — O(C²×G)
|
||
* Fixed: unordered_set<int> membership — O(C+G)
|
||
*
|
||
* Compile: javac -d . TimVXConflictMapAlgorithm.java
|
||
* Run: java -ea unit.TimVXConflictMapAlgorithm
|
||
*/
|
||
public class TimVXConflictMapAlgorithm {
|
||
|
||
// Simplified DNN layer: list of consumer layer IDs
|
||
static class LayerData {
|
||
final int id;
|
||
final List<Integer> consumers;
|
||
LayerData(int id, List<Integer> consumers) {
|
||
this.id = id; this.consumers = consumers;
|
||
}
|
||
}
|
||
|
||
// ── defective implementation ──────────────────────────────────────────────
|
||
|
||
/** graphConflictMap: layerId → List<Integer> of conflicting graph indices */
|
||
static void defectiveUpdateConflictMap(
|
||
int graphIndex, LayerData ld,
|
||
Map<Integer, List<Integer>> graphConflictMap,
|
||
Map<Integer, LayerData> layers) {
|
||
if (ld.consumers.isEmpty()) return;
|
||
for (int cid : ld.consumers) {
|
||
List<Integer> conflicts = graphConflictMap.computeIfAbsent(cid, k -> new ArrayList<>());
|
||
// O(G) linear scan to check membership
|
||
boolean found = false;
|
||
for (int g : conflicts) { if (g == graphIndex) { found = true; break; } }
|
||
if (!found) {
|
||
conflicts.add(graphIndex);
|
||
defectiveUpdateConflictMap(graphIndex, layers.get(cid), graphConflictMap, layers);
|
||
}
|
||
}
|
||
}
|
||
|
||
static boolean defectiveIsConflict(int layerId, int graphIndex,
|
||
Map<Integer, List<Integer>> graphConflictMap) {
|
||
List<Integer> c = graphConflictMap.get(layerId);
|
||
if (c == null) return false;
|
||
for (int g : c) if (g == graphIndex) return true; // O(G) linear scan
|
||
return false;
|
||
}
|
||
|
||
// ── fixed implementation ──────────────────────────────────────────────────
|
||
|
||
/** graphConflictMap: layerId → Set<Integer> of conflicting graph indices */
|
||
static void fixedUpdateConflictMap(
|
||
int graphIndex, LayerData ld,
|
||
Map<Integer, Set<Integer>> graphConflictMap,
|
||
Map<Integer, LayerData> layers) {
|
||
if (ld.consumers.isEmpty()) return;
|
||
for (int cid : ld.consumers) {
|
||
Set<Integer> conflicts = graphConflictMap.computeIfAbsent(cid, k -> new HashSet<>());
|
||
if (conflicts.add(graphIndex)) { // O(1) insert + dedup
|
||
fixedUpdateConflictMap(graphIndex, layers.get(cid), graphConflictMap, layers);
|
||
}
|
||
}
|
||
}
|
||
|
||
static boolean fixedIsConflict(int layerId, int graphIndex,
|
||
Map<Integer, Set<Integer>> graphConflictMap) {
|
||
Set<Integer> c = graphConflictMap.get(layerId);
|
||
return c != null && c.contains(graphIndex); // O(1)
|
||
}
|
||
|
||
// ── helpers ───────────────────────────────────────────────────────────────
|
||
|
||
/** Build a linear chain: 0 → 1 → 2 → ... → n-1 */
|
||
static Map<Integer, LayerData> buildChain(int n) {
|
||
Map<Integer, LayerData> layers = new HashMap<>();
|
||
for (int i = 0; i < n; i++) {
|
||
List<Integer> consumers = (i + 1 < n) ? Arrays.asList(i + 1) : Collections.emptyList();
|
||
layers.put(i, new LayerData(i, consumers));
|
||
}
|
||
return layers;
|
||
}
|
||
|
||
/** Build a fan-out: layer 0 → layers 1..n-1 */
|
||
static Map<Integer, LayerData> buildFanOut(int n) {
|
||
Map<Integer, LayerData> layers = new HashMap<>();
|
||
List<Integer> consumers = new ArrayList<>();
|
||
for (int i = 1; i < n; i++) consumers.add(i);
|
||
layers.put(0, new LayerData(0, consumers));
|
||
for (int i = 1; i < n; i++) layers.put(i, new LayerData(i, Collections.emptyList()));
|
||
return layers;
|
||
}
|
||
|
||
// ── conflict map equivalence ──────────────────────────────────────────────
|
||
|
||
static boolean mapsEquivalent(Map<Integer, List<Integer>> defMap,
|
||
Map<Integer, Set<Integer>> fixMap) {
|
||
Set<Integer> keys = new HashSet<>();
|
||
keys.addAll(defMap.keySet());
|
||
keys.addAll(fixMap.keySet());
|
||
for (int k : keys) {
|
||
Set<Integer> dSet = new HashSet<>(defMap.getOrDefault(k, Collections.emptyList()));
|
||
Set<Integer> fSet = fixMap.getOrDefault(k, Collections.emptySet());
|
||
if (!dSet.equals(fSet)) return false;
|
||
}
|
||
return true;
|
||
}
|
||
|
||
// ── tests ─────────────────────────────────────────────────────────────────
|
||
|
||
static int pass = 0, total = 0;
|
||
|
||
static void assertTrue(String name, boolean cond) {
|
||
total++;
|
||
if (cond) { pass++; System.out.println("PASS " + name); }
|
||
else System.out.println("FAIL " + name);
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
// Test 1: single layer no consumers → no conflict propagation
|
||
{
|
||
Map<Integer, LayerData> layers = new HashMap<>();
|
||
layers.put(0, new LayerData(0, Collections.emptyList()));
|
||
Map<Integer, List<Integer>> defMap = new HashMap<>();
|
||
Map<Integer, Set<Integer>> fixMap = new HashMap<>();
|
||
defectiveUpdateConflictMap(0, layers.get(0), defMap, layers);
|
||
fixedUpdateConflictMap(0, layers.get(0), fixMap, layers);
|
||
assertTrue("no-consumer-defective", defMap.isEmpty());
|
||
assertTrue("no-consumer-fixed", fixMap.isEmpty());
|
||
}
|
||
|
||
// Test 2: chain of 5 layers — graph 0 propagates to all
|
||
{
|
||
int N = 5;
|
||
Map<Integer, LayerData> layers = buildChain(N);
|
||
Map<Integer, List<Integer>> defMap = new HashMap<>();
|
||
Map<Integer, Set<Integer>> fixMap = new HashMap<>();
|
||
defectiveUpdateConflictMap(0, layers.get(0), defMap, layers);
|
||
fixedUpdateConflictMap(0, layers.get(0), fixMap, layers);
|
||
// Layers 1..4 should all have graphIndex=0 in their conflict set
|
||
boolean defOk = true, fixOk = true;
|
||
for (int i = 1; i < N; i++) {
|
||
defOk &= defectiveIsConflict(i, 0, defMap);
|
||
fixOk &= fixedIsConflict(i, 0, fixMap);
|
||
}
|
||
assertTrue("chain-defective", defOk);
|
||
assertTrue("chain-fixed", fixOk);
|
||
assertTrue("chain-equiv", mapsEquivalent(defMap, fixMap));
|
||
}
|
||
|
||
// Test 3: fan-out — graph 1 propagates to all leaves
|
||
{
|
||
int N = 10;
|
||
Map<Integer, LayerData> layers = buildFanOut(N);
|
||
Map<Integer, List<Integer>> defMap = new HashMap<>();
|
||
Map<Integer, Set<Integer>> fixMap = new HashMap<>();
|
||
defectiveUpdateConflictMap(1, layers.get(0), defMap, layers);
|
||
fixedUpdateConflictMap(1, layers.get(0), fixMap, layers);
|
||
boolean defOk = true, fixOk = true;
|
||
for (int i = 1; i < N; i++) {
|
||
defOk &= defectiveIsConflict(i, 1, defMap);
|
||
fixOk &= fixedIsConflict(i, 1, fixMap);
|
||
}
|
||
assertTrue("fanout-defective", defOk);
|
||
assertTrue("fanout-fixed", fixOk);
|
||
assertTrue("fanout-equiv", mapsEquivalent(defMap, fixMap));
|
||
}
|
||
|
||
// Test 4: multiple graphs — no double-insertion
|
||
{
|
||
Map<Integer, LayerData> layers = buildChain(4);
|
||
Map<Integer, List<Integer>> defMap = new HashMap<>();
|
||
Map<Integer, Set<Integer>> fixMap = new HashMap<>();
|
||
// Propagate graph 0 twice — should not double-insert
|
||
defectiveUpdateConflictMap(0, layers.get(0), defMap, layers);
|
||
defectiveUpdateConflictMap(0, layers.get(0), defMap, layers);
|
||
fixedUpdateConflictMap(0, layers.get(0), fixMap, layers);
|
||
fixedUpdateConflictMap(0, layers.get(0), fixMap, layers);
|
||
// Each layer should have exactly one entry for graphIndex=0
|
||
boolean defOk = true;
|
||
for (List<Integer> c : defMap.values()) {
|
||
int cnt = 0; for (int g : c) if (g == 0) cnt++;
|
||
if (cnt != 1) defOk = false;
|
||
}
|
||
boolean fixOk = true;
|
||
for (Set<Integer> c : fixMap.values()) fixOk &= c.contains(0);
|
||
assertTrue("no-double-insert-defective", defOk);
|
||
assertTrue("no-double-insert-fixed", fixOk);
|
||
}
|
||
|
||
// Test 5: isConflict — false for non-propagated graph
|
||
{
|
||
Map<Integer, LayerData> layers = buildChain(3);
|
||
Map<Integer, List<Integer>> defMap = new HashMap<>();
|
||
Map<Integer, Set<Integer>> fixMap = new HashMap<>();
|
||
defectiveUpdateConflictMap(5, layers.get(0), defMap, layers);
|
||
fixedUpdateConflictMap(5, layers.get(0), fixMap, layers);
|
||
assertTrue("not-conflict-defective", !defectiveIsConflict(1, 99, defMap));
|
||
assertTrue("not-conflict-fixed", !fixedIsConflict(1, 99, fixMap));
|
||
}
|
||
|
||
// Test 6: performance — isConflict() called in a tight loop simulating inference
|
||
// Builds a conflict map with G=500 graphs per layer, then calls isConflict G*L times.
|
||
// This isolates the O(G) vs O(1) membership check.
|
||
{
|
||
int G = 500; // graphs
|
||
int L = 100; // layers
|
||
Map<Integer, List<Integer>> defMap = new HashMap<>();
|
||
Map<Integer, Set<Integer>> fixMap = new HashMap<>();
|
||
for (int layer = 0; layer < L; layer++) {
|
||
List<Integer> conflicts = new ArrayList<>();
|
||
Set<Integer> conflictSet = new HashSet<>();
|
||
for (int g = 0; g < G; g++) {
|
||
conflicts.add(g);
|
||
conflictSet.add(g);
|
||
}
|
||
defMap.put(layer, conflicts);
|
||
fixMap.put(layer, conflictSet);
|
||
}
|
||
|
||
long t0 = System.nanoTime();
|
||
int defHits = 0;
|
||
for (int r = 0; r < 20; r++)
|
||
for (int layer = 0; layer < L; layer++)
|
||
for (int g = 0; g < G; g++)
|
||
if (defectiveIsConflict(layer, g, defMap)) defHits++;
|
||
long tDef = System.nanoTime() - t0;
|
||
|
||
t0 = System.nanoTime();
|
||
int fixHits = 0;
|
||
for (int r = 0; r < 20; r++)
|
||
for (int layer = 0; layer < L; layer++)
|
||
for (int g = 0; g < G; g++)
|
||
if (fixedIsConflict(layer, g, fixMap)) fixHits++;
|
||
long tFix = System.nanoTime() - t0;
|
||
|
||
double ratio = (double) tDef / tFix;
|
||
System.out.printf(" Perf isConflict L=%d G=%d: defective=%.1fms fixed=%.1fms ratio=%.1fx%n",
|
||
L, G, tDef / 1e6, tFix / 1e6, ratio);
|
||
assertTrue("perf-hits-match", defHits == fixHits);
|
||
assertTrue("perf-speedup", ratio > 3.0);
|
||
}
|
||
|
||
System.out.println(pass + "/" + total + " PASS");
|
||
assert pass == total : pass + "/" + total + " passed";
|
||
}
|
||
}
|