Optimize the functions called in circuit_launch_by_extend_info()

Ref to https://trac.torproject.org/projects/tor/ticket/8902#comment:10

You can see that on a loaded HS, some functions are called quite a lot and they take a lot of CPU.

https://people.torproject.org/~dgoulet/tor-hs-perf-100-circ.png

They should be optimize to bring that CPU usage down.

changed milestone to %Tor: unspecified

added component::core tor/tor milestone::Tor: unspecified optimization parent::30221 performance points::3 priority::medium profile resolution::duplicate severity::normal sponsor::27-can status::closed tor-hs type::defect labels

Trac:
Keywords: SponsorR, tor-hs deleted, tor-hs SponsorR performance added

These functions seem to be a maze of linear operations over the entire set of nodes: yuck. We need to look for better ways. One choice is to memoize results at some level; another is to precompute results at some level; another is to replace linear low-level ops with sublinear ones.

David suggest that optimizing nodelist_add_node_and_family() would suffice here. The expensive part of that is the linear iteration through the entire nodelist. What if we use freebsd's tree.h to build a red-black tree of nodes sorted by address, so that it's easy to get "all the nodes with the same prefix as X"?

Trac:
Cc: N/A to rob.g.jansen@nrl.navy.mil

Trac:
Parent: N/A to #15463 (moved)

Bulk-replace SponsorR keyword with SponsorR sponsor field in Tor component.

Trac:
Keywords: tor-hs SponsorR performance deleted, tor-hs, performance added
Sponsor: N/A to SponsorR

Move those from SponsorR to SponsorR-can.

Trac:
Sponsor: SponsorR to SponsorR-can

Milestone renamed

Trac:
Milestone: Tor: 0.2.??? to Tor: 0.3.???

Finally admitting that 0.3.??? was a euphemism for Tor: unspecified all along.

Trac:
Milestone: Tor: 0.3.??? to Tor: unspecified
Keywords: N/A deleted, tor-03-unspecified-201612 added

Remove an old triaging keyword.

Trac:
Keywords: tor-03-unspecified-201612 deleted, N/A added

Trac:
Sponsor: SponsorR-can to N/A
Severity: N/A to Normal
Reviewer: N/A to N/A

Trac:
Keywords: N/A deleted, optimization, profile added

Trac:
Sponsor: N/A to Sponsor27

Trac:
Sponsor: Sponsor27 to Sponsor27-can

Trac:
Points: N/A to 3

Trac:
Parent: #15463 (moved) to N/A

Trac:
Parent: N/A to #30221 (moved)

Closing in favor of the more complete #30291 (moved)

Trac:
Resolution: N/A to duplicate
Status: new to closed

closed

changed time estimate to 24h

mentioned in issue #15463 (moved)

mentioned in issue #15516 (moved)

mentioned in issue #30291 (moved)

mentioned in issue #30221 (moved)

moved to tpo/core/tor#13739 (closed)

mentioned in issue tpo/core/tor#30291 (closed)