Use a linear algorithm to subtract two nodelists.

The nodelist_idx for each node_t serves as a unique identifier for
the node, so we can use a bitarray to hold all the excluded
nodes, and then remove them from the smartlist.

Previously use used smartlist_subtract(sl, excluded), which is
O(len(sl)*len(excluded)).

We can use this function in other places too, but this is the one
that showed up on the profiles of 30291.

Closes ticket 30307.

1 files changed, 4 insertions, 0 deletions

diff --git a/changes/ticket30307 b/changes/ticket30307
new file mode 100644
index 0000000000..abcacb6085
--- /dev/null
+++ b/changes/ticket30307
@@ -0,0 +1,4 @@
+  o Major features (performance):
+    - Update our node selection algorithm to exclude nodes in linear time.
+      Previously, the algorithm was quadratic, which could slow down heavily
+      used onion services.  Closes ticket 30307.