]> git.bitcoin.ninja Git - rust-lightning/commit
Drop A* implementation in the router for simple Dijkstra's
authorMatt Corallo <git@bluematt.me>
Tue, 25 Oct 2022 03:15:03 +0000 (03:15 +0000)
committerMatt Corallo <git@bluematt.me>
Wed, 25 Jan 2023 17:17:55 +0000 (17:17 +0000)
commita3f7b790b45698ccc33d9f08265a1863688c08fe
tree8b37bab671105112f5f936f1068dd9b3e45e81b0
parentefdd2217b78b1b5b3cbbcb8f4bce26f1c6a0cf87
Drop A* implementation in the router for simple Dijkstra's

As evidenced by the previous commit, it appears our A* router
does worse than a more naive approach. This isn't super surpsising,
as the A* heuristic calculation requires a map lookup, which is
relatively expensive.

```
test routing::router::benches::generate_mpp_routes_with_probabilistic_scorer ... bench: 169,991,943 ns/iter (+/- 30,838,048)
test routing::router::benches::generate_mpp_routes_with_zero_penalty_scorer  ... bench: 122,144,987 ns/iter (+/- 61,708,911)
test routing::router::benches::generate_routes_with_probabilistic_scorer     ... bench:  48,546,068 ns/iter (+/- 10,379,642)
test routing::router::benches::generate_routes_with_zero_penalty_scorer      ... bench:  32,898,557 ns/iter (+/- 14,157,641)
```
lightning/src/routing/gossip.rs
lightning/src/routing/router.rs