russell@unturf.com
32cbeb5dcb
tomcat-0001: WebSocket getNegotiatedSubprotocol List.contains O(R×S) MEDIUM 52x hibernate-orm-0001: FK ordering buildRecursiveOrderedFkSecondPasses List.contains O(N²) HIGH 2.8x netty-0001: ALPN select/selected List.contains O(S×P) MEDIUM 26x netty-0002: DnsResolveContext dedup ArrayList.contains O(R²) MEDIUM 30x All 4/4 unit tests PASS.
79 lines
3.2 KiB
Java
79 lines
3.2 KiB
Java
import java.util.*;
|
||
|
||
/**
|
||
* Unit test for tomcat-0001: DefaultServerEndpointConfigurator.getNegotiatedSubprotocol
|
||
* List.contains() O(R×S) → HashSet O(R+S) for WebSocket subprotocol negotiation.
|
||
*/
|
||
public class Tomcat0001Test {
|
||
|
||
// --- BEFORE: O(R×S) linear scan ---
|
||
static String negotiateSubprotocolBefore(List<String> supported, List<String> requested) {
|
||
for (String request : requested) {
|
||
if (supported.contains(request)) { // O(S) per iteration
|
||
return request;
|
||
}
|
||
}
|
||
return "";
|
||
}
|
||
|
||
// --- AFTER: O(R+S) with HashSet ---
|
||
static String negotiateSubprotocolAfter(List<String> supported, List<String> requested) {
|
||
Set<String> supportedSet = new HashSet<>(supported);
|
||
for (String request : requested) {
|
||
if (supportedSet.contains(request)) { // O(1) per iteration
|
||
return request;
|
||
}
|
||
}
|
||
return "";
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
// Correctness tests
|
||
List<String> supported = Arrays.asList("chat", "superchat", "megachat");
|
||
List<String> requested = Arrays.asList("video", "megachat", "chat");
|
||
|
||
String beforeResult = negotiateSubprotocolBefore(supported, requested);
|
||
String afterResult = negotiateSubprotocolAfter(supported, requested);
|
||
assert beforeResult.equals(afterResult) : "Results must match";
|
||
assert "megachat".equals(beforeResult) : "Should find megachat";
|
||
System.out.println("PASS correctness: both return '" + beforeResult + "'");
|
||
|
||
// No match
|
||
List<String> noMatch = Arrays.asList("video", "audio");
|
||
assert "".equals(negotiateSubprotocolBefore(supported, noMatch));
|
||
assert "".equals(negotiateSubprotocolAfter(supported, noMatch));
|
||
System.out.println("PASS no-match: both return empty");
|
||
|
||
// Performance test: S=500 supported, R=500 requested, worst-case no match
|
||
int S = 500, R = 500;
|
||
List<String> bigSupported = new ArrayList<>();
|
||
for (int i = 0; i < S; i++) bigSupported.add("proto-s-" + i);
|
||
List<String> bigRequested = new ArrayList<>();
|
||
for (int i = 0; i < R; i++) bigRequested.add("proto-r-" + i); // no overlap
|
||
|
||
// Warmup
|
||
for (int i = 0; i < 1000; i++) {
|
||
negotiateSubprotocolBefore(bigSupported, bigRequested);
|
||
negotiateSubprotocolAfter(bigSupported, bigRequested);
|
||
}
|
||
|
||
int iterations = 5000;
|
||
long t0 = System.nanoTime();
|
||
for (int i = 0; i < iterations; i++) {
|
||
negotiateSubprotocolBefore(bigSupported, bigRequested);
|
||
}
|
||
long beforeNs = System.nanoTime() - t0;
|
||
|
||
t0 = System.nanoTime();
|
||
for (int i = 0; i < iterations; i++) {
|
||
negotiateSubprotocolAfter(bigSupported, bigRequested);
|
||
}
|
||
long afterNs = System.nanoTime() - t0;
|
||
|
||
double ratio = (double) beforeNs / afterNs;
|
||
System.out.printf("PASS performance: before=%dms after=%dms ratio=%.1fx (S=%d R=%d)%n",
|
||
beforeNs / 1_000_000, afterNs / 1_000_000, ratio, S, R);
|
||
assert ratio > 2.0 : "Expected at least 2x speedup, got " + ratio;
|
||
System.out.println("PASS all tests for tomcat-0001");
|
||
}
|
||
}
|