overflow panic in debug estimating cost

[tbillington]

Hey, while running in debug mode I got a panic in the astar implmentation due to overflow.

thread 'Async Compute Task Pool (0)' panicked at /Users/choc/.cargo/registry/src/index.crates.io-6f17d22bba15001f/pathfinding-4.10.0/src/directed/astar.rs:140:33:
attempt to add with overflow

pathfinding/src/directed/astar.rs

Line 140 in 2aa2326

estimated_cost: new_cost + h,

I probably have some pathological setup, but for correctness the estimated cost should probably saturate instead of wrapping. Thoughts on using new_cost.saturating_add(h) ?

[samueltardieu]

Saturating arithmetic could give incorrect results. The best way would probably be to use checked arithmetic instead in the few places where this might happen (such as adding costs), and document in a "# Panics" section in which case this method might panic.

[tbillington]

If the estimated cost is exceeding the bound of the numeric datatype neither wrapping nor saturating will be "correct", but as a user my preference would be saturating > wrapping > panic.

For a game I prioritise not crashing over total correctness, and accept that if the costs I've fed to astar are this high it's a problem on my end I should fix it. But it's still vastly more preferable that some routes be suboptimal or not resolvable over a straight panic. The majority of the time this code will be run is on end-user systems who cannot/will not be able to report or debug a panic like this.

If checked add is the chosen option, either returning None or changing to a Result type would still be preferable in my use case over a panic.

[samueltardieu]

Thanks Trent for discussing this further.

First of all, I'm not ready to have this crate silently report incorrect results ("suboptimal" is incorrect as far as A* is concerned), but we can try to devise solutions to the problem and the needs you are exposing (those are different).

Right now, I cannot use any other operator than + for cost computation as the C generic type expressing the cost would require adding num_traits::CheckedAdd or num_traits::SaturatingAdd, and that would be a breaking change. The only thing I can do immediately through a patch version is panic so that no incorrect result is returned, and would match the behavior seen in debug mode. I'll open an issue so that all pathfinding algorithms return a Result instead of an Option in a future release. That would let us express various reasons for failure, such as an overflow, and so on. Moreover, it would be extensible.

Concerning the point you raise: you can already get the behavior you want by using a thin wrapper around your cost type which defines addition as a saturating one. This would get you the result you expect, even in the case of panics on overflow since it will never overflow. Could that work for you?

[tbillington]

Oh, I'd forgotten C was a generic, so yes I could indeed do that :) thank you for the suggestion.

First of all, I'm not ready to have this crate silently report incorrect results

Understandable :)

[tachsin]

Two things to add here: the release-build behaviour is worse than the title suggests, and the breaking-change blocker turns out to be avoidable.

Release builds do not just fail to panic, they return a wrong cost

The issue is filed as a debug panic, but the same addition in release silently wraps and the wrapped value is returned as if it were the answer. Three edges of u32::MAX / 2:

function	returned cost	correct cost
astar	2,147,483,645	6,442,450,941
dijkstra	2,147,483,645	6,442,450,941
fringe	2,147,483,645	6,442,450,941
idastar	2,147,483,645	6,442,450,941

2,147,483,645 is exactly 6442450941 mod 2^32. Nothing in the result distinguishes it from a real answer.

In fairness to the scale of the problem: I tried to build a case where the wrap also makes the search choose the wrong path, and could not. Dijkstra's ordering partly protects it, because a wrapped total is small but is only reachable through expensive intermediates that pop late. So the demonstrated damage is a wrong cost rather than a wrong route.

Checked arithmetic without a breaking change

Right now, I cannot use any other operator than + for cost computation as the C generic type expressing the cost would require adding num_traits::CheckedAdd or num_traits::SaturatingAdd, and that would be a breaking change.

The existing bounds are enough. C is already Zero + Ord + Copy, and num_traits::Zero implies Add<Output = Self> while Ord gives comparison. Since costs are required to be non-negative, adding one can never produce a smaller value, so a wrapped sum is detectable by comparison alone:

#[cold]
#[inline(never)]
fn cost_overflow() -> ! {
    panic!("cost overflow: the total path cost does not fit in the cost type");
}

#[inline]
pub(crate) fn add_costs<C>(a: C, b: C) -> C
where
    C: num_traits::Zero + Ord + Copy,
{
    let sum = a + b;
    if sum < a && b >= C::zero() {
        cost_overflow();
    }
    sum
}

No new trait bound, so this is doable in a patch release. It gives exactly the behaviour you described wanting: panic so that no incorrect result is returned, matching debug builds.

It also leaves your suggested workaround intact, which I think is the important part. A cost type whose addition saturates never produces a smaller sum, so it never trips the check and never panics. Floating point costs reach infinity rather than wrapping and are likewise untouched. The negative-addend guard is there so the check stays silent on inputs these algorithms do not support anyway, rather than inventing a new panic for them.

Cost

This puts a branch in the innermost loop of every cost-based search, so it is not free, and the honest numbers are mixed.

Instruction counts (iai, comparing two trees that differ only in the body of add_costs, so the call structure and inlining opportunities are identical):

benchmark	check disabled	check enabled	change
corner_to_corner_dijkstra	3,077,484	3,650,734	+18.6%
no_path_dijkstra	3,047,873	3,604,028	+18.2%
corner_to_corner_idastar	66,028	96,163	+45.6%
corner_to_corner_iddfs (no costs, control)	3,712,137	3,717,954	+0.2%

The dijkstra figure reproduced at +18.07%, +18.11%, +18.63% and +18.25% across four independent build pairs, so I believe it.

Wall clock, same machine, 256x256 grid, fastest of 40 runs over 5 alternated rounds: no measurable change. dijkstra came out 5.4% faster with the check, but bfs, which uses no costs and cannot be affected, came out 5.8% faster in the same run, so that is code layout rather than the check. The added work is a perfectly predicted branch and the CPU absorbs it.

Two caveats on the measurements. I could not use every benchmark, because several of them do not currently measure the work they run (#833), and I excluded those. And corner_to_corner_bfs_bidirectional moves +10.1% between these builds despite never calling add_costs, which is codegen drift of the same kind, so the smaller figures above should not be read too closely.

Some cheaper formulations do not help: dropping the negative-addend guard gives +19.9%, and making the cold path abort() instead of panic! produces byte-identical counts, since the cold body never executes. The cost is the branch, not the panic machinery.

So the trade is roughly 18% more instructions in dijkstra, for no measurable wall-clock difference, in exchange for never returning a wrapped cost. That is your call rather than mine, and if the instruction count is too high a price I am happy to drop it or to look at a narrower placement.

PR: #834. It covers astar, astar_bag, dijkstra and its variants, fringe, idastar and yen, adds the # Panics sections you asked for, and comes with tests that fail on current main and pass with the fix.

[tachsin]

Correcting the cost figures in my comment above.

I reported the overflow check as +18.6% instructions on corner_to_corner_dijkstra. That was an artefact of the benchmarks rather than a property of the change, and the real figure is +0.7%.

The cause is #833: with the benchmarks as they stand on main, dijkstra is inlined wholesale into the benchmark harness, so adding a branch to its inner loop upends that inlining and the comparison ends up measuring the harness. Re-measured with the corrected benchmarks from #835, where the search sits behind a call the optimiser cannot see through, which is also closer to how callers actually invoke it:

benchmark	uses costs	main	with the check	change
corner_to_corner_idastar	yes	153,194	158,177	+3.3%
no_path_fringe	yes	2,907,008	2,936,349	+1.0%
no_path_dijkstra	yes	3,033,622	3,054,515	+0.7%
corner_to_corner_dijkstra	yes	3,059,458	3,080,348	+0.7%
corner_to_corner_astar	yes	152,818	153,796	+0.6%
corner_to_corner_fringe	yes	118,850	119,578	+0.6%
no_path_astar	yes	3,517,679	3,537,909	+0.6%
corner_to_corner_bfs	no (control)	2,636,674	2,636,676	0.0%
no_path_bfs	no (control)	2,543,357	2,543,360	0.0%
corner_to_corner_bfs_bidirectional	no (control)	2,797,635	2,797,664	0.0%
no_path_bfs_bidirectional	no (control)	2,662,484	2,662,523	0.0%
corner_to_corner_iddfs	no (control)	3,790,714	3,790,713	0.0%

Everything that adds costs pays between 0.6% and 3.3%, and five of the six that do not add costs are unchanged to the instruction.

So the trade is much better than I made it sound: under 1% on dijkstra, rather than 18%. The paragraph above where I said the cost was "your call rather than mine, and if the instruction count is too high a price I am happy to drop it" was written against the wrong number, and I would not raise that concern at 0.7%.

Everything else in my earlier comment stands: the release-mode wrap, the approach, and that a saturating cost type still opts out of the panic.