A Dynamic-Programming-like code helper?

This is a reduced example of the kind of code you get if you implement a Dynamic Programming algorithm:

fn main() {
    let n = 10;
    let s = 3;
    let mut arr = vec![1; n];

    for i in s .. n {
        arr[i] += arr[i - s];
    }
}

In this kind of code you often can't use iterators because you both read and write slice items, and often you can't use split_at_mut because the intervals are often overlapping. And LLVM often fails at reasoning about those index sums and differences, so it often leaves some array bound tests, stopping vectorization. To solve all such problems perhaps we can add a slice function similar to slice::copy_within but with an extra closure argument at the end:

arr.pairwise_within(0 .. n - s, s, |a, b| a + b);

// This is the same as arr::copy_within(0 .. n - s, s):
arr.pairwise_within(0 .. n - s, s, |_, b| b);

Two disadvantages: sometimes in such algorithms you need to work with three instead of two indexes (adding a slice::triplewise_within function that works on three different sub-slices is possible but it's becoming a bit too much hairy). Another downside is that the API of this function is not that easy to use (this is true for slice::copy_within too in my opinion).

You can use Cell to temporarily opt-in to shared mutability.

use std::cell::Cell;

fn main() {
    let n = 10;
    let s = 3;
    let mut arr = vec![1; n];
    
    let arr_view = Cell::from_mut(&mut arr[..]).as_slice_of_cells();

    for i in s .. n {
        arr_view[i].set(arr_view[i].get() + arr_view[i - s].get());
    }
    
    println!("{:?}", arr);
}

playground

2 Likes

Did you mean code like this?

use std::cell::Cell;

fn main() {
    let n = 10;
    let s = 3;
    let mut arr = vec![1; n];
    let arr_view = Cell::from_mut(&mut arr[..]).as_slice_of_cells();

    let source = &arr_view[.. n - s];
    let dest = &arr_view[s .. n];

    for (s, d) in source.iter().zip(dest) {
        d.set(d.get() + s.get());
    }
}

I will try it in some situations to see how it fares.

What about implementing your own extension trait(s) that add the desired method to slice types?

use std::ops::RangeBounds;

trait SliceExt<T> {
    fn pairwise_within<R, F>(&mut self, range: R, index: usize, func: F)
    where
        R: RangeBounds<usize>,
        F: FnMut(&T, &T) -> T;
}

impl<T> SliceExt<T> for [T] {
    fn pairwise_within<R, F>(&mut self, range: R, index: usize, func: F)
    where
        R: RangeBounds<usize>,
        F: FnMut(&T, &T) -> T,
    {
        todo!()
    }
}

fn main() {
    let n = 10;
    let s = 3;
    let mut arr = vec![1; n];

    arr.pairwise_within(0..n - s, s, |a, b| a + b);
}

(playground)

If you are the one implementing SliceExt you can use unsafe code and slice.get_unchecked() to skip the bounds checks (preferably with a healthy smattering of debug_assert!()'s).

It's also perfectly fine to use unsafe when existing methods (e.g. some_slice.split_at_mut() and friends) would be too restrictive, and you can guarantee at runtime that the borrow checker's rules can't be violated... Just make sure to run your code through miri and get someone else to review it for soundness.

1 Like

Yes, in the first post of this thread I was asking if it's a good idea to add a similar function to the Rust stdlib

That's perfectly fine, and often preferred over wrappers because people wanting your extra functionality get to keep using types from the standard library.

You need to use a trait before you get access to its methods, so you can't accidentally break someone else's code (the main complaint about "monkeypatching" in Python and Ruby).