Grundlegendes zur Branch-Prediction-Optimierung in Python ⇐ Python

[Anonymous]

Ich habe kürzlich an einem einfachen Leetcode-Problem gearbeitet, um eine Funktion zu schreiben, die „True“ zurückgibt, wenn eine Liste von Zahlen ein Duplikat enthält, andernfalls „False“. Der Code, den ich eingereicht habe, war so einfach, dass ich mir sicher war, dass es die schnellste Lösung sein musste, aber die Leistung lag bei etwa dem 40. Perzentil. Ich habe mir eine der schnelleren Lösungen angesehen und der einzige Unterschied war ein else, das ich weggelassen hatte, weil die Funktion im entsprechenden if zurückgegeben wurde, was bedeutet, dass das else logischerweise nicht notwendig war. Beim lokalen Benchmarking dieses Codes kann ich eine konsistente Geschwindigkeitsverbesserung von etwa 20 % feststellen, wenn else vorhanden ist, allerdings nur unter bestimmten (zufälligen) Testfällen. Im folgenden Skript finden Sie einige Testfälle, die diese Verbesserung zeigen oder nicht.

Code: Select all

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

Ausgabe:

Code: Select all

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%

Ich vermute, dass diese Verbesserung etwas mit der Verzweigungsvorhersage der CPU zu tun hat, aber ich habe ein paar Fragen dazu:

• Wenn ich den Bytecode für diese beiden Funktionen generiere, sieht er identisch aus. Ich weiß nicht genug über Python-Kompilierung/-Ausführung, um zu verstehen, wann der Quellcode anstelle des Bytecodes verwendet werden würde, aber er muss sich irgendwie auf den Quellcode beziehen, um den Unterschied zu erklären, wenn der Bytecode identisch ist.
• Ich verstehe, warum Testfall 1 nicht von der Verzweigungsvorhersage profitieren würde, da es nie ein Duplikat gibt und wir immer die if-Bedingung verpassen. Ich gehe davon aus, dass Testfall 2 so repetitiv ist, dass der Compiler oder Prozessor ein Muster erkennt und wir nicht mehr von der Verzweigungsvorhersage profitieren. Aber für Testfall 3, bei dem die Eingaben jedes Mal zufällig sind, sehe ich nicht wirklich, wie die Verzweigungsvorhersage helfen soll. Ist es so, dass im ersten Beispiel das Fehlen eines else die Verzweigungsvorhersage überhaupt verhindert? Oder beginnt die erste Version immer mit der Set-Operation, die manchmal verworfen werden muss, weil sie die Verzweigung nicht vorhersagen kann? Ich bin nur auf der Suche nach einer Vorstellung davon, was möglicherweise zu einer konsistenten Verbesserung für Testfall 3 führt.