Using priority_queue::PriorityQueue::change_priority

[cscherrer]

Hi, I'm working through some little projects to help me learn Rust. Currently I'm working on a prime number sieve (implementation here). This is a Sieve of Eratosthenes, using some ideas from Melissa O'Neil's JFP paper.

I'm a little stuck on something, hoping to get some advice to get unstuck.

After the small primes (2, 3, 5, 7), I have a struct to help me walk through "bigger primes":

struct BiggerPrimes {
    state: Wheel,
    active_filters: PriorityQueue<Filter, Reverse<u64>>,
    queued_filters: VecDeque<Filter>,
}

For my current question, the Wheel and VecDeque stuff isn't important -- all of that is working fine. But PriorityQueues are giving me some grief.

Filter looks like this:

#[derive(Hash, Copy, Clone, Eq, PartialEq)]
struct Filter {
    base: u64,
    state: u64,
}

The idea is that each base is a prime, and state steps through multiples of that prime.

Then BiggerPrimes has a method

fn step(&mut self) -> Option<u64>

that includes this loop:

while let Some((ref_f, _)) = self.active_filters.peek() {
    match ref_f.state {
        x if x < n => {
            let mut f = self.active_filters.pop().unwrap().0;
            f.state += f.base;
            self.active_filters.push(f, Reverse(f.state));
        }
        x if x == n => {
            return None;
        }
        _ => {
            break;
        }
    }
}

Here ref_f: &Filter and f: Filter. Note that unlike BinaryHeaps, a PriorityQueue takes the item and priority separately as arguments.

The code works fine as is, but it's much slower than the BinaryHeap implementation. But currently I'm popping the queue, updating f, and then pushing it back on. I'd guess it could be more efficient to use PriorityQueue::change_priority, which has this spec:

pub fn change_priority<Q>(&mut self, item: &Q, new_priority: P) -> Option<P>

So my first twentieth or so attempt is

let fs = &mut self.active_filters;
while let Some((ref_f, _)) = fs.peek_mut() {
    match ref_f.state {
        x if x < n => {
            ref_f.state += ref_f.base;
            fs.change_priority(ref_f, Reverse(ref_f.state));
        }
        x if x == n => {
            return None;
        }
        _ => {
            break;
        }
    }
}

This doesn't work:

 1  error[E0499]: cannot borrow `*fs` as mutable more than once at a time
    --> src/main.rs:106:21
     |
 103 |         while let Some((ref_f, _)) = fs.peek_mut() {
     |                                      -- first mutable borrow occurs here
 ...
 106 |                     fs.change_priority(ref_f, Reverse(ref_f.state));
     |                     ^^                 ----- first borrow later used here
     |                     |
     |                     second mutable borrow occurs here
 
 For more information about this error, try `rustc --explain E0499`.
 error: could not compile `prime-sieve` (bin "prime-sieve") due to previous error

Sorry this is so long, but my questions are

1. How can I fix this?
2. Why is the compiler happy with the current while loop? It seems like self.active_filters is borrowed twice. Even stranger, self: &mut, ref_f: &Filter, and mut f: Filter are all alive at once. How is rustc happy with this?

[semicoleon]

Your first version compiles because the ref_f value is not in use by the time you need mutable access to active_filters.

Note that peek_mut includes this line in it's documentation

The item is a mutable reference, but it's a logic error to modify it in a way that change the result of Hash or Eq.

Your modifications will do exactly that, so your second version is wrong even if you fix it so it compiles.

[cscherrer]

Thanks @semicoleon

@semicoleon

Your first version compiles because the ref_f value is not in use by the time you need mutable access to active_filters.

Does "not in use" mean its lifetime has ended? Is that because I don't match on the whole value, but only its state field?

@semicoleon

The item is a mutable reference, but it's a logic error to modify it in a way that change the result of Hash or Eq.

Your modifications will do exactly that, so your second version is wrong even if you fix it so it compiles.

Hmm, good point. I know the base fields will all be distinct, so I could implement Hash and Eq to only look at those. But I'm guessing that's not the reason it won't compile.

[semicoleon]

We can break the first version in the same way for illustrative purposes

while let Some((ref_f, _)) = self.active_filters.peek() {
    match ref_f.state {
        x if x < n => {
            let mut f = self.active_filters.pop().unwrap().0;
            f.state += f.base;
            self.active_filters.push(f, Reverse(f.state));
            let _ = ref_f;
        }
        x if x == n => {
            return None;
        }
        _ => {
            break;
        }
    }
}

By referencing ref_f after we need to borrow active_filters again, we force the borrow to live longer which creates a conflict.

You can make the second version compile by creating a copy of ref_f so that the borrow can end earlier, like in the first version.

while let Some((ref_f, _)) = self.active_filters.peek_mut() {
    match ref_f.state {
        x if x < n => {
            ref_f.state += ref_f.base;
            let f = *ref_f;
            self.active_filters.change_priority(&f, Reverse(f.state));
        }
        x if x == n => {
            return None;
        }
        _ => {
            break;
        }
    }
}

Then ref_f is no longer used by the time you need to borrow active_filters again.

Though of course that assumes you made the change to the Hash and Eq impls, otherwise things may break at runtime.

[cscherrer]

Thank you! I'll need to think about this for a while to understand the details.