overclocked_sort 0.2.1

use overclocked_sort::{overclocked_kp_sort, KeyPtr};
use std::time::Instant;

struct Lcg { seed: u64 }
impl Lcg {
    fn next(&mut self) -> u32 {
        self.seed = self.seed.wrapping_mul(6364136223846793005).wrapping_add(1);
        (self.seed >> 32) as u32
    }
}

fn main() {
    println!("=== SO SÁNH OVERCLOCKED SỬ DỤNG CẤU TRÚC OBJECT (KEY-POINTER) ===");
    
    let mut rng = Lcg { seed: 987654321 };
    let n = 20_000_000;
    let max_val = 100_000;
    
    println!("\n[1] Chuẩn bị Data: N = {}, M = {} ({} bytes/Struct)", n, max_val, std::mem::size_of::<KeyPtr>());
    println!("-> Cập nhật cấu trúc từ integer sang Key-Ptr (Scatter Memory)");
    
    let mut data = Vec::with_capacity(n);
    for i in 0..n {
        data.push(KeyPtr {
            key: (rng.next() % (max_val as u32 + 1)) as i32,
            ptr: i as u64, // Mô phỏng Pointer hoặc Index gốc
        });
    }
    
    let mut data_clone_pdq = data.clone();
    let mut data_clone_stable = data.clone();
    
    // ---------------------------------------------------------
    // 1. Overclocked KP Sort (Parallel Prefix-Sum Scatter)
    // ---------------------------------------------------------
    println!("\n▶ Đang chạy: Overclocked KP Sort (Multi-threading + Buffer Scatter)");
    let start = Instant::now();
    let result_overclocked = overclocked_kp_sort(&data, max_val);
    let elapsed_ovc = start.elapsed();
    
    // ---------------------------------------------------------
    // 2. std::sort_unstable_by_key (In-place C++ PDQ)
    // ---------------------------------------------------------
    println!("▶ Đang chạy: std::sort_unstable_by_key (Single-threaded PDQ-Sort)");
    let start = Instant::now();
    data_clone_pdq.sort_unstable_by_key(|kp| kp.key);
    let elapsed_pdq = start.elapsed();
    
    // ---------------------------------------------------------
    // Validate kết quả
    // ---------------------------------------------------------
    assert_eq!(result_overclocked.len(), n, "Missing elements!");
    for i in 1..n {
        assert!(result_overclocked[i - 1].key <= result_overclocked[i].key, "Lỗi phân loại!");
    }
    
    println!("\n======================================");
    println!("⏱ KẾT QUẢ BENCHMARK (KEY-PTR OBJECT)");
    println!("======================================");
    println!("🚀 Overclocked KP:\t {:?}", elapsed_ovc);
    println!("🐢 std::sort_unstable:\t {:?}", elapsed_pdq);
    println!("⚡ Hệ số khuếch đại:\t {:.2}x nhanh hơn", elapsed_pdq.as_secs_f64() / elapsed_ovc.as_secs_f64());
}