Memoizing Fibonacci with bkt

[dimo414]

Here's a naive Fibonacci implementation:

#!/bin/bash

if (( $1 == 0 || $1 == 1 )); then
  echo "$1"
else
  fib1=$("$0" "$(( $1 - 1 ))")
  fib2=$("$0" "$(( $1 - 2 ))")
  echo "$(( fib1 + fib2 ))"
fi

And here's the same approach but using bkt to memoize intermediate results:

#!/bin/bash

# Export a unique scope so separate calls don't share a cache but subprocesses do
# This block is optional - see what happens if you delete it
if [[ -z "$BKT_SCOPE" ]]; then
  printf -v BKT_SCOPE 'fib-%(%s)T-%s' -1 "$$"
  export BKT_SCOPE
fi

if (( $1 == 0 || $1 == 1 )); then
  echo "$1"
else
  fib1=$(bkt --ttl=30s -- "$0" "$(( $1 - 1 ))")
  fib2=$(bkt --ttl=30s -- "$0" "$(( $1 - 2 ))")
  echo "$(( fib1 + fib2 ))"
fi

Here's a timing comparison:

$ time /tmp/naive.sh 20
6765

real    0m20.068s
user    0m19.382s
sys     0m1.216s

$ time /tmp/cached.sh 20
6765

real    0m0.100s
user    0m0.090s
sys     0m0.013s

# largest Fib that fits in 64 signed bits
$ time /tmp/cached.sh 92
7540113804746346429

real    0m0.262s
user    0m0.250s
sys     0m0.016s

The only change that is actually needed is prefixing the recursive calls with bkt --ttl=30s -- - this caches the subproces invocations and therefore each intermediate value will only be executed once. However we also set a custom BKT_SCOPE so that each invocation is cached separately. Without this two separate invocations will share the same cache and the second call would complete ~immediately (assuming the TTL hasn't expired yet). Try running time BKT_SCOPE=1 /tmp/cached.sh 92 repeatedly and you'll see the cache is shared. Of course normally this is a good thing! But scopes let you isolate cache pools when desired.