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.
88 lines
3.4 KiB
Java
88 lines
3.4 KiB
Java
import java.util.*;
|
||
|
||
/**
|
||
* Unit test for netty-0001: JdkBaseApplicationProtocolNegotiator
|
||
* ALPN select() List.contains() O(S×P) → HashSet O(S+P).
|
||
*/
|
||
public class Netty0001Test {
|
||
|
||
// --- BEFORE: O(S×P) linear scan ---
|
||
static String selectBefore(Set<String> supportedProtocols, List<String> protocols) {
|
||
for (String p : supportedProtocols) {
|
||
if (protocols.contains(p)) { // O(P) per iteration
|
||
return p;
|
||
}
|
||
}
|
||
return null;
|
||
}
|
||
|
||
// --- AFTER: O(S+P) with HashSet ---
|
||
static String selectAfter(Set<String> supportedProtocols, List<String> protocols) {
|
||
Set<String> protocolSet = new HashSet<>(protocols);
|
||
for (String p : supportedProtocols) {
|
||
if (protocolSet.contains(p)) { // O(1) per iteration
|
||
return p;
|
||
}
|
||
}
|
||
return null;
|
||
}
|
||
|
||
// Simulate the selected() listener path
|
||
static boolean selectedBefore(List<String> supportedProtocols, String protocol) {
|
||
return supportedProtocols.contains(protocol); // O(S)
|
||
}
|
||
|
||
static boolean selectedAfter(Set<String> supportedProtocolSet, String protocol) {
|
||
return supportedProtocolSet.contains(protocol); // O(1)
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
// Correctness: select()
|
||
Set<String> supported = new LinkedHashSet<>(Arrays.asList("h2", "http/1.1", "spdy/3.1"));
|
||
List<String> offered = Arrays.asList("spdy/3.1", "h2", "http/1.1");
|
||
|
||
String beforeResult = selectBefore(supported, offered);
|
||
String afterResult = selectAfter(supported, offered);
|
||
assert Objects.equals(beforeResult, afterResult) : "Results must match";
|
||
System.out.println("PASS correctness select: '" + beforeResult + "'");
|
||
|
||
// Correctness: selected()
|
||
List<String> supportedList = Arrays.asList("h2", "http/1.1");
|
||
Set<String> supportedSet = new HashSet<>(supportedList);
|
||
assert selectedBefore(supportedList, "h2") == selectedAfter(supportedSet, "h2");
|
||
assert selectedBefore(supportedList, "spdy") == selectedAfter(supportedSet, "spdy");
|
||
System.out.println("PASS correctness selected");
|
||
|
||
// Performance: S=500 supported, P=500 offered, worst-case no match
|
||
int S = 500, P = 500;
|
||
Set<String> bigSupported = new LinkedHashSet<>();
|
||
for (int i = 0; i < S; i++) bigSupported.add("supported-" + i);
|
||
List<String> bigOffered = new ArrayList<>();
|
||
for (int i = 0; i < P; i++) bigOffered.add("offered-" + i); // no overlap
|
||
|
||
// Warmup
|
||
for (int i = 0; i < 1000; i++) {
|
||
selectBefore(bigSupported, bigOffered);
|
||
selectAfter(bigSupported, bigOffered);
|
||
}
|
||
|
||
int iterations = 5000;
|
||
long t0 = System.nanoTime();
|
||
for (int i = 0; i < iterations; i++) {
|
||
selectBefore(bigSupported, bigOffered);
|
||
}
|
||
long beforeNs = System.nanoTime() - t0;
|
||
|
||
t0 = System.nanoTime();
|
||
for (int i = 0; i < iterations; i++) {
|
||
selectAfter(bigSupported, bigOffered);
|
||
}
|
||
long afterNs = System.nanoTime() - t0;
|
||
|
||
double ratio = (double) beforeNs / afterNs;
|
||
System.out.printf("PASS performance: before=%dms after=%dms ratio=%.1fx (S=%d P=%d)%n",
|
||
beforeNs / 1_000_000, afterNs / 1_000_000, ratio, S, P);
|
||
assert ratio > 2.0 : "Expected at least 2x speedup, got " + ratio;
|
||
System.out.println("PASS all tests for netty-0001");
|
||
}
|
||
}
|