I was talking about fully automatic memoization, which does not play nicely with the type system. Thus, it's a speedup in a language where every function is loosely typed anyway, but a distinct slow down in a language with nice type behavior (and an implementation smart enough to leverage it). That's why I called automatic memoization "worse than useless" – you take a possibly slow, but nicely typed function and turn it into poorly typed, memoized function. There might be a way to make it work better, but I suspect it would require some very deep language support and would generally be inferior to just having people use an explicit cache structure. In the case of npartitions, this is precisely what's happening: there's an explicit, correctly typed cache.
On Tue, Feb 25, 2014 at 1:36 PM, Kevin Squire <[email protected]>wrote: > What you're suggesting is memoization, which has come up a number of >> times. The short version is that it is an easy way to speed up a slow >> language but is worse than useless in fast languages. You don't see people >> doing memoization in C or Fortran, do you? >> > > That's a little, um, strong, don't you think? Certainly it's not common, > but probably not "worse than useless". ;-) (The lack of a standard > map/dictionary/hash table in these languages probably contributes as well.) > > A couple of examples in Julia where it's useful (and would be just as > useful in C or Fortran): > > > https://github.com/JuliaLang/julia/blob/master/base/combinatorics.jl#L304-L321 > > https://github.com/JuliaLang/julia/blob/master/base/combinatorics.jl#L368-L379 > > (Those should probably be wrapped in let statements. I'll do that.) > > These are not common functions, of course, but memoization here is > definitely useful. > > Cheers! > Kevin >
