Number of hits in fibonacci using lru_cache

Question

I am using functools.lru_cache to implement Fibonacci using memoization. But I do not understand the number of hits that my output generates. My code is as follows:

@lru_cache(maxsize=8)
def fib(n):
    if n <2:
        return n
    else:
        return fib(n-1) + fib(n-2)
print(fib(8))
print(fib.cache_info())
for i in range(9, 12):
    fib(i)
    print(fib.cache_info())

The output is:

CacheInfo(hits=6, misses=9, maxsize=8, currsize=8)
CacheInfo(hits=8, misses=10, maxsize=8, currsize=8)
CacheInfo(hits=10, misses=11, maxsize=8, currsize=8)
CacheInfo(hits=12, misses=12, maxsize=8, currsize=8)

I understand that the number of misses is 8 (fib(0),...fib(8)) in the call fib(8) and the number of misses in all the subsequent calls.

But the number of hits in fib(9), fib(10), fib(11) is not clear to me. If I understand correctly, in fib(9), the hits will be for fib(2)...fib(8). So, the number of hits will be 7. Is it due to the maxsize=8?

Answer 1

No, it is not because of the cache's max size (you would get the same results with maxsize=3). You get these statistics because you make life easier for the call to fib(9) by already having made the call to fib(8) before the loop. Realize also that these statistics are not only about one of your calls, but of all your calls thus far. In your main program, the call of fib(9) does not make as many hits as you suggest. It just has a hit for fib(8) and for fib(7) and that's it.

If you would not have made the call to fib(8) before the loop, you would get one less hit in the statistics in the first iteration of the loop. This is expected.

In your version, you made one more call to fib(8) in total: by the time you make the call fib(9), there is an extra hit counted for fib(8), while if you would not have made fib(8) before the loop, then it is not a hit when fib(9) is called (and it will have all the misses that fib(8) would have had, plus one).

This effect is similar when you go to the next iteration of the loop: since the previous iteration already cached the result for an argument that is one less, the current call will have a hit in its first recursive call. And so every iteration of the loop just adds two hits (for the recursive calls) and adds one miss for the call itself.