catch {return -code $memo($cmd)}would be the most efficient way to dispatch if the cache item existed.This is when I discovered that catch prevents return from working even though no error has been generated. This may be the designed semantics of the catch command , but this case is definitely suboptimal.So as a compromise I settled for the following: if { ! [catch {set x $::memo($x)} ] } {
return -code return $x
}
...This avoids the expensive info exists command as well as only requiring one lookup for the array variable.The above tested out as twice as fast as the original. My thoughts then turned to automaticaly specialising the code by automatically inserting the code for the memoizing directly into the code. Something like:memoize fibqThat gives (for example):
proc fibq x {
if { ! [catch {set x $::memo($x)} ] } {
return $x
}
set ::memo($x) \
[expr {$x <=1? 1 : [fibq [expr {$x-1}]] + [fibq [expr {$x-2}]]}]
}by automatically inserting the cache and saving the expression result.At this point The realisation that this is not the way you would code up this type of function an generated: proc fibq-nr x {
set i-2 1
set i-1 2
for {set i 3} {$i <= $x } {incr i} {
set new [expr wide(${i-1}) + ${i-2}]
set i-2 ${i-1}
set i-1 $new
}
set new
}As we see , the above needs no specialising or memoization to achive acceptable performance speeds. The above runs 30% faster than the fibq proc.So what have we learned:- That fib is the definitive example of the fallacy of functional programming.
- We all post trivial examples for brevity that don't show the full potential of the technique.
- TCL is not fast with recursive algorithms.
- Memoization is a technique that makes up for bad programming practices.
proc Fib4 n { expr {round(pow(1.61803398875,$n)/2.2360679775)} }WHD -- Ah! But you're assuming that the only value to caching fib(n) is to aid in computing fib(n+1). But if you're needing fib(n) many times in one program, then caching the result rather than recomputing it each time still makes sense.In other words, memoizing (or result caching) might still be useful even in your non-recursive version. - RS: See for instance St John's chapel, where 3D points are projected to 2D, but as polygons very often share points, it brings quite a speed gain to cache the projection result...AK: Another place where I have seen memoization recently is the packrat parsing technique (http://www.pdos.lcs.mit.edu/~baford/packrat/
). It is derived from regular top-down parsing with backtracking, which can be exponential-time, because of reparsing everything after backtracking. Through the memoization of all test-results using during parsing any further tests at the same location done after some backtracking do not need to actually parse things again, and the technique become linear-time in the length of the input string.PWQ Thanks for the examples, I could eloborate my position on both those but instead I will leave you with this thought.Real world problems involve much larger computation spaces than most examples. A Real 3D application would more likely have 300,000 vertices A graph search space could contain 30,000 nodes and millions of arcs. This means that the caches could occupy 20-100Meg or more. While this is still less than the Java VM requires just to print "Hello World!", it can impact on performance. If implemented naively (as is the case with memoization), they could consume all available memory becore the processing has completed.When caching is applied to these situations you will need to consider:
- That the hash tables automatically expand and the existing keys must be rehashed. This can get very expensive for large hash tables.
- Cache performance on the CPU will drop as random access to large areas of memory will cause cause flushing.
- Large memory spaces will cause more Page Faults and thus impact on performance.
NEM One area from my experience where caching (in a similar manner to memoizing) is definitely a big win is in large-scale pattern matching algorithms, as used in Expert Systems (and dozens of other application areas). All the main algorithms (Rete, Treat, Leaps etc) do some sort of caching to a greater or lesser extent. If you have a large number of patterns, and a large number of objects to match (i.e. a combinatorial problem), but only a few changes per cycle, it really makes sense to cache partial matches. Designing better algorithms will only get you so far: if your computation is fundamentally expensive, then you need to think about caching/memoization.
AMG: Philip, Tcl recursion isn't fast? Look at [ftw_8] in Directory recursion. It outperforms all the other depth-first traversal procedures.
