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

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) : https://beta.atcoder.jp/contests/abc012/submissions/2282548
C++ (996 ms maximum) : https://beta.atcoder.jp/contests/abc012/submissions/2281364

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.

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
``````    graph[src].push(Edge::new(src, dst, weight));
}

pub fn add_weighted_edge(graph: &mut Graph, src: usize, dst: usize, weight: Weight) {
}

pub fn add_arc(graph: &mut Graph, src: usize, dst: usize) {
}

pub fn add_edge(graph: &mut Graph, src: usize, dst: usize) {
}
``````

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

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… 10 Likes