Is there a standard way of cyclically rotating mutable variables in Rust?

Question

A very common operation in implementing algorithms is the cyclic rotate: given, say, 3 variables a, b, c change them to the effect of

t ⇽ c
c ⇽ b
b ⇽ a
a ⇽ t

Given that everything is bitwise swappable, cyclic rotation should be an area where Rust excels more than any other language I know of.

For comparison, in C++ the most efficient generic way to rotate N elements is performing n+1 std::move operations, which in turn roughly leads to (for a typical move constructor implementation) 3 (n+1) sizeof(T) word assignments (this can be improved for PODs via template specializing rotate, but requires work).

In Rust, the language makes it possible to implement rotate with only (n+1) size_of(T) word assignments. To my surprise, I could not find standard library support for rotation. (No rotate method in std::mem). It would probably look like this:

pub fn rotate<T>(x: &mut T, y: &mut T, z: &mut T) {
    unsafe {
        let mut t: T = std::mem::uninitialized();
        std::ptr::copy_nonoverlapping(&*z, &mut t, 1);
        std::ptr::copy_nonoverlapping(&*y, z, 1);
        std::ptr::copy_nonoverlapping(&*x, y, 1);
        std::ptr::copy_nonoverlapping(&t, x, 1);
        std::mem::forget(t);
    }
}

---

For clarification on why rotation cannot be implemented efficiently in C++, consider:

struct String {
  char *data1;
  char *data2;
  String(String &&other) : data1(other.data1), data2(other.data2)
    { other.data1 = other.data2 = nullptr;}
  String &operator=(String &&other)
    { std::swap(data1, other.data1); std::swap(data2, other.data2);
      return *this; }
  ~String() { delete [] data1; delete [] data2; }
};

Here an operation like s2 = std::move(s1); will take 3 pointer assignments for each member field, totaling to 6 assignments since pointer swap requires 3 assignments (1 into temp, 1 out of temp, one across operands)

Answer 1

A better Rust implementation would be to simply implement your pseudocode from the top of the question directly:

pub fn rotate<T>(x: &mut T, y: &mut T, z: &mut T) {
    unsafe {
        let t = std::ptr::read(z);
        std::ptr::write(z, std::ptr::read(y));
        std::ptr::write(y, std::ptr::read(x));
        std::ptr::write(x, t);
    }
}

Shorter, cleaner, more straightforward and intuitive. You don't need to mem::forget t since x takes ownership of it.

Answer 2

Is there a standard way of cyclically rotating mutable variables in Rust?

No.

I'd just swap the variables twice, no need for unsafe:

use std::mem;

pub fn rotate<T>(x: &mut T, y: &mut T, z: &mut T) {
    mem::swap(x, y);
    mem::swap(y, z);
}

fn main() {
    let mut a = 1;
    let mut b = 2;
    let mut c = 3;

    println!("{}, {}, {}", a, b, c);
    // 1, 2, 3

    rotate(&mut a, &mut b, &mut c);

    println!("{}, {}, {}", a, b, c);
    // 2, 3, 1
}

---

This produces 7 movl instructions (Rust 1.35.0, Release, x86_64, Linux)

playground::rotate:
    movl    (%rdi), %eax
    movl    (%rsi), %ecx
    movl    %ecx, (%rdi)
    movl    %eax, (%rsi)
    movl    (%rdx), %ecx
    movl    %ecx, (%rsi)
    movl    %eax, (%rdx)
    retq

As opposed to the original 6 movl instructions:

playground::rotate_original:
    movl    (%rdx), %eax
    movl    (%rsi), %ecx
    movl    %ecx, (%rdx)
    movl    (%rdi), %ecx
    movl    %ecx, (%rsi)
    movl    %eax, (%rdi)
    retq

I'm OK giving up that single instruction for purely safe code that is also easier to reason about.

---

In "real" code, I'd make use of the fact that all the variables are the same type and that slice::rotate_left and slice::rotate_right exist:

fn main() {
    let mut vals = [1, 2, 3];

    let [a, b, c] = &vals;
    println!("{}, {}, {}", a, b, c);
    // 1, 2, 3

    vals.rotate_left(1);

    let [a, b, c] = &vals;
    println!("{}, {}, {}", a, b, c);
    // 2, 3, 1
}