Opened 3 years ago

Last modified 11 months ago

#13739 new defect

Optimize the functions called in circuit_launch_by_extend_info()

Reported by: dgoulet Owned by:
Priority: Medium Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-hs, performance, profile, optimization
Cc: rob.g.jansen@… Actual Points:
Parent ID: #15463 Points:
Reviewer: Sponsor:

Description

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.

Child Tickets

Change History (12)

comment:1 Changed 3 years ago by nickm

Keywords: performance added

comment:2 Changed 3 years ago by nickm

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.

comment:3 Changed 3 years ago by nickm

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"?

comment:4 Changed 3 years ago by robgjansen

Cc: rob.g.jansen@… added

comment:5 Changed 3 years ago by yawning

Parent ID: #15463

comment:6 Changed 3 years ago by nickm

Keywords: SponsorR removed
Sponsor: SponsorR

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

comment:7 Changed 2 years ago by dgoulet

Sponsor: SponsorRSponsorR-can

Move those from SponsorR to SponsorR-can.

comment:8 Changed 17 months ago by teor

Milestone: Tor: 0.2.???Tor: 0.3.???

Milestone renamed

comment:9 Changed 16 months ago by nickm

Keywords: tor-03-unspecified-201612 added
Milestone: Tor: 0.3.???Tor: unspecified

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

comment:10 Changed 11 months ago by nickm

Keywords: tor-03-unspecified-201612 removed

Remove an old triaging keyword.

comment:11 Changed 11 months ago by dgoulet

Severity: Normal
Sponsor: SponsorR-can

comment:12 Changed 11 months ago by nickm

Keywords: profile optimization added
Note: See TracTickets for help on using tickets.