IncPy: Automatic memoization for Python
stanford.edu
stanford.edu
This is pretty amazing, and totally different from a memoizing decorator, and anything which could be done at the application level (unless it did deep deep magic; the kind you can't really do in Python).
Firstly, it is fully automatic. You don't need to annotate anything.
Secondly it works on impure functions! (as opposed to pure functions like fib.) It tracks data dependencies through the program, including global variables, external files(!), etc. If they do not change, then it uses a cached value.
Assuming that it works as he explains it in the video, this is properly amazing (and I've a PhD in compilers).
In comparison, a memoization decorator:
- requires you to annotate functions,
- can be accidentally put on functions which are not pure, which would lead to bugs and unsafe behaviour,
- does not (safely) support functions where data in the body of the function changes (such as global variables, external files, etc). Instead, it would only check the arguments.
Anyway, I'm impressed.
I had the misfortune of reading the earlier comments and writing this off as a trivial accomplishment that could be disregarded, but now I know it is actually a useful tool to have in my arsenal.
if you have any further suggestions, please email me personally.
anyways, this is still an early-stage research project where i'm the only developer, so i can't make much guarantees about its robustness (i can only test on my own machine with my own research scripts).
that said, though, i am very interested in getting new users and feedback. please email me at the email address listed on the IncPy website if you have any questions. i am more than happy to answer them!
sorry that it didn't work out of the box; as you can tell, it's still a research prototype :)
i'll add the Mercurial test suite to my TODO list of programs to try. in your experience, what kind of Mercurial operations do you think can be sped up by memoization?
The linked article is about run-time memoization: rather than caching the compiled version of a function's code, you cache just the output of the function for particular inputs.
Think of the function as the compiler and the inputs as your C files. The kinds of things the two are doing are very similar, but incPy's job is much harder.
class Memoize:
def __init__ (self, f):
self.f = f
self.mem = {}
def __call__ (self, *args, **kwargs):
if (args, str(kwargs)) in self.mem:
return self.mem[args, str(kwargs)]
else:
tmp = self.f(*args, **kwargs)
self.mem[args, str(kwargs)] = tmp
return tmpIt is possible to implement a trivial and transparent cache as decorator and apply it to particular bottle neck functions.
0 development effort, 0 running overhead, 0 maintainability issues
Its hardly transparent if its a decorator.
Maintainance issue: applying it to a functions which isn't pure. Avoiding it adds development overhead.
There are other advantages I outlined in my comment.
(defmacro defmemoize (fn val &body body)
(with-gensyms (lst hash-code)
`(let ((,lst (make-hash-table :test #'equal)))
(defun ,fn ,val
(let ((,hash-code (list ,@val)))
(or
(gethash ,hash-code ,lst)
(setf (gethash ,hash-code ,lst)
,@body)))))))
(defmemoize fib (n)
(if (<= n 2) ; first two = 1
1
(+ (fib (1- n))
(fib (- n 2)))))