Cache whether a node is a first-hop target in the per-node state
authorMatt Corallo <git@bluematt.me>
Sun, 10 Dec 2023 03:28:37 +0000 (03:28 +0000)
committerMatt Corallo <git@bluematt.me>
Wed, 20 Mar 2024 00:51:20 +0000 (00:51 +0000)
commitb208ffa15b264506fbea922055773d6a03dbcd20
treefafcda76a59d7dfaf8e909e1e8ccd8924a23d968
parente9327c8fe0f9bb66a238ee8553f5ec24aea26892
Cache whether a node is a first-hop target in the per-node state

When processing the main loop during routefinding, for each node,
we check whether it happens to be our peer in one of our channels.
This ensures we never fail to find a route that takes a hop through
a private channel of ours, to a private node, then through
invoice-provided route hints to reach the ultimate payee.

Because this is incredibly hot code, doing a full `HashMap` lookup
to check if each node is a first-hop target ends up eating a good
chunk of time during routing. Luckily, we can trivially avoid this
cost.

Because we're already looking up the per-node state in the `dist`
map, we can store a bool in each first-hop target's state, avoiding
the lookup unless we know its going to succeed.

This requires storing a dummy entry in `dist`, which feels somewhat
strange, but is ultimately fine as we should never be looking at
per-node state unless we've already found a path to that node,
updating the fields in doign so.
lightning/src/routing/router.rs