112 lines
3.4 KiB
Rust
112 lines
3.4 KiB
Rust
// Unit test for veloren-0001: TradePricing O(N^2) linear scan in PriceEntries/FreqEntries
|
|
//
|
|
// DEFECT: PriceEntries::add_alternative() and FreqEntries::add() use
|
|
// Vec::iter().find() to check for duplicate items before inserting.
|
|
// With N = number of unique items (1300+ in Veloren), initialization
|
|
// performs O(N^2) linear scans.
|
|
//
|
|
// FIX: Add HashMap<ItemDefinitionIdOwned, usize> index alongside Vec
|
|
// for O(1) lookup by item name during dedup.
|
|
|
|
use std::collections::HashMap;
|
|
use std::time::Instant;
|
|
|
|
/// Simulates the defective pattern: Vec linear scan for dedup
|
|
fn vec_dedup_add(entries: &mut Vec<(String, f32)>, name: String, value: f32) {
|
|
if let Some(entry) = entries.iter_mut().find(|(n, _)| *n == name) {
|
|
entry.1 += value;
|
|
} else {
|
|
entries.push((name, value));
|
|
}
|
|
}
|
|
|
|
/// Simulates the fixed pattern: HashMap index for O(1) dedup
|
|
fn hashmap_dedup_add(
|
|
entries: &mut Vec<(String, f32)>,
|
|
index: &mut HashMap<String, usize>,
|
|
name: String,
|
|
value: f32,
|
|
) {
|
|
if let Some(&idx) = index.get(&name) {
|
|
entries[idx].1 += value;
|
|
} else {
|
|
index.insert(name.clone(), entries.len());
|
|
entries.push((name, value));
|
|
}
|
|
}
|
|
|
|
#[test]
|
|
fn test_correctness() {
|
|
// Both patterns should produce identical results
|
|
let items: Vec<(String, f32)> = (0..100)
|
|
.map(|i| (format!("item_{}", i % 50), i as f32))
|
|
.collect();
|
|
|
|
let mut vec_entries = Vec::new();
|
|
for (name, value) in items.iter() {
|
|
vec_dedup_add(&mut vec_entries, name.clone(), *value);
|
|
}
|
|
|
|
let mut hm_entries = Vec::new();
|
|
let mut hm_index = HashMap::new();
|
|
for (name, value) in items.iter() {
|
|
hashmap_dedup_add(&mut hm_entries, &mut hm_index, name.clone(), *value);
|
|
}
|
|
|
|
assert_eq!(vec_entries.len(), hm_entries.len());
|
|
for (v, h) in vec_entries.iter().zip(hm_entries.iter()) {
|
|
assert_eq!(v.0, h.0);
|
|
assert!((v.1 - h.1).abs() < f32::EPSILON);
|
|
}
|
|
}
|
|
|
|
#[test]
|
|
fn test_performance_ratio() {
|
|
// Simulate N=1300 unique items (Veloren item count) with repeated adds
|
|
let n = 1300;
|
|
let names: Vec<String> = (0..n).map(|i| format!("common.items.item_{}", i)).collect();
|
|
|
|
// Defective: Vec linear scan
|
|
let start = Instant::now();
|
|
let mut vec_entries = Vec::new();
|
|
for name in names.iter() {
|
|
vec_dedup_add(&mut vec_entries, name.clone(), 1.0);
|
|
}
|
|
// Second pass (simulating recipe processing)
|
|
for name in names.iter() {
|
|
vec_dedup_add(&mut vec_entries, name.clone(), 0.5);
|
|
}
|
|
let vec_time = start.elapsed();
|
|
|
|
// Fixed: HashMap index
|
|
let start = Instant::now();
|
|
let mut hm_entries = Vec::new();
|
|
let mut hm_index = HashMap::new();
|
|
for name in names.iter() {
|
|
hashmap_dedup_add(&mut hm_entries, &mut hm_index, name.clone(), 1.0);
|
|
}
|
|
for name in names.iter() {
|
|
hashmap_dedup_add(&mut hm_entries, &mut hm_index, name.clone(), 0.5);
|
|
}
|
|
let hm_time = start.elapsed();
|
|
|
|
let ratio = vec_time.as_nanos() as f64 / hm_time.as_nanos().max(1) as f64;
|
|
println!(
|
|
"veloren-0001: Vec O(N^2) = {:?}, HashMap O(N) = {:?}, ratio = {:.1}x",
|
|
vec_time, hm_time, ratio
|
|
);
|
|
|
|
// Vec scan should be measurably slower at N=1300
|
|
assert!(
|
|
ratio > 2.0,
|
|
"Expected significant speedup with HashMap index, got ratio {:.1}x",
|
|
ratio
|
|
);
|
|
assert_eq!(vec_entries.len(), hm_entries.len());
|
|
}
|
|
|
|
fn main() {
|
|
test_correctness();
|
|
test_performance_ratio();
|
|
println!("PASS");
|
|
}
|