How to get optimization from a "pure function" in C#?

Question

If I have the following function, it is considered pure in that it has no side effects and will always produce the same result given the same input x.

public static int AddOne(int x) { return x + 1; }

As I understand it, if the runtime understood the functional purity it could optimize execution so that return values wouldn't have to be re-calculated.

Is there a way to achieve this kind of runtime optimization in C#? And I assume there is a name for this kind of optimization. What's it called?

Edit: Obviously, my example function wouldn't have a lot of benefit from this kind of optimization. The example was given to express the type of purity I had in mind rather than the real-world example.

Answer 1

As others have noted, if you want to save on the cost of re-computing a result you've already computed, then you can memoize the function. This trades increased memory usage for increased speed -- remember to clear your cache occasionally if you suspect that you might run out of memory should the cache grow without bound.

However, there are other optimizations one can perform on pure functions than memoizing their results. For example, pure functions, having no side effects, are usually safe to call on other threads. Algorithms which use a lot of pure functions can often be parallelized to take advantage of multiple cores.

This area will become increasingly important as massively multi-core machines become less expensive and more common. We have a long-term research goal for the C# language to figure out some way to take advantage of the power of pure functions (and impure but "isolated" functions) in the language, compiler and runtime. But doing so involves many difficult problems, problems about which there is little consensus in industry or academia as to the best approach. Top minds are thinking about it, but do not expect any major results any time soon.

Answer 2

if the calculation was a costly one, you could cache the result in a dictionary?

    static Dictionary<int, int> cache = new Dictionary<int, int>();
    public static int AddOne(int x)
    {
        int result;
        if(!cache.TryGetValue(x, out result))
        {
            result = x + 1;
            cache[x] = result;
        }
        return result;
    }

of course, the dictionary lookup in this case is more costly than the add :)

There's another much cooler way to do functional memoization explained by Wes Dyer here: http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx - if you do a LOT of this caching, then his Memoize function might save you a lot of code...