From c9e0bfb7fe3827df7fa58aeeff7e603d6289fca0 Mon Sep 17 00:00:00 2001 From: ThorstenB Date: Fri, 19 Nov 2010 13:33:12 +0100 Subject: [PATCH] Improved tile cache priority scheme. Use priorities for loading/unloading. Maintain an expiry time for each tile. Replaced "cache lock" by "current view" flag. --- simgear/scene/tgdb/TileCache.cxx | 94 ++++++++++++++++++-------------- simgear/scene/tgdb/TileCache.hxx | 25 ++++----- simgear/scene/tgdb/TileEntry.cxx | 68 +---------------------- simgear/scene/tgdb/TileEntry.hxx | 35 +++++++----- 4 files changed, 88 insertions(+), 134 deletions(-) diff --git a/simgear/scene/tgdb/TileCache.cxx b/simgear/scene/tgdb/TileCache.cxx index 390e52d5..26dffe7c 100644 --- a/simgear/scene/tgdb/TileCache.cxx +++ b/simgear/scene/tgdb/TileCache.cxx @@ -1,4 +1,4 @@ -// newcache.cxx -- routines to handle scenery tile caching +// TileCache.cxx -- routines to handle scenery tile caching // // Written by Curtis Olson, started December 2000. // @@ -51,10 +51,9 @@ void TileCache::entry_free( long cache_index ) { SG_LOG( SG_TERRAIN, SG_DEBUG, "FREEING CACHE ENTRY = " << cache_index ); TileEntry *tile = tile_cache[cache_index]; tile->removeFromSceneGraph(); + tile_cache.erase( cache_index ); delete tile; - - tile_cache.erase( cache_index ); } @@ -84,13 +83,12 @@ bool TileCache::exists( const SGBucket& b ) const { } -// Return the index of the oldest tile in the cache, return -1 if +// Return the index of a tile to be dropped from the cache, return -1 if // nothing available to be removed. -long TileCache::get_oldest_tile() { - // we need to free the furthest entry +long TileCache::get_drop_tile() { long min_index = -1; - double timestamp = 0.0; double min_time = DBL_MAX; + float priority = FLT_MAX; tile_map_iterator current = tile_cache.begin(); tile_map_iterator end = tile_cache.end(); @@ -98,20 +96,27 @@ long TileCache::get_oldest_tile() { for ( ; current != end; ++current ) { long index = current->first; TileEntry *e = current->second; - if (e->get_cache_lock()) + if (( !e->is_current_view() )&& + ( e->is_expired(current_time) )) { - // tile locked to cache => must not be dropped - } - else - if ( e->is_loaded() ) { - timestamp = e->get_timestamp(); - if ( timestamp < min_time ) { - min_time = timestamp; + if (e->is_expired(current_time - 1.0)&& + !e->is_loaded()) + { + /* Immediately drop "empty" tiles which are no longer used/requested, and were last requested > 1 second ago... + * Allow a 1 second timeout since an empty tiles may just be loaded... + */ + SG_LOG( SG_TERRAIN, SG_DEBUG, " dropping an unused and empty tile"); + break; + } + if (( e->get_time_expired() < min_time )|| + (( e->get_time_expired() == min_time)&& + ( priority > e->get_priority()))) + { + // drop oldest tile with lowest priority + min_time = e->get_time_expired(); + priority = e->get_priority(); min_index = index; } - } else { - SG_LOG( SG_TERRAIN, SG_DEBUG, "loaded = " << e->is_loaded() - << " time stamp = " << e->get_timestamp() ); } } @@ -122,35 +127,19 @@ long TileCache::get_oldest_tile() { } -// Clear the inner ring flag for all tiles in the cache so that the -// external tile scheduler can flag the inner ring correctly. -void TileCache::clear_inner_ring_flags() { - tile_map_iterator current = tile_cache.begin(); - tile_map_iterator end = tile_cache.end(); - - for ( ; current != end; ++current ) { - TileEntry *e = current->second; - //if ( e->is_loaded() ) { - e->set_inner_ring( false ); - //} - } -} - -// Clear all locked flags for all tiles in the cache. -// (Tiles belonging to the current position are locked to -// the cache to prevent them from being dropped). -void TileCache::clear_cache_lock_flags() +// Clear all flags indicating tiles belonging to the current view +void TileCache::clear_current_view() { tile_map_iterator current = tile_cache.begin(); tile_map_iterator end = tile_cache.end(); for ( ; current != end; ++current ) { TileEntry *e = current->second; - if (e->get_cache_lock()) + if (e->is_current_view()) { - // update timestamps for tiles belonging to most recent position - e->set_timestamp( current_time ); - e->set_cache_lock( false ); + // update expiry time for tiles belonging to most recent position + e->update_time_expired( current_time ); + e->set_current_view( false ); } } } @@ -190,8 +179,31 @@ bool TileCache::insert_tile( TileEntry *e ) { // register tile in the cache long tile_index = e->get_tile_bucket().gen_index(); tile_cache[tile_index] = e; - e->set_timestamp(current_time); + e->update_time_expired(current_time); return true; } +// update tile's priority and expiry time according to current request +void TileCache::request_tile(TileEntry* t,float priority,bool current_view,double request_time) +{ + if ((!current_view)&&(request_time<=0.0)) + return; + + // update priority when hire - or old has expired + if ((t->is_expired(current_time))|| + (priority > t->get_priority())) + { + t->set_priority( priority ); + } + + if (current_view) + { + t->update_time_expired( current_time ); + t->set_current_view( true ); + } + else + { + t->update_time_expired( current_time+request_time ); + } +} diff --git a/simgear/scene/tgdb/TileCache.hxx b/simgear/scene/tgdb/TileCache.hxx index f427c2bf..5fedab9c 100644 --- a/simgear/scene/tgdb/TileCache.hxx +++ b/simgear/scene/tgdb/TileCache.hxx @@ -1,4 +1,4 @@ -// newcache.hxx -- routines to handle scenery tile caching +// TileCache.hxx -- routines to handle scenery tile caching // // Written by Curtis Olson, started December 2000. // @@ -49,11 +49,11 @@ private: // pointers to allow an external linear traversal of cache entries tile_map_iterator current; + double current_time; + // Free a tile cache entry void entry_free( long cache_index ); - double current_time; - public: tile_map_iterator begin() { return tile_cache.begin(); } tile_map_iterator end() { return tile_cache.end(); } @@ -72,18 +72,12 @@ public: // Check if the specified "bucket" exists in the cache bool exists( const SGBucket& b ) const; - // Return the index of the oldest tile in the cache, return -1 if + // Return the index of a tile to be dropped from the cache, return -1 if // nothing available to be removed. - long get_oldest_tile(); - - // Clear the inner ring flag for all tiles in the cache so that - // the external tile scheduler can flag the inner ring correctly. - void clear_inner_ring_flags(); - - // Clear all locked flags for all tiles in the cache. - // (Tiles belonging to the current position are locked to - // the cache to prevent them from being dropped). - void clear_cache_lock_flags(); + long get_drop_tile(); + + // Clear all flags indicating tiles belonging to the current view + void clear_current_view(); // Clear a cache entry, note that the cache only holds pointers // and this does not free the object which is pointed to. @@ -131,6 +125,9 @@ public: void set_current_time(double val) { current_time = val; } double get_current_time() const { return current_time; } + + // update tile's priority and expiry time according to current request + void request_tile(TileEntry* t,float priority,bool current_view,double requesttime); }; } diff --git a/simgear/scene/tgdb/TileEntry.cxx b/simgear/scene/tgdb/TileEntry.cxx index ffe59352..0e417865 100644 --- a/simgear/scene/tgdb/TileEntry.cxx +++ b/simgear/scene/tgdb/TileEntry.cxx @@ -64,77 +64,16 @@ osgDB::RegisterReaderWriterProxy g_readerWriterSTGProxy; ModelRegistryCallbackProxy g_stgCallbackProxy("stg"); } -#ifdef USE_CULLCALLBACK_TS -namespace -{ -// Update the timestamp on a tile whenever it is in view. - -class TileCullCallback : public osg::NodeCallback -{ -public: - TileCullCallback() : _timeStamp(0) {} - TileCullCallback(const TileCullCallback& tc, const osg::CopyOp& copyOp) : - NodeCallback(tc, copyOp), _timeStamp(tc._timeStamp) - { - } - - virtual void operator()(osg::Node* node, osg::NodeVisitor* nv); - double getTimeStamp() const { return _timeStamp; } - void setTimeStamp(double timeStamp) { _timeStamp = timeStamp; } -protected: - double _timeStamp; -}; -} - -void TileCullCallback::operator()(osg::Node* node, osg::NodeVisitor* nv) -{ - if (nv->getFrameStamp()) - _timeStamp = nv->getFrameStamp()->getReferenceTime(); - traverse(node, nv); -} -#endif - -double TileEntry::get_timestamp() const -{ -#ifdef USE_CULLCALLBACK_TS - if (_node.valid()) { - return (dynamic_cast(_node->getCullCallback())) - ->getTimeStamp(); - } else - return DBL_MAX; -#else - return timestamp; -#endif -} - -void TileEntry::set_timestamp(double time_ms) -{ -#ifdef USE_CULLCALLBACK_TS - if (_node.valid()) { - TileCullCallback* cb - = dynamic_cast(_node->getCullCallback()); - if (cb) - cb->setTimeStamp(time_ms); - } -#else - timestamp = time_ms; -#endif -} // Constructor TileEntry::TileEntry ( const SGBucket& b ) : tile_bucket( b ), tileFileName(b.gen_index_str()), _node( new osg::LOD ), - is_inner_ring(false) - ,is_cache_locked(false) -#ifndef USE_CULLCALLBACK_TS - ,timestamp(0.0) -#endif + _priority(-FLT_MAX), + _current_view(false), + _time_expired(-1.0) { -#ifdef USE_CULLCALLBACK_TS - _node->setCullCallback(new TileCullCallback); -#endif tileFileName += ".stg"; _node->setName(tileFileName); // Give a default LOD range so that traversals that traverse @@ -462,4 +401,3 @@ TileEntry::removeFromSceneGraph() } } } - diff --git a/simgear/scene/tgdb/TileEntry.hxx b/simgear/scene/tgdb/TileEntry.hxx index 924b5666..ffe78947 100644 --- a/simgear/scene/tgdb/TileEntry.hxx +++ b/simgear/scene/tgdb/TileEntry.hxx @@ -74,15 +74,16 @@ private: const osgDB::ReaderWriter::Options* options); /** - * this value is used by the tile scheduler/loader to mark which - * tiles are in the primary ring (i.e. the current tile or the - * surrounding eight.) Other routines then can use this as an - * optimization and not do some operation to tiles outside of this - * inner ring. (For instance vasi color updating) + * This value is used by the tile scheduler/loader to load tiles + * in a useful sequence. The priority is set to reflect the tiles + * distance from the center, so all tiles are loaded in an innermost + * to outermost sequence. */ - bool is_inner_ring; - bool is_cache_locked; - double timestamp; + float _priority; + /** Flag indicating if tile belongs to current view. */ + bool _current_view; + /** Time when tile expires. */ + double _time_expired; static ModelLoadHelper *_modelLoader; @@ -136,13 +137,19 @@ public: */ osg::LOD *getNode() const { return _node.get(); } - double get_timestamp() const; - void set_timestamp( double time_ms ); + inline double get_time_expired() const { return _time_expired; } + inline void update_time_expired( double time_expired ) { if (_time_expired _time_expired); } // Get the ref_ptr to the DatabaseRequest object, in order to pass // this to the pager. -- 2.39.5