# Having trouble in understanding lifetimes

I was trying to implement quicksort algorithm in a purely iterable manner:

initial code
``````fn _partition<T: Ord>(slice: &mut [T], mut i: usize) -> Option<usize> {
loop {
let (left, right) = slice.split_at_mut(i);

i = if let Some((pivot, right)) = right.split_first_mut() {
let mut left_iter = left.iter_mut().enumerate();
let mut right_iter = right.iter_mut().enumerate().rev();
loop {
if let Some((l, lele)) = left_iter.by_ref().find(|(_, ele)| ele > &pivot) {
if let Some((_, rele)) = right_iter.by_ref().find(|(_, ele)| ele < &pivot) {
std::mem::swap(lele, rele);
} else {
std::mem::swap(pivot, lele);
break l
}
} else {
if let Some((r, rele)) = right_iter.by_ref().find(|(_, ele)| ele < &pivot) {
std::mem::swap(pivot, rele);
break i + r
} else {
return Some(i)
}
}
}
} else {
return None
}
}
}

fn partition<T: Ord>(slice: &mut [T]) -> Option<usize> {
let len = slice.len();
let pivot = len / 2;
_partition(slice, pivot)
}
fn quick_sort<T: Ord>(slice: &mut [T]) {
partition(slice).map(|i| {
let (left, right) = slice.split_at_mut(i);
quick_sort(left);
right.split_first_mut().map(|(_, right)| quick_sort(right))
});
}
``````

It works correctly and passes all the tests(here)
However, I modified the code like this:

``````fn _partition<T: Ord>(slice: &mut [T], mut i: usize) -> Option<(&mut [T], &mut [T])> {
loop {
let (left, right) = slice.split_at_mut(i);

i = if let Some((pivot, right)) = right.split_first_mut() {
let mut left_iter = left.iter_mut().enumerate();
let mut right_iter = right.iter_mut().enumerate().rev();
loop {
if let Some((l, lele)) = left_iter.by_ref().find(|(_, ele)| ele > &pivot) {
if let Some((_, rele)) = right_iter.by_ref().find(|(_, ele)| ele < &pivot) {
std::mem::swap(lele, rele);
} else {
std::mem::swap(pivot, lele);
break l
}
} else {
if let Some((r, rele)) = right_iter.by_ref().find(|(_, ele)| ele < &pivot) {
std::mem::swap(pivot, rele);
break i + r
} else {
return Some((left, right))
}
}
}
} else {
return None
}
}
}
fn partition<T: Ord>(slice: &mut [T]) -> Option<(&mut [T], &mut [T])> {
let len = slice.len();
let pivot = len / 2;
_partition(slice, pivot)
}

fn quick_sort<T: Ord>(slice: &mut [T]) {
partition(slice).map(|(left, right)| {
quick_sort(left);
right.split_first_mut().map(|(_, right)| quick_sort(right))
});
}
``````

Almost similar to the original but, here it will not do the splitting of slice again(playround).
Here it throws an error.

``````error[E0499]: cannot borrow `*slice` as mutable more than once at a time
--> src/main.rs:4:29
|
2  | fn _partition<T: Ord>(slice: &mut [T], mut i: usize) -> Option<(&mut [T], &mut [T])> {
|                              - let's call the lifetime of this reference `'1`
3  |     loop {
4  |         let (left, right) = slice.split_at_mut(i);
|                             ^^^^^^^^^^^^^^^^^^^^^ `*slice` was mutably borrowed here in the previous iteration of the loop
...
22 |                         return Some((left, right))
|                                ------------------- returning this value requires that `*slice` is borrowed for `'1`
``````

I actually rewrote the `_partition` function in a recursive manner(here).

``````fn _partition<T: Ord>(slice: &mut [T], i: usize) -> Option<usize> {
let (left, right) = slice.split_at_mut(i);

let i = if let Some((pivot, right)) = right.split_first_mut() {
let mut left_iter = left.iter_mut().enumerate();
let mut right_iter = right.iter_mut().enumerate().rev();
loop {
if let Some((l, lele)) = left_iter.by_ref().find(|(_, ele)| ele > &pivot) {
if let Some((_, rele)) = right_iter.by_ref().find(|(_, ele)| ele < &pivot) {
std::mem::swap(lele, rele);
} else {
std::mem::swap(pivot, lele);
break l
}
} else {
if let Some((r, rele)) = right_iter.by_ref().find(|(_, ele)| ele < &pivot) {
std::mem::swap(pivot, rele);
break i + r
} else {
return Some(i)
}
}
}
} else {
return None
};
_partition(slice, i)

}
``````

Here also two mutable borrows are happening. One at line 3: `let (left, right) = slice.split_at_mut(i);` and another at line 28:`_partition(slice, i)`. But, it will not give an error. Only distinction from the second implementation is: there, it also returns the borrow `return Some((left, right))` which needs to be alive as slice.
The problem here is: the compiler knows that if the function is already returning `Some((left, right))` means the second borrow never occurs. If it is not returning anything means, the function is almost same the third implementation of the `_partition` function. Why does this has to be an error?
Is there anyway the code can be rearranged to the second implementation work? Or should I stick with first implementation?
Also on side note, why there is no fallible version of `split_at_mut` method? I checked in rust godbolt(here). There is panicking code also added.
I don't think it will ever fail this assumption(`assertion failed: mid <= self.len()`). But unfortunately, the rust compiler wasn't able to prove that.
The tests didn't fail tho.
Is there any way to remove that ` assert!(mid <= self.len());` in `split_at_mut` method?
It would've nicer if it had api like this`fn split_at_mut(&mut self, mid: usize) -> Option<(&mut [T], &mut [T])>`. I mean `split_first`, `split_last` has Option as return but, why not this?

This is a place where the compiler is stricter than necessary. Currently, when you return a reference, the compiler marks that borrow as lasting until the end of the function, but this incorrectly applies to all possible paths of execution from the creation of the borrow, rather than just those that return it.

Often you can fix it by borrowing twice — once to check that you want to return, then a second time when you are sure that you're going to return. This works because the borrow that actually gets returned doesn't have any other execution paths where it continues running.

3 Likes

How can I borrow twice here?

Like this:

``````return Some(slice.split_at_mut(i));
``````
3 Likes

That's almost the same thing as what I did initially:

Only thing here is its doing inside `_partition` instead in quicksort. Its still a good solution.
But, it's still adding the panicking code.

How can I say to compiler that mid never be more than len?

I believe operations on Rust slices are always bounds-checked, so there may be nothing you can do about that using safe Rust.

I believe arrays indexed by constants are not bounds-checked, and there is a crate (arrayref - Rust) for converting a slice into an array so that you can index without bounds checking. But I have the feeling this won't help in your situation.

Do you think the extra bounds check has a noticeable performance impact?

With `unsafe`.

When you write `unsafe` you are, quite literally, giving compiler the promise to uphold all the invariants without compiler help.

Of course if you violate such promises compiler reserves the right to punish you. By producing incorrect code.

And since by invoking superpowers of `unsafe` you can reimplement fallible `split_at_mut` easily such method is not really needed.

But, perhaps, it would have been nice to have, anyway.

True, but you can stay mostly in safe Rust if you just give compiler enough hints.

Hints are, of course, inherently unsafe.

1 Like

The problem is: it is panicking upon out of bounds. This hinders optimizations. For example here:

this code

It will not do tail call optimization eventhough it has all the correct conditions for tail call recursion.
It should've been returning an Option like split_first, slit_first mut etc. So, the user can handle the case rather than silently panicking.

You just need to give the optimizer enough information to know that it's in-bounds. For example, that `split_at_mut` at the beginning can be out of range, because it's a safe function so someone could pass `usize::MAX`, so of course it codegens a potential panic. If you put a `if i > slice.len() { return None }` before it, the panic will probably disappear.

Another common solution to this is re-slicing. See, for example, how `reverse` is now implemented without any bounds checks at runtime, by communicating enough info to LLVM to have them optimize out: https://github.com/rust-lang/rust/pull/90821/files#diff-e8ccaf64ce21f955ccebef33b52158631493a6f0966815a2ebc142d7cd2b5e06R650-R654

1 Like

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.