Memory-friendly 2d array with variable-length rows

Hello everyone, I am looking for feedback and best practices (still learning Rust).

In my use case I have data with structure known on compile time, it's basically table with rows but each row length is different.

In most cases rows are short, but rarely they are pretty long.

So using max rows length for all the rows in 2d array is not efficient, there will be a lot of unused allocated memory.

Still, I don't want to use Vecs because I already know the data on compile time and want to go as static as possible.

So here is my first iteration of VariableRowArray collection.

pub struct VariableRowArray<T, const SIZE: usize, const ROWS: usize> {
    data: [T; SIZE],          // The main data array where rows are stored.
    index: [usize; ROWS],     // An index array to track the start of each row in the data array.
    num_rows: usize,          // The current number of rows in the array.
}

impl<T: Default + std::marker::Copy, const SIZE: usize, const ROWS: usize>
    VariableRowArray<T, SIZE, ROWS>
{
    // Create a new VariableRowArray with default values.
    pub fn new() -> Self {
        VariableRowArray {
            data: [T::default(); SIZE],
            index: [0; ROWS],
            num_rows: 0,
        }
    }

    pub fn add_row(&mut self, row: &[T]) {
        // Calculate the start index for the new row.
        let start = if self.num_rows > 0 {
            self.index[self.num_rows - 1]
        } else {
            0 // first row always has 0 start index so we don't track it
        };

        // Copy each element from the input row to the data array.
        for (i, &item) in row.iter().enumerate() {
            self.data[start + i] = item;
        }

        // Update the index array beforehand to mark the start of the row which will be added next time.
        // for last possible row will be used in get_row method only as end of slice.
        self.index[self.num_rows] = start + row.len();
        self.num_rows += 1; // Increment the number of rows.
    }

    pub fn get_row(&self, row_index: usize) -> Option<&[T]> {
        if row_index < self.num_rows {
            // Calculate the start and end indices of the requested row.
            let start = if row_index > 0 {
                self.index[row_index - 1]
            } else {
                0 // first row always has 0 start index so we don't track it
            };
            let end = self.index[row_index];
            
            // Return a reference to the slice containing the row's data.
            Some(&self.data[start..end])
        } else {
            None // Row index is out of bounds.
        }
    }

    // Get the current number of rows in the array.
    pub fn num_rows(&self) -> usize {
        self.num_rows
    }
}

usage:

fn main() {
    // Create a new VariableRowArray with a maximum data size of 9 elements
    // and support for up to 3 rows.
    let mut array: VariableRowArray<i32, 9, 3> = VariableRowArray::new();

    // Add rows to the array
    let row1 = [1, 2, 3];
    let row2 = [4, 5];
    let row3 = [6, 7, 8, 9];
    
    array.add_row(&row1);
    array.add_row(&row2);
    array.add_row(&row3);

    // Retrieve and print rows
    for i in 0..array.num_rows() {
        if let Some(row) = array.get_row(i) {
            println!("Row {}: {:?}", i, row);
        } else {
            println!("Row {} not found.", i);
        }
    }
}

It uses two arrays:

  • data - all the rows glued together without gaps so memory is allocated efficiently
  • index - to track each row position in the data array in order to access it quickly.

I use const generic prams to enforce user code define all the size on compile time (because it's my goal)
As I see I didn't introduce any more complexity compared to vanilla array, should work with very little overhead and compiler should be happy to optimize everything very well.

Please rate&suggest on above implementation. It feels for me like reinventing the wheel, maybe there is a crate for this?
Is it fine to return option from get_row or better to panic on out of range index?

This looks like a subset of the "compressed sparse row" (CSR) format used for sparse matrices in scientific computing; you may want to search for that expression for general ideas and practices.

1 Like

Thanks for pointing to interesting topic!

My specific use case seems to be much more prosaic:
each row will hold probabilistic distribution of graph node weight parameter, so I will pick various variants during my graph model simulations.

I guess CSR toolset is overkill here as I am simply picking random row element for each row(=node) in order to rate currently simulated scenario (and find optimal model parameters as a global goal) and starting leraning CSR world is not a priority for my project?

So from general-purpose collection perspective - does my approach seems correct/efficient?
Or still you would recommend to invest some time studying CSR in context of my use case?

I was not saying you should change your representation/implementation. You asked for more general advice on what to study in this context, and I merely provided that.

That said, your current implementation can be improved. It can be made simpler, more idiomatic, and faster, by using iterator methods and Option combinators instead of explicit indexing and checking. Playground.

1 Like

Omg, thanks a lot, will go read about such an approach as you demonstrated.

Note that you can use static slices if you want the usage ergonomics of a Vec of Vecs without allocation:

static array: &'static [&'static [i32]] = &[
  &[1, 2, 3],
  &[4, 5],
  &[6, 7, 8, 9],
];

fn iter_array() {
  for row in array {
    for item in row {
       ...
    }
  }
}

fn index_array() {
  let value = array[y][x];
  ...
}

The implementation is the static arrays for each row gets baked into the program, then the address and length of each row gets baked into the outer array. You can beat this, one simple option is storing a sentinel value like -1 to mark the end of the row, but it makes it expensive to jump to a specific row like the second example.

2 Likes

Thanks a lot for your reply, you challenged me with a lot of questions and research :slight_smile:
Let me ask, am I thinking right, that my collection from op post is not usable if I want to make it static or const? Like using my 'new' method I will have data and index arrays full of zeros, but attempt to use add_row method will failed because entire collection instance is already defined as zeros and const?
To address this I need something like new_with_data method, which will accept something like your array of slices, and I will need then to iterate over it in new method and prepare proper data and index once and forever? Would it be possible to keep everything static?

Also back to your suggestion, can you guesstimate read performance of array of slices as you suggest vs my approach with data and index? get_row method might be not good enough example to measure final performance, let's compare individual elements access by known row/column index.

in my case drawback is reading two arrays consequently:

    pub fn get(&self, row_index: usize, col_index: usize) -> Option<T> {
        if row_index >= self.num_rows {
            return None;
        }

        let start = row_index.checked_sub(1).map_or(0, |i| self.index[i]);
        let end = self.index[row_index];

        if col_index >= end - start {
            return None;
        }

        Some(self.data[start + col_index])
    }

Benefit - all the data allocated as a single solid array, all elements are adjacent in memory, which is good for "cache efficiency" (but I honestly don't know how exactly it helps to optimize memory managemant maybe in my case it doesn't play a role?)
Another concern - I still don't know how to properly support static/const initialization if possible at all.

In you example memory is much more fragmented, instead of two continues arrays we have one continues array of pointers to small separate chunks of memory.
Maybe it does matter for throughout iteration only but in my case I will access individual elements by indexes, so it's totally ok? Or still a bit slower?
And your suggestion offers OOB static/const support which is really good.

Any more comments?

You can improve coherence a bit by doing something like this:

static items: &[i32] = &[1,2,3,4,5,6,7,8,9];
static array: &'static [&'static [i32]] = &[
  &items[0..3],
  &items[3..5],
  &items[5..9]
];

But I'd guess it's not likely to make a noticable difference unless you're embedding at least megabytes, at which point you'd want to generate these anyway.

It seems you can't take slices from static/const array, but I benched your initial suggestion and it seems to be same as my approach and both takes 0(1).
here is my bench to validate:

So based on this I am happy to drop my array implementation and use array of refs as it's fully native approach and feature rich.

BTW I've managed to implement const new_with_data method and it was way full of discoveries (a lot of stuff is not available in const functions)
Here is a final version with absorbed improvements suggested by @H2CO3 and const constructor which accepts array of slices as initial data:

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.