Changeset 9920


Ignore:
Timestamp:
Jan 12, 2010, 8:17:22 PM (12 years ago)
Author:
charles
Message:

(trunk libT) #2705 "speeding up request queue management" -- committed v1.1.diff for 1.80

File:
1 edited

Legend:

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

    r9890 r9920  
    157157{
    158158    tr_piece_index_t index;
    159     tr_piece_index_t salt;
     159    int16_t salt;
    160160    int16_t requestCount;
    161161};
     
    181181
    182182    struct weighted_piece    * pieces;
    183     int                        piecesSort;
    184183    int                        pieceCount;
    185 
    186     tr_bool                    isInEndgame;
    187184}
    188185Torrent;
     
    806803         || mode==PIECES_SORTED_BY_WEIGHT );
    807804
    808     if( t->piecesSort != mode )
    809     {
    810         t->piecesSort = mode;
    811 
    812         switch( mode ) {
    813             case PIECES_SORTED_BY_WEIGHT: compar = comparePieceByWeight; break;
    814             case PIECES_SORTED_BY_INDEX: compar = comparePieceByIndex; break;
    815             default: assert( 0 && "unhandled" );  break;
    816         }
    817 
    818         weightTorrent = t->tor;
    819         qsort( t->pieces, t->pieceCount,
    820                sizeof( struct weighted_piece ), compar );
    821     }
    822 
    823     /* Also, as long as we've got the pieces sorted by weight,
    824      * let's also update t.isInEndgame */
    825     if( t->piecesSort == PIECES_SORTED_BY_WEIGHT )
    826     {
    827         tr_bool endgame = TRUE;
    828 
    829         if( ( t->pieces != NULL ) && ( t->pieceCount > 0 ) )
    830         {
    831             const tr_completion * cp = &t->tor->completion;
    832             const struct weighted_piece * p = t->pieces;
    833             const int pending = p->requestCount;
    834             const int missing = tr_cpMissingBlocksInPiece( cp, p->index );
    835             endgame = pending >= missing;
    836         }
    837 
    838         t->isInEndgame = endgame;
    839         /*if( t->isInEndgame ) fprintf( stderr, "ENDGAME reached\n" );*/
    840     }
     805    switch( mode ) {
     806        case PIECES_SORTED_BY_WEIGHT: compar = comparePieceByWeight; break;
     807        case PIECES_SORTED_BY_INDEX: compar = comparePieceByIndex; break;
     808        default: assert( 0 && "unhandled" );  break;
     809    }
     810
     811    weightTorrent = t->tor;
     812    qsort( t->pieces, t->pieceCount,
     813           sizeof( struct weighted_piece ), compar );
     814}
     815
     816static tr_bool
     817isInEndgame( Torrent * t )
     818{
     819    tr_bool endgame = TRUE;
     820
     821    if( ( t->pieces != NULL ) && ( t->pieceCount > 0 ) )
     822    {
     823        const tr_completion * cp = &t->tor->completion;
     824        const struct weighted_piece * p = t->pieces;
     825        const int pending = p->requestCount;
     826        const int missing = tr_cpMissingBlocksInPiece( cp, p->index );
     827        endgame = pending >= missing;
     828    }
     829
     830    /*if( endgame ) fprintf( stderr, "ENDGAME reached\n" );*/
     831    return endgame;
    841832}
    842833
     
    844835pieceListLookup( Torrent * t, tr_piece_index_t index )
    845836{
    846     struct weighted_piece key;
    847     key.index = index;
    848 
    849     pieceListSort( t, PIECES_SORTED_BY_INDEX );
    850 
    851     return bsearch( &key, t->pieces, t->pieceCount,
    852                     sizeof( struct weighted_piece ),
    853                     comparePieceByIndex );
     837    const struct weighted_piece * limit = t->pieces;
     838    struct weighted_piece * piece = t->pieces + t->pieceCount - 1;
     839
     840    if ( t->pieceCount == 0 ) return NULL;
     841
     842    /* reverse linear search */
     843    for( ;; )
     844    {
     845        if( piece < limit ) return NULL;
     846        if( index == piece->index ) return piece; else --piece;
     847    }
    854848}
    855849
     
    907901        t->pieces = pieces;
    908902        t->pieceCount = pieceCount;
    909         t->piecesSort = PIECES_SORTED_BY_INDEX;
     903
     904        pieceListSort( t, PIECES_SORTED_BY_WEIGHT );
    910905
    911906        /* cleanup */
     
    938933pieceListRemoveRequest( Torrent * t, tr_block_index_t block )
    939934{
    940     struct weighted_piece * p;
    941935    const tr_piece_index_t index = tr_torBlockPiece( t->tor, block );
    942 
    943     if(( p = pieceListLookup( t, index )))
    944         if( p->requestCount > 0 )
    945             --p->requestCount;
    946 
    947     /* note: this invalidates the weighted.piece.weight field,
    948      * but that's OK since the call to pieceListLookup ensured
    949      * that we were sorted by index anyway.. next time we resort
    950      * by weight, pieceListSort() will update the weights */
     936    const struct weighted_piece * p = pieceListLookup( t, index );
     937
     938    if( p != NULL )
     939    {
     940        const int pos = p - t->pieces;
     941        struct weighted_piece piece = t->pieces[pos];
     942        int newpos;
     943        tr_bool exact;
     944
     945        /* remove request */
     946        if( piece.requestCount > 0 )
     947            --piece.requestCount;
     948
     949        /* List is nearly sorted (by weight) : insert piece into the right place. */
     950
     951        weightTorrent = t->tor;
     952        newpos = tr_lowerBound( &piece, t->pieces, t->pieceCount,
     953                                sizeof( struct weighted_piece ),
     954                                comparePieceByWeight, &exact );
     955
     956        if( newpos == pos || newpos == pos + 1 )
     957        {
     958            /* it's VERY likely that piece keeps its position */
     959            t->pieces[pos].requestCount = piece.requestCount;
     960        }
     961        else
     962        {
     963            /* piece is removed temporally to make insertion easier */
     964            memmove( &t->pieces[pos],
     965                     &t->pieces[pos + 1],
     966                     sizeof( struct weighted_piece ) * ( --t->pieceCount - pos ) );
     967
     968            if( newpos > pos ) --newpos;
     969
     970            memmove( &t->pieces[newpos + 1],
     971                     &t->pieces[newpos],
     972                     sizeof( struct weighted_piece ) * ( t->pieceCount++ - newpos ) );
     973
     974            t->pieces[newpos] = piece;
     975        }
     976    }
    951977}
    952978
     
    973999    int got;
    9741000    Torrent * t;
     1001    tr_bool endgame;
    9751002    struct weighted_piece * pieces;
    9761003    const tr_bitset * have = &peer->have;
     
    9871014    if( t->pieces == NULL )
    9881015        pieceListRebuild( t );
    989     pieceListSort( t, PIECES_SORTED_BY_WEIGHT );
     1016
     1017    endgame = isInEndgame( t );
    9901018
    9911019    pieces = t->pieces;
     
    9941022        struct weighted_piece * p = pieces + i;
    9951023        const int missing = tr_cpMissingBlocksInPiece( &tor->completion, p->index );
    996         const int maxDuplicatesPerBlock = t->isInEndgame ? 3 : 1;
     1024        const int maxDuplicatesPerBlock = endgame ? 3 : 1;
    9971025
    9981026        if( p->requestCount > ( missing * maxDuplicatesPerBlock ) )
     
    10301058
    10311059    /* In most cases we've just changed the weights of a small number of pieces.
    1032      * So rather than qsort()ing the entire array, it's faster to sort only the
    1033      * changed ones, then do a standard merge-two-sorted-arrays pass on the
    1034      * changed and unchanged pieces. */
     1060     * So rather than qsort()ing the entire array, it's faster to apply an
     1061     * adaptive insertion sort algorithm. */
    10351062    if( got > 0 )
    10361063    {
    1037         struct weighted_piece * p;
    1038         struct weighted_piece * pieces;
    1039         struct weighted_piece * a = t->pieces;
    1040         struct weighted_piece * a_end = t->pieces + i;
    1041         struct weighted_piece * b = a_end;
    1042         struct weighted_piece * b_end = t->pieces + t->pieceCount;
    1043 
    1044         /* resort the pieces that we changed */
     1064        /* not enough requests || last piece modified */
     1065        if ( i == t->pieceCount ) --i;
     1066
    10451067        weightTorrent = t->tor;
    1046         qsort( a, a_end-a, sizeof( struct weighted_piece ), comparePieceByWeight );
    1047 
    1048         /* allocate a new array */
    1049         p = pieces = tr_new( struct weighted_piece, t->pieceCount );
    1050 
    1051         /* merge the two sorted arrays into this new array */
    1052         weightTorrent = t->tor;
    1053         while( a!=a_end && b!=b_end )
    1054             *p++ = comparePieceByWeight( a, b ) < 0 ? *a++ : *b++;
    1055         while( a!=a_end ) *p++ = *a++;
    1056         while( b!=b_end ) *p++ = *b++;
    1057 
    1058 #if 0
    1059         /* make sure we did it right */
    1060         assert( p - pieces == t->pieceCount );
    1061         for( it=pieces; it+1<p; ++it )
    1062             assert( it->weight <= it[1].weight );
    1063 #endif
    1064 
    1065         /* update */
    1066         tr_free( t->pieces );
    1067         t->pieces = pieces;
     1068        while( --i >= 0 )
     1069        {
     1070            tr_bool exact;
     1071
     1072            /* relative position! */
     1073            const int newpos = tr_lowerBound( &t->pieces[i], &t->pieces[i + 1],
     1074                                              t->pieceCount - (i + 1),
     1075                                              sizeof( struct weighted_piece ),
     1076                                              comparePieceByWeight, &exact );
     1077            if( newpos > 0 )
     1078            {
     1079                const struct weighted_piece piece = t->pieces[i];
     1080                memmove( &t->pieces[i],
     1081                         &t->pieces[i + 1],
     1082                         sizeof( struct weighted_piece ) * ( newpos ) );
     1083                t->pieces[i + newpos] = piece;
     1084            }
     1085        }
    10681086    }
    10691087
     
    13681386
    13691387            requestListRemove( t, block, peer );
    1370             pieceListRemoveRequest( t, block );
    13711388
    13721389            if( tr_cpBlockIsComplete( &tor->completion, block ) )
     
    13741391                tordbg( t, "we have this block already..." );
    13751392                clientGotUnwantedBlock( tor, block );
     1393                pieceListRemoveRequest( t, block );
    13761394            }
    13771395            else
    13781396            {
    13791397                tr_cpBlockAdd( &tor->completion, block );
     1398                pieceListRemoveRequest( t, block );
    13801399                tr_torrentSetDirty( tor );
    13811400
Note: See TracChangeset for help on using the changeset viewer.