114 lines
4.2 KiB
Java
114 lines
4.2 KiB
Java
import java.util.*;
|
|
|
|
/**
|
|
* Unit test for PCSX2 pcsx2-0003:
|
|
* Achievements::DrawAchievement uses std::find_if on a std::vector of
|
|
* (pointer, path) pairs to look up our cached badge path per achievement.
|
|
* Called once per achievement per ImGui frame while our achievements window
|
|
* is open. A game with A achievements gives O(A^2) total scan work per frame.
|
|
*
|
|
* Modern PS2 titles routinely ship 50-200 RetroAchievements entries.
|
|
*
|
|
* Defect file: pcsx2/Achievements.cpp line 2777
|
|
* Pattern: std::find_if(s_achievement_badge_paths.begin(), ..., ptr == cheevo)
|
|
* Fix: change s_achievement_badge_paths to std::unordered_map<const void*, string>
|
|
* and use .find(cheevo) for O(1) lookup.
|
|
*/
|
|
public class AchievementBadgePathsTest {
|
|
|
|
// --- Defective: vector-as-map, O(A) lookup per draw call ---
|
|
static String drawAchievementDefective(
|
|
List<long[]> badgePaths, // pair<ptr_id, path_index>
|
|
Map<Long, String> pathStore,
|
|
long cheevoId,
|
|
int[] pathCounter) {
|
|
|
|
for (long[] entry : badgePaths) {
|
|
if (entry[0] == cheevoId) {
|
|
return pathStore.get(entry[1]);
|
|
}
|
|
}
|
|
// Not found: add new entry
|
|
long idx = pathCounter[0]++;
|
|
pathStore.put(idx, "badge_" + cheevoId + ".png");
|
|
badgePaths.add(new long[]{cheevoId, idx});
|
|
return pathStore.get(idx);
|
|
}
|
|
|
|
// --- Fixed: unordered_map, O(1) lookup per draw call ---
|
|
static String drawAchievementFixed(
|
|
Map<Long, String> badgeMap,
|
|
long cheevoId) {
|
|
|
|
return badgeMap.computeIfAbsent(cheevoId,
|
|
id -> "badge_" + id + ".png");
|
|
}
|
|
|
|
// Simulate one frame: draw all achievements
|
|
static long frameDefective(int numAchievements) {
|
|
List<long[]> badgePaths = new ArrayList<>(numAchievements);
|
|
Map<Long, String> pathStore = new HashMap<>();
|
|
int[] counter = {0};
|
|
|
|
long ops = 0;
|
|
for (int i = 0; i < numAchievements; i++) {
|
|
drawAchievementDefective(badgePaths, pathStore, (long) i, counter);
|
|
ops += badgePaths.size(); // track scan length
|
|
}
|
|
return ops;
|
|
}
|
|
|
|
static void frameFixed(int numAchievements) {
|
|
Map<Long, String> badgeMap = new HashMap<>(numAchievements);
|
|
for (int i = 0; i < numAchievements; i++) {
|
|
drawAchievementFixed(badgeMap, (long) i);
|
|
}
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
int N = 200;
|
|
|
|
// Correctness: both paths must return same badge path
|
|
List<long[]> vecPaths = new ArrayList<>();
|
|
Map<Long, String> pathStore = new HashMap<>();
|
|
int[] counter = {0};
|
|
Map<Long, String> mapPaths = new HashMap<>();
|
|
|
|
for (int i = 0; i < N; i++) {
|
|
String defPath = drawAchievementDefective(vecPaths, pathStore, (long) i, counter);
|
|
String fixPath = drawAchievementFixed(mapPaths, (long) i);
|
|
assert defPath.equals(fixPath)
|
|
: "Path mismatch at i=" + i + ": " + defPath + " != " + fixPath;
|
|
}
|
|
|
|
// Second pass: lookup must return same path (not duplicate)
|
|
for (int i = 0; i < N; i++) {
|
|
String defPath = drawAchievementDefective(vecPaths, pathStore, (long) i, counter);
|
|
String fixPath = drawAchievementFixed(mapPaths, (long) i);
|
|
assert defPath.equals(fixPath) : "Cache miss mismatch at i=" + i;
|
|
}
|
|
|
|
// Warm up
|
|
for (int i = 0; i < 50; i++) {
|
|
frameDefective(N);
|
|
frameFixed(N);
|
|
}
|
|
|
|
// Benchmark: simulate 500 frames
|
|
int FRAMES = 500;
|
|
long t0 = System.nanoTime();
|
|
for (int f = 0; f < FRAMES; f++) frameDefective(N);
|
|
long defectNs = System.nanoTime() - t0;
|
|
|
|
t0 = System.nanoTime();
|
|
for (int f = 0; f < FRAMES; f++) frameFixed(N);
|
|
long fixedNs = System.nanoTime() - t0;
|
|
|
|
double ratio = (double) defectNs / fixedNs;
|
|
System.out.printf("DrawAchievement badge lookup A=%d achievements %d frames defect=%.1fms fixed=%.1fms ratio=%.1fx%n",
|
|
N, FRAMES, defectNs / 1e6, fixedNs / 1e6, ratio);
|
|
|
|
assert ratio > 2.0 : "Expected >2x speedup, got " + ratio;
|
|
System.out.println("PASS");
|
|
}
|
|
}
|