258 lines
9.6 KiB
Java
258 lines
9.6 KiB
Java
package unit;
|
||
import java.util.*;
|
||
|
||
/**
|
||
* WeechatTest — CWE-407 benchmark for weechat-0001 + weechat-0002
|
||
*
|
||
* weechat-0001: irc_nick_search() O(n) called per-channel in AWAY/NICK/QUIT/KILL
|
||
* SLOW: for each channel (C), walk linked list of nicks (N) → O(C×N)
|
||
* FAST: HashMap lookup per channel → O(C)
|
||
*
|
||
* weechat-0002: irc_nick_new() calls irc_nick_search() during 353 NAMES → O(n²)
|
||
* SLOW: for each of n nicks inserted, scan growing list → O(n²)
|
||
* FAST: HashMap dedup check → O(n)
|
||
*/
|
||
public class WeechatTest {
|
||
|
||
// -------------------------------------------------------------------------
|
||
// Data model
|
||
// -------------------------------------------------------------------------
|
||
|
||
static class IrcNick {
|
||
final String name;
|
||
IrcNick(String name) { this.name = name; }
|
||
}
|
||
|
||
static class IrcChannel {
|
||
final String name;
|
||
// Slow: linked list representation (simulated as ArrayList for ops counting)
|
||
final List<IrcNick> nicks = new ArrayList<>();
|
||
// Fast: pre-built hash map
|
||
final Map<String, IrcNick> nicksMap = new HashMap<>();
|
||
|
||
IrcChannel(String name) { this.name = name; }
|
||
|
||
void addNick(IrcNick n) {
|
||
nicks.add(n);
|
||
nicksMap.put(n.name.toLowerCase(), n);
|
||
}
|
||
}
|
||
|
||
static class IrcServer {
|
||
final List<IrcChannel> channels = new ArrayList<>();
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// weechat-0001: AWAY/NICK/QUIT/KILL handlers
|
||
// -------------------------------------------------------------------------
|
||
|
||
/**
|
||
* SLOW: O(C × N) — for each channel, scan linked list for nick.
|
||
* Returns total comparisons made.
|
||
*/
|
||
static long protocolHandler_slow(IrcServer server, String nickName) {
|
||
long ops = 0;
|
||
for (IrcChannel ch : server.channels) {
|
||
// irc_nick_search: O(n) linked-list walk
|
||
for (IrcNick n : ch.nicks) {
|
||
ops++;
|
||
if (n.name.equalsIgnoreCase(nickName)) break;
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/**
|
||
* FAST: O(C) — for each channel, O(1) hash lookup.
|
||
* Returns total lookups made.
|
||
*/
|
||
static long protocolHandler_fast(IrcServer server, String nickName) {
|
||
long ops = 0;
|
||
String key = nickName.toLowerCase();
|
||
for (IrcChannel ch : server.channels) {
|
||
ops++; // one hash lookup per channel
|
||
ch.nicksMap.get(key); // O(1)
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// weechat-0002: 353 NAMES processing
|
||
// -------------------------------------------------------------------------
|
||
|
||
/**
|
||
* SLOW: O(n²) — for each nick being added, scan the growing list for dedup.
|
||
* Returns total comparisons.
|
||
*/
|
||
static long names353_slow(String[] nickList) {
|
||
long ops = 0;
|
||
List<String> added = new ArrayList<>();
|
||
for (String nick : nickList) {
|
||
String lc = nick.toLowerCase();
|
||
// irc_nick_search over already-added nicks
|
||
boolean found = false;
|
||
for (String existing : added) {
|
||
ops++;
|
||
if (existing.equals(lc)) { found = true; break; }
|
||
}
|
||
if (!found) added.add(lc);
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
/**
|
||
* FAST: O(n) — HashMap for dedup check.
|
||
* Returns total operations.
|
||
*/
|
||
static long names353_fast(String[] nickList) {
|
||
long ops = 0;
|
||
Map<String, Boolean> seen = new HashMap<>(nickList.length * 2);
|
||
for (String nick : nickList) {
|
||
ops++;
|
||
seen.putIfAbsent(nick.toLowerCase(), Boolean.TRUE);
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// Benchmark harness
|
||
// -------------------------------------------------------------------------
|
||
|
||
static void bench(String label, Runnable slow, Runnable fast, long sOps, long fOps) {
|
||
slow.run(); fast.run();
|
||
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 r = fOps > 0 ? (double) sOps / fOps : 0;
|
||
System.out.printf(" %-52s slow:%4dms (%,d ops) fast:%4dms (%,d ops) speedup:%.0fx%n",
|
||
label, sMs, sOps, fMs, fOps, r);
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// Setup helpers
|
||
// -------------------------------------------------------------------------
|
||
|
||
static IrcServer makeServer(int numChannels, int nicksPerChannel, String targetNick) {
|
||
IrcServer srv = new IrcServer();
|
||
for (int c = 0; c < numChannels; c++) {
|
||
IrcChannel ch = new IrcChannel("#chan" + c);
|
||
// Insert target nick near the end (worst case for linear scan)
|
||
for (int n = 0; n < nicksPerChannel - 1; n++)
|
||
ch.addNick(new IrcNick("user" + c + "_" + n));
|
||
ch.addNick(new IrcNick(targetNick));
|
||
srv.channels.add(ch);
|
||
}
|
||
return srv;
|
||
}
|
||
|
||
static String[] makeNickList(int n) {
|
||
String[] nicks = new String[n];
|
||
for (int i = 0; i < n; i++) nicks[i] = "nick" + i;
|
||
return nicks;
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// Main
|
||
// -------------------------------------------------------------------------
|
||
|
||
public static void main(String[] args) {
|
||
System.out.println("weechat-0001/0002: irc_nick_search CWE-407 benchmark");
|
||
System.out.println("======================================================");
|
||
|
||
// --- weechat-0001: AWAY handler C=200 channels, N=500 nicks ---
|
||
{
|
||
int C = 200, N = 500;
|
||
IrcServer srv = makeServer(C, N, "awayuser");
|
||
|
||
long[] sOps = {0}, fOps = {0};
|
||
Runnable slow = () -> {
|
||
long ops = 0;
|
||
// Simulate 1000 AWAY messages
|
||
for (int i = 0; i < 1000; i++) ops += protocolHandler_slow(srv, "awayuser");
|
||
sOps[0] = ops;
|
||
};
|
||
Runnable fast = () -> {
|
||
long ops = 0;
|
||
for (int i = 0; i < 1000; i++) ops += protocolHandler_fast(srv, "awayuser");
|
||
fOps[0] = ops;
|
||
};
|
||
slow.run(); fast.run();
|
||
bench("away-handler C=200 N=500 (1000 events)", slow, fast, sOps[0], fOps[0]);
|
||
assert sOps[0] > fOps[0] * 50 :
|
||
"Expected slow ops >> fast ops, got slow=" + sOps[0] + " fast=" + fOps[0];
|
||
}
|
||
|
||
// --- weechat-0001: NICK rename handler C=100 channels, N=300 nicks ---
|
||
{
|
||
int C = 100, N = 300;
|
||
IrcServer srv = makeServer(C, N, "oldnick");
|
||
|
||
long[] sOps = {0}, fOps = {0};
|
||
Runnable slow = () -> {
|
||
long ops = 0;
|
||
for (int i = 0; i < 500; i++) ops += protocolHandler_slow(srv, "oldnick");
|
||
sOps[0] = ops;
|
||
};
|
||
Runnable fast = () -> {
|
||
long ops = 0;
|
||
for (int i = 0; i < 500; i++) ops += protocolHandler_fast(srv, "oldnick");
|
||
fOps[0] = ops;
|
||
};
|
||
slow.run(); fast.run();
|
||
bench("nick-handler C=100 N=300 (500 events)", slow, fast, sOps[0], fOps[0]);
|
||
assert sOps[0] > fOps[0] * 50 :
|
||
"Expected slow ops >> fast ops, got slow=" + sOps[0] + " fast=" + fOps[0];
|
||
}
|
||
|
||
// --- weechat-0001: QUIT handler C=50 channels, N=8000 nicks (large chan) ---
|
||
{
|
||
int C = 50, N = 8000;
|
||
IrcServer srv = makeServer(C, N, "quitter");
|
||
|
||
long[] sOps = {0}, fOps = {0};
|
||
Runnable slow = () -> {
|
||
long ops = 0;
|
||
for (int i = 0; i < 100; i++) ops += protocolHandler_slow(srv, "quitter");
|
||
sOps[0] = ops;
|
||
};
|
||
Runnable fast = () -> {
|
||
long ops = 0;
|
||
for (int i = 0; i < 100; i++) ops += protocolHandler_fast(srv, "quitter");
|
||
fOps[0] = ops;
|
||
};
|
||
slow.run(); fast.run();
|
||
bench("quit-handler C=50 N=8000 (100 events)", slow, fast, sOps[0], fOps[0]);
|
||
assert sOps[0] > fOps[0] * 100 :
|
||
"Expected slow ops >> fast ops, got slow=" + sOps[0] + " fast=" + fOps[0];
|
||
}
|
||
|
||
// --- weechat-0002: 353 NAMES dedup N=1000 nicks ---
|
||
{
|
||
int N = 1000;
|
||
String[] nicks = makeNickList(N);
|
||
|
||
long[] sOps = {0}, fOps = {0};
|
||
Runnable slow = () -> sOps[0] = names353_slow(nicks);
|
||
Runnable fast = () -> fOps[0] = names353_fast(nicks);
|
||
slow.run(); fast.run();
|
||
bench("names353-dedup N=1000", slow, fast, sOps[0], fOps[0]);
|
||
assert sOps[0] > fOps[0] * 100 :
|
||
"Expected slow ops >> fast ops, got slow=" + sOps[0] + " fast=" + fOps[0];
|
||
}
|
||
|
||
// --- weechat-0002: 353 NAMES dedup N=8000 (large channel like freenode) ---
|
||
{
|
||
int N = 8000;
|
||
String[] nicks = makeNickList(N);
|
||
|
||
long[] sOps = {0}, fOps = {0};
|
||
Runnable slow = () -> sOps[0] = names353_slow(nicks);
|
||
Runnable fast = () -> fOps[0] = names353_fast(nicks);
|
||
slow.run(); fast.run();
|
||
bench("names353-dedup N=8000 (large chan)", slow, fast, sOps[0], fOps[0]);
|
||
assert sOps[0] > fOps[0] * 500 :
|
||
"Expected slow ops >> fast ops, got slow=" + sOps[0] + " fast=" + fOps[0];
|
||
}
|
||
|
||
System.out.println("\nAll assertions passed.");
|
||
}
|
||
}
|