260 lines
9.6 KiB
Java
260 lines
9.6 KiB
Java
package unit;
|
||
|
||
import java.util.ArrayList;
|
||
import java.util.HashMap;
|
||
import java.util.List;
|
||
|
||
/**
|
||
* haproxy-0003: flt_spoe.c spoe_check_config O(P×M), O(P×G), O(G×P×M) nested resolution.
|
||
*
|
||
* Models placeholder-to-message and group resolution using nested list walks (SLOW)
|
||
* vs ebtree/HashMap-based O(log N) or O(1) lookup (FAST).
|
||
*
|
||
* Run: javac HaproxySpoeCheckConfigAlgorithmTest.java && java unit.HaproxySpoeCheckConfigAlgorithmTest
|
||
*/
|
||
public class HaproxySpoeCheckConfigAlgorithmTest {
|
||
|
||
// --- Data structures mirroring SPOE config objects ---
|
||
|
||
static class SpoeMessage {
|
||
String id;
|
||
String group; // resolved group name (null initially)
|
||
SpoeMessage(String id) { this.id = id; }
|
||
}
|
||
|
||
static class SpoeGroup {
|
||
String id;
|
||
List<String> phIds; // placeholder message ids
|
||
List<SpoeMessage> messages = new ArrayList<>();
|
||
SpoeGroup(String id, List<String> phIds) {
|
||
this.id = id;
|
||
this.phIds = phIds;
|
||
}
|
||
}
|
||
|
||
// -------------------------------------------------------
|
||
|
||
static long slowOps = 0;
|
||
static long fastOps = 0;
|
||
|
||
/**
|
||
* SLOW Pattern 1: O(P×M) — placeholder-to-message resolution.
|
||
* mirrors lines ~2407–2504 in spoe_check_config.
|
||
*/
|
||
static int[] resolvePlaceholdersSlow(List<String> placeholderIds, List<SpoeMessage> messages) {
|
||
int[] result = new int[placeholderIds.size()];
|
||
for (int p = 0; p < placeholderIds.size(); p++) { // outer: P
|
||
result[p] = -1;
|
||
for (int m = 0; m < messages.size(); m++) { // inner: M
|
||
slowOps++;
|
||
if (placeholderIds.get(p).equals(messages.get(m).id)) {
|
||
result[p] = m;
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
return result;
|
||
}
|
||
|
||
/**
|
||
* FAST Pattern 1: O(P + M) — build HashMap from messages, then O(1) per placeholder.
|
||
* mirrors the ebtst fix.
|
||
*/
|
||
static int[] resolvePlaceholdersFast(List<String> placeholderIds, List<SpoeMessage> messages) {
|
||
HashMap<String, Integer> msgMap = new HashMap<>(messages.size() * 2);
|
||
for (int m = 0; m < messages.size(); m++) {
|
||
fastOps++;
|
||
msgMap.put(messages.get(m).id, m);
|
||
}
|
||
int[] result = new int[placeholderIds.size()];
|
||
for (int p = 0; p < placeholderIds.size(); p++) {
|
||
fastOps++;
|
||
Integer idx = msgMap.get(placeholderIds.get(p));
|
||
result[p] = (idx != null) ? idx : -1;
|
||
}
|
||
return result;
|
||
}
|
||
|
||
/**
|
||
* SLOW Pattern 3: O(G×P×M) — group message assignment.
|
||
* mirrors lines ~2526–2553 in spoe_check_config.
|
||
*/
|
||
static int slowTripleResolution(List<SpoeGroup> groups, List<SpoeMessage> messages) {
|
||
int assigned = 0;
|
||
for (SpoeGroup grp : groups) { // outer: G
|
||
for (String phId : grp.phIds) { // mid: P per group
|
||
for (SpoeMessage msg : messages) { // inner: M
|
||
slowOps++;
|
||
if (phId.equals(msg.id)) {
|
||
grp.messages.add(msg);
|
||
assigned++;
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
}
|
||
return assigned;
|
||
}
|
||
|
||
/**
|
||
* FAST Pattern 3: O((G×P) + M) — HashMap for messages.
|
||
*/
|
||
static int fastTripleResolution(List<SpoeGroup> groups, List<SpoeMessage> messages) {
|
||
// Build message map once: O(M)
|
||
HashMap<String, SpoeMessage> msgMap = new HashMap<>(messages.size() * 2);
|
||
for (SpoeMessage msg : messages) {
|
||
fastOps++;
|
||
msgMap.put(msg.id, msg);
|
||
}
|
||
int assigned = 0;
|
||
for (SpoeGroup grp : groups) { // outer: G
|
||
for (String phId : grp.phIds) { // inner: P per group
|
||
fastOps++;
|
||
SpoeMessage msg = msgMap.get(phId);
|
||
if (msg != null) {
|
||
grp.messages.add(msg);
|
||
assigned++;
|
||
}
|
||
}
|
||
}
|
||
return assigned;
|
||
}
|
||
|
||
// --- Test helpers ---
|
||
|
||
static List<SpoeMessage> makeMessages(int count) {
|
||
List<SpoeMessage> msgs = new ArrayList<>(count);
|
||
for (int i = 0; i < count; i++) msgs.add(new SpoeMessage("msg_" + i));
|
||
return msgs;
|
||
}
|
||
|
||
/**
|
||
* Build placeholders that reference messages near the END of the message list,
|
||
* forcing worst-case O(M) inner scan in the SLOW path.
|
||
*/
|
||
static List<String> makePlaceholders(int count) {
|
||
List<String> phs = new ArrayList<>(count);
|
||
for (int i = 0; i < count; i++) phs.add("msg_" + i);
|
||
return phs;
|
||
}
|
||
|
||
/**
|
||
* Build worst-case placeholders: each placeholder references the last message
|
||
* in the list, maximizing inner-loop iterations.
|
||
*/
|
||
static List<String> makeWorstCasePlaceholders(int count, int numMsg) {
|
||
List<String> phs = new ArrayList<>(count);
|
||
for (int i = 0; i < count; i++) phs.add("msg_" + (numMsg - 1 - (i % (numMsg / 2))));
|
||
return phs;
|
||
}
|
||
|
||
static List<SpoeGroup> makeGroups(int numGroups, int phsPerGroup, int msgCount) {
|
||
List<SpoeGroup> groups = new ArrayList<>(numGroups);
|
||
for (int g = 0; g < numGroups; g++) {
|
||
List<String> phs = new ArrayList<>(phsPerGroup);
|
||
for (int p = 0; p < phsPerGroup; p++) {
|
||
// Each group references messages round-robin
|
||
phs.add("msg_" + ((g * phsPerGroup + p) % msgCount));
|
||
}
|
||
groups.add(new SpoeGroup("grp_" + g, phs));
|
||
}
|
||
return groups;
|
||
}
|
||
|
||
// --- Tests ---
|
||
|
||
static boolean testPattern1(String name, int numPh, int numMsg) {
|
||
List<String> phs = makePlaceholders(numPh);
|
||
// Worst case: pad front with non-matching messages so matches are near end.
|
||
List<SpoeMessage> msgs = new ArrayList<>(numMsg);
|
||
int padding = numMsg - numPh;
|
||
for (int i = 0; i < padding; i++) msgs.add(new SpoeMessage("nomatch_" + i));
|
||
msgs.addAll(makeMessages(numPh)); // matching messages at the end
|
||
|
||
slowOps = 0;
|
||
int[] slowResult = resolvePlaceholdersSlow(phs, msgs);
|
||
long slowCount = slowOps;
|
||
|
||
slowOps = 0;
|
||
fastOps = 0;
|
||
int[] fastResult = resolvePlaceholdersFast(phs, msgs);
|
||
long fastCount = fastOps;
|
||
|
||
// Verify
|
||
for (int i = 0; i < numPh; i++) {
|
||
if (slowResult[i] != fastResult[i]) {
|
||
System.out.printf("FAIL [%s P1] P=%d M=%d mismatch at i=%d%n", name, numPh, numMsg, i);
|
||
return false;
|
||
}
|
||
}
|
||
|
||
double ratio = (double) slowCount / fastCount;
|
||
System.out.printf("PASS [%s P1] P=%d M=%d slow=%d fast=%d ratio=%.1fx%n",
|
||
name, numPh, numMsg, slowCount, fastCount, ratio);
|
||
if (numPh >= 20 && ratio < 5.0) {
|
||
System.out.printf("FAIL [%s P1] ratio %.1f < 5.0%n", name, ratio);
|
||
return false;
|
||
}
|
||
return true;
|
||
}
|
||
|
||
static boolean testPattern3(String name, int numGroups, int phsPerGroup, int numMsg) {
|
||
List<SpoeMessage> msgs = makeMessages(numMsg);
|
||
List<SpoeGroup> slowGroups = makeGroups(numGroups, phsPerGroup, numMsg);
|
||
List<SpoeGroup> fastGroups = makeGroups(numGroups, phsPerGroup, numMsg);
|
||
|
||
slowOps = 0;
|
||
int slowAssigned = slowTripleResolution(slowGroups, msgs);
|
||
long slowCount = slowOps;
|
||
|
||
slowOps = 0;
|
||
fastOps = 0;
|
||
int fastAssigned = fastTripleResolution(fastGroups, msgs);
|
||
long fastCount = fastOps;
|
||
|
||
if (slowAssigned != fastAssigned) {
|
||
System.out.printf("FAIL [%s P3] G=%d P=%d M=%d assigned mismatch slow=%d fast=%d%n",
|
||
name, numGroups, phsPerGroup, numMsg, slowAssigned, fastAssigned);
|
||
return false;
|
||
}
|
||
|
||
// Verify group messages match
|
||
for (int g = 0; g < numGroups; g++) {
|
||
List<SpoeMessage> sl = slowGroups.get(g).messages;
|
||
List<SpoeMessage> fl = fastGroups.get(g).messages;
|
||
if (sl.size() != fl.size()) {
|
||
System.out.printf("FAIL [%s P3] group %d size mismatch%n", name, g);
|
||
return false;
|
||
}
|
||
}
|
||
|
||
double ratio = (double) slowCount / fastCount;
|
||
System.out.printf("PASS [%s P3] G=%d P=%d M=%d slow=%d fast=%d ratio=%.1fx%n",
|
||
name, numGroups, phsPerGroup, numMsg, slowCount, fastCount, ratio);
|
||
if (numGroups >= 5 && ratio < 5.0) {
|
||
System.out.printf("FAIL [%s P3] ratio %.1f < 5.0%n", name, ratio);
|
||
return false;
|
||
}
|
||
return true;
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
int passed = 0, total = 0;
|
||
|
||
// Pattern 1: placeholder-to-message resolution (worst-case: match near end)
|
||
total++; if (testPattern1("tiny", 5, 10)) passed++;
|
||
total++; if (testPattern1("small", 20, 80)) passed++; // more messages → worse ratio
|
||
total++; if (testPattern1("medium", 50, 200)) passed++;
|
||
total++; if (testPattern1("large", 100, 400)) passed++;
|
||
|
||
// Pattern 3: triple-nested group→placeholder→message
|
||
total++; if (testPattern3("tiny", 3, 3, 10)) passed++;
|
||
total++; if (testPattern3("small", 5, 5, 20)) passed++;
|
||
total++; if (testPattern3("medium", 10, 10, 50)) passed++;
|
||
total++; if (testPattern3("large", 20, 10, 100)) passed++;
|
||
total++; if (testPattern3("xlarge", 30, 15, 150)) passed++;
|
||
|
||
System.out.printf("%n%d/%d PASS%n", passed, total);
|
||
if (passed != total) System.exit(1);
|
||
}
|
||
}
|