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>
Sun, 10 Dec 2023 03:41:52 +0000 (03:41 +0000)
commitadb69cdb99d0f38ad605cfbbd4898d0784ca09f9
tree5a6e33edd14a083b557d83e795f4d92f267ee0c6
parentdf45cd5165630731ace4bb887fc92814da5766b3
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