115 lines
4.3 KiB
Java
115 lines
4.3 KiB
Java
import java.util.*;
|
|
|
|
/**
|
|
* Unit test for dosbox-x-0003: jtbs/dbox vector<pair<int,int>> O(N^2) membership
|
|
* in Mouse_GetSelected nested row/col loops.
|
|
*
|
|
* Models the DOSBox-X defect where std::find is called on a vector of (row,col)
|
|
* pairs inside nested loops over all screen positions. For a full DBCS screen
|
|
* (80 cols x 25 rows), jtbs can hold ~2000 entries; each position calls find
|
|
* making the total O(rows * cols * N_entries) = O(N^2).
|
|
*
|
|
* The fix encodes (row,col) as a single int key and stores in a HashSet,
|
|
* making each membership test O(1).
|
|
*/
|
|
public class DosboxXJtbsDboxTest {
|
|
|
|
// --- Defect: vector<pair<int,int>> with linear find ---
|
|
static List<long[]> buildVectorList(int screenCols, int screenRows) {
|
|
List<long[]> list = new ArrayList<>();
|
|
// Simulate: every other column is a double-byte char (DBCS), producing (row,col) pairs
|
|
for (int row = 0; row < screenRows; row++) {
|
|
for (int col = 0; col < screenCols; col += 2) {
|
|
list.add(new long[]{row, col});
|
|
}
|
|
}
|
|
return list;
|
|
}
|
|
|
|
static boolean vectorContains(List<long[]> list, int row, int col) {
|
|
for (long[] pair : list) {
|
|
if (pair[0] == row && pair[1] == col) return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
static int countHitsVector(List<long[]> jtbs, int r1, int r2, int c1, int c2) {
|
|
int hits = 0;
|
|
for (int i = r1; i <= r2; i++) {
|
|
for (int j = c1; j <= c2; j++) {
|
|
if (vectorContains(jtbs, i, j)) hits++;
|
|
}
|
|
}
|
|
return hits;
|
|
}
|
|
|
|
// --- Fix: unordered_set<uint32_t> encoded as (row<<16)|col ---
|
|
static int encodePos(int row, int col) {
|
|
return ((row & 0xFFFF) << 16) | (col & 0xFFFF);
|
|
}
|
|
|
|
static Set<Integer> buildHashSet(int screenCols, int screenRows) {
|
|
Set<Integer> set = new HashSet<>();
|
|
for (int row = 0; row < screenRows; row++) {
|
|
for (int col = 0; col < screenCols; col += 2) {
|
|
set.add(encodePos(row, col));
|
|
}
|
|
}
|
|
return set;
|
|
}
|
|
|
|
static int countHitsHashSet(Set<Integer> jtbs, int r1, int r2, int c1, int c2) {
|
|
int hits = 0;
|
|
for (int i = r1; i <= r2; i++) {
|
|
for (int j = c1; j <= c2; j++) {
|
|
if (jtbs.contains(encodePos(i, j))) hits++;
|
|
}
|
|
}
|
|
return hits;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
// Small correctness test
|
|
int smallCols = 10, smallRows = 5;
|
|
List<long[]> vec = buildVectorList(smallCols, smallRows);
|
|
Set<Integer> set = buildHashSet(smallCols, smallRows);
|
|
|
|
int vecHits = countHitsVector(vec, 0, smallRows - 1, 0, smallCols - 1);
|
|
int setHits = countHitsHashSet(set, 0, smallRows - 1, 0, smallCols - 1);
|
|
assert vecHits == setHits : "Correctness failed: vec=" + vecHits + " set=" + setHits;
|
|
System.out.println("Correctness OK: " + vecHits + " hits in " + smallCols + "x" + smallRows + " grid");
|
|
|
|
// Performance test: 80x25 full DBCS screen
|
|
int cols = 80, rows = 25;
|
|
List<long[]> bigVec = buildVectorList(cols, rows);
|
|
Set<Integer> bigSet = buildHashSet(cols, rows);
|
|
|
|
// Warmup
|
|
for (int i = 0; i < 3; i++) {
|
|
countHitsVector(bigVec, 0, rows - 1, 0, cols - 1);
|
|
countHitsHashSet(bigSet, 0, rows - 1, 0, cols - 1);
|
|
}
|
|
|
|
int reps = 200;
|
|
long t0 = System.nanoTime();
|
|
int totalVec = 0;
|
|
for (int i = 0; i < reps; i++) totalVec += countHitsVector(bigVec, 0, rows - 1, 0, cols - 1);
|
|
long vecNs = System.nanoTime() - t0;
|
|
|
|
long t1 = System.nanoTime();
|
|
int totalSet = 0;
|
|
for (int i = 0; i < reps; i++) totalSet += countHitsHashSet(bigSet, 0, rows - 1, 0, cols - 1);
|
|
long setNs = System.nanoTime() - t1;
|
|
|
|
assert totalVec == totalSet : "Result mismatch";
|
|
|
|
double ratio = (double) vecNs / setNs;
|
|
System.out.printf("80x25 DBCS text selection (%d reps):%n", reps);
|
|
System.out.printf(" vector<pair> linear scan: %,d ns%n", vecNs);
|
|
System.out.printf(" unordered_set O(1) lookup: %,d ns%n", setNs);
|
|
System.out.printf(" speedup: %.1fx%n", ratio);
|
|
|
|
assert ratio > 3.0 : "Expected >3x speedup, got " + ratio;
|
|
System.out.println("PASS");
|
|
}
|
|
}
|