Intro

1. It creates a HashMap that stores arguments passed to the program.
2. It generates a random matrix using the generate_random_matrix function.
3. Then, it performs convolution on the matrix 100 times in both horizontal and vertical orientations and measures the time it takes for each.

For vertical conv it is also possible to first transpose the matrix to later convolve it with the given kernel. However I decided to just use a 1D contiguous array with index-ing functions.

To learn more about it read wiki

Add dependencies

cargo add rand

Build and run the project

cargo build && ./target/debug/convolution --rows 100 --cols 100

My setup

• OS: Arch Linux x86_64
• Kernel: 6.4.7-arch1-2
• CPU: AMD Ryzen 9 6900HS with Radeon Graphics (16) @ 3.300GHz
• rustc -- version: rustc 1.71.0 (8ede3aae2 2023-07-12)

Results

For 100 reps for 100x100 the results are:

• Horizontal average time 1359 over 100 reps
• Vertical average time 1301 over 100 reps

use std::{
    env, 
    collections::HashMap,
    fmt::Display,
    cmp::{
        min,
        max,
    },
    time,
};
use rand::{prelude::thread_rng, Rng, rngs::ThreadRng};

// Better create a 2D vector to store data
#[derive(Debug)]
struct Matrix 
{
    // Store as a contiguous array
    vector: Vec<u8>,
    row: usize,
    col: usize,

    // Store min/max
    min: u8,
    max: u8,
}

impl Matrix {
    // Constructor
    fn new(row: usize, col: usize) -> Matrix {
        let mut vec: Vec<u8> = Vec::with_capacity(row * col);
        for _ in 0..row * col {
            vec.push(0);
        }

        Self {
            vector: vec,
            row: row,
            col: col,
            min: u8::MAX,
            max: u8::MIN,
        }
    }

    // Index for immutable elements
    fn index(&self, row: usize, col: usize) -> &u8 {
        let index: usize = self.col * row;

        &self.vector[index + col]
    }

    // Index for mutable elements
    fn index_mut(&mut self, row: usize, col: usize) -> &mut u8 {
        let index: usize = self.col * row;

        &mut self.vector[index + col]
    }

    fn convolve(&self, kernel: &[i8], orientation: &String) -> Matrix {
        let mut convolved_matrix = Matrix::new(self.row, self.col);
        let mut row: usize = 0;
        let mut col: usize = 0;

        for matrix_index in 0..(self.row * self.col - 1) {
            // Move in either horizontal or vertical based on the division's 'whole' and 'remainder'
            if orientation == "horizontal" {
                row = matrix_index / self.row;
                col = matrix_index % self.col;    
            } else {
                row = matrix_index % self.row;
                col = matrix_index / self.col;    
            }
            
            let mut convolved_value: i32 = 0;

            for kernel_index in 0..kernel.len() {
                // Find mid to traverse the entire filter as in [-left; left] since the filter is simmetrical
                let midium: i32 = kernel.len() as i32 / 2; // it's left here for readability
                let current_kernel_position: i32 = -midium as i32 + kernel_index as i32;
                let mut current_matrix_element: i32 = 0;
                // Basically extract a sub-range in original matrix to further multiply below
                if orientation == "horizontal" {
                    let current_col_index: i8 = col as i8 + current_kernel_position as i8;

                    current_matrix_element = 
                        // 0 if it is out of range
                        if current_col_index < 0 || current_col_index >= self.col as i8 { 
                            0
                        } else { 
                            *self.index(row, current_col_index as usize) as i32
                        };
                } else {
                    let current_row_index: i8 = row as i8 + current_kernel_position as i8;

                    current_matrix_element = 
                        // 0 if it is out of scope
                        if current_row_index < 0 || current_row_index >= self.row as i8 {
                            0
                        } else {
                            *self.index(current_row_index as usize, col) as i32
                        };
                }
                        
                convolved_value += kernel[kernel_index] as i32 * current_matrix_element as i32;
            }
            
            convolved_value /= kernel.len() as i32;
            *convolved_matrix.index_mut(row, col) = min(convolved_value as u8, u8::MAX);
            convolved_matrix.min = min(convolved_matrix.min, convolved_value as u8);
            convolved_matrix.max = max(convolved_matrix.max, convolved_value as u8);
        }        
        
        convolved_matrix
    }
}

fn generate_random_matrix(rows: usize, cols: usize) -> Matrix {
    let mut matrix: Matrix = Matrix::new(rows as usize, cols as usize);

    let mut random_generator: ThreadRng = thread_rng();
    for index in 0..(rows * cols - 1) {
        let row = index / rows;
        let col = index % cols;
        *matrix.index_mut(row as usize, col as usize) = (random_generator.gen::<f32>() * u8::MAX as f32) as u8;
    }

    matrix
}

impl Display for Matrix {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let mut elements = String::new();

        // Push every element into the string
        for index in 0..(self.row * self.col - 1) {
            let row = index / self.row;
            let col = index % self.col;

            // if col == self.col - 1 {
            if index % self.col == 0 {
                elements.push_str("\n");
            }
            
            elements.push_str(&format!("{:?} ", &self.index(row, col)));
        }

        write!(f, "[{}]", elements)
    }
}
fn main() {
    // Collect all the args passed to the exectuable
    let args: Vec<String> = env::args().collect();
    let mut args_set: HashMap<String, String> = HashMap::with_capacity(2);

    // Store corresponding mappings, even though accessing HashMap is quite expensive
    // it should be ok for a small case
    for index in (1..args.len() - 1).step_by(1) {
        let arg_name = &args[index];
        let arg_value = &args[index + 1];
        args_set.insert(arg_name.to_string(), arg_value.to_string());
    }

    // Just print them to verify the code
    for (arg_name, arg_value) in &args_set {
        println!("{} - {}", arg_name, arg_value);
    }

    // Get a random matrix
    let cols: usize = args_set["--cols"].parse().unwrap(); 
    let rows: usize = args_set["--rows"].parse().unwrap();
    let started_time = time::Instant::now();
    let matrix = generate_random_matrix(cols, rows);
    let elapsed_time = time::Instant::now() - started_time;
    println!("{}\n - It took: {}", matrix, elapsed_time.as_micros());

    // Convolve with the given filter
    let filter: [i8; 3] = [-1, 0, 1];

    // Calculate some basic statistics
    let reps: u32 = 100;
    let mut time_horizontal = 0;
    let mut time_vertical = 0;
    for rep in 0..reps {
        let started_time = time::Instant::now();
        let convolved_matrix = matrix.convolve(&filter, &"horizontal".to_string());
        let elapsed_time_horizontal = time::Instant::now() - started_time;
        println!(" - Horizontal took {}, min = {}, max = {}", elapsed_time_horizontal.as_micros(), convolved_matrix.min, convolved_matrix.max);
        time_horizontal += elapsed_time_horizontal.as_micros();

        let started_time = time::Instant::now();
        let convolved_matrix = matrix.convolve(&filter, &"vertical".to_string());
        let elapsed_time_vertical = time::Instant::now() - started_time;
        println!(" - Vertical took {}, min = {}, max = {}", elapsed_time_vertical.as_micros(),convolved_matrix.min, convolved_matrix.max);
        time_vertical += elapsed_time_vertical.as_micros()
    }

    // Print average running time
    println!("Horizontal average time {} over {} reps", time_horizontal / reps as u128, reps);
    println!("Vertical average time {} over {} reps", time_vertical / reps as u128, reps);
}