Why my code runs slower than C++ version? [solved]

help
1

I wrote an algorithm (bidirectional Dijkstra algorithm for undirected graph) with both of Rust and C++ to solve this problem. In short: You are given a simple undirected graph G. Calculate the radius of G.

Rust version gives correct output, but runs much slower than C++ with some test cases.

Rust (4659 ms maximum) : Submission #2282548 - AtCoder Beginner Contest 012
C++ (996 ms maximum) : Submission #2281364 - AtCoder Beginner Contest 012

I believe that the bottleneck is function bidirectional_dijkstra pasted bellow:

/// Pair of (id of vertex) and (distance to there)
#[derive(PartialEq, Eq, Clone, Copy)]
struct DijkstraState(usize, Weight);
 
/// Reverse order of distance
impl Ord for DijkstraState {
    fn cmp(&self, other: &DijkstraState) -> Ordering {
        other.1.cmp(&self.1)
    }
}
 
impl PartialOrd for DijkstraState {
    fn partial_cmp(&self, other: &DijkstraState) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
 
/// Find the distance between `src` and `dst` on `graph`.
/// Returns `Some(value)` if reachable and the distance is `value`, `None` otherwise.
pub fn bidirectional_dijkstra(graph: &Graph, src: usize, dst: usize) -> Option<Weight> {
    if src == dst {
        Some(0)
    } else {
        let inf: Weight = Weight::max_value() / 2;
 
        let n = graph.len();
        // heap from `src`
        let mut heaps = BinaryHeap::with_capacity(n);
        // heap from `dst`
        let mut heapd = BinaryHeap::with_capacity(n);
        heaps.push(DijkstraState(src, 0));
        heapd.push(DijkstraState(dst, 0));
        // distance table from `src`
        let mut dists = vec![inf; n];
        // distance table from `dst`
        let mut distd = vec![inf; n];
        dists[src] = 0;
        distd[dst] = 0;
 
        // upper bound of return value
        let mut mu = inf;
 
        while let Some((DijkstraState(v, d), heap, dist, dist_)) = {
            let DijkstraState(_, ds) = *heaps.peek().unwrap_or(&DijkstraState(n, inf));
            let DijkstraState(_, dd) = *heapd.peek().unwrap_or(&DijkstraState(n, inf));
            if ds + dd >= mu {
                // optimal value which can be obtained in future is greater than or equal to mu,
                // so break loop.
                None
            } else if ds <= dd {
                // update from `src`-side
                heaps.pop().map(|x| (x, &mut heaps, &mut dists, &mut distd)) 
            } else {
                // update from `dst`-side
                heapd.pop().map(|x| (x, &mut heapd, &mut distd, &mut dists)) 
            }
        } {
            // update around `v` if optimal distance to v equals to d
            if dist[v] == d {
                // iterate vertices adjacent to `v`
                for e in graph[v].iter() {
                    if dist[e.dst] > d + e.weight {
                        dist[e.dst] = d + e.weight;
                        heap.push(DijkstraState(e.dst, dist[e.dst]));
                        mu = min(mu, dist[e.dst] + dist_[e.dst]);
                    }
                }
            }
        }
 
        if mu != inf {
            Some(mu)
        } else {
            None
        }
    }
}

Do you have any idea to speed up this?
I know that there are more efficient ways to solve the problem, but I simply hope to know why this code is slow.

Thank you.

2

How to download the test files?

At first glance, I am suspecting you're doing too many things in the condition of while loop, but not reall sure. Actually what I said didn't make much sense.

1 Like
3 
    graph[src].push(Edge::new(src, dst, weight));
}
 
pub fn add_weighted_edge(graph: &mut Graph, src: usize, dst: usize, weight: Weight) {
    add_weighted_arc(graph, src, dst, weight);
    add_weighted_arc(graph, dst, src, weight);
}
 
pub fn add_arc(graph: &mut Graph, src: usize, dst: usize) {
    add_weighted_arc(graph, src, dst, 1);
}
 
pub fn add_edge(graph: &mut Graph, src: usize, dst: usize) {
    add_weighted_edge(graph, src, dst, 1);
}

Begin putting an #[inline] here.

However, there is something wrong, it is anomalous that an identical program in C ++ and Rust has fewer lines in C ++

1 Like
4

I cooled my brain and found that C++ code does additional branching (if(cand > res) break;).

        int res = 1e9;
        rep(i, n){
            int cand = 0;
            rep(j, n){
                cand = max(cand, bidirectional_dijkstra(g, i, j));
                if(cand > res) break; // <--
            }
            res = min(res, cand);
        }
        cout << res << endl;

I also added this line to Rust then somehow Rust code becomes faster than C++! (778 ms)
I wasted 3 hours to tackle this problem.
Sorry answerers... :innocent:

10 Likes