108 lines
3.7 KiB
Java
108 lines
3.7 KiB
Java
package unit;
|
||
|
||
import java.util.*;
|
||
|
||
/**
|
||
* artemis-0001: ActiveMQ Artemis BindingsImpl idsToAckList List.contains O(N×M) → HashSet O(N+M)
|
||
*
|
||
* In BindingsImpl.routeFromCluster() (BindingsImpl.java:639):
|
||
*
|
||
* List<Long> idsToAckList = new ArrayList<>(); // built from HDR_ROUTE_TO_ACK_IDS
|
||
* while (buff.hasRemaining()) {
|
||
* long bindingID = buff.getLong();
|
||
* if (idsToAckList.contains(bindingID)) { // O(M) per binding — CWE-407
|
||
* binding.routeWithAck(...);
|
||
* } else {
|
||
* binding.route(...);
|
||
* }
|
||
* }
|
||
*
|
||
* N = binding IDs in the message, M = ack IDs.
|
||
* Total: O(N×M) per cluster message delivery.
|
||
*
|
||
* Fix: Set<Long> idsToAckSet = new HashSet<>() — O(1) lookup.
|
||
*
|
||
* UNDF: assigned by generate_undf.py
|
||
* Severity: MEDIUM
|
||
*/
|
||
public class Artemis0001BindingsTest {
|
||
|
||
static long cmpOps = 0;
|
||
|
||
// SLOW: List.contains — O(M) per binding
|
||
static void routeSlow(long[] bindingIds, List<Long> idsToAckList,
|
||
long[] routeCount, long[] routeWithAckCount) {
|
||
for (long bindingId : bindingIds) {
|
||
boolean shouldAck = false;
|
||
for (Long id : idsToAckList) {
|
||
cmpOps++;
|
||
if (id == bindingId) { shouldAck = true; break; }
|
||
}
|
||
if (shouldAck) routeWithAckCount[0]++;
|
||
else routeCount[0]++;
|
||
}
|
||
}
|
||
|
||
// FAST: Set.contains — O(1) per binding
|
||
static void routeFast(long[] bindingIds, Set<Long> idsToAckSet,
|
||
long[] routeCount, long[] routeWithAckCount, long[] fastOps) {
|
||
for (long bindingId : bindingIds) {
|
||
fastOps[0]++; // O(1) hash lookup
|
||
if (idsToAckSet.contains(bindingId)) routeWithAckCount[0]++;
|
||
else routeCount[0]++;
|
||
}
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
int N = 100; // binding IDs per message
|
||
int M = 50; // ack IDs per message
|
||
int MSG_COUNT = 1000; // messages per benchmark run
|
||
|
||
// Build test data: binding IDs 0..N-1, ack IDs N/2..N/2+M-1 (overlap)
|
||
long[] bindingIds = new long[N];
|
||
for (int i = 0; i < N; i++) bindingIds[i] = i;
|
||
|
||
List<Long> slowAckList = new ArrayList<>();
|
||
Set<Long> fastAckSet = new HashSet<>();
|
||
for (int i = N / 2; i < N / 2 + M; i++) {
|
||
slowAckList.add((long) i);
|
||
fastAckSet.add((long) i);
|
||
}
|
||
|
||
// Verify correctness
|
||
long[] slowRoute = {0}, slowAck = {0};
|
||
long[] fastRoute = {0}, fastAck = {0};
|
||
long[] fastOps = {0};
|
||
routeSlow(bindingIds, slowAckList, slowRoute, slowAck);
|
||
routeFast(bindingIds, fastAckSet, fastRoute, fastAck, fastOps);
|
||
|
||
if (slowRoute[0] != fastRoute[0] || slowAck[0] != fastAck[0]) {
|
||
System.err.printf("FAIL: route slow=%d fast=%d; ack slow=%d fast=%d%n",
|
||
slowRoute[0], fastRoute[0], slowAck[0], fastAck[0]);
|
||
System.exit(1);
|
||
}
|
||
|
||
// Benchmark
|
||
cmpOps = 0;
|
||
for (int m = 0; m < MSG_COUNT; m++) {
|
||
long[] r = {0}, a = {0};
|
||
routeSlow(bindingIds, slowAckList, r, a);
|
||
}
|
||
long slowCmp = cmpOps;
|
||
fastOps[0] = 0;
|
||
for (int m = 0; m < MSG_COUNT; m++) {
|
||
long[] r = {0}, a = {0};
|
||
routeFast(bindingIds, fastAckSet, r, a, fastOps);
|
||
}
|
||
|
||
double ratio = (double) slowCmp / Math.max(fastOps[0], 1);
|
||
System.out.printf("artemis-0001 BindingsImpl: SLOW=%d cmpOps, FAST~=%d ops, ratio=%.1fx%n",
|
||
slowCmp, fastOps[0], ratio);
|
||
|
||
if (ratio < 5.0) {
|
||
System.err.printf("FAIL: ratio %.1f < 5x%n", ratio);
|
||
System.exit(1);
|
||
}
|
||
System.out.println("PASS");
|
||
}
|
||
}
|