101 lines
3.5 KiB
Java
101 lines
3.5 KiB
Java
import java.util.*;
|
|
|
|
/**
|
|
* Unit test for dosbox-x-0004: bdlist std::list<uint16_t> O(N^2) membership
|
|
* in String_DBCS_TO_HOST_UTF16/UTF8 per-character conversion loop.
|
|
*
|
|
* Models DOSBox-X's DBCS filename conversion where std::find(bdlist) is called
|
|
* for every character in the input string. bdlist tracks byte positions of
|
|
* box-draw characters; with CROSS_LEN=512, worst case is 512*512=262,144
|
|
* comparisons per filename conversion.
|
|
*
|
|
* The fix replaces std::list<uint16_t> with std::unordered_set<uint16_t>,
|
|
* making each membership test O(1).
|
|
*/
|
|
public class DosboxXBdlistTest {
|
|
|
|
static final int CROSS_LEN = 512;
|
|
|
|
// --- Defect: std::list<uint16_t> with std::find per character ---
|
|
static boolean listContains(List<Integer> bdlist, int pos) {
|
|
for (int v : bdlist) {
|
|
if (v == pos) return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
static int convertWithList(int[] stringBytes, List<Integer> bdlist) {
|
|
int converted = 0;
|
|
for (int i = 0; i < stringBytes.length; i++) {
|
|
if (listContains(bdlist, i)) {
|
|
converted++; // box-draw path
|
|
} else {
|
|
converted++; // normal DBCS path
|
|
}
|
|
}
|
|
return converted;
|
|
}
|
|
|
|
// --- Fix: std::unordered_set<uint16_t> with O(1) count ---
|
|
static int convertWithSet(int[] stringBytes, Set<Integer> bdset) {
|
|
int converted = 0;
|
|
for (int i = 0; i < stringBytes.length; i++) {
|
|
if (bdset.contains(i)) {
|
|
converted++; // box-draw path
|
|
} else {
|
|
converted++; // normal DBCS path
|
|
}
|
|
}
|
|
return converted;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
// Build a worst-case string: CROSS_LEN chars, half are box-draw positions
|
|
int[] str = new int[CROSS_LEN];
|
|
Arrays.fill(str, 0xA1); // Kanji-range bytes
|
|
|
|
List<Integer> bdlist = new ArrayList<>();
|
|
Set<Integer> bdset = new HashSet<>();
|
|
for (int i = 0; i < CROSS_LEN; i += 2) {
|
|
bdlist.add(i);
|
|
bdset.add(i);
|
|
}
|
|
|
|
// Correctness check
|
|
int listResult = convertWithList(str, bdlist);
|
|
int setResult = convertWithSet(str, bdset);
|
|
assert listResult == setResult : "Correctness failed: list=" + listResult + " set=" + setResult;
|
|
System.out.println("Correctness OK: both produce " + listResult + " converted chars");
|
|
|
|
// Performance benchmark
|
|
int reps = 5000;
|
|
|
|
// Warmup
|
|
for (int i = 0; i < 10; i++) {
|
|
convertWithList(str, bdlist);
|
|
convertWithSet(str, bdset);
|
|
}
|
|
|
|
long t0 = System.nanoTime();
|
|
long totalList = 0;
|
|
for (int i = 0; i < reps; i++) totalList += convertWithList(str, bdlist);
|
|
long listNs = System.nanoTime() - t0;
|
|
|
|
long t1 = System.nanoTime();
|
|
long totalSet = 0;
|
|
for (int i = 0; i < reps; i++) totalSet += convertWithSet(str, bdset);
|
|
long setNs = System.nanoTime() - t1;
|
|
|
|
assert totalList == totalSet : "Result mismatch";
|
|
|
|
double ratio = (double) listNs / setNs;
|
|
System.out.printf("DBCS filename conversion CROSS_LEN=%d, bdlist=%d entries (%d reps):%n",
|
|
CROSS_LEN, bdlist.size(), reps);
|
|
System.out.printf(" std::list<uint16_t> linear find: %,d ns%n", listNs);
|
|
System.out.printf(" unordered_set<uint16_t> O(1): %,d ns%n", setNs);
|
|
System.out.printf(" speedup: %.1fx%n", ratio);
|
|
|
|
assert ratio > 5.0 : "Expected >5x speedup, got " + ratio;
|
|
System.out.println("PASS");
|
|
}
|
|
}
|