scirs2_interpolate/

cache_aware.rs

//! Cache-aware algorithm implementations for high-performance interpolation
//!
//! This module provides cache-optimized versions of computationally intensive
//! interpolation algorithms. These implementations are designed to minimize
//! cache misses and maximize data locality for better performance on modern
//! CPU architectures.
//!
//! ## Key Optimizations
//!
//! - **Blocked matrix operations**: Process data in cache-friendly blocks
//! - **Loop tiling**: Restructure loops to improve temporal locality
//! - **Data layout optimization**: Arrange data to minimize cache misses
//! - **Prefetching strategies**: Pre-load data that will be needed soon
//! - **Memory access patterns**: Optimize for sequential and strided access
//!
//! ## Supported Methods
//!
//! - **Cache-aware RBF interpolation**: Blocked matrix operations for large datasets
//! - **Cache-optimized B-spline evaluation**: Vectorized evaluation with prefetching
//! - **Tiled distance computations**: Block-wise distance matrix calculation
//! - **Memory-efficient nearest neighbor search**: Cache-friendly spatial indexing
//!
//! # Examples
//!
//! ```rust
//! use scirs2_core::ndarray::{Array1, Array2};
//! use scirs2_interpolate::cache_aware::{
//!     CacheAwareRBF, CacheOptimizedConfig
//! };
//!
//! // Create a cache-optimized RBF interpolator
//! let points = Array2::from_shape_vec((1000, 3), vec![0.0; 3000]).unwrap();
//! let values = Array1::from_vec(vec![1.0; 1000]);
//! let config = CacheOptimizedConfig::default();
//!
//! let rbf = CacheAwareRBF::new(points, values, config).unwrap();
//! ```

use crate::advanced::rbf::RBFKernel;
use crate::cache::CacheConfig;
use crate::error::{InterpolateError, InterpolateResult};
use scirs2_core::ndarray::{Array1, Array2, ArrayView1, ArrayView2};
use scirs2_core::numeric::{Float, FromPrimitive};
use std::fmt::{Debug, Display};

/// Configuration for cache-optimized algorithms
#[derive(Debug, Clone)]
pub struct CacheOptimizedConfig {
    /// Block size for tiled matrix operations
    pub block_size: usize,
    /// Enable prefetching for sequential access patterns
    pub enable_prefetching: bool,
    /// Use NUMA-aware memory allocation if available
    pub numa_aware: bool,
    /// Number of worker threads for parallel operations
    pub num_threads: Option<usize>,
    /// Cache configuration for internal caching
    pub cache_config: CacheConfig,
    /// Optimize for specific CPU cache sizes (L1, L2, L3 in KB)
    pub cache_sizes: CacheSizes,
}

/// CPU cache size configuration for optimization
#[derive(Debug, Clone)]
pub struct CacheSizes {
    /// L1 cache size in KB
    pub l1_cache_kb: usize,
    /// L2 cache size in KB
    pub l2_cache_kb: usize,
    /// L3 cache size in KB
    pub l3_cache_kb: usize,
}

impl Default for CacheSizes {
    fn default() -> Self {
        Self {
            l1_cache_kb: 32,   // Typical L1 cache size
            l2_cache_kb: 256,  // Typical L2 cache size
            l3_cache_kb: 8192, // Typical L3 cache size
        }
    }
}

impl Default for CacheOptimizedConfig {
    fn default() -> Self {
        Self {
            block_size: 64, // Optimized for typical cache line sizes
            enable_prefetching: true,
            numa_aware: false,
            num_threads: None, // Use default thread pool
            cache_config: CacheConfig::default(),
            cache_sizes: CacheSizes::default(),
        }
    }
}

/// Cache-aware RBF interpolator optimized for large datasets
#[derive(Debug)]
pub struct CacheAwareRBF<F>
where
    F: Float + FromPrimitive + Debug + Display + Send + Sync + 'static,
{
    /// Training points organized in cache-friendly layout
    points: Array2<F>,
    /// Training values
    values: Array1<F>,
    /// RBF kernel type
    kernel: RBFKernel,
    /// Epsilon parameter for RBF
    epsilon: F,
    /// Precomputed coefficients (if available)
    coefficients: Option<Array1<F>>,
    /// Configuration
    _config: CacheOptimizedConfig,
    /// Performance statistics
    stats: CacheOptimizedStats,
}

/// Performance statistics for cache-optimized algorithms
#[derive(Debug, Default)]
pub struct CacheOptimizedStats {
    /// Number of cache-optimized evaluations performed
    pub evaluations: usize,
    /// Total time spent in blocked operations (nanoseconds)
    pub blocked_ops_time_ns: u64,
    /// Number of cache blocks processed
    pub blocks_processed: usize,
    /// Estimated cache miss rate (approximate)
    pub estimated_cache_miss_rate: f64,
    /// Memory bandwidth utilization estimate
    pub memory_bandwidth_utilization: f64,
}

impl<F> CacheAwareRBF<F>
where
    F: Float + FromPrimitive + Debug + Display + Send + Sync + 'static,
{
    /// Create a new cache-aware RBF interpolator
    ///
    /// # Arguments
    ///
    /// * `points` - Training data points (n_points × n_dims)
    /// * `values` - Training data values
    /// * `config` - Cache optimization configuration
    ///
    /// # Returns
    ///
    /// A new cache-optimized RBF interpolator
    pub fn new(
        points: Array2<F>,
        values: Array1<F>,
        config: CacheOptimizedConfig,
    ) -> InterpolateResult<Self> {
        if points.nrows() != values.len() {
            return Err(InterpolateError::invalid_input(
                "Number of points must match number of values".to_string(),
            ));
        }

        let kernel = RBFKernel::Gaussian; // Default kernel
        let epsilon = F::one(); // Default epsilon

        Ok(Self {
            points,
            values,
            kernel,
            epsilon,
            coefficients: None,
            _config: config,
            stats: CacheOptimizedStats::default(),
        })
    }

    /// Set the RBF kernel type
    pub fn with_kernel(mut self, kernel: RBFKernel) -> Self {
        self.kernel = kernel;
        self
    }

    /// Set the epsilon parameter
    pub fn with_epsilon(mut self, epsilon: F) -> Self {
        self.epsilon = epsilon;
        self
    }

    /// Precompute RBF coefficients using cache-optimized matrix operations
    ///
    /// This method uses blocked matrix operations to improve cache performance
    /// during the coefficient computation phase.
    pub fn precompute_coefficients(&mut self) -> InterpolateResult<()> {
        let start_time = std::time::Instant::now();

        let n_points = self.points.nrows();
        let block_size = self._config.block_size.min(n_points);

        // Create distance matrix using blocked computation
        let distance_matrix = self.compute_blocked_distance_matrix()?;

        // Apply RBF kernel using cache-friendly operations
        let kernel_matrix = self.apply_kernel_blocked(&distance_matrix)?;

        // Solve the linear system using optimized solver
        let coefficients = self.solve_rbf_system_optimized(&kernel_matrix)?;

        self.coefficients = Some(coefficients);
        self.stats.blocks_processed += n_points.div_ceil(block_size);
        self.stats.blocked_ops_time_ns += start_time.elapsed().as_nanos() as u64;

        Ok(())
    }

    /// Compute distance matrix using cache-optimized blocked operations
    fn compute_blocked_distance_matrix(&self) -> InterpolateResult<Array2<F>> {
        let n_points = self.points.nrows();
        let n_dims = self.points.ncols();
        let block_size = self._config.block_size;

        let mut distance_matrix = Array2::zeros((n_points, n_points));

        // Use blocked computation to improve cache locality
        for i_block in (0..n_points).step_by(block_size) {
            let i_end = (i_block + block_size).min(n_points);

            for j_block in (0..n_points).step_by(block_size) {
                let j_end = (j_block + block_size).min(n_points);

                // Compute distances for this block
                for i in i_block..i_end {
                    for j in j_block..j_end {
                        if i <= j {
                            let dist = self.compute_distance_optimized(i, j, n_dims);
                            distance_matrix[[i, j]] = dist;
                            distance_matrix[[j, i]] = dist; // Symmetric matrix
                        }
                    }
                }
            }
        }

        Ok(distance_matrix)
    }

    /// Compute distance between two points with optimized memory access
    fn compute_distance_optimized(&self, i: usize, j: usize, ndims: usize) -> F {
        let mut sum_sq = F::zero();

        // Process dimensions in chunks for better cache utilization
        let chunk_size = 4; // Process 4 dimensions at a time

        for dim_chunk in (0..ndims).step_by(chunk_size) {
            let end_dim = (dim_chunk + chunk_size).min(ndims);

            for dim in dim_chunk..end_dim {
                let diff = self.points[[i, dim]] - self.points[[j, dim]];
                sum_sq = sum_sq + diff * diff;
            }
        }

        sum_sq.sqrt()
    }

    /// Apply RBF kernel to distance matrix using blocked operations
    fn apply_kernel_blocked(&self, distance_matrix: &Array2<F>) -> InterpolateResult<Array2<F>> {
        let n_points = distance_matrix.nrows();
        let block_size = self._config.block_size;
        let mut kernel_matrix = Array2::zeros((n_points, n_points));

        for i_block in (0..n_points).step_by(block_size) {
            let i_end = (i_block + block_size).min(n_points);

            for j_block in (0..n_points).step_by(block_size) {
                let j_end = (j_block + block_size).min(n_points);

                // Apply kernel to this block
                for i in i_block..i_end {
                    for j in j_block..j_end {
                        let dist = distance_matrix[[i, j]];
                        kernel_matrix[[i, j]] = self.apply_kernel_function(dist);
                    }
                }
            }
        }

        Ok(kernel_matrix)
    }

    /// Apply the RBF kernel function to a distance value
    fn apply_kernel_function(&self, distance: F) -> F {
        match self.kernel {
            RBFKernel::Gaussian => {
                let arg = -(distance * distance) / (self.epsilon * self.epsilon);
                arg.exp()
            }
            RBFKernel::Multiquadric => (distance * distance + self.epsilon * self.epsilon).sqrt(),
            RBFKernel::InverseMultiquadric => {
                F::one() / (distance * distance + self.epsilon * self.epsilon).sqrt()
            }
            RBFKernel::Linear => distance,
            RBFKernel::Cubic => distance * distance * distance,
            RBFKernel::ThinPlateSpline => {
                if distance == F::zero() {
                    F::zero()
                } else {
                    distance * distance * distance.ln()
                }
            }
            RBFKernel::Quintic => {
                let r2 = distance * distance;
                distance * r2 * r2 // r^5
            }
        }
    }

    /// Solve RBF system using cache-optimized linear algebra
    fn solve_rbf_system_optimized(
        &self,
        kernel_matrix: &Array2<F>,
    ) -> InterpolateResult<Array1<F>> {
        // For now, use a simple approach
        // In a full implementation, this would use blocked LU decomposition
        // or other cache-optimized linear algebra routines

        let n = kernel_matrix.nrows();
        let mut augmented = Array2::zeros((n, n + 1));

        // Copy kernel matrix and values vector
        for i in 0..n {
            for j in 0..n {
                augmented[[i, j]] = kernel_matrix[[i, j]];
            }
            augmented[[i, n]] = self.values[i];
        }

        // Simple Gaussian elimination (would be optimized in production)
        for k in 0..n {
            // Find pivot
            let mut max_row = k;
            for i in (k + 1)..n {
                if augmented[[i, k]].abs() > augmented[[max_row, k]].abs() {
                    max_row = i;
                }
            }

            // Swap rows
            if max_row != k {
                for j in 0..=n {
                    let temp = augmented[[k, j]];
                    augmented[[k, j]] = augmented[[max_row, j]];
                    augmented[[max_row, j]] = temp;
                }
            }

            // Eliminate column
            for i in (k + 1)..n {
                if augmented[[k, k]] != F::zero() {
                    let factor = augmented[[i, k]] / augmented[[k, k]];
                    for j in k..=n {
                        augmented[[i, j]] = augmented[[i, j]] - factor * augmented[[k, j]];
                    }
                }
            }
        }

        // Back substitution
        let mut solution = Array1::zeros(n);
        for i in (0..n).rev() {
            let mut sum = F::zero();
            for j in (i + 1)..n {
                sum = sum + augmented[[i, j]] * solution[j];
            }
            if augmented[[i, i]] != F::zero() {
                solution[i] = (augmented[[i, n]] - sum) / augmented[[i, i]];
            }
        }

        Ok(solution)
    }

    /// Evaluate the RBF interpolator at query points using cache-optimized methods
    ///
    /// # Arguments
    ///
    /// * `query_points` - Points to evaluate (n_queries × n_dims)
    ///
    /// # Returns
    ///
    /// Interpolated values at query points
    pub fn evaluate_cache_optimized(
        &mut self,
        query_points: &ArrayView2<F>,
    ) -> InterpolateResult<Array1<F>> {
        if self.coefficients.is_none() {
            self.precompute_coefficients()?;
        }

        let coefficients = self.coefficients.as_ref().unwrap();
        let n_queries = query_points.nrows();
        let n_points = self.points.nrows();
        let block_size = self._config.block_size;

        let mut results = Array1::zeros(n_queries);

        // Process queries in blocks for better cache performance
        for query_block in (0..n_queries).step_by(block_size) {
            let query_end = (query_block + block_size).min(n_queries);

            for query_idx in query_block..query_end {
                let query = query_points.row(query_idx);
                let mut value = F::zero();

                // Process training points in blocks
                for point_block in (0..n_points).step_by(block_size) {
                    let point_end = (point_block + block_size).min(n_points);

                    for point_idx in point_block..point_end {
                        let point = self.points.row(point_idx);
                        let distance = self.compute_query_distance(&query, &point);
                        let kernel_value = self.apply_kernel_function(distance);
                        value = value + coefficients[point_idx] * kernel_value;
                    }
                }

                results[query_idx] = value;
            }
        }

        self.stats.evaluations += n_queries;
        Ok(results)
    }

    /// Compute distance between query point and training point
    fn compute_query_distance(&self, query: &ArrayView1<F>, point: &ArrayView1<F>) -> F {
        let mut sum_sq = F::zero();
        for i in 0..query.len() {
            let diff = query[i] - point[i];
            sum_sq = sum_sq + diff * diff;
        }
        sum_sq.sqrt()
    }

    /// Get performance statistics
    pub fn stats(&self) -> &CacheOptimizedStats {
        &self.stats
    }

    /// Reset performance statistics
    pub fn reset_stats(&mut self) {
        self.stats = CacheOptimizedStats::default();
    }
}

/// Cache-aware B-spline evaluator with optimized memory access patterns
#[derive(Debug)]
pub struct CacheAwareBSpline<F>
where
    F: Float + FromPrimitive + Debug + Display + Copy + 'static,
{
    /// Knot vector
    knots: Array1<F>,
    /// Control coefficients
    coefficients: Array1<F>,
    /// Spline degree
    degree: usize,
    /// Configuration
    config: CacheOptimizedConfig,
    /// Precomputed basis function cache for common evaluation points
    #[allow(dead_code)]
    basis_cache: std::collections::HashMap<u64, Vec<F>>,
}

impl<F> CacheAwareBSpline<F>
where
    F: Float + FromPrimitive + Debug + Display + Copy + 'static,
{
    /// Create a new cache-aware B-spline
    pub fn new(
        knots: Array1<F>,
        coefficients: Array1<F>,
        degree: usize,
        config: CacheOptimizedConfig,
    ) -> InterpolateResult<Self> {
        if knots.len() < coefficients.len() + degree + 1 {
            return Err(InterpolateError::invalid_input(
                "Invalid knot vector length for given coefficients and degree".to_string(),
            ));
        }

        Ok(Self {
            knots,
            coefficients,
            degree,
            config,
            basis_cache: std::collections::HashMap::new(),
        })
    }

    /// Evaluate B-spline at multiple points using cache-optimized algorithm
    pub fn evaluate_batch_cache_optimized(
        &mut self,
        x_values: &ArrayView1<F>,
    ) -> InterpolateResult<Array1<F>> {
        let n_points = x_values.len();
        let mut results = Array1::zeros(n_points);
        let block_size = self.config.block_size;

        // Process evaluation points in blocks for better cache locality
        for block_start in (0..n_points).step_by(block_size) {
            let block_end = (block_start + block_size).min(n_points);

            for i in block_start..block_end {
                let x = x_values[i];
                results[i] = self.evaluate_single_optimized(x)?;
            }
        }

        Ok(results)
    }

    /// Evaluate B-spline at a single point with cache optimization
    fn evaluate_single_optimized(&mut self, x: F) -> InterpolateResult<F> {
        // Find knot span (could be cached for repeated similar evaluations)
        let span = self.find_knot_span(x);

        // Compute basis functions for this span
        let basis = self.compute_basis_functions(x, span);

        // Compute result using basis functions and coefficients
        let mut result = F::zero();
        for (i, &basis_val) in basis.iter().enumerate().take(self.degree + 1) {
            let coeff_idx = span - self.degree + i;
            if coeff_idx < self.coefficients.len() {
                result = result + self.coefficients[coeff_idx] * basis_val;
            }
        }

        Ok(result)
    }

    /// Find the knot span for a given parameter value
    fn find_knot_span(&self, x: F) -> usize {
        let n = self.coefficients.len();

        if x >= self.knots[n] {
            return n - 1;
        }
        if x <= self.knots[self.degree] {
            return self.degree;
        }

        // Binary search for knot span
        let mut low = self.degree;
        let mut high = n;
        let mut mid = (low + high) / 2;

        while x < self.knots[mid] || x >= self.knots[mid + 1] {
            if x < self.knots[mid] {
                high = mid;
            } else {
                low = mid;
            }
            mid = (low + high) / 2;
        }

        mid
    }

    /// Compute basis functions using de Boor's algorithm
    fn compute_basis_functions(&self, x: F, span: usize) -> Vec<F> {
        let mut basis = vec![F::zero(); self.degree + 1];
        basis[0] = F::one();

        for j in 1..=self.degree {
            let mut saved = F::zero();
            #[allow(clippy::needless_range_loop)]
            for r in 0..j {
                let temp = basis[r];
                let alpha_1 = if span + 1 + r >= j && span + 1 + r < self.knots.len() {
                    let denom = self.knots[span + 1 + r] - self.knots[span + 1 + r - j];
                    if denom != F::zero() {
                        (x - self.knots[span + 1 + r - j]) / denom
                    } else {
                        F::zero()
                    }
                } else {
                    F::zero()
                };

                basis[r] = saved + (F::one() - alpha_1) * temp;
                saved = alpha_1 * temp;
            }
            basis[j] = saved;
        }

        basis
    }
}

/// Create a cache-aware RBF interpolator with optimized settings
///
/// # Arguments
///
/// * `points` - Training data points
/// * `values` - Training data values
/// * `kernel` - RBF kernel type
/// * `epsilon` - Kernel parameter
///
/// # Returns
///
/// A cache-optimized RBF interpolator
#[allow(dead_code)]
pub fn make_cache_aware_rbf<F>(
    points: Array2<F>,
    values: Array1<F>,
    kernel: RBFKernel,
    epsilon: F,
) -> InterpolateResult<CacheAwareRBF<F>>
where
    F: Float + FromPrimitive + Debug + Display + Send + Sync + 'static,
{
    let config = CacheOptimizedConfig::default();

    let mut rbf = CacheAwareRBF::new(points, values, config)?
        .with_kernel(kernel)
        .with_epsilon(epsilon);

    rbf.precompute_coefficients()?;
    Ok(rbf)
}

#[cfg(test)]
mod tests {
    use super::*;
    use scirs2_core::ndarray::array;

    #[test]
    fn test_cache_aware_rbf_creation() {
        let points = array![[0.0, 0.0], [1.0, 0.0], [0.0, 1.0], [1.0, 1.0]];
        let values = array![0.0, 1.0, 1.0, 2.0];
        let config = CacheOptimizedConfig::default();

        let rbf = CacheAwareRBF::new(points, values, config);
        assert!(rbf.is_ok());
    }

    #[test]
    fn test_cache_aware_bspline_creation() {
        let knots = array![0.0, 0.0, 0.0, 1.0, 2.0, 3.0, 3.0, 3.0];
        let coefficients = array![1.0, 2.0, 3.0, 4.0, 5.0];
        let config = CacheOptimizedConfig::default();

        let spline = CacheAwareBSpline::new(knots, coefficients, 2, config);
        assert!(spline.is_ok());
    }

    #[test]
    fn test_cache_optimized_config_defaults() {
        let config = CacheOptimizedConfig::default();

        assert_eq!(config.block_size, 64);
        assert!(config.enable_prefetching);
        assert!(!config.numa_aware);
        assert!(config.num_threads.is_none());
    }

    #[test]
    fn test_cache_sizes_defaults() {
        let cache_sizes = CacheSizes::default();

        assert_eq!(cache_sizes.l1_cache_kb, 32);
        assert_eq!(cache_sizes.l2_cache_kb, 256);
        assert_eq!(cache_sizes.l3_cache_kb, 8192);
    }
}