I've been using Rust in leetcode.com to practice my skills with the language, and I noticed that I consistently get higher memory usage when I use .rev() to iterate over a range in reverse. For example this code:
impl Solution {
pub fn min_path_sum(mut grid: Vec<Vec<i32>>) -> i32 {
let n = grid.len() - 1;
let m = grid[0].len() - 1;
for j in (0..m).rev() {
grid[n][j] += grid[n][j + 1];
}
for i in (0..n).rev() {
grid[i][m] += grid[i + 1][m];
for j in (0..m).rev() {
grid[i][j] += grid[i][j + 1].min(grid[i + 1][j]);
}
}
grid[0][0]
}
}
Uses up 2.6MB of memory, while the same algorithm without the .rev() calls takes only 2.1MB:
impl Solution {
pub fn min_path_sum(mut grid: Vec<Vec<i32>>) -> i32 {
let n = grid.len() - 1;
let m = grid[0].len() - 1;
for j in 0..m {
grid[n][m - j - 1] += grid[n][m - j];
}
for i in 0..n {
grid[n - i - 1][m] += grid[n - i][m];
for j in 0..m {
grid[n - i - 1][m - j - 1] += grid[n - i - 1][m - j].min(grid[n - i][m - j - 1]);
}
}
grid[0][0]
}
}
This is counter-intuitive to me, and honestly a bummer, since as far as I know there aren't any clean ways to avoid using .rev() for backwards iteration. Is this a deliberate choice or something that should be fixed?
<Range as Iterator>::rev() doesn't itself allocate memory. How are you measuring memory consumption, and how do you know it's Range::rev() that allocates the difference of 500 kB?
I only have empirical evidence, unfortunately. I don't know how the LeetCode judge evaluates memory consumption. I only see the reported measurement. But I have tried identical submissions apart from using .rev() for 3+ very different problems and they all have come down with a measurable memory usage difference.
If there isn't anything in the Rust standard library that would explain this behaviour, I have two hypotheses. One is that the difference is due to extra code being included in the executable when .rev() is used, which inflates the process memory at runtime. The other is that this is something unique about LeetCode's setup, though I couldn't tell what that would be.
I will try to reproduce this locally in a couple of weeks. Going to be away from computers for a little while. But thanks for the quick initial response @H2CO3.
PS: LeetCode's benchmarking implementation is terrible, but it's at least consistent for repeated submissions of the same code, so it's not random/arbitrary.
Oh don't get me started, the types they require in the interface are often non-idiomatic nonsense. I expect they have some code to generate from C/C++ types, so you end up with i32 for lengths and indexing, for example. But this quirk with .rev() seemed interesting enough to dig into.
That is a very interesting experiment. First of all, I observed that in fact the memory measurement is not as deterministic as I thought. I don't know if something changed with LeetCode, or if I had just been lucky with my original submissions, but I tried resubmitting a bunch of problems (including the one posted here) and got a sort of normal distribution with ~0.5MB standard deviation.
Anecdotally, I do observe a lower average for submissions including .rev() than for those without it. But as embarrassing as that is to admit, I don't think that is statistically relevant.
So that I don't waste anybody's time further, let's call the case closed. I do want to run some controlled tests when I get the chance to confirm, but that's on me.
PS: To clarify, I don't observe any meaningful difference between .rev() and .rev().rev(). Not that I have reliable evidence that either one is different to a non-reversed range, either.
This doesn't account for any systemic problems with measurement. I.e. maybe adding that one rev statement in your particular problem adds memory consumption, but in 1000 other programs it wouldn't (e.g. for reasons related to the particular arrangement of memory in that case).
