Понимание оптимизации прогнозирования ветвей в Python ⇐ Python

[Anonymous]

Недавно я работал над простой задачей Leetcode, чтобы написать функцию, которая возвращает True, если список чисел содержит дубликат, и False в противном случае. Код, который я отправил, был настолько простым, что я был уверен, что это самое быстрое решение, но оно дало примерно 40-й процентиль производительности. Я рассмотрел одно из более быстрых решений, и единственной разницей было else, которое я пропустил, поскольку функция возвращала соответствующий if, а это означает, что логически else не было необходимым. Сравнивая этот код локально, я вижу постоянное улучшение скорости примерно на 20 % при наличии else, но только в определенных (случайных) тестовых случаях. См. приведенный ниже сценарий для некоторых тестовых случаев, которые демонстрируют или не демонстрируют это улучшение.

Код: Выделить всё

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}%")

Выход:

Код: Выделить всё

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%

Я предполагаю, что это улучшение как-то связано с предсказанием ветвей ЦП, но у меня есть несколько вопросов по этому поводу:

• Когда я генерирую байт-код для обеих этих функций, он выглядит одинаково. Я недостаточно знаю о компиляции/выполнении Python, чтобы понять, когда вместо байт-кода будет использоваться исходный код, но это должно каким-то образом ссылаться на исходный код, чтобы объяснить разницу, когда байт-код идентичен.
  Я понимаю, почему тестовый пример 1 не выиграет от прогнозирования ветвления, поскольку дубликатов никогда не бывает, и мы всегда пропускаем условие if. Я предполагаю, что тестовый пример 2 достаточно повторяется, чтобы компилятор или процессор заметил закономерность, и мы больше не получаем выгоды от предсказания ветвей. Но для тестового примера 3, где входные данные каждый раз случайны, я не совсем понимаю, как помогает предсказание ветвления. Действительно ли в первом примере отсутствие else вообще предотвращает предсказание ветвления? Или первая версия всегда начинается с операции установки, которую иногда приходится отбрасывать, поскольку она не может предсказать ветвление? Я просто пытаюсь понять, что может привести к последовательному улучшению тестового примера 3.

Подробнее здесь: https://stackoverflow.com/questions/793 ... -in-python