113 lines
4.1 KiB
Java
113 lines
4.1 KiB
Java
import java.util.*;
|
|
|
|
/**
|
|
* CWE-407 simulation: TiDB updateDroppingPartitionInfo O(P*D) partition name lookup.
|
|
*
|
|
* tidb-0001: slices.Contains(partLowerNames, oldDefs[i].Name.L) inside
|
|
* for i := range oldDefs => O(P*D).
|
|
* Fix: map[string]struct{} for O(1) lookup => O(P+D).
|
|
*/
|
|
public class TidbTest {
|
|
|
|
// --- Defective: linear scan per partition definition ---
|
|
static List<String> updateDroppingPartitionDefective(
|
|
List<String> oldDefNames, List<String> partLowerNames) {
|
|
List<String> newDefs = new ArrayList<>();
|
|
List<String> droppingDefs = new ArrayList<>();
|
|
// "consider using a map to probe partLowerNames if too many partLowerNames"
|
|
for (String defName : oldDefNames) {
|
|
boolean found = partLowerNames.contains(defName); // O(D) per call
|
|
if (found) {
|
|
droppingDefs.add(defName);
|
|
} else {
|
|
newDefs.add(defName);
|
|
}
|
|
}
|
|
return newDefs;
|
|
}
|
|
|
|
// --- Fixed: hash set for O(1) lookup ---
|
|
static List<String> updateDroppingPartitionFixed(
|
|
List<String> oldDefNames, List<String> partLowerNames) {
|
|
Set<String> nameSet = new HashSet<>(partLowerNames); // O(D)
|
|
List<String> newDefs = new ArrayList<>();
|
|
List<String> droppingDefs = new ArrayList<>();
|
|
for (String defName : oldDefNames) {
|
|
if (nameSet.contains(defName)) { // O(1)
|
|
droppingDefs.add(defName);
|
|
} else {
|
|
newDefs.add(defName);
|
|
}
|
|
}
|
|
return newDefs;
|
|
}
|
|
|
|
// --- Correctness ---
|
|
static void testCorrectness() {
|
|
List<String> oldDefs = Arrays.asList("p0", "p1", "p2", "p3", "p4");
|
|
List<String> dropping = Arrays.asList("p1", "p3");
|
|
|
|
List<String> resultDefective = updateDroppingPartitionDefective(oldDefs, dropping);
|
|
List<String> resultFixed = updateDroppingPartitionFixed(oldDefs, dropping);
|
|
|
|
assert resultDefective.equals(Arrays.asList("p0", "p2", "p4"))
|
|
: "Defective correctness failed: " + resultDefective;
|
|
assert resultFixed.equals(Arrays.asList("p0", "p2", "p4"))
|
|
: "Fixed correctness failed: " + resultFixed;
|
|
assert resultDefective.equals(resultFixed)
|
|
: "Results differ";
|
|
System.out.println("PASS correctness");
|
|
}
|
|
|
|
// --- Performance ---
|
|
static void testPerformance() {
|
|
int P = 8192; // max partitions in TiDB
|
|
int D = 500; // dropping half
|
|
|
|
List<String> oldDefs = new ArrayList<>(P);
|
|
for (int i = 0; i < P; i++) {
|
|
oldDefs.add("partition_" + i);
|
|
}
|
|
List<String> dropping = new ArrayList<>(D);
|
|
for (int i = 0; i < D; i++) {
|
|
dropping.add("partition_" + (i * (P / D)));
|
|
}
|
|
|
|
// Warm up
|
|
for (int w = 0; w < 3; w++) {
|
|
updateDroppingPartitionDefective(oldDefs, dropping);
|
|
updateDroppingPartitionFixed(oldDefs, dropping);
|
|
}
|
|
|
|
int iterations = 200;
|
|
|
|
long startDefective = System.nanoTime();
|
|
for (int i = 0; i < iterations; i++) {
|
|
updateDroppingPartitionDefective(oldDefs, dropping);
|
|
}
|
|
long defectiveNs = System.nanoTime() - startDefective;
|
|
|
|
long startFixed = System.nanoTime();
|
|
for (int i = 0; i < iterations; i++) {
|
|
updateDroppingPartitionFixed(oldDefs, dropping);
|
|
}
|
|
long fixedNs = System.nanoTime() - startFixed;
|
|
|
|
double ratio = (double) defectiveNs / fixedNs;
|
|
|
|
System.out.printf("tidb-0001 updateDroppingPartitionInfo P=%d D=%d%n", P, D);
|
|
System.out.printf(" defective: %,d ns%n", defectiveNs);
|
|
System.out.printf(" fixed: %,d ns%n", fixedNs);
|
|
System.out.printf(" ratio: %.1fx%n", ratio);
|
|
|
|
assert ratio > 5.0
|
|
: "Expected significant speedup, got only " + ratio + "x";
|
|
System.out.println("PASS performance (ratio=" + String.format("%.1f", ratio) + "x)");
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
testCorrectness();
|
|
testPerformance();
|
|
System.out.println("ALL TESTS PASSED");
|
|
}
|
|
}
|