Asking review: my crate for structured dynamic programming

code review
1

I'd like to ask you code review for rust-generic-dp[1].
The main points are:

  • Optimizing execution time. It's around 20 times slower than naive DP if give them task to compute 31st fibonacchi number.
  • Correctness. Especially, is tap_non_empty_uninit_vec safe?
  • Efficiency. I'm using clippy, but there may be more.
  • Any churn, except:
    • There's main
    • measuring performance in #[test] functions

  1. I know this is not good crate name, per described in Rust API Guidelines ↩︎

2

No, it's unsound. If tap doesn't actually initialize the passed-in buffer, then a.assume_init() is Undefined Behavior. You either need to mark tap_non_empty_uninit_vec() as unsafe and document what the tap should do (which essentially defines away the problem), or ensure by means of the type system that you get an initialized buffer back, e.g.:

pub fn tap_non_empty_uninit_vec<R>(len: usize, tap: impl FnOnce(NonEmpty<MaybeUninit<R>>) -> NonEmpty<R>) -> NonEmpty<R> {
    let temp: NonEmpty<_> = core::iter::repeat_with(MaybeUninit::uninit)
        .take(len)
        .collect::<Vec<_>>()
        .try_into()
        .expect("len must be > 0");
    
    tap(temp)
}

Also note that || MaybeUninit::uninit() is equivalent to MaybeUninit::uninit – there's no need to create a closure, because just the reference to the MaybeUninit::uninit function has the appropriate sugnature (fn() -> MaybeUninit<_>). It's also possible to avoid the mutable resize_with() by collecting an appropriately-sized iterator in the first place.

2 Likes
3

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.