[tor-bugs] #30291 [Core Tor/Tor]: Optimize our path selection code

[Tor Bug Tracker & Wiki]

#30291: Optimize our path selection code
-------------------------------------------------+-------------------------
 Reporter:  dgoulet                              |          Owner:  (none)
     Type:  enhancement                          |         Status:  new
 Priority:  Medium                               |      Milestone:  Tor:
                                                 |  unspecified
Component:  Core Tor/Tor                         |        Version:
 Severity:  Normal                               |     Resolution:
 Keywords:  tor-performance tor-hs path-         |  Actual Points:
  selection refactoring tor-dos                  |
Parent ID:  #30221                               |         Points:  10
 Reviewer:                                       |        Sponsor:
                                                 |  Sponsor27-can
-------------------------------------------------+-------------------------

Comment (by nickm):

 Replying to [ticket:30291 dgoulet]:
 >This is in theory `O(n) + O(n) + O(n)` actually theoretically being
 `O(n)` but reality is far from the theory here in CPU consumption ;).

 For the record, it's actually worse.  `smartlist_subtract(l1, l2)` is not
 linear, but quadratic: it runs in `O(smartlist_len(l1) *
 smartlist_len(l2)`.  Fix (for this case of it) in #30307

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/30291#comment:4>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online