Warum läuft dieses Python-Skript auf mehreren Kernen 4x langsamer als auf einem einzigen Kern?

Question

Ich versuche zu verstehen, wie CPython GIL funktioniert und was die Unterschiede zwischen GIL in CPython 2.7.x und CPython 3.4.x sind. Ich verwende diesen Code für das Benchmarking:

from __future__ import print_function 

import argparse 
import resource 
import sys 
import threading 
import time 


def countdown(n): 
    while n > 0: 
     n -= 1 


def get_time(): 
    stats = resource.getrusage(resource.RUSAGE_SELF) 
    total_cpu_time = stats.ru_utime + stats.ru_stime 
    return time.time(), total_cpu_time, stats.ru_utime, stats.ru_stime 


def get_time_diff(start_time, end_time): 
    return tuple((end-start) for start, end in zip(start_time, end_time)) 


def main(total_cycles, max_threads, no_headers=False): 
    header = ("%4s %8s %8s %8s %8s %8s %8s %8s %8s" % 
       ("#t", "seq_r", "seq_c", "seq_u", "seq_s", 
       "par_r", "par_c", "par_u", "par_s")) 
    row_format = ("%(threads)4d " 
        "%(seq_r)8.2f %(seq_c)8.2f %(seq_u)8.2f %(seq_s)8.2f " 
        "%(par_r)8.2f %(par_c)8.2f %(par_u)8.2f %(par_s)8.2f") 
    if not no_headers: 
     print(header) 
    for thread_count in range(1, max_threads+1): 
     # We don't care about a few lost cycles 
     cycles = total_cycles // thread_count 

     threads = [threading.Thread(target=countdown, args=(cycles,)) 
        for i in range(thread_count)] 

     start_time = get_time() 
     for thread in threads: 
      thread.start() 
      thread.join() 
     end_time = get_time() 
     sequential = get_time_diff(start_time, end_time) 

     threads = [threading.Thread(target=countdown, args=(cycles,)) 
        for i in range(thread_count)] 
     start_time = get_time() 
     for thread in threads: 
      thread.start() 
     for thread in threads: 
      thread.join() 
     end_time = get_time() 
     parallel = get_time_diff(start_time, end_time) 

     print(row_format % {"threads": thread_count, 
          "seq_r": sequential[0], 
          "seq_c": sequential[1], 
          "seq_u": sequential[2], 
          "seq_s": sequential[3], 
          "par_r": parallel[0], 
          "par_c": parallel[1], 
          "par_u": parallel[2], 
          "par_s": parallel[3]}) 


if __name__ == "__main__": 
    arg_parser = argparse.ArgumentParser() 
    arg_parser.add_argument("max_threads", nargs="?", 
          type=int, default=5) 
    arg_parser.add_argument("total_cycles", nargs="?", 
          type=int, default=50000000) 
    arg_parser.add_argument("--no-headers", 
          action="store_true") 
    args = arg_parser.parse_args() 
    sys.exit(main(args.total_cycles, args.max_threads, args.no_headers)) 

Wenn dieses Skript läuft auf meiner Quad-Core-i5-2500 Maschine unter Ubuntu 14.04 mit Python 2.7.6, erhalte ich die folgenden Ergebnisse (_R für Echtzeit steht, _c für CPU-Zeit, _u für Benutzermodus, _S für Kernel-Modus):

#t seq_r seq_c seq_u seq_s par_r par_c par_u par_s 
    1  1.47  1.47  1.47  0.00  1.46  1.46  1.46  0.00 
    2  1.74  1.74  1.74  0.00  3.33  5.45  3.52  1.93 
    3  1.87  1.90  1.90  0.00  3.08  6.42  3.77  2.65 
    4  1.78  1.83  1.83  0.00  3.73  6.18  3.88  2.30 
    5  1.73  1.79  1.79  0.00  3.74  6.26  3.87  2.39 

Nun, wenn ich alle Themen auf einen Kern zu binden, sind die Ergebnisse sehr unterschiedlich:

taskset -c 0 python countdown.py 
    #t seq_r seq_c seq_u seq_s par_r par_c par_u par_s 
    1  1.46  1.46  1.46  0.00  1.46  1.46  1.46  0.00 
    2  1.74  1.74  1.73  0.00  1.69  1.68  1.68  0.00 
    3  1.47  1.47  1.47  0.00  1.58  1.58  1.54  0.04 
    4  1.74  1.74  1.74  0.00  2.02  2.02  1.87  0.15 
    5  1.46  1.46  1.46  0.00  1.91  1.90  1.75  0.15 

So ist die Frage : Warum läuft dieser Python? Code auf mehreren Kernen ist 1.5x-2x langsamer durch die Wanduhr und 4x-5x langsamer durch CPU-Takt als auf einem einzelnen Kern laufen?

herum Vorstellung und zwei Hypothesen erzeugt googeln:

1. Wenn auf mehreren Kernen ausgeführt wird, kann ein Thread neu geplant werden, auf einem anderen Kern laufen, was bedeutet, dass die lokalen Cache, die Verlangsamung somit für ungültig erklärt wird.
2. Der Overhead zum Aufhängen eines Threads auf einem Kern und Aktivieren auf einem anderen Kern ist größer als das Aufheben und Aktivieren des Threads auf demselben Kern.

Gibt es noch andere Gründe? Ich würde gerne verstehen, was vor sich geht, und mein Verständnis mit Zahlen untermauern können (das heißt, wenn die Verlangsamung auf Cache-Misses zurückzuführen ist, möchte ich die Zahlen für beide Fälle sehen und vergleichen).

Answer 1

Es ist wegen GIL-Thrashing, wenn mehrere native Threads für die GIL konkurrieren. David Beazleys Materialien zu diesem Thema werden Ihnen alles erzählen, was Sie wissen wollen.

Siehe info here für eine schöne grafische Darstellung dessen, was passiert.

In Python3.2 wurden Änderungen an der GIL eingeführt, die zur Lösung dieses Problems beitragen. Daher sollten Sie mit 3.2 und höher eine verbesserte Leistung sehen.

Es sollte auch beachtet werden, dass die GIL ein Implementierungsdetail der cpython Referenzimplementierung der Sprache ist. Andere Implementierungen wie Jython haben keine GIL und leiden nicht unter diesem speziellen Problem.

The rest of D. Beazley's info on the GIL wird auch für Sie hilfreich sein.

Um speziell Ihre Frage zu beantworten, warum die Leistung bei mehreren Kernen so viel schlechter ist, lesen Sie Folie 29-41 der Inside the GIL Präsentation. Es wird eine detaillierte Diskussion über Multicore-GIL-Konflikte im Gegensatz zu mehreren Threads auf einem einzelnen Kern geführt. Folie 32 zeigt speziell, dass die Anzahl der Systemaufrufe aufgrund von Thread-Signalisierungs-Overhead durch das Dach geht, wenn Sie Kerne hinzufügen. Der Grund dafür ist, dass die Threads jetzt auf verschiedenen Kernen laufen und es ihnen ermöglicht, an einem echten GIL-Kampf teilzunehmen. Im Gegensatz zu mehreren Threads, die sich eine einzige CPU teilen. Eine gute Zusammenfassung Kugel aus der obigen Darstellung ist:

mit mehreren Kernen, CPU-gebundene Threads gleichzeitig geplant bekommen (auf verschiedenen Kernen) und dann eine GIL Schlacht haben.

Answer 2

Die GIL verhindert, dass mehrere Python-Threads gleichzeitig ausgeführt werden. Das bedeutet, wenn ein Thread Python-Bytecode (die interne Darstellung des Codes) ausführen muss, wird die Sperre aktiviert (wodurch die anderen Threads auf den anderen Kernen effektiv gestoppt werden). Damit dies funktioniert, muss die CPU alle Cache-Zeilen leeren. Andernfalls würde der aktive Thread mit veralteten Daten arbeiten.

Wenn Sie die Threads auf einer einzelnen CPU ausführen, ist kein Cache-Flush erforderlich.

Dies sollte für den Großteil der Verlangsamung verantwortlich sein. Wenn Sie Python-Code parallel ausführen möchten, müssen Sie Prozesse und IPC (Sockets, Semaphore, Memory-Mapped-IO) verwenden. Aber das kann aus verschiedenen Gründen langsam sein (Speicher muss zwischen Prozessen kopiert werden).

Ein anderer Ansatz ist das Verschieben von mehr Code in einer C-Bibliothek, die die GIL während der Ausführung nicht enthält. Das würde es ermöglichen, mehr Code parallel auszuführen.