What features are candidates for replacement?

Question

I decided to use PostSharp (indistinguishable from magic) to read attributes and memoize functions . The hash of the function call will be the key, and the cached (in Velocity ) result will be returned instead of the function call again. Easy peasy, mac-and-cheesy.

I already refused the opportunity to detect side effects in the decorated functions, which turned out to be a "difficult problem", even for experts, which I, of course, do not have. Then I have to find out what other functions are candidates for demoning.

• What about methods that accept complex reference types as parameters?
• What about methods that depend on the data inside the instances from which they are called?

ActiveRecord-esque data objects come to mind on this last.

Will I have to reorganize the weekly code to support memoization?

Answer 1

You can only memoize a function if all its inputs are value types or immutable reference types, if it returns a value type or a new instance of the reference type, and if it has no side effects. Period.

Memorization depends on the deterministic mapping between inputs and outputs. Each call to F(a, b, c) , in which a, b, and c contain the same values, must return the same result so that memoning is possible.

If the parameter is a reference type, then although its value does not change, several calls to the function using it may lead to a different result. Trivial example:

 public int MyFunction(MyType t) { return t.Value; } Console.WriteLine(MyFunction(t)); t.Value++; Console.WriteLine(MyFunction(t)); 

Similarly, if a function depends on an external value, then several calls to this function with the same parameters can return different results:

 int Value = 0; public int MyFunction(int input) { return Value; } Console.WriteLine(MyFunction(1)); Value++; Console.WriteLine(MyFunction(1)); 

And heaven helps you if your memoized function does something other than return a value or a new reference type:

 int Value = 0; public int MyFunction(int input) { Value++; return input; } 

If you call this function 10 times, Value will be 10. If you reorganize it to use memoization, and then call it 10 times, Value will be 1.

You can begin to take the path of figuring out how to save memoize state so that you can fake a function that remembers the type of link. But what you really remember is a set of values ​​that the function works on. Similarly, you can hack a memoized function that has side effects so that its side effects occur before recording. But this is all asking for trouble.

If you want to implement memoization in a function that takes a reference type, then a suitable approach is to reorganize the part of the function that only works with value types, and memoize this function, for example:

 public int MyFunction(MyType t) { return t.Value + 1; } 

:

 public int MyFunction(MyType t) { return MyMemoizableFunction(t.Value); } private int MyMemoizableFunction(int value) { return value + 1; } 

Any other approach to implementing memoization that you take either a) does the same, through more obscure means, or b) will not work.

Answer 2

Well, any function, theoretically, is a candidate for substitution. However, remember that memoization is all about trading space for speed -

In general, this means that the more state the function requires or depends on it to calculate the answer, the higher the cost of space, which reduces the desirability for the memoize method.

Both of your examples are mostly cases where you need to maintain a larger state. This has two side effects.

First, memorizing a function will require much more memory space, as additional information is required.

Secondly, this will potentially slow down the function involved, since the larger the space, the higher the cost of finding the answer, and also the higher the cost of finding whether the result was previously saved.

In general, I mean only functions that have few possible resources and low storage requirements, unless there is a very high cost in calculating the answer.

I admit that this is vague, but it is part of the "artistry" in architecture. There is no “right” answer without the implementation of both options (memozied and non memoized functions), profiling and measurement.

Answer 3

You’ve already thought about how to provide an AOP solution for providing memoization around the Foo function, so what remains to be seen?

Yes, you can pass an object of arbitrary complexity as a parameter for a memoized function, if it is immutable, like everything on which it depends. Again, it is not at all easy to detect statically at the moment.

You still agree that you can statically examine the code to tell your users the question: "Is it a good idea to apply memoization to the Foo function?"

If you do this one of your requirements, you will join the global research effort that has lasted for many years. I suppose it depends on how ambitious you are.