Getting Cache out of Nowhere for a Tiny Functionality in Pharo

This is yet another post about the anti-best practices of programming :). But it definitely can help you to better understand the reflective features of Pharo.

Imagine that you want to add a Fibonacci sequence computation to Integer. The straightforward recursive implementation looks like this:

Integer>>fibonacci
    self < 0 ifTrue: [ ArithmeticError signal: self fibNegativeErrorText ].
    self < 2 ifTrue: [ ^ self ]. "for 0 and 1" 
    ^ (self - 2) fibonacci + (self - 1) fibonacci

The problem is in computational complexity. I think that this is a classic example of how recursion can do wrong. You see, each time you send fibonacci to an integer, it will send two more messages to a bit smaller integers until they reach 0 or 1. As a result, the complexity of this algorithm is 2n, which is very slow. Just to give some numbers:

[ 40 fibonacci ] timeToRun -> "0:00:00:01.752"
[ 50 fibonacci ] timeToRun -> "0:00:02:59.628"

To avoid such complexity you can implement this using a simple iteration, but that's lame. Another common version to do this is to have a cache (to memoize) for each Fibonacci number, so you don't have to compute anything more than once. But as you have your code in Integer, and you cannot extend its internal state (and instance variables). You can do another method that additionally accepts a dictionary with cache, but that's ugly. You can have a dedicated class for caching that you can access from your method i.e. "the global variable way." But you can also use the properties' key-value storage of the method itself. Each method had properties. You you can say (Object>>#asString) propertyAt: #key, or (Object>>#asString) propertyAt: #key put: #value. Now we can transform our method this way:

fibonacci
    ^ thisContext method propertyAt: self asString asSymbol ifAbsentPut: [
        self < 0 ifTrue: [ ArithmeticError signal: self fibNegativeErrorText ].
        self < 2
            ifTrue: [ self ] "for 0 and 1"
            ifFalse: [ (self - 2) fibonacci + (self - 1) fibonacci ] ]

Besides minor changes everything got wrapped into thisContext method propertyAt: … ifAbsentPut: []. It takes the method which is currently being executed, looks if it has a property for the key which is the current integer, and returns it. Unless there is no such key, it computes it and stores it in the property. Now the numbers are way better:

[ 4000 fibonacci ] timeToRun -> "0:00:00:00.345"
[ 5000 fibonacci ] timeToRun -> "0:00:00:00.524"

And of course, I've reset the cache before each measurement.

Now pay attention:

1. I used self asString asSymbol because while storing the property, key is converted to a symbol anyway, but not on retrieval.
2. You have no easy control over the cache, it will be invalidated on method recompilation together with all the other properties, but you cannot easily remove it from UI, etc…
3. It is not a good idea to put the cache in properties themselves because if someone else uses the same keys for his own business, you will have clashes. So usually you put a dictionary at a key like #fibonacciCache and then work with that dictionary.