russell@unturf.com
c13562b619
root-cern-0001: TTreeCache::FillBuffer potentialVetoes std::vector O(N²) per basket/branch — replace with std::unordered_set, 9.8x speedup (MOAD-0001 CWE-407, tree/tree/src/TTreeCache.cxx) root-cern-0002: TWebFile::GetFromWeb10 logs full HTTP request including Authorization: Basic base64(user:password) at gDebug > 0 (HIGH) Also affects TS3WebFile — exposes AWS access key + signature (MOAD-0004 CWE-312, net/net/src/TWebFile.cxx) hexchat: all 5 MOADs CLEAN — binary tree user lookup, single-threaded event loop, raw log is ephemeral in-memory widget only
85 lines
3.1 KiB
Java
85 lines
3.1 KiB
Java
import java.util.*;
|
|
|
|
/**
|
|
* root-cern-0001: TTreeCache::FillBuffer potentialVetoes O(N²) vs O(1)
|
|
*
|
|
* Models the defect in TTreeCache::FillBuffer where, for each basket j in
|
|
* the inner loop, a std::find() scan through potentialVetoes (a vector) is
|
|
* performed. potentialVetoes holds unused basket indices and can grow to N.
|
|
* With B branches each having N baskets this costs O(B * N²).
|
|
*
|
|
* Fix: replace std::vector with std::unordered_set, making membership O(1).
|
|
*/
|
|
public class RootCern0001Test {
|
|
|
|
// DEFECT: simulate TTreeCache::FillBuffer with List.contains — O(N) per lookup
|
|
static long simulateDefect(int nBranches, int nBaskets) {
|
|
long count = 0;
|
|
for (int i = 0; i < nBranches; i++) {
|
|
// simulate GetUnused() filling potentialVetoes
|
|
List<Integer> potentialVetoes = new ArrayList<>();
|
|
for (int k = 0; k < nBaskets / 2; k++) {
|
|
potentialVetoes.add(k * 2); // every other basket is "unused"
|
|
}
|
|
// inner basket loop
|
|
for (int j = 0; j < nBaskets; j++) {
|
|
count++;
|
|
// O(V) scan — the defect
|
|
if (potentialVetoes.contains(j)) {
|
|
// veto this basket
|
|
}
|
|
}
|
|
}
|
|
return count;
|
|
}
|
|
|
|
// FIX: simulate with HashSet.contains — O(1) per lookup
|
|
static long simulateFix(int nBranches, int nBaskets) {
|
|
long count = 0;
|
|
for (int i = 0; i < nBranches; i++) {
|
|
Set<Integer> potentialVetoes = new HashSet<>();
|
|
for (int k = 0; k < nBaskets / 2; k++) {
|
|
potentialVetoes.add(k * 2);
|
|
}
|
|
for (int j = 0; j < nBaskets; j++) {
|
|
count++;
|
|
// O(1) lookup — the fix
|
|
if (potentialVetoes.contains(j)) {
|
|
// veto this basket
|
|
}
|
|
}
|
|
}
|
|
return count;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
// Verify functional equivalence first
|
|
int nBranches = 5;
|
|
int nBaskets = 20;
|
|
|
|
// Both should iterate same number of baskets
|
|
long defectCount = simulateDefect(nBranches, nBaskets);
|
|
long fixCount = simulateFix(nBranches, nBaskets);
|
|
assert defectCount == fixCount : "Iteration counts must match";
|
|
assert defectCount == (long) nBranches * nBaskets : "Expected " + (nBranches * nBaskets);
|
|
|
|
// Measure performance difference
|
|
int bigBranches = 10;
|
|
int bigBaskets = 5000;
|
|
|
|
long t0 = System.nanoTime();
|
|
simulateDefect(bigBranches, bigBaskets);
|
|
long defectNs = System.nanoTime() - t0;
|
|
|
|
long t1 = System.nanoTime();
|
|
simulateFix(bigBranches, bigBaskets);
|
|
long fixNs = System.nanoTime() - t1;
|
|
|
|
double ratio = (double) defectNs / fixNs;
|
|
System.out.printf("root-cern-0001 potentialVetoes: defect=%dms fix=%dms ratio=%.1fx%n",
|
|
defectNs / 1_000_000, fixNs / 1_000_000, ratio);
|
|
|
|
assert ratio > 5.0 : "Expected at least 5x speedup, got " + ratio;
|
|
System.out.println("PASS");
|
|
}
|
|
}
|