Pre-calculate heap element scores (retaining RouteGraphNode size) 2023-12-2551-followups
authorMatt Corallo <git@bluematt.me>
Wed, 6 Dec 2023 05:29:28 +0000 (05:29 +0000)
committerMatt Corallo <git@bluematt.me>
Fri, 8 Dec 2023 20:45:06 +0000 (20:45 +0000)
commit1171bc191349442eb9029ba3a6c8b0962a8455c3
tree4b59e0e36252e5510e4ea4d758c2a49f9a349aba
parent8ba3e83bb0a38b9fc8a3e492f70e6f78bd575d73
Pre-calculate heap element scores (retaining RouteGraphNode size)

`RouteGraphNode` currently recalculates scores in its `Ord`
implementation, wasting time while sorting the main Dijkstra's
heap.

Further, some time ago, when implementing the `htlc_maximum_msat`
amount reduction while walking the graph, we added
`PathBuildingHop::was_processed`, looking up the source node in
`dist` each time we pop'ed an element off of the binary heap.
As a result, we now have a reference to our `PathBuildingHop` when
processing a best-node's channels, leading to several fields in
`RouteGraphNode` being entirely redundant.

Here we drop those fields, but add a pre-calculated score field,
as well as force a suboptimal `RouteGraphNode` layout, retaining
its existing 64 byte size.

Without the suboptimal layout, performance is very mixed, but with
it performance is mostly improved, by around 10% in most tests.
lightning/src/routing/router.rs