Hi,
This is a distilled version of what I'm trying to do (code snipet guaranteed
to compile). I have a Fn which has an operator that I want to cache.
Fn is used as basis for a functional algebra for more complex function
expressions.
The benchmark for the caching performance is EvalCache defined below.
I'm comparing performance of EvalCacheWithVe c with EvalCache using ideas
suggested kindly by Ivan Vecerina.
For my application, I'm finding that EvalCache outperforms EvalCacheWithVe c
by a factor of close to two.
In fact EvalCacheWithVe c runs quicker with smaller cache sizes.
I don't really want to move the cache outside of the class Fn.
Any suggestions on how I can improve the performance of EvalCacheWithVe c
further?
Thanks in advance.
class Fn
{
private:
typedef EvalCache<int,i nt,double> CACHE;
// typedef EvalCacheWithVe c<int,int,doubl e> CACHE;
SharedPtr<CACHE > _fnCache;
SharedPtr<blah> _rep;
public:
double operator()( int date_, int evalDate_ ) const
{
//! check to see whether cached value is valid and use if so.
std::pair<int,i nt> args=std::make_ pair(date_, evalDate_);
const double* cached=_fnCache->lookup(args) ;
if (cached==0)//! ie invalid
{
double res=(*_rep)(dat e_, evalDate_);
_fnCache->add(args, res);
return res;
}
else
{
return *cached;
}
}
};
template< typename T1, typename T2, typename R >
class EvalCache
{
private:
typedef std::pair<T1,T2 > FNARGS;
FNARGS _args;
R _cached;
bool _valid;
public:
~EvalCache(){}
EvalCache():_va lid(false){}
//! return value of 0 indicates that the cached value cannot be used.
inline const R* lookup(const FNARGS& args_)
{
if (_valid==false) return 0;
if (_args==args_) return &_cached;
else return 0;
}
inline void add(const FNARGS& args_, const R& res_)
{
_args = args_;
_cached= res_;
_valid = true;
}
inline void clear(){ _valid=false; }
};
template<typena me T1, typename T2, typename R>
class EvalCacheWithVe c{
private:
typedef std::pair<T1,T2 > FNARGS;
typedef std::pair<FNARG S,R> ENTRY;
std::vector<ENT RY> _cached;
R _cachedVal;
enum{kCacheSize =64};
std::bitset<kCa cheSize> _valid;
bool _noneValid;
size_t getHashedIndex( T1 a, T2 b)
{ // A LOT OF ROOM FOR IMPROVEMENT HERE
return (17*a + 0x193*b) % kCacheSize;
}
public:
~EvalCacheWithV ec(){}
EvalCacheWithVe c()
:
_cached(kCacheS ize),
_valid(),
_noneValid(true )
{}
//! return value of 0 indicates that the cached value cannot be used.
const R* lookup(const FNARGS& args_)
{
if (_noneValid==tr ue) return 0;
T1 arg1(args_.firs t);
T2 arg2(args_.seco nd);
size_t idx = getHashedIndex( arg1, arg2);
if (_valid[idx]==false) return 0;
const ENTRY& entry = _cached[idx];
if (entry.first!=a rgs_) return 0;
_cachedVal=entr y.second;
return &_cachedVal;
}
void add(const FNARGS& args_, const R& res_)
{
T1 arg1(args_.firs t);
T2 arg2(args_.seco nd);
size_t idx = getHashedIndex( arg1, arg2);
_cached[idx]=std::make_pair (args_,res_);
_valid[idx]=true;
_noneValid=fals e;
}
void clear()
{
_noneValid=true ;
_valid.reset();
}
};
"Ivan Vecerina" <se*********@ve cerina.com> wrote in message
news:c0******** **@newshispeed. ch...
"Kin Pang" <Ki******@canta b.net> wrote in message
news:bv******** **@hercules.bti nternet.com...
| I have a routine where I'm using a std::map from a pair of ints to
double | for caching evaluation results.
| The cache depth could be upto say 1000 in depth.
| However, my application needs to clear and replenish the cache
repeatedly | and profiling seems to suggests
| the performance is handicated by repeated calls to new.
| Can anybody advice me on how to improve the performance or suggests
| alternatives please.
As others suggested, some type of hash table is likely to provide
the best results.
Here's a basic example:
double expensiveComput e(int a, int b); // the expensive function
class CachedCompute
{
struct Entry {
Entry(int a_, int b_)
: a(a_), b(b_), result(::expens iveCompute(a_,b _)) {}
int a, b;
double result;
};
enum { kCacheSize = 1024 };
std::vector<Ent ry> cache_;
static int getHashedIndex( int a, int b)
{ // A LOT OF ROOM FOR IMPROVEMENT HERE
return (17*a + 0x193*b) % kCacheSize;
}
public:
CachedCompute()
: cache_( kCacheSize, Entry(0,0) ) // init cache with dummy contents
{ }
double compute(int a, int b)
{
Entry& entry = cache_[ getHashedIndex( a,b) ];
if( entry.a!=a || entry.b!=b )
entry = Entry(a,b); //overwrite the non-matching entry
return entry.result;
}
};
Create an instance of CachedCompute and use its compute()
member function instead of the global expensiveComput e()
to benefit from the caching.
The getHashedIndex( ) function should be optimized to avoid
collisions (different values of a&b used repeatedly that
lead to the same index).
An application-specific optimization is sometimes possible.
Alternatively, consider a proven hashing approach such as the
FNV hash: http://www.isthe.com/chongo/tech/comp/fnv/index.html
The table size (kCacheSize) can also be improved (the std::vector
is anyway more memory-efficient than std::map, the saving is
probably about 50%).
Another improvement might be to look at multiple hash table
entries when calling compute (e.g. the 4 following ones).
There are various ways to handle table refreshes in this case...
Anyway, I would expect the snippet above to provide much better
performance than an approach based on std::map ...
But please let me know of your results.
I hope this helps,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- e-mail contact form
