Idea: `shift_move` to efficiently move elements in a `Vec`

I'm not sure whether something like this has been suggested before but I'm thinking something along the lines of:

pub trait ShiftMove {
    /// moves the item at index `from` to the index `to`, shifting
    /// all items in between in the appropriate direction.
    fn shift_move(&mut self, from: usize, to: usize);
}

impl<T> ShiftMove for Vec<T> {
    fn shift_move(&mut self, from: usize, to: usize) {
        if from == to {
            return;
        }

        assert!(from < self.len());
        assert!(to < self.len());

        unsafe {
            let from_ptr = self.as_mut_ptr().add(from);
            let to_ptr = self.as_mut_ptr().add(to);

            // SAFETY: from < len
            let elem = std::ptr::read(from_ptr);

            if from > to {
                // shift all elements between `to` and `from` to the right by one index
                std::ptr::copy(to_ptr, to_ptr.add(1), from - to);
            } else {
                // shift all elements between `from` and `to` to the left by one index
                std::ptr::copy(from_ptr.add(1), from_ptr, to - from);
            }

            // SAFETY: to < len
            std::ptr::write(to_ptr, elem);
        }
    }
}

#[cfg(test)]
mod test {
    use crate::ShiftMove;

    #[test]
    fn test1() {
        let mut vec = vec![1, 2, 3, 4, 5, 6];

        vec.shift_move(3, 0);

        assert_eq!(&vec, &[4, 1, 2, 3, 5, 6]);
    }

    #[test]
    fn test2() {
        let mut vec = vec![1, 2, 3, 4, 5, 6];

        vec.shift_move(0, 3);

        assert_eq!(&vec, &[2, 3, 4, 1, 5, 6]);
    }
}

The implementation is inspired by Vec::remove and Vec::insert.

Comparison to Vec::remove + Vec::insert: Compiler Explorer

Ideally this'd be implemented for slices, however Miri complains about stacked borrows if I just change the impl type.

2 Likes

I would consider something like

    fn shift_move(&mut self, from: usize, to: usize) {
        if from > to {
            self[to..=from].rotate_right(1);
        } else {
            self[from..=to].rotate_left(1);
        }
    }

though – at least for the from > to case – the assembly I get seems more complicated than what your code produces.

3 Likes

IndexMap has move_index, and the Vec part is implemented by rotation like @steffahn suggested:

1 Like

Sounds like

5 Likes

Ah yes, I hadn't thought of that. If anyone figures out the reason why slice::ptr_rotate is so hard for LLVM to simplify in slice::rotate_{left, right} that'd be the better implementation, however there isn't anything immediately obvious to me. Maybe Algorithm 2 should always be used for small min(left, right) instead of Algorithm 1, even when the slice length itself is short?

I forget what the numbers mean exactly, but yes, I'd certainly think that the memcpy+memmove+memcpy version should always be used for shifts small enough to fit into the local buffer, because that way it'll always match what people expect it to be from their experience with Vec::remove+Vec::push.

But the other possibility (if, for some reason, that's really bad) would be to have the implementation check for a constant shift below some threshold, since we now have an internal intrinsic for that the core can use.

PRs highly welcome, feel free to r? @scottmcm on them :slight_smile:

Sean Parent describes a more generic form of this algorithm which operates on ranges in his 2013 talk "C++ Seasoning"[1] and refers to it as slide. shift_move can be seen as a special case for sliding a range of length 1.

I've needed to use both functions in the past but shift_move seems more immediately suitable for library inclusion and possibly better optimized as its own function. Some behaviors for slide as described in the talk may be susceptible to bikeshedding.

Playground link


  1. Examples start on page 33/slide 11 and the final code is on page 47/slide 19.
    https://sean-parent.stlab.cc/presentations/2013-09-11-cpp-seasoning/cpp-seasoning.pdf
    https://youtu.be/qH6sSOr-yk8?t=632 ↩ī¸Ž