overclocked_sort 0.1.1

pub mod key_ptr;
pub use key_ptr::{overclocked_kp_sort, KeyPtr};


/// Sắp xếp một dải giá trị số nguyên (lớn) với thời gian thực thi cực nhanh ($O(N + K)$ song song).
/// 
/// * `input`: Bất kỳ lát cắt tham chiếu `&[i32]` nào cần định hình.
/// * `max_val`: Giá trị lớn nhất mà mảng có. Vượt quá `max_val` có thể gây tràn Bucket (Panic).
pub fn overclocked_parallel_sort(input: &[i32], max_val: usize) -> Vec<i32> {
    let num_elements = input.len();
    if num_elements == 0 {
        return vec![];
    }
    
    // =========================================================================
    // 1. HEURISTIC CHECK (Kiểm tra mảng đã Sort)
    // =========================================================================
    // Lướt qua mảng với O(N). LLVM sẽ tự động "cán" đoạn này bằng lệnh SIMD
    // Nếu mảng đã được sort, nó sẽ trả về ngay lập tức (Chỉ tốn ~10ms cho 100 Triệu số)
    if input.windows(2).all(|w| w[0] <= w[1]) {
        return input.to_vec();
    }
    
    // Auto-tuning: Tự động phát hiện số lượng core vật lý của CPU
    let num_threads = std::thread::available_parallelism()
        .map(|n| n.get())
        .unwrap_or(4); 

    // =========================================================================
    // 2. SPARSE/DENSE ADAPTIVITY (Chống Bão L2 Cache & Bùng nổ RAM)
    // =========================================================================
    // Đánh giá khối lượng Ma trận Bucket: Mật độ (threads * max_val * 8 bytes)
    let bucket_mem_bytes = num_threads.saturating_mul(max_val).saturating_mul(8);
    
    // Kích hoạt Fallback về Cấu trúc Comparison-Sort (O(N log N) In-place) NẾU:
    // - Ma trận đếm ngốn quá ngưỡng ~512 MB RAM (Đánh nát L3 Cache & TLB).
    // - Sparse Data: Cấp biên độ M > N (Số lượng hộp đựng lớn hơn số lượng hạt).
    if bucket_mem_bytes > 512_000_000 || max_val > num_elements {
        let mut fallback_vec = input.to_vec();
        fallback_vec.sort_unstable(); // Delegate về O(N log N) của Pattern-defeating Quicksort
        return fallback_vec;
    }

    let chunk_sz = num_elements / num_threads;
    
    // Bước 1: Tính toán "buồng" (Cache-Oblivious/Cache-Aware Blocking)
    let mut local_buckets = vec![vec![0usize; max_val + 1]; num_threads];
    
    std::thread::scope(|s| {
        for (i, bucket) in local_buckets.iter_mut().enumerate() {
            let start = i * chunk_sz;
            let end = if i == num_threads - 1 { num_elements } else { (i + 1) * chunk_sz };
            
            s.spawn(move || {
                // Giả định L2 Cache của CPU hiện đại cỡ 256KB -> 512KB. 
                const L2_CACHE_BLOCK_SIZE: usize = 256_000; 
                
                let mut idx = start;
                while idx < end {
                    let block_end = std::cmp::min(idx + L2_CACHE_BLOCK_SIZE, end);
                    for &x in &input[idx..block_end] {
                        bucket[x as usize] += 1;
                    }
                    idx = block_end;
                }
            });
        }
    });

    // Bước 2: Prefix-Sum (Scan) để tính toán Offset
    let mut global_offsets = vec![0usize; max_val + 2];
    let mut current_offset = 0;
    
    struct WriteJob {
        offset: usize,
        count: usize,
        val: i32,
    }
    let mut write_jobs = Vec::new();
    let max_job_size = 500_000; 
    
    for val in 1..=max_val {
        global_offsets[val] = current_offset;
        let mut count = 0;
        for t in 0..num_threads {
            count += local_buckets[t][val];
        }
        
        if count == 0 { continue; }
        
        let mut remaining = count;
        while remaining > 0 {
            let job_count = std::cmp::min(remaining, max_job_size);
            write_jobs.push(WriteJob {
                offset: current_offset,
                count: job_count,
                val: val as i32,
            });
            current_offset += job_count;
            remaining -= job_count;
        }
    }

    // Bước 3: Build buffer & Dynamic Work Stealing Parallel Write
    let mut result_vec = vec![0i32; num_elements];
    let result_ptr = result_vec.as_mut_ptr() as usize;

    let job_counter = std::sync::atomic::AtomicUsize::new(0);
    let jobs_ref = &write_jobs;

    std::thread::scope(|s| {
        for _ in 0..num_threads {
            s.spawn(|| {
                loop {
                    let idx = job_counter.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
                    if idx >= jobs_ref.len() { break; }
                    
                    let job = &jobs_ref[idx];
                    unsafe {
                        let ptr = (result_ptr as *mut i32).add(job.offset);
                        std::slice::from_raw_parts_mut(ptr, job.count).fill(job.val);
                    }
                }
            });
        }
    });
    
    result_vec
}