Example 2 – inherently sequential tasks

Let us consider a quick example:

Computing f¹⁰⁰⁰(3), with f(x) = x² - x + 1, and f^{n + 1}(x) = f(fⁿ(x)).

With complicated functions like f (where it is relatively difficult to find a general form of fⁿ(x)), the only obviously reasonable way to compute f¹⁰⁰⁰(3) or similar values is to iteratively compute f²(3) = f( f(3)), f³(3) = f( f²(3)), ... , f⁹⁹⁹(3) = f( f⁹⁹⁸(3)), and, finally, f¹⁰⁰⁰(3) = f( f⁹⁹⁹(3)).

Since it will take significant time to actually compute f¹⁰⁰⁰(3), even when using a computer, we will only consider f²⁰(3) in our code (my laptop actually started heating up after f²⁵(3)):

# Chapter01/example2.py

def f(x):
    return x * x - x + 1

# sequential
def f(x):
    return x * x - x + 1

start = timer()
result = 3
for i in range(20):
    result = f(result)

print('Result is very large. Only printing the last 5 digits:', result % 100000)
print('Sequential took: %.2f seconds.' % (timer() - start))

Run it (or use python example2.py); the following code shows the output I received:

> python example2.py
Result is very large. Only printing the last 5 digits: 35443
Sequential took: 0.10 seconds.

Now, if we were to attempt to apply concurrency to this script, the only possible way would be through a for loop. One solution might be as follows:

# Chapter01/example2.py

# concurrent
def concurrent_f(x):
    global result
    result = f(result)

result = 3

with concurrent.futures.ThreadPoolExecutor(max_workers=20) as exector:
    futures = [exector.submit(concurrent_f, i) for i in range(20)]

    _ = concurrent.futures.as_completed(futures)

print('Result is very large. Only printing the last 5 digits:', result % 100000)
print('Concurrent took: %.2f seconds.' % (timer() - start))

The output I received is shown as follows:

> python example2.py
Result is very large. Only printing the last 5 digits: 35443
Concurrent took: 0.19 seconds.

Even though both methods produced the same result, the concurrent method took almost twice as long as the sequential method. This is due to the fact that every time a new thread (from ThreadPoolExecutor) was spawned, the function conconcurrent_f(), inside that thread, needed to wait for the variable result to be processed by the previous thread completely, and the program as a whole was thus executed in a sequential manner, nonetheless.

So, while there was no actual concurrency involved in the second method, the overhead cost of spawning new threads contributed to the significantly worse execution time. This is one example of inherently sequential tasks, where concurrency or parallelism should not be applied to attempt an improvement in execution time.