More efficient way to iterate through columns of flattened 2D Vec

Reading data column by column is going to be slow no matter what you do, since you will be jumping in memory. Computing the indexes is noise compared to that.

Is there a more efficient way to do this?

One idea is putting bits together to reduce memory by 8. Another is keeping your data column by column and only update when required (this depends on your access patterns).

You could preload the indexes so then you just need to iterate over them. Which may be more efficient in time but not in space:

fn preload_indexes(row_size: usize, column_size: usize) -> Vec<usize> {
    let mut indexes = Vec::new();
    for x in 0..row_size {
        for y in 0..column_size {
            let i = y*row_size+x;
            indexes.push(i);
        }
    }
    indexes
}

As a full example:

use std::fmt::Display;

struct Matrix<T: Display> {
    row_size: usize,
    column_size: usize,
    data: Vec<T>,
    columns_indexes: Vec<usize>,
}


fn preload_indexes(row_size: usize, column_size: usize) -> Vec<usize> {
    let mut indexes = Vec::new();
    for x in 0..row_size {
        for y in 0..column_size {
            let i = y*row_size+x;
            indexes.push(i);
        }
    }
    indexes
}

impl<T: Display> Matrix<T> {
    fn new(data: Vec<T>, row_size: usize, column_size: usize) -> Self {
        assert_eq!(data.len(), row_size*column_size);
        
        Self {
            row_size,
            column_size,
            data,
            columns_indexes: preload_indexes(row_size, column_size),
        }
    }
    
    fn print_rows(&self) {
        for e in self.data.iter() {
            println!("{}", e);
        }
    }
    
    fn print_columns(&self) {
        for i in self.columns_indexes.iter() {
            println!("{}", self.data[*i]);
        }
    }
}


fn main() {
    let matrix = Matrix::new(vec![1, 2, 3, 4], 2, 2);
    println!("Rows");
    matrix.print_rows();
    println!("Columns");
    matrix.print_columns();
}

Playground

Playing around your example, I was very surprised to see that the index computation (y*width+x) does not seem to be simplified by the optimiser. Moreover, I though the memory access was much more significant than the removed multiplication in index computation. But when it comes to timing I can see a substantial difference (with various grid sizes and true/false initialisations).

edit

After reading some comments below, I compared the two versions, _v1 and _v2, in the compiler explorer (godbolt). They look very similar except that _v1 uses the lea instruction and _v2 uses add and inc instead. According to vtune-amplifier, most of the time of _v1 is spent on this exact lea instruction. So, at least on my computer, and on this specific example, and counter-intuitively, the choice of lea instead of add and inc seems more detrimental than the irregular memory access pattern.

/*
  $ rustc -C opt-level=3 prog.rs && ./prog
  avg1=50.5
    v1: 4453 ms
  avg2=50.5
    v2: 2361 ms
*/

pub struct Board {
    width: usize,
    height: usize,
    data: Vec<bool>,
}

impl Board {
    pub fn new(
        width: usize,
        height: usize,
    ) -> Self {
        Self {
            width,
            height,
            data: vec![false; width * height],
        }
    }

    pub fn calc_avg_height_v1(&self) -> f32 {
        let mut heights = 0;
        for x in 0..self.width {
            for y in 0..self.height {
                if self.data[(y * self.width) + x] {
                    heights += self.height - y;
                    break;
                }
            }
        }
        heights as f32 / self.width as f32
    }

    pub fn calc_avg_height_v2(&self) -> f32 {
        let mut heights = 0;
        for x in 0..self.width {
            let mut idx = x;
            for y in 0..self.height {
                if self.data[idx] {
                    heights += self.height - y;
                    break;
                }
                idx += self.width;
            }
        }
        heights as f32 / self.width as f32
    }
}

pub fn run<F>(
    name: &str,
    repeat: usize,
    fnct: F,
) -> u128
where
    F: Fn() -> f32,
{
    let mut prev = -1.0_f32;
    let warmup = repeat / 10;
    for _ in 0..warmup {
        let avg = fnct();
        if avg != prev {
            println!("{}={}", name, avg);
            prev = avg;
        }
    }
    let now = std::time::Instant::now();
    for _ in 0..repeat {
        let avg = fnct();
        if avg != prev {
            println!("{}={}", name, avg);
            prev = avg;
        }
    }
    now.elapsed().as_millis()
}

pub fn main() {
    let mut board = Board::new(100, 100);
    for y in 0..board.height {
        for x in 0..board.width {
            board.data[y * board.width + x] = x == y;
        }
    }
    let repeat = 1_000_000;
    println!(
        "  v1: {} ms",
        run("avg1", repeat, || board.calc_avg_height_v1())
    );
    println!(
        "  v2: {} ms",
        run("avg2", repeat, || board.calc_avg_height_v2())
    );
}