Issue with VecDeque

help
#1

I would expect that

let vec_deque2: VecDeque<usize> = vec_deque.iter().take(i).copied().collect();

and

let vec_deque2: VecDeque<usize> = vec_deque.make_contiguous()[..i].to_vec().into();

do the same thing. But when I use the latter, my program runs out of memory after a while. Can anyone explain the difference?

Here's the full program, it is a solution for Advent of Code, day 22, part 2.

use std::collections::{HashSet, VecDeque};

const P1: [usize; 25] = [
    12, 48, 26, 22, 44, 16, 31, 19, 30, 10, 40, 47, 21, 27, 2, 46, 9, 15, 23, 6, 50, 28, 5, 42, 34,
];

const P2: [usize; 25] = [
    14, 45, 4, 24, 1, 7, 36, 29, 38, 33, 3, 13, 11, 17, 39, 43, 8, 41, 32, 37, 35, 49, 20, 18, 25,
];

#[derive(Debug)]
enum Player {
    Player1,
    Player2,
}

fn recursive_combat(deck1: &mut VecDeque<usize>, deck2: &mut VecDeque<usize>) -> Player {
    use Player::*;
    let mut previous: HashSet<(VecDeque<usize>, VecDeque<usize>)> = HashSet::new();

    loop {
        if deck1.is_empty() {
            return Player2;
        }
        if deck2.is_empty() {
            return Player1;
        }

        if !previous.insert((deck1.clone(), deck2.clone())) {
            return Player1;
        }

        let card1 = deck1.pop_front().unwrap();
        let card2 = deck2.pop_front().unwrap();

        let winner = if deck1.len() >= card1 && deck2.len() >= card2 {
            let mut v1: VecDeque<usize> = deck1.iter().take(card1).copied().collect();
            //let mut v1: VecDeque<usize> = deck1.make_contiguous()[..card1].to_vec().into();
            let mut v2: VecDeque<usize> = deck2.iter().take(card2).copied().collect();
            //let mut v2: VecDeque<usize> = deck2.make_contiguous()[..card2].to_vec().into();
            recursive_combat(&mut v1, &mut v2)
        } else if card1 < card2 {
            Player2
        } else {
            Player1
        };

        match winner {
            Player1 => {
                deck1.push_back(card1);
                deck1.push_back(card2);
            }
            Player2 => {
                deck2.push_back(card2);
                deck2.push_back(card1);
            }
        }
    }
}

fn main() {
    dbg!(recursive_combat(
        &mut P1.to_vec().into(),
        &mut P2.to_vec().into()
    ));
}
#2
  1. The second way does two allocations, 1 for to_vec and 1 for into (which will probably reallocate unless you meet very specific conditions). The first way will likely only allocate once.
  2. VecDeque allocates space in powers of 2, which can be really wasteful.

So if you recurse enough (and keep things alive the entire time), you may run out of memory for these reasons.

#3

Sorry, I'm not quite convinced. The allocated memory for to_vec would be freed immediately, wouldn't it? And I don't really see why the second approach would allocate much more memory for the VecDeque than the first.

The second way takes more than 4GB of memory before it crashes after a while, the first needs around 10 MB to finish in under a second. I can't imagine the problem is just allocating a bit more than necessary.

#5

I got it, it was probably this soundness issue: https://github.com/rust-lang/rust/pull/79814

After running rustup update it works now on nightly.

4 Likes