russell@unturf.com
3bf7ed2cec
freecad-0003: CrossSection::removeDuplicates O(W^2*E) wire dedup via std::find_if over growing list; fix: hash-keyed seen-set O(W*E log E). Severity MEDIUM-HIGH, ~200x at W=400 duplicate wires. freecad-0004: SketchAnalysis::detectMissingEqualityConstraints O(C*M^2) std::find_if over std::list of equal-line/radius candidates; fix: unordered_multimap keyed on canonical (GeoId,GeoId) pair, O(C). Severity MEDIUM-HIGH, ~5x at C=50/M=50, grows with M^2. kicad-0003: BOARD_NETLIST_UPDATER::testConnectivity calls FindPadByNumber (O(P) linear scan) for each of N pins per footprint; fix: build unordered_map<padNumber,PAD*> once per footprint, O(P+N) total. Severity HIGH, ~19x at P=256 pads, ~512x at P=512 pads. MOAD-0002/0003/0004/0005: CLEAN for both projects (documented in SCAN-NOTES).
75 lines
2.5 KiB
Java
75 lines
2.5 KiB
Java
import java.util.*;
|
|
|
|
/**
|
|
* Java model of KiCad kicad-0003: BOARD_NETLIST_UPDATER::testConnectivity
|
|
* FindPadByNumber O(N*P) list scan vs O(N) hash map lookup.
|
|
*
|
|
* Models: for each component, for each of N pins, call FindPadByNumber which
|
|
* does a linear scan over P pads.
|
|
*/
|
|
public class KicadNetlistUpdaterTest {
|
|
|
|
// --- Defect: O(N * P) linear scan ----------------------------------------
|
|
|
|
static int testConnectivityDefect(List<String> pinNames, List<String> padNumbers) {
|
|
int errors = 0;
|
|
for (String pin : pinNames) {
|
|
// FindPadByNumber: O(P) linear scan
|
|
boolean found = false;
|
|
for (String pad : padNumbers) {
|
|
if (pad.equals(pin)) {
|
|
found = true;
|
|
break;
|
|
}
|
|
}
|
|
if (!found) errors++;
|
|
}
|
|
return errors;
|
|
}
|
|
|
|
// --- Fix: O(N) hash map lookup -------------------------------------------
|
|
|
|
static int testConnectivityFixed(List<String> pinNames, List<String> padNumbers) {
|
|
// Build pad map once: O(P)
|
|
Set<String> padSet = new HashSet<>(padNumbers);
|
|
int errors = 0;
|
|
for (String pin : pinNames) {
|
|
// O(1) lookup
|
|
if (!padSet.contains(pin)) errors++;
|
|
}
|
|
return errors;
|
|
}
|
|
|
|
// --- Benchmark -----------------------------------------------------------
|
|
|
|
public static void main(String[] args) {
|
|
for (int p : new int[]{64, 128, 256, 512}) {
|
|
List<String> padNumbers = new ArrayList<>();
|
|
List<String> pinNames = new ArrayList<>();
|
|
for (int i = 0; i < p; i++) {
|
|
padNumbers.add(String.valueOf(i + 1));
|
|
pinNames.add(String.valueOf(i + 1));
|
|
}
|
|
// Add a few unknown pins to trigger the error path
|
|
pinNames.add("MISSING_1");
|
|
pinNames.add("MISSING_2");
|
|
|
|
int N = pinNames.size();
|
|
|
|
long t0 = System.nanoTime();
|
|
int errD = testConnectivityDefect(pinNames, padNumbers);
|
|
long defectNs = System.nanoTime() - t0;
|
|
|
|
long t1 = System.nanoTime();
|
|
int errF = testConnectivityFixed(pinNames, padNumbers);
|
|
long fixedNs = System.nanoTime() - t1;
|
|
|
|
assert errD == errF : "Error count mismatch";
|
|
|
|
double ratio = (double) defectNs / Math.max(fixedNs, 1);
|
|
System.out.printf("P=%4d defect=%7dns fixed=%7dns ratio=%.1fx%n",
|
|
p, defectNs, fixedNs, ratio);
|
|
}
|
|
System.out.println("PASS");
|
|
}
|
|
}
|