Last Updated on September 12, 2022
The ProcessPoolExecutor class in Python can be used to calculate multiple Fibonacci numbers at the same time.
This can dramatically speed-up your program compared to calculating Fibonacci numbers, one-by-one.
In this tutorial, you will discover how to calculate Fibonacci concurrently using a pool of worker processes.
Let’s dive in.
How to Calculate Fibonacci Numbers One at a Time (slowly)
Fibonacci numbers are a famous sequence of numbers.
For example, the first handful of numbers in the sequence are as follows:
- 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
The sequence of numbers are related to the golden ratio and are named after the discoverer of the sequence known as Fibonacci.
It is a common mathematical task to calculate the n’th Fibonacci number, that is the Fibonacci number at a specific point in the sequence.
The numbers in the sequence are calculated as the sum of the last two numbers in the sequence where the first two numbers in the sequence are 0 and 1.
For example:
- f_n = f_(n-1) + f_(n-2)
If we were to calculate the third number in the sequence (n=3) and we known that f1=1 and f0=0, then it would be calculated as:
- f_n = f_(n-1) + f_(n-2)
- f3 = 1 + 0
- f3 = 1
Given that the n’th Fibonacci is dependent on the previous two numbers in the sequence, the only way to figure out what a given number in the sequence is, is to calculate it.
This makes it a good task to explore concurrency in Python. For example, we might ask for a few different Fibonacci numbers and require our CPUs to grind away and compute them.
Next, let’s see how we can calculate Fibonacci numbers in Python.
Calculate Fibonacci Numbers
Calculating Fibonacci numbers is relatively straightforward.
Let’s look at the two main approaches, recursive and iterative implementations.
Calculate Fibonacci Numbers Recursively
Perhaps the most common implementation is to calculate the numbers recursively. That is to write a function that calls itself.
Writing recursive functions is a common exercise for new programmers and computer science students, although it is probably poor form in modern software development.
Given that we want to calculate the n’th number in the sequence as the sum of the previous two numbers, we can define a function that calls itself to calculate the n-1 and n-2 numbers in the sequence. The recursive call continues until we reach 0 or 1 in which case we bubble the numbers back up.
For example, the function below will calculate Fibonacci numbers using recursion.
|
1 2 3 4 5 6 |
# calculate the nth fibonacci number def fibonacci(n): # check for the start of the sequence if n <= 1: return n return (fibonacci(n-1) + fibonacci(n-2)) |
Let’s desk-check the function.
Consider we want to calculate the 4th number:
|
1 2 3 4 5 6 7 8 9 |
fibonacci(4) = fibonacci(3) + fibonacci(2) = 3 fibonacci(3) = fibonacci(2) + fibonacci(1) = 2 fibonacci(2) = fibonacci(1) + fibonacci(0) = 1 fibonacci(1) = 1 fibonacci(0) = 0 fibonacci(1) = 1 fibonacci(2) = fibonacci(1) + fibonacci(0) = 1 fibonacci(1) = 1 fibonacci(0) = 0 |
We can see that f(4) = 3, which is correct.
The example below uses this recursive implementation of calculating Fibonacci numbers to calculate the first 30 numbers in the sequence.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
# SuperFastPython.com # calculate fibonacci numbers using recursion # calculate the nth fibonacci number def fibonacci(n): # check for the start of the sequence if n <= 1: return n return (fibonacci(n-1) + fibonacci(n-2)) # calculate some fibonacci numbers for i in range(30): print(f'f({i}) = {fibonacci(i)}') |
Running the example calculates and reports Fibonacci numbers from 0 to 29.
|
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 |
f(0) = 0 f(1) = 1 f(2) = 1 f(3) = 2 f(4) = 3 f(5) = 5 f(6) = 8 f(7) = 13 f(8) = 21 f(9) = 34 f(10) = 55 f(11) = 89 f(12) = 144 f(13) = 233 f(14) = 377 f(15) = 610 f(16) = 987 f(17) = 1597 f(18) = 2584 f(19) = 4181 f(20) = 6765 f(21) = 10946 f(22) = 17711 f(23) = 28657 f(24) = 46368 f(25) = 75025 f(26) = 121393 f(27) = 196418 f(28) = 317811 f(29) = 514229 |
By the time we start calculating numbers around 30, this recursive approach becomes very slow.
This is not surprising given that there is a lot of redundancy in this recursive implementation. We have to calculate the same sub-sequences many times.
Let’s consider an iterative approach.
Calculate Fibonacci Numbers Iteratively
We can develop an iterative algorithm for calculating Fibonacci numbers.
It too is relatively straightforward.
First, we need to define the start of the sequence, that is the 0th and 1st numbers in the sequence as 0 and 1 respectively.
|
1 2 3 |
... # start the sequence f0, f1 = 0, 1 |
We then need to build up a sum to the nth number in the sequence.
This can be achieved with just two variables.
Each iteration we can shift up the sequence by one element, where f0 is the current number in the sequence and f1 is the next number in the sequence.
We continue to inch up the sequence until we reach the desired nth number.
|
1 2 3 4 |
... # compute the nth number for _ in range(0, n): f0, f1 = f1, (f1 + f0) |
The function below implements this algorithm, common to many programming textbooks.
|
1 2 3 4 5 6 7 8 |
# calculate the nth fibonacci number def fibonacci(n): # start the sequence f0, f1 = 0, 1 # compute the nth number for _ in range(0, n): f0, f1 = f1, (f1 + f0) return f0 |
Let’s desk-check it with n=4.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
Definition (n=0) f0 = 0 f1 = 1 f(0) = 0 Iteration 0: f0 = f1 = 1 f1 = f1 + f0 = 1 + 0 = 1 f(1) = f0 = 1 Iteration 1: f0 = f1 = 1 f1 = f1 + f0 = 1 + 1 = 2 f(2) = f0 = 1 Iteration 2: (n=3) f0 = f1 = 2 f1 = f1 + f0 = 1 + 2 = 3 f(3) = f0 = 2 Iteration 3: f0 = f1 = 3 f1 = f1 + f0 = 2 + 3 = 5 f(3) = 3 |
Looks good.
The complete example of calculating the first 30 Fibonacci numbers is listed below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
# SuperFastPython.com # calculate fibonacci numbers using iteration # calculate the nth fibonacci number def fibonacci(n): # start the sequence f0, f1 = 0, 1 # compute the nth number for _ in range(0, n): f0, f1 = f1, (f1 + f0) return f0 # calculate some fibonacci numbers for i in range(30): print(f'f({i}) = {fibonacci(i)}') |
Running the example, we can see that we get the same sequence of numbers as the recursive case.
It is also a lot faster as it does not have to recalculate each sub-sequence while calculating each Fibonacci number, as we did with the recursive case.
|
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 |
f(0) = 0 f(1) = 1 f(2) = 1 f(3) = 2 f(4) = 3 f(5) = 5 f(6) = 8 f(7) = 13 f(8) = 21 f(9) = 34 f(10) = 55 f(11) = 89 f(12) = 144 f(13) = 233 f(14) = 377 f(15) = 610 f(16) = 987 f(17) = 1597 f(18) = 2584 f(19) = 4181 f(20) = 6765 f(21) = 10946 f(22) = 17711 f(23) = 28657 f(24) = 46368 f(25) = 75025 f(26) = 121393 f(27) = 196418 f(28) = 317811 f(29) = 514229 |
Now that we know how to calculate Fibonacci numbers, let’s look at calculating lots of numbers.
Calculate Many Fibonacci Numbers
We can use our iterative implementation for calculating Fibonacci numbers to calculate many numbers in the sequence.
For example, we can calculate the first 10,000 numbers.
First, we can define an iterable with the numbers we want to calculate, in this case a range.
|
1 2 3 |
... # fibonacci numbers to calculate numbers = range(10000) |
We can then iterate over the numbers, calculate the Fibonacci number for each then store them in a dictionary that maps the number in the sequence (input) to the Fibonacci number (output).
|
1 2 3 4 5 |
... # calculate each in turn results = {} for i in numbers: results[i] = fibonacci(i) |
This is Python, so we can do better than this.
Let’s use the map() built-in function to apply the fibonacci() function to each value in the iterable to give an iterable of results.
|
1 2 3 |
... # calculate fibonacci numbers fibs = map(fibonacci, numbers) |
We can then create a dictionary directly from the iterable of numbers and the iterable of results by using the zip() built-in function.
|
1 2 3 |
... # store results results = dict(zip(numbers, fibs)) |
You can do this on one line if you like, but I try to avoid large compound statements.
|
1 2 3 |
... # calculate fibonacci numbers results = dict(zip(numbers, map(fibonacci, numbers))) |
Tying this together, the complete example of calculating the first 10,000 Fibonacci numbers is as follows:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
# SuperFastPython.com # calculate some large fibonacci numbers # calculate the nth fibonacci number def fibonacci(n): # start the sequence f0, f1 = 0, 1 # compute the nth number for _ in range(0, n): f0, f1 = f1, (f1 + f0) return f0 # entry point if __name__ == '__main__': # fibonacci numbers to calculate numbers = range(10000) # calculate fibonacci numbers fibs = map(fibonacci, numbers) # store results results = dict(zip(numbers, fibs)) print('Done') |
Running the example will take a moment.
On my system it takes about 6.5 seconds.
How long does it take to run on your system?
Let me know in the comments below.
Next, let’s look at how we can adapt our program for calculating Fibonacci numbers to make use of the ProcessPoolExecutor.
Run loops using all CPUs, download your FREE book to learn how.
Calculate Fibonacci Numbers Concurrently
We can update the example of calculating Fibonacci numbers to use the ProcessPoolExecutor.
Given that we are already using the built-in map() function, we can update the example to use the ProcessPoolExecutor map() function directly.
First, we can create the process pool with the default number of processes that matches the number of logical cores in our system.
|
1 2 3 4 |
... # create the process pool with ProcessPoolExecutor() as executor: # ... |
We can then update the call to map() to use the executor, for example:
|
1 2 3 |
... # calculate concurrently fibs = executor.map(fibonacci, numbers) |
And that’s it.
The complete example of calculating Fibonacci numbers concurrently using multiple CPU cores is listed 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 |
# SuperFastPython.com # calculate some large fibonacci numbers concurrently from concurrent.futures import ProcessPoolExecutor # calculate the nth fibonacci number def fibonacci(n): # start the sequence f0, f1 = 0, 1 # compute the nth number for _ in range(0, n): f0, f1 = f1, (f1 + f0) return f0 # entry point if __name__ == '__main__': # create the process pool with ProcessPoolExecutor() as executor: # fibonacci numbers to calculate numbers = range(10000) # calculate concurrently fibs = executor.map(fibonacci, numbers) # store results results = dict(zip(numbers, fibs)) print('Done') |
Running the example is dramatically faster compared to the sequential case.
On my system, it executes in about 2.7 seconds, compared to the 6.5 seconds for the serial version. That is about a 2.4x speedup.
How much speed-up did you see on your system?
Let me know in the comments below.
Speed-up Calculating Fibonacci Numbers with Chunksize
We can further speed-up the concurrent calculation of Fibonacci numbers.
The map() function on the ProcessPoolExeuctor takes a “chunksize” argument.
This argument is responsible for mapping tasks submitted to the process pool to internal tasks that are sent to worker processes in the pool for execution.
If the tasks are short duration and we have a lot of tasks to execute, then configuring the chunksize argument is a good idea. This matches our specific use case, we have a large number of short duration tasks.
By default the chunksize argument is set to 1, meaning each task submitted to the process pool is mapped to one internal task and sent to a worker process. Each task has some computational and memory overhead as it must be serialized (pickled) and transmitted to a separate process using inter-process communication. Fewer internal tasks means less overhead and a faster overall process.
|
1 2 3 |
... # calculate concurrently fibs = executor.map(fibonacci, numbers, chunksize=1) |
A good starting point for setting the chunksize is to divide the number of tasks by the number of logical CPUs.
|
1 2 3 4 5 |
... # mapping of external tasks to internal tasks size = 10000 / 8 # calculate concurrently fibs = executor.map(fibonacci, numbers, chunksize=size) |
This is good if all tasks have about the same execution duration, but that is not the case here as calculating the n=10 Fibonacci number is a lot faster than calculating the f=1000 number.
As such, it is a good idea to try different chunksize values and see what works best.
After some experimentation, I found that a value of 50 works well for this problem on my system.
|
1 2 3 4 5 |
... # mapping of external tasks to internal tasks size = 50 # calculate concurrently fibs = executor.map(fibonacci, numbers, chunksize=size) |
Experiment with different chunksizes in order to discover what works best on your system. Let me know in the comments below, I’d love to see what you discover.
The complete example of calculating Fibonacci numbers concurrently with an optimized chunksize is listed 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 |
# SuperFastPython.com # calculate some large fibonacci numbers concurrently from concurrent.futures import ProcessPoolExecutor # calculate the nth fibonacci number def fibonacci(n): # start the sequence f0, f1 = 0, 1 # compute the nth number for _ in range(0, n): f0, f1 = f1, (f1 + f0) return f0 # entry point if __name__ == '__main__': # create the process pool with ProcessPoolExecutor() as executor: # fibonacci numbers to calculate numbers = range(10000) # mapping of external tasks to internal tasks size = 50 # calculate concurrently fibs = executor.map(fibonacci, numbers, chunksize=size) # store results results = dict(zip(numbers, fibs)) print('Done') |
Running the example calculates the first 10,000 Fibonacci numbers as before, but is faster again than the concurrent version above.
On my system the example completes in about 1.6 seconds, compared to 2.7 seconds when chunksize=1 in the previous section.
How much further speed-up did you see on your system?
Let me know in the comments below.
Free Python ProcessPoolExecutor Course
Download your FREE ProcessPoolExecutor PDF cheat sheet and get BONUS access to my free 7-day crash course on the ProcessPoolExecutor API.
Discover how to use the ProcessPoolExecutor class including how to configure the number of workers and how to execute tasks asynchronously.
Extensions
This section lists ideas for extending the tutorial.
- Memorize Calculated Numbers. Update the example so that the fibonacci() function memorizes and reuses previously calculated numbers in the sequence.
- Parallelize Calculation of One Number. Explore how you might parallelize the calculation of a single number in the sequence using the process pool.
- Tune Chunksize. Tune the chunksize argument on your system and compare a range of values in order to discover what value is optimal.
Share your extensions in the comments below, it would be great to see what you come up with.
Overwhelmed by the python concurrency APIs?
Find relief, download my FREE Python Concurrency Mind Maps
Further Reading
This section provides additional resources that you may find helpful.
Books
- ProcessPoolExecutor Jump-Start, Jason Brownlee (my book!)
- Concurrent Futures API Interview Questions
- ProcessPoolExecutor PDF Cheat Sheet
I also recommend specific chapters from the following books:
- Effective Python, Brett Slatkin, 2019.
- See Chapter 7: Concurrency and Parallelism
- Python in a Nutshell, Alex Martelli, et al., 2017.
- See: Chapter: 14: Threads and Processes
Guides
- Python ProcessPoolExecutor: The Complete Guide
- Python ThreadPoolExecutor: The Complete Guide
- Python Multiprocessing: The Complete Guide
- Python Pool: The Complete Guide
APIs
References
- Thread (computing), Wikipedia.
- Process (computing), Wikipedia.
- Thread Pool, Wikipedia.
- Futures and promises, Wikipedia.
Takeaways
In this tutorial you discovered how to calculate Fibonacci concurrently using a pool of worker processes.
Do you have any questions?
Leave your question in a comment below and I will reply fast with my best advice.
Do you have any questions?