Luna Moon wrote:
To same the time of costly function evaluation, I want to explore the
possibility of caching.
Suppose in millions of calls to the function evaluation, there are some
computations, in which only a portion of the parameters change, others
remain the same as the parameters that are used in some other function
evaluations some time before. To save time, I can group the varying
parameters into sub-groups, and cache the results for later use. This needs
a highly efficient cache and a efficient organzation and look-up. Also, the
decision of whether a group of parameters has been seen before should be
based on data trunk in binary form, instead of decimal formats, so I can
compare memory data trunks directly using memory comparison.
Does anybody have good suggestions and pointers on this approach?
Caching the results of calculations is always a trade-off between
several things. If I had a computer with infinite memory I'd pre-compute
the result of every function and then never actually calculate anything
at runtime. In the real world though you find that you can't cache
absolutely everything, and therefore it's best to cache only "the most
worthwhile" results, where "worthwhile" is usually some function of
frequency of hits and cost to calculate.
The other big thing to bear in mind is the cost of accessing the cache -
if the function is really cheap to compute (and may get inlined
automatically by any half decent optimising compiler if it makes sense
on your platform to do so) then there's no point adding a complicated
caching mechanism that will never be inlined and requires you getting a
global lock that's being contended for by all your threads. And you
could still find that on your architecture a (CPU) cache miss which
results in a fetch from RAM or worse still swap will be more expensive
than the function you're trying to cache.
It's been said a million times before, but profiling really is the only
sane way to start optimizing things.
I believe hash_map either is shortly will be standardised, with a struct
for that enables you to use your function parameters as a key with some
kind of added mask, a suitable hashing function, and some kind of RW
locking mechanism for MT support it should be possible to do what you want.
Alan