#30307 closed defect (fixed)

Make router_choose_random_node() linear instead of quadratic

Reported by: nickm Owned by: nickm
Priority: Medium Milestone: Tor: 0.4.1.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-performance tor-hs path-selection refactoring tor-dos
Cc: Actual Points: .3
Parent ID: #30291 Points:
Reviewer: dgoulet Sponsor: Sponsor27-can


See parent for motivation.

The smartlist_subtract() function is O(m*n), so we should try not to use it here if we can.

Child Tickets

Change History (4)

comment:1 Changed 18 months ago by nickm

Actual Points: .3
Milestone: Tor: unspecifiedTor: 0.4.1.x-final
Status: assignedneeds_review

See branch ticket30307_30308 with PR in https://github.com/torproject/tor/pull/983

comment:2 Changed 18 months ago by dgoulet

Reviewer: dgoulet

comment:3 Changed 18 months ago by dgoulet

Status: needs_reviewmerge_ready

This looks great! Will test the performance gain shortly!

comment:4 Changed 18 months ago by dgoulet

Resolution: fixed
Status: merge_readyclosed

Merged through #30308

Note: See TracTickets for help on using tickets.