overclocked_sort 0.2.1

use std::time::Instant;

#[derive(Clone, Eq, PartialEq)]
pub struct ComplexData {
    pub category: u16,     // Tiêu chí sắp xếp 1 (VD: Mã phòng ban)
    pub priority: u16,     // Tiêu chí sắp xếp 2 (VD: Mức độ ưu tiên)
    pub padding: [u64; 4], // Data rác để cấu trúc phình to ra (36 Bytes) - Mô phỏng Object nặng
}

// Sinh số ngẫu nhiên
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() {
    let n = 5_000_000;
    let mut rng = Lcg { seed: 999 };
    
    let mut data = Vec::with_capacity(n);
    for _ in 0..n {
        data.push(ComplexData {
            category: (rng.next() % 1000) as u16,
            priority: (rng.next() % 5000) as u16,
            padding: [0, 0, 0, 0],
        });
    }

    println!("Tạo {} elements ComplexData ({} bytes/struct).", n, std::mem::size_of::<ComplexData>());
    
    let mut d1 = data.clone();
    let mut d2 = data.clone();
    let mut d3 = data.clone();

    // ====================================================================
    // PHƯƠNG PHÁP 1: Dùng hàm so sánh chuẩn (Custom CMP - .then)
    // ====================================================================
    println!("\n▶ 1. Chạy std::sort_unstable_by (Sử dụng hàm CMP: a.cmp(b) then c.cmp(d))");
    let start = Instant::now();
    // Hàm cmp() nối tiếp: So sánh Category -> Bằng nhau thì so sánh tiếp Priority
    d1.sort_unstable_by(|a, b| {
        a.category.cmp(&b.category).then(a.priority.cmp(&b.priority))
    });
    println!("⏱ Thời gian: {:?}", start.elapsed());

    // ====================================================================
    // PHƯƠNG PHÁP 2: Dùng Tuple Key (sort_by_key trả về cấu trúc Tuple)
    // ====================================================================
    println!("\n▶ 2. Chạy std::sort_unstable_by_key (Trả về Tuple: (category, priority))");
    let start = Instant::now();
    d2.sort_unstable_by_key(|item| (item.category, item.priority));
    println!("⏱ Thời gian: {:?}", start.elapsed());

    // ====================================================================
    // PHƯƠNG PHÁP 3: Thiết lập Key nguyên khối (Pack Integer Key)
    // ====================================================================
    println!("\n▶ 3. Chạy std::sort_unstable_by_key (Packed Integer Key 32-bit)");
    let start = Instant::now();
    // Gộp (Pack) 2 số u16 vào 1 số u32 (Shifting/Bitwise)
    // CPU so sánh 1 số u32 nhanh hơn rất nhiều so với kiểm tra phân nhánh Tuple hay IF-ELSE CMP
    d3.sort_unstable_by_key(|item| {
        ((item.category as u32) << 16) | (item.priority as u32)
    });
    println!("⏱ Thời gian: {:?}", start.elapsed());

    // Kiểm định kết quả
    assert_eq!(d1[0].category, d2[0].category);
    assert_eq!(d2[0].category, d3[0].category);
}