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

This will probably be inlined (aka inline expansion) by the compiler ...

Just make sure you compile your code with the "Optimize Code" flag set (in VS : project properties / build tab / Optimize Code)

---

The other thing you can do is to cache the results (aka memoization). However, there is a huge initial performance hit due to your lookup logic, so this is interesting only for slow functions (ie not an int addition).

There is also a memory impact, but this can be managed through a clever use of weak references.

---

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.

In your example, the runtime WILL have to compute the result, unless x is known at compile time. In that case, your code will be further optimized through the use of constant folding

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...

Answer 3

I think you're looking for functional memoization

Answer 4

A compiler can optimize this function through a combination of inlining (replacing a function call with the body of that function at the call site) and constant propagation (replacing an expression with no free variables with the result of that expression). For example, in this bit of code:

AddOne(5);

AddOne can be inlined:

5 + 1;

Constant propagation can then simplify the expression:

6;

(Dead code elimination can then simplify this expression even further, but this is just an example).

Knowing that AddOne() has no side effects might also enable the a compiler to perform common subexpression elimination, so that:

AddOne(3) + AddOne(3)

may be transformed to:

int x = AddOne(3);
x + x;

or by strength reduction, even:

2*AddOne(3);

There is no way to command the c# JIT compiler to perform these optimizations; it optimizes at its own discretion. But it's pretty smart, and you should feel comfortable relying on it to perform these sorts of transformations without your intervention.

Answer 5

The technique you are after is memoization: cache the results of execution, keyed off the arguments passed in to the function, in an array or dictionary. Runtimes do not tend to apply it automatically, although there are certainly cases where they would. Neither C# nor .NET applies memoization automatically. You can implement memoization yourself - it's rather easy -, but doing so is generally useful only for slower pure functions where you tend to repeat calculations and where you have enough memory.

Answer 6

How could the compiler do that ? How does it know what values of x are going to be passed in at runtime?

and re: other answers that mention inlining... My understanding is that inlining (as an optimization) is warranted for small functions that are used only once (or only a very few times...) not because they have no side effects...

Answer 7

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.