Is it OK to use many nested heap allocation structs like Vec<Vec<T>>, Vec<BtreeMap<K, V>>?

1

I am writing a struct SparseMat<T: Numeric> to store some large sparse matrix data (more than 10,000 rows and more than 10,0000 nonzero entries). SparseMat<T> should allocate data on the heap, and will be initialized with no any data, meaning that the matrix is all zeros. Then I need to addassign some nonzero values to some entries of this matrix. Finally, I need to convert this matrix to CSR format like this.

I have come up with two different implementations of SparseMat<T>. The first one is close to CSR format, storing data as Vec<BTreeMap<usize, T>>. A nonzero element at index (i, j) can be indexed as self.data[i].get(&j).

// First implementation
pub struct SparseMat<T: Numeric> {
    // A row-major sparse matrix that is easy to add values, and can convert to CSR format when fixed.
    pub nrow: usize,
    pub ncol: usize,
    pub data: Vec<BTreeMap<usize, T>>,
}

impl<T: Numeric> SparseMat<T>
{
    #[inline]
    pub fn new( nrow: usize, ncol: usize ) -> Self {
        let data = vec![BTreeMap::<usize, T>::new(); nrow];
        Self { nrow, ncol, data }
    }

    #[inline]
    pub fn addassign_at( &mut self, i: usize, j: usize, val: T ) {
        match self.data[i].entry(j) {
            Entry::Occupied(mut entry) => {*entry.get_mut() += val;},
            Entry::Vacant(entry) => {entry.insert(val);},
        }
    }
}

The second one stores data as BTreeMap<RowMatIdx, T>, where RowMatIdx is simply a struct of (i, j) that is ordered (impl Ord trait) by i first then j. A nonzero element at index (i, j) can be indexed as self.data.get(&RowMatIdx{i,j}).

// Second implementation
pub struct SparseMat<T: Numeric> {
    // A row-major sparse matrix that is easy to add values, and can convert to CSR format when fixed.
    pub nrow: usize,
    pub ncol: usize,
    pub data: BTreeMap<RowMatIdx, T>,
}

impl<T: Numeric> SparseMat<T>
{
    #[inline]
    pub fn new( nrow: usize, ncol: usize ) -> Self {
        let data = BTreeMap::<RowMatIdx, T>::new();
        Self { nrow, ncol, data }
    }

    #[inline]
    pub fn addassign_at( &mut self, i: usize, j: usize, val: T ) {
        match self.data.entry(RowMatIdx{i, j}) {
            Entry::Occupied(mut entry) => {*entry.get_mut() += val;},
            Entry::Vacant(entry) => {entry.insert(val);},
        }
    }
}

pub struct RowMatIdx {
    i: usize,
    j: usize,
}

impl Ord for RowMatIdx
{
    #[inline]
    fn cmp( &self, other: &Self ) -> Ordering {
        match self.i.cmp(&other.i) {
            Ordering::Less => Ordering::Less,
            Ordering::Greater => Ordering::Greater,
            Ordering::Equal => self.j.cmp(&other.j),
        }
    }
}

Comparing these two implementations, the first one makes it easy to iterate all the nonzero elements in a certain row, while the second one uses flattened rather than nested data structure (that may be more efficient?). Both has the advantage of convenient insertion, and can ensure the inserted nonzero entries are always ordered first by row then by column. Which one do you think is better, or are thery any better solutions? I have heard that too many (is this case, more than 10,000) nested heap allocations like Vec<Vec<T>>, Vec<String>, Vec<BtreeMap> may be not efficient, is that true?

2

If you swap the order of the fields in RowMatIdx, you can do that in the second one too, with BTreeMap::range().

As to efficiency, since you're using a BTreeMap, the map inherently contains nested (tree) structure, so there is probably not a whole lot of difference in that respect; in fact, the “nested” form might be much flatter because the Vec contains more elements with one indirection than a single B-tree node does.

But, as always, the important thing is to measure the performance of your data structures in actual applications. The access pattern, the shape of the data, and the hardware you run the program on will all affect which one is more efficient.

I have heard that too many (is this case, more than 10,000) nested heap allocations like Vec<Vec<T>> , Vec<String> , Vec<BtreeMap> may be not efficient, is that true?

All else being equal, you should choose structures with fewer allocations and fewer indirections. But all else is not equal; the choice of data structure affects what operations can be performed efficiently at all, so you need, not the most efficient data structure in a vacuum, but the most efficient data structure for the operations you need to perform.

For example, the flattest possible data structure for a sparse matrix would be a HashMap<RowMatIdx, T>. But then you have no ability to query by row at all.

Also, you should probably look at how sparse matrices are implemented in other libraries and languages. I've given some general advice based on what you've written, but I don't know any tricks for how to work with sparse matrices — I've never needed them.

By the way, this can be more concisely expressed as self.i.cmp(&other.i).then(self.j.cmp(&other.j)) — or it can be replaced entirely with #[derive(Ord, PartialOrd)], which will generate the same code.

5 Likes
3

Thanks for this answer, so my two implementations probably have no much difference as BtreeMap is itself a nested structure. If I want a structure as flat as possible while easy to insert values, I should probably use HashMap. As I do not need to preserve the order when constructing a sparse matrix, I can do sorting later when converting to the CSR format.

4

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.