Show
Ignore:
Timestamp:
03/24/10 15:27:00 (5 years ago)
Author:
robert
Message:

Refactored the way that the RequestQueue?'s are pruned and highest prioty items taken from them so the operation is
now O(n) rather than O(nlogn) where n is the number of requests. The refactoring also cleans up the access of the
request lists so that the code is more readable/maintainable.

Files:
1 modified

Legend:

Unmodified
Added
Removed
  • OpenSceneGraph/trunk/src/osgDB/DatabasePager.cpp

    r11236 r11285  
    282282//  RequestQueue 
    283283// 
     284DatabasePager::RequestQueue::RequestQueue(DatabasePager* pager): 
     285    _pager(pager), 
     286    _frameNumberLastPruned(-1) 
     287{ 
     288} 
     289 
     290DatabasePager::RequestQueue::~RequestQueue() 
     291{ 
     292    OSG_INFO<<"DatabasePager::RequestQueue::~RequestQueue() Destructing queue."<<std::endl; 
     293    for(RequestList::iterator itr = _requestList.begin(); 
     294        itr != _requestList.end(); 
     295        ++itr) 
     296    { 
     297        (*itr)->invalidate(); 
     298    } 
     299} 
     300 
    284301void DatabasePager::DatabaseRequest::invalidate() 
    285302{ 
     
    292309} 
    293310 
    294 DatabasePager::RequestQueue::~RequestQueue() 
    295 { 
    296     OSG_INFO<<"DatabasePager::RequestQueue::~RequestQueue() Destructing queue."<<std::endl; 
    297     for(RequestList::iterator itr = _requestList.begin(); 
    298         itr != _requestList.end(); 
    299         ++itr) 
    300     { 
    301         (*itr)->invalidate(); 
    302     } 
    303 } 
    304  
    305 void DatabasePager::RequestQueue::sort() 
    306 { 
    307     std::sort(_requestList.begin(),_requestList.end(),SortFileRequestFunctor()); 
    308 } 
    309  
     311bool DatabasePager::RequestQueue::pruneOldRequestsAndCheckIfEmpty() 
     312{ 
     313    OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_requestMutex); 
     314 
     315    if (_frameNumberLastPruned != _pager->_frameNumber) 
     316    { 
     317        for(RequestQueue::RequestList::iterator citr = _requestList.begin(); 
     318            citr != _requestList.end(); 
     319            ) 
     320        { 
     321            if ((*citr)->isRequestCurrent(_pager->_frameNumber)) 
     322            { 
     323                ++citr; 
     324            } 
     325            else 
     326            { 
     327                (*citr)->invalidate(); 
     328 
     329                citr = _requestList.erase(citr); 
     330                OSG_INFO<<"DatabasePager::RequestQueue::pruneOldRequestsAndCheckIfEmpty(): Pruning "<<(*citr)<<std::endl; 
     331            } 
     332        } 
     333 
     334        _frameNumberLastPruned = _pager->_frameNumber; 
     335 
     336        updateBlock(); 
     337    } 
     338 
     339    return _requestList.empty(); 
     340} 
     341 
     342 
     343void DatabasePager::RequestQueue::clear() 
     344{ 
     345    OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_requestMutex); 
     346 
     347    for(RequestList::iterator citr = _requestList.begin(); 
     348        citr != _requestList.end(); 
     349        ++citr) 
     350    { 
     351        (*citr)->invalidate(); 
     352    } 
     353 
     354    _requestList.clear(); 
     355 
     356    _frameNumberLastPruned = _pager->_frameNumber; 
     357 
     358    updateBlock(); 
     359} 
     360 
     361 
     362void DatabasePager::RequestQueue::add(DatabasePager::DatabaseRequest* databaseRequest) 
     363{ 
     364    OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_requestMutex); 
     365 
     366    _requestList.push_back(databaseRequest); 
     367    databaseRequest->_requestQueue = this; 
     368 
     369    updateBlock(); 
     370} 
     371 
     372void DatabasePager::RequestQueue::takeFirst(osg::ref_ptr<DatabaseRequest>& databaseRequest) 
     373{ 
     374    OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_requestMutex); 
     375 
     376    if (!_requestList.empty()) 
     377    { 
     378        DatabasePager::SortFileRequestFunctor highPriority; 
     379 
     380        RequestQueue::RequestList::iterator selected_itr = _requestList.end(); 
     381 
     382        for(RequestQueue::RequestList::iterator citr = _requestList.begin(); 
     383            citr != _requestList.end(); 
     384            ) 
     385        { 
     386            if ((*citr)->isRequestCurrent(_pager->_frameNumber)) 
     387            { 
     388                if (selected_itr==_requestList.end() || highPriority(*citr, *selected_itr)) 
     389                { 
     390                    selected_itr = citr; 
     391                } 
     392 
     393                ++citr; 
     394            } 
     395            else 
     396            { 
     397                (*citr)->invalidate(); 
     398 
     399                citr = _requestList.erase(citr); 
     400                OSG_INFO<<"DatabasePager::RequestQueue::takeFirst(): Pruning "<<(*citr)<<std::endl; 
     401            } 
     402 
     403        } 
     404 
     405        _frameNumberLastPruned = _pager->_frameNumber; 
     406 
     407        if (selected_itr != _requestList.end()) 
     408        { 
     409            databaseRequest = *selected_itr; 
     410            databaseRequest->_requestQueue = 0; 
     411            _requestList.erase(selected_itr); 
     412            OSG_INFO<<" DatabasePager::RequestQueue::takeFirst() Found DatabaseRequest size()="<<_requestList.size()<<std::endl; 
     413        } 
     414        else 
     415        { 
     416            OSG_INFO<<" DatabasePager::RequestQueue::takeFirst() No suitable DatabaseRequest found size()="<<_requestList.size()<<std::endl; 
     417        } 
     418 
     419        updateBlock(); 
     420    } 
     421} 
    310422 
    311423///////////////////////////////////////////////////////////////////////////////////////////////////////////////// 
     
    314426// 
    315427DatabasePager::ReadQueue::ReadQueue(DatabasePager* pager, const std::string& name): 
    316     _pager(pager), 
    317     _name(name), 
    318     _frameNumberLastPruned(-1) 
     428    RequestQueue(pager), 
     429    _name(name) 
    319430{ 
    320431    _block = new osg::RefBlock; 
    321432} 
    322433 
    323 void DatabasePager::ReadQueue::clear() 
    324 { 
    325     OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_requestMutex); 
    326  
    327     for(RequestList::iterator citr = _requestList.begin(); 
    328         citr != _requestList.end(); 
    329         ++citr) 
    330     { 
    331         (*citr)->invalidate(); 
    332     } 
    333  
    334     _requestList.clear(); 
    335  
    336     updateBlock(); 
    337 } 
    338  
    339 void DatabasePager::ReadQueue::add(DatabasePager::DatabaseRequest* databaseRequest) 
    340 { 
    341     OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_requestMutex); 
    342     _requestList.push_back(databaseRequest); 
    343     databaseRequest->_requestQueue = this; 
    344  
    345     updateBlock(); 
    346 } 
    347  
    348 void DatabasePager::ReadQueue::takeFirst(osg::ref_ptr<DatabaseRequest>& databaseRequest) 
    349 { 
    350     OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_requestMutex); 
    351  
    352     if (!_requestList.empty()) 
    353     { 
    354         sort(); 
    355  
    356         if (_frameNumberLastPruned != _pager->_frameNumber) 
    357         { 
    358             // Prune all the old entries. 
    359             RequestQueue::RequestList::iterator tooOld 
    360                 = std::find_if(_requestList.begin(), 
    361                                 _requestList.end(), 
    362                                 refPtrAdapt(std::not1(std::bind2nd(std::mem_fun(&DatabaseRequest::isRequestCurrent), 
    363                                 _pager->_frameNumber)))); 
    364  
    365             // delete the entries 
    366             for(RequestQueue::RequestList::iterator citr = tooOld; 
    367                 citr != _requestList.end(); 
    368                 ++citr) 
    369             { 
    370                 (*citr)->invalidate(); 
    371             } 
    372  
    373             _requestList.erase(tooOld, _requestList.end()); 
    374  
    375             _frameNumberLastPruned = _pager->_frameNumber; 
    376         } 
    377  
    378         if (!_requestList.empty()) 
    379         { 
    380             databaseRequest = _requestList.front(); 
    381             databaseRequest->_requestQueue = 0; 
    382             _requestList.erase(_requestList.begin()); 
    383         } 
    384  
    385         updateBlock(); 
    386     } 
     434void DatabasePager::ReadQueue::updateBlock() 
     435{ 
     436    _block->set((!_requestList.empty() || !_childrenToDeleteList.empty()) && 
     437                !_pager->_databasePagerThreadPaused); 
    387438} 
    388439 
     
    712763                if (loadedObjectsNeedToBeCompiled) 
    713764                { 
    714                     OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_pager->_dataToCompileList->_requestMutex); 
    715                     databaseRequest->_requestQueue = _pager->_dataToCompileList.get(); 
    716                     _pager->_dataToCompileList->_requestList.push_back(databaseRequest); 
     765                    _pager->_dataToCompileList->add(databaseRequest.get()); 
    717766                } 
    718767                else 
    719768                { 
    720                     OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_pager->_dataToMergeList->_requestMutex); 
    721                     databaseRequest->_requestQueue = _pager->_dataToMergeList.get(); 
    722                     _pager->_dataToMergeList->_requestList.push_back(databaseRequest); 
     769                    _pager->_dataToMergeList->add(databaseRequest.get()); 
    723770                } 
    724             }         
     771            } 
    725772 
    726773            // Prepare and prune the to-be-compiled list here in 
     
    729776            if (loadedObjectsNeedToBeCompiled) 
    730777            { 
    731                 OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_pager->_dataToCompileList->_requestMutex); 
    732  
    733                 _pager->_dataToCompileList->sort(); 
    734  
    735                 // Prune all the old entries. 
    736                 RequestQueue::RequestList::iterator tooOld 
    737                     = std::find_if(_pager->_dataToCompileList->_requestList.begin(), 
    738                                    _pager->_dataToCompileList->_requestList.end(), 
    739                                    refPtrAdapt(std::not1(std::bind2nd(std::mem_fun(&DatabaseRequest::isRequestCurrent), 
    740                                    _pager->_frameNumber)))); 
    741  
    742                 // This is the database thread, so just delete 
    743                 for(RequestQueue::RequestList::iterator citr = tooOld; 
    744                     citr != _pager->_dataToCompileList->_requestList.end(); 
    745                     ++citr) 
    746                 { 
    747                     OSG_INFO<<_name<<": pruning from compile list"<<std::endl; 
    748                     (*citr)->_loadedModel = 0; 
    749                     (*citr)->_requestQueue = 0; 
    750                 } 
    751  
    752                 _pager->_dataToCompileList->_requestList.erase(tooOld, _pager->_dataToCompileList->_requestList.end()); 
    753  
    754                 loadedObjectsNeedToBeCompiled = !_pager->_dataToCompileList->_requestList.empty(); 
     778                loadedObjectsNeedToBeCompiled = ! _pager->_dataToCompileList->pruneOldRequestsAndCheckIfEmpty(); 
    755779            } 
    756780 
     
    972996    _httpRequestQueue = new ReadQueue(this,"httpRequestQueue"); 
    973997     
    974     _dataToCompileList = new RequestQueue; 
    975     _dataToMergeList = new RequestQueue; 
     998    _dataToCompileList = new RequestQueue(this); 
     999    _dataToMergeList = new RequestQueue(this); 
    9761000     
    9771001    setUpThreads( 
     
    10201044    _httpRequestQueue = new ReadQueue(this,"httpRequestQueue"); 
    10211045     
    1022     _dataToCompileList = new RequestQueue; 
    1023     _dataToMergeList = new RequestQueue; 
     1046    _dataToCompileList = new RequestQueue(this); 
     1047    _dataToMergeList = new RequestQueue(this); 
    10241048 
    10251049    for(DatabaseThreadList::const_iterator dt_itr = rhs._databaseThreads.begin(); 
     
    11741198    _fileRequestQueue->clear(); 
    11751199    _httpRequestQueue->clear(); 
    1176          
    1177     { 
    1178         OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_dataToCompileList->_requestMutex); 
    1179         for(RequestQueue::RequestList::iterator citr = _dataToCompileList->_requestList.begin(); 
    1180             citr != _dataToCompileList->_requestList.end(); 
    1181             ++citr) 
    1182         { 
    1183             (*citr)->_loadedModel = 0; 
    1184             (*citr)->_requestQueue = 0; 
    1185         } 
    1186         _dataToCompileList->_requestList.clear(); 
    1187     } 
    1188  
    1189     { 
    1190         OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_dataToMergeList->_requestMutex); 
    1191         for(RequestQueue::RequestList::iterator citr = _dataToMergeList->_requestList.begin(); 
    1192             citr != _dataToMergeList->_requestList.end(); 
    1193             ++citr) 
    1194         { 
    1195             (*citr)->_loadedModel = 0; 
    1196             (*citr)->_requestQueue = 0; 
    1197         } 
    1198         _dataToMergeList->_requestList.clear(); 
    1199     } 
     1200 
     1201    _dataToCompileList->clear(); 
     1202    _dataToMergeList->clear(); 
    12001203 
    12011204    // note, no need to use a mutex as the list is only accessed from the update thread. 
     
    12821285    { 
    12831286        DatabaseRequest* databaseRequest = dynamic_cast<DatabaseRequest*>(databaseRequestRef.get()); 
    1284         if (databaseRequest && databaseRequest->valid()) 
    1285         { 
    1286             OSG_NOTICE<<"DatabaseRequest has been previously invalidated whilst still attached to scene graph."<<std::endl; 
     1287        if (databaseRequest && !(databaseRequest->valid())) 
     1288        { 
     1289            OSG_INFO<<"DatabaseRequest has been previously invalidated whilst still attached to scene graph."<<std::endl; 
    12871290            databaseRequest = 0; 
    12881291        } 
     
    12971300                OpenThreads::ScopedLock<OpenThreads::Mutex> lock(requestQueue->_requestMutex); 
    12981301 
     1302                databaseRequest->_valid = true; 
    12991303                databaseRequest->_frameNumberLastRequest = frameNumber; 
    13001304                databaseRequest->_timestampLastRequest = timestamp; 
     
    13041308            else 
    13051309            { 
     1310                databaseRequest->_valid = true; 
    13061311                databaseRequest->_frameNumberLastRequest = frameNumber; 
    13071312                databaseRequest->_timestampLastRequest = timestamp; 
     
    13161321                OSG_INFO<<"DatabasePager::requestNodeFile("<<fileName<<") orphaned, resubmitting."<<std::endl; 
    13171322 
     1323                databaseRequest->_valid = true; 
    13181324                databaseRequest->_frameNumberFirstRequest = frameNumber; 
    13191325                databaseRequest->_timestampFirstRequest = timestamp; 
     
    13451351            databaseRequestRef = databaseRequest.get(); 
    13461352 
     1353            databaseRequest->_valid = true; 
    13471354            databaseRequest->_fileName = fileName; 
    13481355            databaseRequest->_frameNumberFirstRequest = frameNumber; 
     
    14221429bool DatabasePager::requiresUpdateSceneGraph() const 
    14231430{ 
    1424     { 
    1425         OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_dataToMergeList->_requestMutex); 
    1426         if (!_dataToMergeList->_requestList.empty()) return true; 
    1427     } 
    1428      
    1429     return false; 
    1430      
     1431#if 0 
     1432    OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_dataToMergeList->_requestMutex); 
     1433#endif 
     1434    return !(_dataToMergeList->_requestList.empty()); 
    14311435} 
    14321436 
     
    14581462#ifdef UPDATE_TIMING 
    14591463    double elapsedTime = timer.elapsedTime_m(); 
    1460     if (elapsedTime>0.2) 
     1464    if (elapsedTime>1.0) 
    14611465    { 
    14621466        OSG_NOTICE<<"DatabasePager::updateSceneGraph() total time = "<<elapsedTime<<"ms"<<std::endl; 
     
    18351839bool DatabasePager::requiresCompileGLObjects() const 
    18361840{ 
     1841#if 0 
    18371842    OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_dataToCompileList->_requestMutex); 
     1843#endif 
    18381844    return !_dataToCompileList->_requestList.empty(); 
    18391845} 
     
    19051911 
    19061912        osg::ref_ptr<DatabaseRequest> databaseRequest; 
    1907  
    1908         // get the first compilable entry. 
    1909         { 
    1910             OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_dataToCompileList->_requestMutex); 
    1911          
    1912             // advance to the next entry to compile if one is available. 
    1913             databaseRequest = _dataToCompileList->_requestList.empty() ? 0 : _dataToCompileList->_requestList.front().get(); 
    1914         }; 
     1913        _dataToCompileList->takeFirst(databaseRequest); 
    19151914 
    19161915        unsigned int numObjectsCompiled = 0; 
     
    19181917        // while there are valid databaseRequest's in the to compile list and there is 
    19191918        // sufficient time left compile each databaseRequest's stateset and drawables. 
    1920         while (databaseRequest.valid() && (compileAll || (elapsedTime<availableTime && numObjectsCompiled<_maximumNumOfObjectsToCompilePerFrame)) )  
     1919        while (databaseRequest.valid() && databaseRequest->valid() && (compileAll || (elapsedTime<availableTime && numObjectsCompiled<_maximumNumOfObjectsToCompilePerFrame)) ) 
    19211920        { 
    19221921            DataToCompileMap& dcm = databaseRequest->_dataToCompileMap; 
     
    20282027                // we've compiled all of the current databaseRequest so we can now pop it off the 
    20292028                // to compile list and place it on the merge list. 
    2030                 // OSG_NOTICE<<"All compiled"<<std::endl; 
    2031  
    2032  
    2033                 OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_dataToCompileList->_requestMutex); 
    2034  
    2035                 // The request might have been removed from the 
    2036                 // _dataToCompile list by another graphics thread, in 
    2037                 // which case it's already on the merge list, or by 
    2038                 // the pager, which means that the request has 
    2039                 // expired. Also, the compile list might have been 
    2040                 // shuffled by the pager, so the current request is 
    2041                 // not guaranteed to still be at the beginning of the 
    2042                 // list. 
    2043                  
    2044                 RequestQueue::RequestList::iterator requestIter 
    2045                     = std::find(_dataToCompileList->_requestList.begin(), _dataToCompileList->_requestList.end(), 
    2046                            databaseRequest); 
    2047                 if (requestIter != _dataToCompileList->_requestList.end()) 
    2048                 { 
    2049                     { 
    2050                         OpenThreads::ScopedLock<OpenThreads::Mutex> lock(_dataToMergeList->_requestMutex); 
    2051                         databaseRequest->_requestQueue = _dataToMergeList.get(); 
    2052                         _dataToMergeList->_requestList.push_back(databaseRequest); 
    2053                     } 
    2054                     _dataToCompileList->_requestList.erase(requestIter); 
    2055                 } 
    2056                  
    2057                 if (!_dataToCompileList->_requestList.empty()) databaseRequest = _dataToCompileList->_requestList.front(); 
    2058                 else databaseRequest = 0; 
    2059  
    2060             } 
    2061             else  
    2062             { 
    2063                 // OSG_NOTICE<<"Not all compiled"<<std::endl; 
     2029                OSG_INFO<<"All compiled"<<std::endl; 
     2030 
     2031                _dataToMergeList->add(databaseRequest.get()); 
     2032 
     2033                databaseRequest = 0; 
     2034                _dataToCompileList->takeFirst(databaseRequest); 
     2035            } 
     2036            else 
     2037            { 
     2038                OSG_INFO<<"Not all compiled"<<std::endl; 
     2039                _dataToCompileList->add(databaseRequest.get()); 
    20642040                databaseRequest = 0; 
    20652041            }