Changeset 13123


Ignore:
Timestamp:
Dec 31, 2011, 9:28:53 PM (9 years ago)
Author:
jordan
Message:

(trunk libT) #4690 "getPeerCandidates() uses more CPU than necessary" -- fixed.

Once we've scored all n candidates, we sort them by score so that we can pick out the k best candidates. If n is large, sorting them can be expensive. If we use the Selection Algorithm, we select in O(n) without having to sort.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/libtransmission/peer-mgr.c

    r12954 r13123  
    38333833}
    38343834
    3835 /* sort an array of peer candidates */
     3835#ifndef NDEBUG
    38363836static int
    3837 comparePeerCandidates( const void * va, const void * vb )
    3838 {
    3839     const struct peer_candidate * a = va;
    3840     const struct peer_candidate * b = vb;
    3841 
    3842     if( a->score < b->score ) return -1;
    3843     if( a->score > b->score ) return 1;
    3844 
    3845     return 0;
    3846 }
     3837checkPartition( const struct peer_candidate * candidates, int left, int right, uint64_t pivotScore, int storeIndex )
     3838{
     3839    int i;
     3840
     3841    assert( storeIndex >= left );
     3842    assert( storeIndex <= right );
     3843    assert( candidates[storeIndex].score == pivotScore );
     3844
     3845    for( i=left; i<storeIndex; ++i )
     3846        assert( candidates[i].score < pivotScore );
     3847    for( i=storeIndex+1; i<=right; ++i )
     3848        assert( candidates[i].score >= pivotScore );
     3849
     3850    return true;
     3851}
     3852#endif
     3853
     3854/* Helper to selectBestCandidates().
     3855 * Adapted from http://en.wikipedia.org/wiki/Selection_algorithm */
     3856static int
     3857partitionPeerCandidates( struct peer_candidate * candidates, int left, int right, int pivotIndex )
     3858{
     3859    int i;
     3860    int storeIndex;
     3861    struct peer_candidate tmp;
     3862    const struct peer_candidate pivotValue = candidates[pivotIndex];
     3863
     3864    /* move pivot to end */
     3865    tmp = candidates[right];
     3866    candidates[right] = pivotValue;
     3867    candidates[pivotIndex] = tmp;
     3868
     3869    storeIndex = left;
     3870    for( i=left; i<=right; ++i )
     3871    {
     3872        if( candidates[i].score < pivotValue.score )
     3873        {
     3874            tmp = candidates[storeIndex];
     3875            candidates[storeIndex] = candidates[i];
     3876            candidates[i] = tmp;
     3877            storeIndex++;
     3878        }
     3879    }
     3880
     3881    /* move pivot to its final place */
     3882    tmp = candidates[right];
     3883    candidates[right] = candidates[storeIndex];
     3884    candidates[storeIndex] = tmp;
     3885
     3886    /* sanity check */
     3887    assert( checkPartition( candidates, left, right, pivotValue.score, storeIndex ) );
     3888
     3889    return storeIndex;
     3890}
     3891
     3892/* Adapted from http://en.wikipedia.org/wiki/Selection_algorithm */
     3893static void
     3894selectPeerCandidates( struct peer_candidate * candidates, int left, int right, int k )
     3895{
     3896    if( right > left )
     3897    {
     3898        const int pivotIndex = left + (right-left)/2;
     3899
     3900        int pivotNewIndex = partitionPeerCandidates( candidates, left, right, pivotIndex );
     3901
     3902        if( pivotNewIndex > left + k ) /* new condition */
     3903            selectPeerCandidates( candidates, left, pivotNewIndex-1, k );
     3904        else if( pivotNewIndex < left + k )
     3905            selectPeerCandidates( candidates, pivotNewIndex+1, right, k+left-pivotNewIndex-1 );
     3906    }
     3907}
     3908
     3909#ifndef NDEBUG
     3910static bool
     3911checkBestScoresComeFirst( const struct peer_candidate * candidates, int n, int k )
     3912{
     3913    int i;
     3914    uint64_t worstFirstScore = 0;
     3915    const int x = MIN( n, k ) - 1;
     3916
     3917    for( i=0; i<x; i++ )
     3918        if( worstFirstScore < candidates[i].score )
     3919            worstFirstScore = candidates[i].score;
     3920
     3921    for( i=0; i<x; i++ )
     3922        assert( candidates[i].score <= worstFirstScore );
     3923
     3924    for( i=x+1; i<n; i++ )
     3925        assert( candidates[i].score >= worstFirstScore );
     3926
     3927    return true;
     3928}
     3929#endif /* NDEBUG */
    38473930
    38483931/** @return an array of all the atoms we might want to connect to */
    38493932static struct peer_candidate*
    3850 getPeerCandidates( tr_session * session, int * candidateCount )
     3933getPeerCandidates( tr_session * session, int * candidateCount, int max )
    38513934{
    38523935    int atomCount;
     
    39133996
    39143997    *candidateCount = walk - candidates;
    3915     if( *candidateCount > 1 )
    3916         qsort( candidates, *candidateCount, sizeof( struct peer_candidate ), comparePeerCandidates );
     3998    if( walk != candidates )
     3999        selectPeerCandidates( candidates, 0, (walk-candidates)-1, max );
     4000
     4001    assert( checkBestScoresComeFirst( candidates, *candidateCount, max ) );
     4002
    39174003    return candidates;
    39184004}
     
    39914077    struct peer_candidate * candidates;
    39924078
    3993     candidates = getPeerCandidates( mgr->session, &n );
     4079    candidates = getPeerCandidates( mgr->session, &n, max );
    39944080
    39954081    for( i=0; i<n && i<max; ++i )
Note: See TracChangeset for help on using the changeset viewer.