194 lines
8 KiB
Java
194 lines
8 KiB
Java
package unit;
|
||
import java.util.*;
|
||
|
||
/**
|
||
* DendriteTest — CWE-407 benchmark for dendrite-0001 and dendrite-0002
|
||
*
|
||
* dendrite-0001: syncapi/storage/shared/storage_consumer.go
|
||
* Double loop over prevEventIDs × fetched events to find backward extremities.
|
||
* Slow: O(P × E) nested loop per WriteEvent call
|
||
* Fast: O(P + E) — pre-build map of fetched event IDs, then single pass
|
||
*
|
||
* dendrite-0002: roomserver/internal/perform/perform_backfill.go
|
||
* Nested loop over bwExtrems (map[sucID][]prevEventIDs) to find successor of eventID.
|
||
* Slow: O(E × P) nested scan
|
||
* Fast: O(1) after pre-building reverse map prevEventID → sucID (O(E × P) to build, amortised O(1) per lookup)
|
||
* In practice the map is built once per backfill batch, called N times.
|
||
*
|
||
* compile: javac -d . DendriteTest.java && java -ea unit.DendriteTest
|
||
*/
|
||
public class DendriteTest {
|
||
|
||
static void bench(String label, Runnable slow, Runnable fast, long sOps, long fOps) {
|
||
slow.run(); fast.run(); // warmup
|
||
long t0 = System.nanoTime(); slow.run(); long sMs = (System.nanoTime() - t0) / 1_000_000;
|
||
long t1 = System.nanoTime(); fast.run(); long fMs = (System.nanoTime() - t1) / 1_000_000;
|
||
double ratio = fOps > 0 ? (double) sOps / fOps : 0;
|
||
System.out.printf(" %-60s slow:%4dms (%,d ops) fast:%4dms (%,d ops) speedup:%.0fx%n",
|
||
label, sMs, sOps, fMs, fOps, ratio);
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// dendrite-0001: prevEvents double-loop vs map lookup
|
||
// -----------------------------------------------------------------------
|
||
|
||
/** Slow: O(P*E) — nested loop per WriteEvent call, repeated eventsWritten times */
|
||
static long slowPrevEventsCheck(int prevCount, int fetchedCount, int eventsWritten) {
|
||
long ops = 0;
|
||
for (int w = 0; w < eventsWritten; w++) {
|
||
List<String> prevEventIDs = new ArrayList<>();
|
||
for (int i = 0; i < prevCount; i++) prevEventIDs.add("prev-" + i);
|
||
List<String> fetched = new ArrayList<>();
|
||
// half the prev events are found in DB
|
||
for (int i = 0; i < fetchedCount; i++) fetched.add("prev-" + (i * 2));
|
||
|
||
for (String eID : prevEventIDs) {
|
||
for (String prevEv : fetched) {
|
||
ops++;
|
||
if (eID.equals(prevEv)) break;
|
||
}
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/** Fast: O(P+E) per WriteEvent — build map once, then O(1) per prevEventID lookup */
|
||
static long fastPrevEventsCheck(int prevCount, int fetchedCount, int eventsWritten) {
|
||
long ops = 0;
|
||
for (int w = 0; w < eventsWritten; w++) {
|
||
List<String> prevEventIDs = new ArrayList<>();
|
||
for (int i = 0; i < prevCount; i++) prevEventIDs.add("prev-" + i);
|
||
List<String> fetched = new ArrayList<>();
|
||
for (int i = 0; i < fetchedCount; i++) fetched.add("prev-" + (i * 2));
|
||
|
||
// Build set: O(E)
|
||
Set<String> prevSet = new HashSet<>(fetched);
|
||
ops += fetched.size();
|
||
|
||
// Look up each prevEventID: O(P) × O(1) each
|
||
for (String eID : prevEventIDs) {
|
||
ops += 1;
|
||
prevSet.contains(eID); // O(1)
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
// -----------------------------------------------------------------------
|
||
// dendrite-0002: bwExtrems nested loop vs reverse map
|
||
// -----------------------------------------------------------------------
|
||
|
||
/** Slow: O(E * P) scan for each lookup call */
|
||
static long slowServersAtEvent(int numExtrems, int prevPerExtrem, int lookups) {
|
||
// bwExtrems: sucID -> []prevEventIDs
|
||
Map<String, List<String>> bwExtrems = new LinkedHashMap<>();
|
||
for (int e = 0; e < numExtrems; e++) {
|
||
List<String> prevs = new ArrayList<>();
|
||
for (int p = 0; p < prevPerExtrem; p++) prevs.add("prev-" + e + "-" + p);
|
||
bwExtrems.put("suc-" + e, prevs);
|
||
}
|
||
// The target event is in the last extremity (worst case)
|
||
String targetEvent = "prev-" + (numExtrems - 1) + "-" + (prevPerExtrem - 1);
|
||
|
||
long ops = 0;
|
||
for (int q = 0; q < lookups; q++) {
|
||
String found = null;
|
||
outer:
|
||
for (Map.Entry<String, List<String>> entry : bwExtrems.entrySet()) {
|
||
for (String pe : entry.getValue()) {
|
||
ops++;
|
||
if (pe.equals(targetEvent)) {
|
||
found = entry.getKey();
|
||
break outer;
|
||
}
|
||
}
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/** Fast: build reverse map once (O(E*P)), then O(1) per lookup */
|
||
static long fastServersAtEvent(int numExtrems, int prevPerExtrem, int lookups) {
|
||
Map<String, List<String>> bwExtrems = new LinkedHashMap<>();
|
||
for (int e = 0; e < numExtrems; e++) {
|
||
List<String> prevs = new ArrayList<>();
|
||
for (int p = 0; p < prevPerExtrem; p++) prevs.add("prev-" + e + "-" + p);
|
||
bwExtrems.put("suc-" + e, prevs);
|
||
}
|
||
String targetEvent = "prev-" + (numExtrems - 1) + "-" + (prevPerExtrem - 1);
|
||
|
||
// Build reverse map: O(E*P) once
|
||
Map<String, String> prevToSuccessor = new HashMap<>();
|
||
long ops = 0;
|
||
for (Map.Entry<String, List<String>> entry : bwExtrems.entrySet()) {
|
||
for (String pe : entry.getValue()) {
|
||
prevToSuccessor.put(pe, entry.getKey());
|
||
ops++;
|
||
}
|
||
}
|
||
|
||
// Each lookup: O(1)
|
||
for (int q = 0; q < lookups; q++) {
|
||
ops += 1;
|
||
prevToSuccessor.get(targetEvent);
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
System.out.println("DendriteTest — CWE-407 benchmarks");
|
||
System.out.println();
|
||
|
||
int passed = 0;
|
||
int total = 0;
|
||
|
||
// --- dendrite-0001 ---
|
||
int PREV = 50;
|
||
int FETCHED = 50;
|
||
int EVENTS = 1000;
|
||
|
||
long[] sOps1 = {0}, fOps1 = {0};
|
||
Runnable s1 = () -> sOps1[0] = slowPrevEventsCheck(PREV, FETCHED, EVENTS);
|
||
Runnable f1 = () -> fOps1[0] = fastPrevEventsCheck(PREV, FETCHED, EVENTS);
|
||
|
||
sOps1[0] = slowPrevEventsCheck(PREV, FETCHED, EVENTS);
|
||
fOps1[0] = fastPrevEventsCheck(PREV, FETCHED, EVENTS);
|
||
bench("dendrite-0001 prevEvents double-loop vs map (P=" + PREV + " E=" + FETCHED + " writes=" + EVENTS + ")",
|
||
s1, f1, sOps1[0], fOps1[0]);
|
||
|
||
total++;
|
||
if (sOps1[0] > fOps1[0] * 5L) {
|
||
System.out.println(" dendrite-0001 PASS (slow=" + sOps1[0] + " > 5x fast=" + fOps1[0] + ")");
|
||
passed++;
|
||
} else {
|
||
System.out.println(" dendrite-0001 FAIL (slow=" + sOps1[0] + " fast=" + fOps1[0] + ")");
|
||
}
|
||
assert sOps1[0] > fOps1[0] * 5L : "dendrite-0001: slow ops not 5x fast ops";
|
||
|
||
// --- dendrite-0002 ---
|
||
int EXTREMS = 200;
|
||
int PREV_PER = 20;
|
||
int LOOKUPS = 500;
|
||
|
||
long[] sOps2 = {0}, fOps2 = {0};
|
||
Runnable s2 = () -> sOps2[0] = slowServersAtEvent(EXTREMS, PREV_PER, LOOKUPS);
|
||
Runnable f2 = () -> fOps2[0] = fastServersAtEvent(EXTREMS, PREV_PER, LOOKUPS);
|
||
|
||
sOps2[0] = slowServersAtEvent(EXTREMS, PREV_PER, LOOKUPS);
|
||
fOps2[0] = fastServersAtEvent(EXTREMS, PREV_PER, LOOKUPS);
|
||
bench("dendrite-0002 bwExtrems nested loop vs reverse map (E=" + EXTREMS + " P=" + PREV_PER + " lookups=" + LOOKUPS + ")",
|
||
s2, f2, sOps2[0], fOps2[0]);
|
||
|
||
total++;
|
||
if (sOps2[0] > fOps2[0] * 10L) {
|
||
System.out.println(" dendrite-0002 PASS (slow=" + sOps2[0] + " > 10x fast=" + fOps2[0] + ")");
|
||
passed++;
|
||
} else {
|
||
System.out.println(" dendrite-0002 FAIL (slow=" + sOps2[0] + " fast=" + fOps2[0] + ")");
|
||
}
|
||
assert sOps2[0] > fOps2[0] * 10L : "dendrite-0002: slow ops not 10x fast ops";
|
||
|
||
System.out.println();
|
||
System.out.println(passed + "/" + total + " PASS");
|
||
}
|
||
}
|