Oh, yeah. Looking at the code the comparison function is bad in a way that will hit issues with cmovs. The "else if" there is a nearly 100% predictable branch which follows a branch that's probably completely unpredictable. One optimization you get with -O3 is that branches not marked likely or unlikely can be turned into dataflow. The proper ordering for that code is to pull the equality check forward into an if statement and mark with "unlikely" if you're using -O3, and then return the ordering of the floating point comparison.

Since we're using Rust there's some decent syntactic sugar for this function you can use instead:

    let cmp = |other: &Neighbor| -> Ordering {
        other.dist.partial_cmp(&neighbor.dist).unwrap()
            .then_with(|| other.id.cmp(&neighbor.id))
    };

You probably won't get any CMOVs in -O3 with this function because there are NaN issues with the original code.