Performance bei verschachtelten Schleifen

[Lufia]

Ich habe ein kleines Performance Problem das wohl durch verschachtelte Schleifen verursacht wird. Ich versuche das Problem mal mit einem vereinfachten Beispiel zu erläutern. In meinem reellen Problem (post-processing) berechne ich die Geschwindigkeit an den Integrationspunkten in einem FEM/FVM - Netz. Die Schleife geht über die Knoten des Elements und die verschiedenen betrachteten Bilanzgleichungen.

Ich versuche es mit einem vereinfachten Beispiel. Ich habe eine Schleife über Autos und für jedes Auto berechne ich verschiedene Werte für jeden einzelnen Reifen.

Code: Alles auswählen

for i in xrange(nAutos):
    for j in xrange(nReifen):
        ... berechne Druck am Reifen j
        .... berechne viele Sachen an jedem Reifen j....

Wenn die Zahl der Autos gering ist und die Anzahl der Reifen auch kann ich theoretisch denk Code doppelt schreiben und nur über die nAutos iterieren.

Code: Alles auswählen

for i in xrange(nAutos):
        .... berechne Druck an Reifen a
        .... berechne Druck an Reifen b
        .... berechne viele Sachen an jedem Reifen ....

.... berechne Druck wäre jetzt eine einfache Formel, wobei ich pro Reifen sehr viele Sachen berechnen würde die aber bei jedem Reifen immer Identisch sind. Die zweite Variante verwendet doppelten Code was nicht besonders schön ist gerade wenn die Anzahl der Reifen variabel ist. Der Unterschied zwischen beiden Varianten ist enorm. Die schnelle Version braucht 6 Sekunden die langsame über 10 Sekunden. Zeitfresser ist ganz klar dieser Programmteil. Von der Klarheit des Codes und Allgemeingültigkeit her ist Variante 1 aber auf jeden Fall zu bevorzugen,...

Mein Ziel ist es unter 1 Sekunde zu kommen (wohl hoffnungslos) was immer noch viel langsamer als das C++ ist das die eigentlichen Berechnungen macht. Bin schon am überlegen nach einem fertigen Prototyping auf C++ umzusteigen. Auslagern in C wird wohl nicht sooo viel an Performance bringen wie ich bräuchte zumal ich schon Numpy für die meisten Berechnungen verwende.

Vielleicht habt ihr ja noch irgendwelche klugen Ratschläge wie ich das Programm doch noch schneller bekomme.

[Zap]

Ich hoffe, dass ich dich richtig verstehe.
Du meinst also, in einer Schleife 4 mal eine Funktion "händisch" aufzurufen würde länger dauern als eine weitere Schleife mit 4 Durchläufen zu haben? Das bezweifle ich mal ganz stark.

Ich denke, dass man dir am besten helfen kann wenn du auch den Code zeigst der dir die Probleme bereitet.
Ansonsten gebe ich dir noch den tipp dir die profiling Mechanismen von python anzugucken. Damit kannst du rausfinden welche Funktionen wie oft aufgerufen werden und wie lange sie in Summe brauchen.

[Lufia]

Du meinst also, in einer Schleife 4 mal eine Funktion "händisch" aufzurufen würde länger dauern als eine weitere Schleife mit 4 Durchläufen zu haben? Das bezweifle ich mal ganz stark.

sorry das war unklar ausgedrückt, die verschachtelte Schleife braucht erheblich länger. Um die langsame Schleife zu finden habe ich profiling verwendet, evtl. kann ich aus den Log's noch mehr herauslesen.

[HerrHagen]

Ich glaub eher du hast numpy noch nicht richtig genutzt. Wenn du einfach numpy Funktionen in einer Schleife Aufrufst, wird die Sache kaum performanter als mit Verwendung "normaler" Python Funktionen.

Code: Alles auswählen

a = numpy.arange(1000000)
t = clock()
for i in a:
    x = math.sin(i)
print "math.sin:", clock() - t

t = clock()
for i in a:
    x = numpy.sin(i)
print "numpy.sin:", clock() - t

t = clock()
x = numpy.sin(a)
print "numpy.sin 2:", clock() - t

Code: Alles auswählen

math.sin: 0.636464829637
numpy.sin: 4.10226700117
numpy.sin 2: 0.0769128115267

Numpy ist nur dann performant (und erreicht dann auch mit C vergleichbare Geschwindigkeiten) wenn es in einem Stück auf einem Array arbeiten kann. Zeig doch mal deine konkrete Berechnung, vielleicht lässt sich ja noch was machen...

MFG HerrHagen

[BlackJack]

@Lufia: Habe ich dich falsch verstanden oder berechnest Du im ersten Fall in der inneren Schleife am Ende immer wieder und unnötigerweise Sachen die für alle Reifen je Auto gleich sind!? Falls ja -- lass das doch einfach und berechne das pro Auto nur einmal!?

[Lufia]

Danke für die Hilfe. Ich denke das Problem ist wie HerrHagen beschreibt das ich zwar für manche Operationen numpy verwende aber eben nicht so effizient da ich nicht über die Listen rennen kann.

Ich müsste es also so umschreiben das ich es über Listen laufen lassen kann. Da ich meine Berechnungen aber nicht einfach so aufdröseln kann bringt mir numpy von der Geschwindigkeit her wenig. Ich habe ein Objekt Element (ein Dreieck) an dem ich zuerst mal die Koordinaten speichere und dann die Geometrie (Kantenlänge, etc,) berechne was auch sehr schnell geht. Dann berechne ich die Flüsse zwischen den Knoten was sich aber nicht einfach über eine Matrix/Array ausdrücken lässt. Da ich Berechnungen in Abhängigkeit der Knotenwerte mache (eine Art fully upwinding) und erst das Potential abfragen muss und weitere Berechnungen mache. Ich kann mal schauen ob es sich doch irgendwie weiter vereinfachen lässt.

@BlackJack. Die erste Schleife würde über alle Autos gehen, die Zweite über alle Reifen die einen unterschiedlichen Luftdruck, Durchmesser, Temperatur, etc. haben. Ich berechne für alle Reifen mit meinen Gleichungen immer die selben Sachen nur das jeder Reifen eben andere Werte hat. Das Problem ist aber das zum Teil für die Berechnung eines Reifens eben auch Werte der anderen Reifen relevant sind und diese mit eingehen.

Dann muss ich wohl ctypes oder cython nehmen und die intensiven Teile auslagern oder versuchen es in Arrays und Matrizen zu packen was aber wohl nicht geht. Ich müsste um beim Beispiel von HerrHagen zu bleiben eine Funktion in numpy programmieren.

[BlackJack]

@Lufia: Das was Du am Anfang beschreibst kann so nicht sein. Wenn beide Varianten die selbe Anzahl von Autos und Reifen berechnen, dann kann es eigentlich keinen so grossen Geschwindigkeitsunterschied geben. "Loop unrolling" bringt nur signifikante Geschwindigkeitsvorteile bei Schleifen für den Code zum Kontrollfluss, also Test und Sprunganweisung einen wesentlichen Anteil an der Laufzeit der Schleife haben. Das kann man hier wohl ausschliessen.

[Lufia]

@Lufia: Das was Du am Anfang beschreibst kann so nicht sein. Wenn beide Varianten die selbe Anzahl von Autos und Reifen berechnen, dann kann es eigentlich keinen so grossen Geschwindigkeitsunterschied geben. "Loop unrolling" bringt nur signifikante Geschwindigkeitsvorteile bei Schleifen für den Code zum Kontrollfluss, also Test und Sprunganweisung einen wesentlichen Anteil an der Laufzeit der Schleife haben. Das kann man hier wohl ausschliessen.

Ich habe den Code leider gerade nicht da,.... werde morgen noch mal schauen woran es liegen könnte. Möglicherweise summiert sich das Ganze einfach auf weil die äußere Schleife ein paar tausend mal aufgerufen wird. Ich war auch etwas entsetzt weil man wenn man ähnlichen Code mit C/C++ schriebt ja nicht so einen deutlichen Einbruch spürt.

[Lufia]

So, jetzt musste ich grübeln, hier ein kleiner Test

Code: Alles auswählen

nAutos = 30000
a = 0
b = 0
c = 0
abc = [0,0,0]
d = [1.0,2.0,3.0]
d1 = 1.0
d2 = 2.0
d3 = 3.0
t = clock()

for i in xrange(nAutos):
    for j in xrange(3):
        abc[j] = d[j] + 12

print "Zwei Schleifen", clock() - t

t = clock()
for i in xrange(nAutos):
    a = d1 + 12
    b = d2 + 12
    c = d3 + 12

print "Einfache Schleife", clock() - t

Edit: hatte kleinen Fehler drinnen

[BlackJack]

@Lufia: Ich weiss nicht ob der Test wirklich so aussagekräftig ist. So wie es da steht ist die zweite Variante bei mir zwar fast 4½ mal schneller, aber das auch nur weil in der Schleife fast nichts gemacht wird und in der ersten Variante deutlich mehr als in der zweiten gemacht wird.

Wenn man mehr in beiden Schleifen macht -- ich habe jetzt einfach nur mal den Code in den innersten Schleifen jeweils nochmal kopiert, dann schrumpft der Vorteil schon auf nur etwas mehr als 2½ mal schneller. Und ich nehme mal an, dass Du in der Schleife mehr machst als drei Zahlen addieren!? Wenn ich den Code in beiden Schleifen verdreifache, dann ist die zweite Variante nur noch etwas unter 2 mal schneller.

Das Beispiel zeigt wo "loop unrolling" einen Vorteil bringt: "Enge" Schleifen in denen der Schleifencode von der Laufzeit her den Code innerhalb der Schleife dominiert.

Und der Code in der zweiten Variante ist deutlich einfacher. Die Zeile ``abc[j] = d[j] + 12`` in Bytecode:

Code: Alles auswählen

  2           0 LOAD_GLOBAL              0 (d)
              3 LOAD_GLOBAL              1 (j)
              6 BINARY_SUBSCR       
              7 LOAD_CONST               1 (12)
             10 BINARY_ADD          
             11 LOAD_GLOBAL              2 (abc)
             14 LOAD_GLOBAL              1 (j)
             17 STORE_SUBSCR

Im Gegensatz dazu ``a = d1 + 12``:

Code: Alles auswählen

  2           0 LOAD_GLOBAL              0 (d1)
              3 LOAD_CONST               1 (12)
              6 BINARY_ADD          
              7 STORE_GLOBAL             1 (a)

[Zap]

Der Vegleich ist nicht 100%ig fair, da du in einem Fall ja auf Indizes einer Liste zugreifst und im anderen Fall auf feste Namen.

Ich habe das Spielchen auch mal bei mir ausgeführt und könnte lediglich die Empfehlung geben die Scheifen zu drehen.
Also die Schleife mit der kleineren Anzahl an Iterationen außen und die andere innen.

Code: Alles auswählen

from time import clock

nAutos = 300000

def func_a(abc, d):
    for i in xrange(nAutos):
        for j in xrange(3):
            abc[j] = d[j] + 12

def func_b(abc, d):
    for i in xrange(nAutos):
        abc[0] = d[0] + 12
        abc[1] = d[1] + 12
        abc[2] = d[2] + 12

def func_c(abc, d):
    for j in xrange(3):
        for i in xrange(nAutos):        
            abc[j] = d[j] + 12   
    
for desc, func in (
    ("Eine Schleife", func_b),
    ("Zwei Schleifen", func_a),
    ("Zwei gedreht", func_c)
    ):
    t = clock()   
    func([0, 0, 0], [1.0, 2.0, 3.0])
    print desc, clock() - t

Code: Alles auswählen

Eine Schleife 0.267659508228
Zwei Schleifen 0.432062023268
Zwei gedreht 0.287988658746

[mkesper]

Dann berechne ich die Flüsse zwischen den Knoten was sich aber nicht einfach über eine Matrix/Array ausdrücken lässt. Da ich Berechnungen in Abhängigkeit der Knotenwerte mache (eine Art fully upwinding) und erst das Potential abfragen muss und weitere Berechnungen mache. Ich kann mal schauen ob es sich doch irgendwie weiter vereinfachen lässt.
...
Dann muss ich wohl ctypes oder cython nehmen und die intensiven Teile auslagern oder versuchen es in Arrays und Matrizen zu packen was aber wohl nicht geht. Ich müsste um beim Beispiel von HerrHagen zu bleiben eine Funktion in numpy programmieren.

Hmm, es scheint hier ja einige numpy-Cracks zu geben, vielleicht hat jemand eine Idee für einen brauchbaren Ansatz?

[Lufia]

Also ich habe es nun nach viel hin/her so hinbekommen das ich nur eine Schleife verwende indem ich die Werte zuvor zusammenfasse. Dadurch ist es schon mal deutlich schneller geworden. Ich werde nächste Woche weiter optimieren.