GCC function attributes vs caching

Question

I have one costly function that gets called many times and there is a very limited set of possible values for the parameter.
Function return code depends only on arguments so the obvious way to speed things up is to keep a static cache within the function for possible arguments and corresponding return codes, so for every combination of the parameters, the costly operation will be performed only once.
I always use this approach in such situations and it works fine but it just occurred to me that GCC function attributes const or pure probably can help me with this.

Does anybody have experience with this? How GCC uses pure and const attributes - only at compile time or at runtime as well?
Can I rely on GCC to be smart enough to call a function, declared as

int foo(int) __attribute__ ((pure))

just once for the same parameter value, or there is no guarantee whatsoever and I better stick to caching approach?

EDIT: My question is not about caching/memoization/lookup tables, but GCC function atributes.

Answer 1

I think you are confusing the GCC pure attribute with memoization.

The GCC pure attribute allows the compiler to reduce the number of times the function is called in certain circumstances (such as loop unrolling). However it makes no guarantees that it will do so, only if it think it's appropriate.

What you appear to be looking for is memoization of your function. Memoization is an optimization where calculations for the same input should not be repeated. Instead the previous result should be returned. The GCC pure attribute does not make a function work in this way. You would have to hand implement this.

Answer 2

I have one costly function that gets called many times and there is very limited set of possible values for the parameter.

Why not use a static constant map then (the arguments' can be hashed to generate a key, the return code the value)?

Answer 3

This sounds like it might be solved with a template function. If all if the known parameters and return values are known at compile-time, you could perhaps generate a template instance of the function for each possible parameter. Essentially you'd be calling a different instance of the function for each possible parameter. Not sure it would be any easier than the static cache you've already implemented, but might be worth exploring.

Check out template metaprogramming. The concepts are similar to 'memoization', suggested by JaredPar, even using the same introductory example of a factorial function. It might be appropriate to say that these kinds of templates are compile-time implementations of memoization.

Answer 4

I dont like to reopen old threads, but there was a particularly offensive comment here:

"templates are for dealing with different types, rather than different values of the same type"

Now, take a simple template factorial implementation:

template<int n> struct Factorial {
    static const int value = n * Factorial<n-1>::value;
};

template<> struct Factorial<0> {
    static const int value = 1;
};

The template parameter here is an integer, not a typename.