Hi, I thought about implementing memoization which could be applied globally to Haskell as an optimization. I also asked the question (in a bit different way) here: http://stackoverflow.com/questions/5749039/automatic-memoizing-in-functional... When you want to do that, the most important bit about the implementation is your replacement algorithm (which throws away old data -- because you need some sort of memory limit). As it was pointed out on StackOverflow, page replacement algorithms address exactly this issue. Though, when applied to memoization (esp. in pure functional languages), the problem becomes more specific and so maybe even more clever methods could be used. Earlier, I also came up with an own very simple implementation (using LRU) which can be seen here: http://www.az2000.de/docs/memoization/ I wonder if someone already tried to implement memoization as a global optimization for Haskell. And if so, how has it performed? I would be interested in implementing such thing myself as an addon for GHC and doing some benchmarks. Could you maybe: - Give me some hints where to start in GHC? I never really have worked on GHC so far. - Suggest some good benchmark code? I am mostly interesting in how this performs in huge real-world applications, so having some toy benchmark problems would be nice but some more huge benchmark problems would be better. Best would be some pool of both small and big benchmark programs. Thanks, Albert
On 22 April 2011 09:50, Albert Zeyer
I would be interested in implementing such thing myself as an addon for GHC and doing some benchmarks. Could you maybe: - Give me some hints where to start in GHC? I never really have worked on GHC so far. - Suggest some good benchmark code? I am mostly interesting in how this performs in huge real-world applications, so having some toy benchmark problems would be nice but some more huge benchmark problems would be better. Best would be some pool of both small and big benchmark programs.
Hi Albert There isn't much value to automatic memoization as people have already pointed out on SO - if you believe otherwise, you're probably better off proving a case on paper first before attempting to implement it in GHC. Best wishes Stephen
On Fri, Apr 22, 2011 at 12:55 PM, Stephen Tetley
There isn't much value to automatic memoization as people have already pointed out on SO - if you believe otherwise, you're probably better off proving a case on paper first before attempting to implement it in GHC.
Hi Stephen, I think there are already many many examples where memoization does indeed give much better performance (very simple and common one is the Fibonacci sequence). So the prove was already done. I am not sure what to prove otherwise. Demonstrating that it does indeed perform well when you apply it globally to some real-world application is not really something you prove on a paper. You do the actual benchmarking instead. I.e., you implement the memoization in GHC and benchmark some programs with it. Implementing it shouldn't also be complicated -- I already presented a 60 line Python implementation which is trivial to be applied globally and took 10 minutes to be implemented. I'm not sure though how complicated it would be to add that to GHC. I have no idea where to start. Regards, Albert
Hi Albert My contention is that there are specific programs (or specific functions within them) that memoization improves - hence adding memoization to those programs rather than the compiler is the way to go. Not that I've looked deeply, but I think adding memoization to GHC would be a pretty substantial undertaking. In the first instance where do you put the memo-ed values? - if you're doing it for all functions you might have to change the RTS as well as the compiler. Best wishes Stephen
Hi,
I was mostly thinking about automatic memoization, i.e. not explicit
memoization.
Also, it should only add some small constant overhead for each
function and maybe leads to huge improvements after all. But maybe I'm
also wrong and for an "average" function it doesn't lead to
improvements.
But the only real way to know that is to try it out.
I don't really understand why it would be such a huge substantial
undertaking. I would store the memo-ed values just in some hidden
global variable and proxy every function through some simple
memoizing-handler. Or is that complicated to add as an option to GHC?
Regards,
Albert
On Fri, Apr 22, 2011 at 2:08 PM, Stephen Tetley
Hi Albert
My contention is that there are specific programs (or specific functions within them) that memoization improves - hence adding memoization to those programs rather than the compiler is the way to go.
Not that I've looked deeply, but I think adding memoization to GHC would be a pretty substantial undertaking. In the first instance where do you put the memo-ed values? - if you're doing it for all functions you might have to change the RTS as well as the compiler.
Best wishes
Stephen
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Hi Albert You could try benchmarking with DeltaML instead - DeltaML is the only language I can think of where memoization is (nearly) pervasive, though you need still need to mark memo functions with a keyword as far as I'm aware. This would be a lot easier than modifying GHC: http://www.mpi-sws.org/~umut/projects/delta-ml/ Best wishes Stepehn
participants (2)
-
Albert Zeyer -
Stephen Tetley