The following discussion assumes familiarity with writing functions in a high-level programming language.
The decorator pattern provides a concise and elegant way to add functionality to pre-existing code. The programmer may write the decorating function once and thereafter decorate any number of functions, anywhere. Sound like too much freedom? As is the nature of programming, there are virtually limitless create-o-logical, electroreasonable ways to write things. It's my hope to ground the discussion with practical, actionable examples which might justly and concisely demonstrate the potential of the decorator pattern.
Given the name, it would be natural to imagine there's something ~fancy~ about decorators. They are not, in fact, frivolous adornments (Though the programmer may find them pretty!).
The truth is they are simply a way of writing functions guided by a specific design pattern.
Thankfully, Python and JavaScript both support higher-order functions, meaning all valid functions qualify as "first-class citizens" which can be passed as function arguments and returned from other functions.
Cool. Why does it matter?
The careful reader may reason that "citizens" isn't an entirely semantic way to think about pseudolinguistic abstractions dependent on electricity ... What is meant can be thought of more simply: first-class citizens are treated like values. They have clearance to go anywhere other values can go.
And for our decorators to work, we need to be able to pass functions as values into the decorating function.
Decorators are not exclusive to any specific language, to be clear. One can write a decorator function in JavaScript or Python or another functional language much the same. As two of the most commonly used modern languages, and two I am at least familiar with, I've chosen JS and Python to demonstrate decorators through code in the examples to come.
Now that we've sufficiently murked the water with our stirring, let's see if we can clear things up.
The decorator pattern can be implemented as follows
The decorator takes a function or functions as it's argument:
# PYTHON
def decorator(func):
pass
// JAVASCRIPT
function decorator(func) {
return;
}
It's important to note that a decorator should return a function (or in some cases, a class). Our goal is always to extend, transform, or modify another function's ability, and so we must return a function so that we can use it later as a new and improved "decorated" version.
So we'll setup another function inside the decorator's body and return it:
def decorator(func):
# *args allows for a variable number of arguments
def modifier(*args):
return func(*args)
return modifier
function decorator(func) {
// rest operator allows for a variable number of arguments
function modifier(...args) {
return func(...args);
}
return modifier;
}
There's a lot going on here, and some of it involves closure, which is too rich a topic to indulge intermittently. One may content oneself with the idea that closures allow our functions to keep track of internal values. They are packaged up for future use and modification!
Our function is now available to the innermost scope so that it can be augmented, modified, or enhanced by the decorator. Nonetheless, our decorator remains useless. We need a problem to solve.
Pretend Problem
- We need to optimize some functions that perform computationally intensive work.
- Each function is pure, meaning that, given the same inputs, the function will always produce the same output.
- It is likely that the function will frequently be called with inputs identical to previous calls.
Given these understandings, memoization will be our chosen strategy. And the decorator pattern turns out to be an elegant choice for implementing it!
In order to properly demonstrate memoization, we need a function that emulates an "expensive operation":
"""
Adds x to itself x times
"""
def cpu_spinner(x):
values = [x for _ in range(x)]
return sum(values)
/**
Adds x to itself x times
*/
function cpuSpinner(x) {
return Array.from({ length: x }, (_) => x)
.reduce((sum, val) => (sum += val), 0);
}
Note: One may note that, compared to the javascript implementation, the python code appears overwhelmingly simple. This may be related to the fact that, being a data science-centric language, Python is in some ways more optimized for math.
Sooo, we have a couple of ~highly sophisticated~ and super expensive operations. Now we need to modify our decorator implementations for memoization, allowing the functions to "remember" previous inputs and their respective results. In both implementations, our cache is a simple hash table that stores the input function's arguments as a key, and the result of the function call as the value for that key:
def memoize(func):
# Initialize structure to hold previous results
cache = {}
def wrapper(*args):
"""
If we've passed these args before,
return early with the stored result
"""
if args in cache:
return cache[args]
"""
Otherwise, execute function and store in cache as
[args]: result
"""
result = func(*args)
cache[args] = result
return result
return wrapper
The JavaScript version's logic is essentially identical, but because we can't store complex objects as keys, we need to stringify the key (or use a JS Map that can:
function memoize (func) {
const cache = {}
function wrapper (...args) {
const key = args.toString()
// return early with result if it's stored
if (key in cache) return cache[key]
// otherwise store in cache
const result = func(...args)
cache[key] = result
return result
}
return wrapper
}
Note that these solutions follow the same decorator template we set up previously, albeit with some simple logic in between. The key here is that the decorator allows the inner function to keep track of a stateful value. The inner function captures a reference to it's outer, lexical scope, which in this case includes our mutable cache. This capturing behavior is what is known as closure, and it makes possible class-less statefulness and other functional strategies.
NICE
Typically, functions don't need to concern themselves with the context of previous calls. But in the event that the programmer requires persistence across subsequent calls, as in the case of our memoization strategy, a thorough understanding of closures may prove something of a weapon.
It's finally time to ~decorate~ our wildly expensive functions. since 2004, Python has included support for a dedicated decorator syntax. While JavaScript has not, the underlying principle and application is much the same. For python, it's a simple matter of annotating the expensive function with @name_of_decorator_func:
@memoize
def cpu_spinner(x):
"""
Adds x to itself x times
"""
return sum([x for _ in range(x)])
For JS, we can accomplish the same thing by simply passing the function we wish to memoize as an argument to the decorator, returning a decorated version of the function to be called later:
const memoizedCpuSpinner = memoize(cpuSpinner);
Now, let's make this ~groovy~ experiment even more fun by including yet another decorator function that follows the very same decorator pattern. Don't worry, this one's even simpler than our memo implementation. But instead of memoizing, this final decorator will time the execution of our memoized functions, so we can explicitly see just how effective memoization can be.
For python, we'll have to import the time module:
import time
def timer(func):
"""
Immediately before and after the function call,
we capture the time and print the difference as `elapsed`
"""
def wrapper(*args):
start_time = time.process_time()
result = func(*args)
elapsed = time.process_time() - start_time
print(f"Elapsed: {elapsed:.3f} ")
return result
return wrapper
Before any pitchforks crest my horizon, I should make very clear that the results of my tests are highly subjective and dependent on a wide range of extraneous factors. But I believe the results, regardless of their inherent imprecision, should sufficiently illustrate the potential power of memoization.
JavaScript's console object should serve just fine for this simple example:
function timer (func) {
function wrapper (...args) {
console.time('JavaScript')
const result = func(...args)
console.timeEnd('JavaScript')
return result
}
return wrapper
}
Execution
Let's tie everything together with a final record of our work, along with several function calls to our decorated functions, fully timer-wrapped and memoized. We'll also include some print statements necessary for digesting our results.
# *PYTHON
def memoize(func):
cache = {}
# Let's add a second stateful value that will track execution count
count = 0
def wrapper(*args):
nonlocal count
count += 1
print(f"Execution count: {count}")
if args in cache:
print(f"Cached result for {args}: {cache[args]}")
return cache[args]
result = func(*args)
print(f"Uncached result for {args}: {result}")
cache[args] = result
return result
return wrapper
def timer(func):
def wrapper(*args):
start_time = time.process_time()
result = func(*args)
elapsed = time.process_time() - start_time
print(f"Elapsed: {elapsed:.3f} ")
return result
return wrapper
# Syntax sugar for passing the annotated function as an argument
@timer
@memoize
def cpu_spinner(x):
return sum([x for _ in range(x)])
expensive_input = 100_000_000
cpu_spinner(expensive_input)
cpu_spinner(expensive_input)
cpu_spinner(expensive_input)
/* JAVASCRIPT */
// This time, for fun, we'll implement a function expression
const cpuSpinner = (x) =>
Array.from({ length: x}, _ => x).reduce((sum, val) => (sum += val), 0)
function memoize (func) {
const cache = {}
let count = 0
function wrapper (...args) {
count += 1
console.log(`Execution count: ${count}`)
const key = args.toString()
// return early with result if it's stored
if (key in cache) {
const result = cache[key]
console.log(`Cached results for argument ${key}: ${result}`)
return result
}
const result = func(...args)
console.log(`Uncached result: ${result}`)
cache[key] = result
return result
}
return wrapper
}
function timer (func) {
function wrapper (...args) {
console.time('Elapsed')
const result = func(...args)
console.timeEnd('Elapsed')
console.log('\n')
return result
}
return wrapper
}
const timedMemo = timer(memoize(cpuSpinner))
const expensiveInput = 100_000_000
timedMemo(expensiveInput)
timedMemo(expensiveInput)
timedMemo(expensiveInput)
Results && Conclusion
The point with our chosen experiment is not the speed of the language itself, nor how the performance of each language compares against the other (neither is designed for speed in general). The key takeaway concerning memoization is the proof that each subsequent call to the function using the same argument produces its result almost instantaneously.
The reasons why the Python code outperforms the JS and the reason why the JS still takes a fraction of a second to retrieve a memo-ized value are questions explored in the PostNotes.
Python
Call #1
Uncached result: 1e+16
Execution timer: 4,469ms
Call #2
Cached result for argument 1e+8: 1e+16
Execution timer: 000ms
Call #3
Cached result: 1e+16
Execution timer: 000ms
JS
Call #1
Uncached result: 1e+16
Execution timer: 9,347ms
Call #2
Cached result for argument 1e+8: 1e+16
Execution timer: 306ms
Call #3
Cached result: 1e+16
Execution timer: 442ms
All of the redundancies here are meant to drive home the point that memoization is only effective when a function receives input identical to a previous call and that function is entirely free from side effects. Otherwise, we can't count on the result being the same as the previous call based solely on the input.
We can see that the first function call takes a notable amount of time to finish executing: 4,469ms and 9,347ms for Python and JS respectively. We can see given the timing of subsequent calls with the same input argument that the result is produced nearly instantaneously by comparison.
It is my hope that, by this point, it is clear why these results can be expected. If a function is truly pure, we can count on our identical arguments to produce identical results. So we use closure to keep a record of previous args and their paired output using a hash table which we've called cache. Every time the function is called, our memoization decorator checks the hash table to see if the result is already recorded. If so, the entire operation amounts to a quick lookup in the hash table to retrieve the expected value.
Bye For Now
For quick reference, a few concepts we explored throughout this experiment:
Thanks so much for reading!
Stay tuned in to the following section for some random tidbits that didn't make the cut.
As always,
Keep growing!
PostNotes
Fun Fact:
I accidentally produced a fatal heap overflow error in Node.js when I attempted to increase the input by 5x. I suspect this is related to poor handling of memory by filling an array without a dedicated
rangeoperator like the one we used in the Python implementation. If you know of a more efficient way to populate a JavaScript array for experiments of this kind, please let me know!
And for fun, here's a screen snip of the abbreviated error:
Cool Function, dude
Here's a JavaScript version of the memoize decorator that aims to be as concise as possible by leaning all the way into the functional style. Though not necessarily practical or easy to read, it was groovy and fun to devise:
- Anonymize the second function and return it implicitly.
- Pass the cache silently as a default argument, eliminating the need to declare it inside the function body that we no longer have, but still exposing it to the inner function's lexical scope as is necessary for closure.
- Celebrate victory.
const functionalMemoize =
(func, cache = {}) =>
(...args) => {
const key = args.toString()
if (key in cache) return cache[key]
const result = func(...args)
cache[key] = result
return result
}
Sneaky Snake
The Python implementation of the "expensive function" which I chose somewhat at random came out short, sweet, incredibly readable and relatively fast. The near-zero execution time seen in the memoized Python results makes sense considering the simplicity of a hash table lookup. So why the costly calls in the JavaScript version?
Short answer, I don't actually know. 🙃
But when I removed all console logs from the implementation, the results came much nearer to zero. This suggests that writing to stdio is more expensive in JS than in Python, but this mystery may go the way of the tootsie pop.
For now ...
Top comments (0)