Rose Ames wrote a note recently to show the use of Python decorators for memoization. This was instructive application of decorating, and I've been experimenting with the code. In doing so I ran into a surprise involving the greedy behavior of default dictionaries.
The high-level lesson is that using a default dictionary is inefficient in memoization, if its default is a function whose return-values are what is being memoized; traditional membership-testing is more efficient under those circumstances.
Briefly, I saw a standard test of dictionary membership:
1 2 3 4 | def cached_func(arg):
if arg not in cache:
cache[arg] = func(arg)
return cache[arg]
|
and replaced it with:
1 2 | def cached_func(arg):
return cache.setdefault(arg, func(arg))
|
(The method dict.setdefault(key, [default]) tests for membership of key in dict; if the test returns True, then dict[key] is returned; if False, key is inserted into dict and its value set to default, which is then returned. There's a new datatype, collections.defaultdict, to accomplish the same thing, but I am happy to use the older form with the traditional dict.)
Ames considered a recursive Fibonacci function, notorious for its exponential ramification at large values of n. Her use of a caching decorator dramatically improved running time. But when I changed her explicit dictionary-membership test to dict.setdefault, no such improvement occurred. Why? It turns out that in the code above func(arg) is evaluated not lazily but greedily: each time cache.setdefault is called, func(arg) is evaluated — defeating the purpose of memoization.
Some documentation follows, from high level to low. Here is Rose Ames's original code:
1 2 3 4 5 6 7 8 9 10 11 12 13 | def cache(func):
cache = {}
def cached_func(arg):
if arg not in cache:
cache[arg] = func(arg)
return cache[arg]
return cached_func
@cache
def fib(n):
if n <= 2:
return 1
return fib(n - 1) + fib(n - 2)
|
I replaced cached_func(arg) (lines 3-6) as described above. The actual output of the two versions is identical at various values of n. Based on the following timing test, caching the output from a Standard-Library function, using setdefault is not appreciably slower than explicit membership-testing:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | $ python -m timeit -s '''
import random
random.seed("stochasma")
d = {}
limit = 100000
''' '''
for i in range(limit):
key = random.random()
if key not in d:
d[key] = random.random()
'''
10 loops, best of 3: 54.3 msec per loop
$
$ python -m timeit -s '''
import random
random.seed("stochasma")
d = {}
limit = 100000
''' '''
for i in range(limit):
key = random.random()
d.setdefault(key, random.random())
'''
10 loops, best of 3: 55.6 msec per loop
|
Then I added a print statement to the decorated function, to see how often it is being called (lines 13 and 28, below):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | number = 10
# With explicit membership test.
print('\n\nNow beginning explicit-membership version.')
def cache_orig(func):
cache = {}
def cached_func(arg):
if arg not in cache:
cache[arg] = func(arg)
return cache[arg]
return cached_func
@cache_orig
def fib(n):
print('.', end='') # debug line
if n <= 2:
return 1
return fib(n - 1) + fib(n - 2)
explicit = fib(number)
#
# With setdefault.
print('\n\nNow beginning setdefault version.')
def cache_default(func):
cache = {}
def cached_func(arg):
return cache.setdefault(arg, func(arg))
return cached_func
@cache_default
def fib(n):
print('.', end='') # debug line
if n <= 2:
return 1
return fib(n - 1) + fib(n - 2)
setdefault = fib(number)
|
The decorated function is being called a lot more in the default-dictionary version:
Now beginning explicit-membership version.
..........
Now beginning setdefault version.
.............................................................................................................
As values of number increase, the output of the setdefault version becomes intolerably prolonged, in keeping with what we know about recursive implementations of Fibonacci.
This supports the idea that the decorated function is being evaluated each time it is passed to setdefault, rather than only when arg is not found in the dictionary.
More concretely, here is the bytecode evidence for the greedy evaluation of dict.setdefault's arguments. Below is the dis (disassembler) output of the setdefault version of cached_func(arg):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | In [1]: %cpaste
Pasting code; enter '--' alone on the line to stop or use Ctrl-D.
:import dis
:cache = {}
:def cached_func(arg):
: return cache.setdefault(arg, func(arg))
:--
In [2]: dis.dis(cached_func)
3 0 LOAD_GLOBAL 0 (cache)
3 LOAD_ATTR 1 (setdefault)
6 LOAD_FAST 0 (arg)
9 LOAD_GLOBAL 2 (func)
12 LOAD_FAST 0 (arg)
15 CALL_FUNCTION 1 (1 positional, 0 keyword pair)
18 CALL_FUNCTION 2 (2 positional, 0 keyword pair)
21 RETURN_VALUE
|
Here we can see that func(arg) (loaded at position 9) is indeed always greedily passed to CALL_FUNCTION (position 15: the "1 positional" function, meaning having one argument), just before setdefault (the "2 positional" function, with two arguments) is passed to CALL_FUNCTION in position 18.
If dict.setdefault is meant to be an all-purpose substitute for dictionary membership-testing, this is perhaps a design oversight.
In contrast, here is the disassembler output of the membership-test version of cached_func(arg):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | In [1]: %cpaste
Pasting code; enter '--' alone on the line to stop or use Ctrl-D.
:import dis
:cache = {}
:def cached_func(arg):
: if arg not in cache:
: cache[arg] = func(arg)
: return cache[arg]
:--
In [2]: dis.dis(cached_func)
3 0 LOAD_FAST 0 (arg)
3 LOAD_GLOBAL 0 (cache)
6 COMPARE_OP 7 (not in)
9 POP_JUMP_IF_FALSE 31
4 12 LOAD_GLOBAL 1 (func)
15 LOAD_FAST 0 (arg)
18 CALL_FUNCTION 1 (1 positional, 0 keyword pair)
21 LOAD_GLOBAL 0 (cache)
24 LOAD_FAST 0 (arg)
27 STORE_SUBSCR
28 JUMP_FORWARD 0 (to 31)
5 >> 31 LOAD_GLOBAL 0 (cache)
34 LOAD_FAST 0 (arg)
37 BINARY_SUBSCR
38 RETURN_VALUE
|
In position 9, we have we have the branching statement POP_JUMP_IF_FALSE taking us to to position 31 if arg is found in cache; that is how we avoid greedily evaluating func(arg) (positions 12-28).
[end]