[Python] Understanding Branch Prediction Optimizations in Python

I was recently working on a simple Leetcode problem to write a function that returns True if a list of numbers contains a duplicate, and False otherwise. The code that I submitted was so simple that I was sure it must be the fastest solution, but it came back with a ~40th percentile of performance. I looked at one of the faster solutions, and the only difference was an else that I had omitted because the function was returning in the corresponding if, meaning logically the else was not necessary. Benchmarking this code locally, I can see a consistent speed improvement of about 20% with the else in place, but only under certain (random) test cases. See the script below for some test cases that do or do not show this improvement.

import random
import time

def containsDuplicate1(nums):
seen = set([])
for num in nums:
if num in seen:
return True
seen.add(num)
return False

def containsDuplicate2(nums):
seen = set([])
for num in nums:
if num in seen:
return True
else:
seen.add(num)
return False

# When duplicates are rare or non-existent, we get no difference
time1 = 0
time2 = 0
for i in range(10000):
nums = list(range(1000))
start = time.time()
containsDuplicate1(nums)
time1 += (time.time() - start)
start = time.time()
containsDuplicate2(nums)
time2 += (time.time() - start)
print("Test case 1: No duplicates")
print(f"Execution time for 'no else clause': {time1}")
print(f"Execution time for 'else clause': {time2}")
print(f"Percentage speed improvement: {100 * (time1 - time2) / time1:.2f}%")

# When the numbers are random but are the same on every run, the difference is negligible (easier to predict?)
time1 = 0
time2 = 0
nums = [random.randint(0, 1000) for _ in range(1000)]
for i in range(10000):
start = time.time()
containsDuplicate1(nums)
time1 += (time.time() - start)
start = time.time()
containsDuplicate2(nums)
time2 += (time.time() - start)
print("Test case 2: Random numbers, but same every time")
print(f"Execution time for 'no else clause': {time1}")
print(f"Execution time for 'else clause': {time2}")
print(f"Percentage speed improvement: {100 * (time1 - time2) / time1:.2f}%")

# But when numbers are random and change on every run (with frequent duplicates), the difference is significant
time1 = 0
time2 = 0
for i in range(10000):
nums = [random.randint(0, 1000) for _ in range(1000)]
start = time.time()
containsDuplicate1(nums)
time1 += (time.time() - start)
start = time.time()
containsDuplicate2(nums)
time2 += (time.time() - start)
print("Test case 3: Random numbers, different every time")
print(f"Execution time for 'no else clause': {time1}")
print(f"Execution time for 'else clause': {time2}")
print(f"Percentage speed improvement: {100 * (time1 - time2) / time1:.2f}%")


Output:

Test case 1: No duplicates
Execution time for 'no else clause': 0.19391775131225586
Execution time for 'else clause': 0.19402170181274414
Percentage speed improvement: -0.05%
Test case 2: Random numbers, but same every time
Execution time for 'no else clause': 0.0033860206604003906
Execution time for 'else clause': 0.0034241676330566406
Percentage speed improvement: -1.13%
Test case 3: Random numbers, different every time
Execution time for 'no else clause': 0.02005624771118164
Execution time for 'else clause': 0.016332626342773438
Percentage speed improvement: 18.57%


I'm guessing that this improvement is something to do with the CPU's branch prediction, but I have a few questions about that:

1. When I generate the bytecode for both of these functions, it looks identical. I don't know enough about python compilation/execution to understand when the source code would be used instead of the bytecode, but it must be referring to the source code in some way to explain the difference when the bytecode is identical.
2. I understand why test case 1 would not benefit from branch prediction, since there is never a duplicate and we always miss the if condition. I assume that test case 2 is repetitive enough that the compiler or processor spots a pattern and we no longer benefit from branch prediction. But for test case 3, where the inputs are random every time, I don't really see how branch prediction helps. Is it the case that in the first example, the lack of an else prevents branch prediction from happening at all? Or is the first version always starting on the set operation that must be discarded sometimes because it can't predict the branching? I'm just looking for some intuition around what might be going on to cause the consistent improvement for test case 3.

Continue reading...