Opened 12 years ago

Closed 12 years ago

#1623 closed Enhancement (fixed)

Improve request list performance

Reported by: wereHamster Owned by: charles
Priority: Normal Milestone: 1.50
Component: libtransmission Version: 1.40
Severity: Normal Keywords:
Cc: tom@…

Description

At high speeds, when T is leeching (downloading from other peers) it spends the most time on managing the request lists. The request list (struct request_list in peer-msgs.c) is implemented as an array. reqListAppend is O(1) but reqListFind and reqListRemove are both O(n). reqListFind is called from refillPulse -> tr_peerMsgsAddRequest to ensure no duplicate requests are added to the list, and reqListRemove is called from clientGotBlock -> ... -> tr_peerMsgsCancel when the client receives a block and removes requests of that block from all other request queues. reqListRemove is calling reqListFind and reqListFind is repeatedly calling compareRequest to find the request in the list.

What it means in numbers. In a test I did, T spent ~27% of the time in reqListFind and ~70% of the time in compareRequest. So some ~90% of the time is spent in managing the request queue!

Attachments (1)

request-list-callgraph.png (218.5 KB) - added by wereHamster 12 years ago.

Download all attachments as: .zip

Change History (3)

Changed 12 years ago by wereHamster

comment:1 Changed 12 years ago by charles

  • Milestone changed from None Set to 1.50
  • Status changed from new to assigned
  • Version changed from 1.40+ to 1.40

comment:2 Changed 12 years ago by charles

  • Resolution set to fixed
  • Status changed from assigned to closed

Fixed in trunk in r7610, r6711, r7613

Note: See TracTickets for help on using tickets.