How does `std::mem::swap` work?
Asked Answered
A

2

15

Swap the values at two mutable locations of the same type, without deinitialising or copying either one.

use std::mem;

let x = &mut 5;
let y = &mut 42;

mem::swap(x, y);

assert_eq!(42, *x);
assert_eq!(5, *y);

(From offical Rust doc)

How can two values be swapped without copying? How did the value 42 go from y to x? This shouldn't be possible.

Axe answered 3/7, 2015 at 19:39 Comment(3)
I bet you've never heard of the triple xor trick, which is a popular trivia in coding interviews. Not sure if the standard library implements it this way or not though..Payee
I remember back in the assembly days that doing several XOR statements can swap data without a third memory space to copy to. I'm not sure that is what "swap" uses however. maybe you can view the assembly? en.wikipedia.org/wiki/XOR_swap_algorithmMalamut
Yeah already heard of it :)Axe
R
12

The function does actually make a copy internally: here is its source extracted from the documentation:

pub fn swap<T>(x: &mut T, y: &mut T) {
    unsafe {
        // Give ourselves some scratch space to work with
        let mut t: T = uninitialized();

        // Perform the swap, `&mut` pointers never alias
        ptr::copy_nonoverlapping(&*x, &mut t, 1);
        ptr::copy_nonoverlapping(&*y, x, 1);
        ptr::copy_nonoverlapping(&t, y, 1);

        // y and t now point to the same thing,
        // but we need to completely forget `t`
        // because it's no longer relevant.
        forget(t);
    }
}
Radiotelegraphy answered 3/7, 2015 at 20:22 Comment(4)
Um... doesn't this totally contradict the description: "without [...] copying"? Or do they mean that no value will be duplicated?Axe
There is a difference between “rust-level copying” (duplicated values, would need to be free'd twice) and implementation level copying. In rust semantics, there are no copies here, the two values just move.Distiller
@Axe the "no copy" here mostly means that the type you do the sawp on does not need to be Clone or Copy, it does not mean that no temporary memory storage is used.Radiotelegraphy
Note that by the current rules of Rust this code exhibits undefined behavior because it creates a value containing uninitialized data, as well as a reference to such value. Today the same logic would be expressed with MaybeUninit, like this.Hindorff
A
11

The previous answer is correct in semantics, but outdated in exact details.

Logically, swapping two values works by reading value A into a temporary location, copying B on top of A, then writing the temporary value back into B. There is a brief period where the same value exists twice in memory. This is why the implementation of these functions requires unsafe code, as only a human can guarantee that Rust's safety requirements are upheld.

As of Rust 1.43.0, mem::swap is implemented as:

pub fn swap<T>(x: &mut T, y: &mut T) {
    // SAFETY: the raw pointers have been created from safe mutable references satisfying all the
    // constraints on `ptr::swap_nonoverlapping_one`
    unsafe {
        ptr::swap_nonoverlapping_one(x, y);
    }
}

swap_nonoverlapping_one is private, but its implementation is:

pub(crate) unsafe fn swap_nonoverlapping_one<T>(x: *mut T, y: *mut T) {
    // For types smaller than the block optimization below,
    // just swap directly to avoid pessimizing codegen.
    if mem::size_of::<T>() < 32 {
        let z = read(x);
        copy_nonoverlapping(y, x, 1);
        write(y, z);
    } else {
        swap_nonoverlapping(x, y, 1);
    }
}

You can see the documentation for ptr::copy_nonoverlapping and ptr::swap_nonoverlapping. The latter is basically a highly-optimized version of copying for larger values.

Aramaic answered 15/5, 2020 at 16:49 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.