brute force und Rechenzeitverkürzung

[tian]

Uuuh, mit euren Tipps habe ich im Moment einen lauffähigen parallelen Code. THX, aber dazu später mehr...

Was Parallelisierung und Memory angeht:
Habe gestern eine 50 Elemente-Liste (10.272.278.170 Kombinationen) mit 8 Workern und 100.000er Chunks laufen lassen. Die ist aber nach ein paar Stunden mit 117 GB Memory an mein Limit gestoßen und abgeschmiert. Meine Zielmaschine wird knapp 100 Worker und 1 PB+ an memory haben, aber während der Entwicklung frage ich mich was dort zu optimieren sei.

Meine Prozesse haben ja keine Inter-Prozess-Kommunikation, und "nur" den ganzen MP-Overhead. Da denke ich sollte doch alles gut zu parallelisieren sein. Mit kleinen Testdatensätzen hatte ich zwischen 4 und 8 workern kaum einen Laufzeitgewinn festmachen können.

Ich habe Gedacht Problemgröße / Worker (hier: 10.272.278.170 / 8 Worker => chunk: 1.284.034.772) sollte doch ein guter Ansatz sein. Dann können die 8 Worker alle unabhängig voneinander rödeln. Da habe ich aber wohl irgendwas nicht bedacht.

Mich würde mal interessieren wie ich selbst ein smartes Verhältnis von Workern und Chunksize wähle.

Und wo verdammt kommt der Speicherbedarf her? :-O

[tian]

Ich werte 'res' im nachhinnein aus:

Code: Alles auswählen

# my little children
def process_index2(data, index):
    if   sum(int(data[idx][8]) for idx in index) > min_sum   and   sum(int(data[idx][2]) for idx in index) < max_total_price :
       return(index)
       
# send the children to work
with futures.ProcessPoolExecutor(max_workers=workers) as e:
        res = e.map(process_idx, result, chunksize=chunk_size)
        
# look what they've done
for r in res:
   if r:
    # stuff

Es würde helfen wenn 'res' kleiner wäre, da 90% der Rückgabewerte von 'process_index2' korrekterweise 'none' sind. ich glaube das 'if r:' ist noch langsamer als gleich 'res' nicht mit Millionen von 'none's zu füllen?!?

[__blackjack__]

@tian: Wieso haben die keine Interprozesskommunikation? Die Argumente werden zu den Prozessen übertragen (>60 Milliarden Listen-Elemente) und die Ergebnisse zurück zum Hauptprozess. Der sammelt die in einer Liste mit 10 Milliarden Einträgen. Also sind alleine die Zeiger auf die Elemente 280 Gigabyte gross. Die Daten auf die sie zeigen noch nicht mitgerechnet.

Wenn Du das mit 4 und 8 Workern getestet hast: Hast Du das auch mal *ohne* `multiprocessing` laufen lassen ob es *überhaupt* einen Vorteil bringt? Wenn die Funktion die da parallelisiert wird tatsächlich so simpel und kurz ist, wäre meine Vermutung der ganze Overhead ”wiegt” mehr.

Ich wiederhole das noch mal: Man sollte als erstes eine funktionierende, komplette Lösung ohne irgendwelche Parallelisierung haben. Nur dann kann man sinnvoll Laufzeiten von verschiedenen Lösungen vergleichen. Solange nicht *alles* mit *allen* Daten gemacht wird, weiss man nicht ob das Verhältnis zwischen Kommunikationsoverhead und paralleler Arbeit sinnvoll ist, beziehungsweise wie viel das überhaupt bringt.

[Qubit]

Mich würde mal interessieren wie ich selbst ein smartes Verhältnis von Workern und Chunksize wähle.

Und wo verdammt kommt der Speicherbedarf her? :-O

Das Optimieren von Multiprozess-Anwendungen ist eine "Kunst" für sich und lässt sich nicht pauschal sagen.
Wichtig ist, dass der Dispatcher (Executor) nicht mit sich selbst beschäftigt ist und die Core-Auslastungen ziemlich konstant sind.
Aus Gründen, die Blackjack schon erwähnt hat, wird so bisher viel im Speicher auf und ab rumgerödelt (GC) und die CPU-Auslastungen schwanken.
Da muss man sich ran tasten und eine stabile Konfiguration finden, die man dann mit dem Workload weiter optimieren kann.

Ich habe es mal mit "Slicen" des Result-Tupels probiert und bin so auf eine ziemlich konstante Speicherauslastung von nur ca. 70MB (!) gegenüber dem vorherigen Peak von 5GB(!) gekommen.
Das war mit derselben Konfiguration bei Datalängen von 30, 33 und 40 auch ziemlich stabil. Im letzten Falle war die CPU Prozess-Auslastung aber bei nur konstant 40% pro Prozess.
( siehe https://ibb.co/RDFYWf2 ) und die Ausführung hat ca. 17 min. gedauert. Die Abweichung zur meiner vorherigen Messung mit 30 Dataelementen war mit dieser Konfiguration gering, so ca. 2s länger.

Wieweit dir das letzten Endes Vorteile bringen kann, muss du dann schauen.
Du kannst das ja erstmal zum Nachspielen nehmen, bis du von den Python-Profis hier Tipps aus der Praxis bekommst.. Viel Spass

Code: Alles auswählen

from time import monotonic
from concurrent import futures
from itertools import combinations, islice
from functools import partial


def process_index(index):
    return index[0]+index[1]

def process_index2(data, index):
    return sum(data[idx]['x'] for idx in index)


if __name__=='__main__':

    start = monotonic()

    data = tuple({'x': i, 'y': str(i)} for i in range(40))  # 33 30

    result = combinations(range(len(data)), 10)

    process_idx = partial(process_index2, data)

    print("Start..")

    results = []

    with futures.ProcessPoolExecutor(max_workers=4) as e:
        while chunk := tuple(islice(result,40000)):
            res = e.map(process_idx, chunk, chunksize=10000)
            results.append(sum(res))

    print(f"Summe = {sum(results)}")

    ende = monotonic()
    print(f"Ende: {ende-start:.2f}s")

Code: Alles auswählen

Start..
Summe = 4356527175
Ende: 33.36s

Start..
Summe = 14809766400
Ende: 105.39s

Start..
Summe = 165293802960
Ende: 1034.09s

[tian]

Hab heute mal ein paar Graphen mit Cores vs. Chunks gemacht. Folgen noch...

Musste auch in meine Windows Umgebung umziehen Jupyter Notebook war zu instabil.

Wie misst du denn den Speicherbedarf? Ich schaue im Taskmanager bei Details auf maximalen Speicher im Python Prozess.

[narpfel]

@tian: Hast du mal eine Überschlagsrechnung gemacht, ob es überhaupt möglich ist, das Problem zu bruteforcen? Also allein schon größenordnungsmäßig?

Und gibt es einen speziellen Grund, warum du unbedingt eine Bruteforce-Lösung brauchst? Und dann auch noch in Python, das dafür nicht so besonders prädestiniert ist? Warum nicht einen effizienten Algorithmus implementieren (oder eine Implementierung benutzen, die schon existiert)?

[tian]

Wenn ich mein Problem mit Hardware erschlagen und mit einer 100 Item Liste umgehen kann wäre das gut genug.

Lt. meinem Mathematiker Kollegen gibt es keine optimale Lösung für das sog. Rucksack Problem, als alles zu probieren.

Python nehme ich, weil ich es einfach nebenbei wieder erlernen wollte. Das ist der Grund. Mein Studium ist lang genug her. Mein Skillset: Perl 20%, Python 10%, C 2%. ;-P

Mein Ziel: mit einer möglichst grossen Liste (100 Elemente) über Nacht (12h) das beste Ergebnis zu erzielen. Wenn ich mehr als 100 Kerne und mehr als 1PB Speicher benötige müsste ich vielleicht über MPI nachdenken. Aber das Thema will ich erst mal nicht aufmachen.

[__deets__]

Also mit Rust oder C++ sollten da mindestens eine, wenn nich zwei Groessenordnungen an Speicher einsparbar sein. Und damit wird es dann auch schneller, weil weniger cache-misses und was nicht. Da ist IMHO Python fehl am Platz. Ausser man kann das so stricken, dass die eigentliche Arbeit (Parallelisierung inklusive) in numpy oder sowas passiert, bei dem dann aber am Ende nur C/FORTRAN dahinter stehen.

[snafu]

Cython wäre noch eine Möglichkeit. Das bringt die Welt von C und die Welt von Python zusammen und führt, wenn man es richtig macht und das Problem "passend" ist, zu spürbaren Performance-Vorteilen.

Bezüglich meines Vorschlags, den ``knapsack_solver`` aus den ``ortools`` zu nutzen, habe ich übrigens nicht wirklich verstanden, warum das keine Option für dich darstellt...

[narpfel]

Ich bezweifle auch, dass alles durchprobieren wirklich nicht langsamer ist als eine DP-Lösung.

[Qubit]

Also mit Rust oder C++ sollten da mindestens eine, wenn nich zwei Groessenordnungen an Speicher einsparbar sein. Und damit wird es dann auch schneller, weil weniger cache-misses und was nicht. Da ist IMHO Python fehl am Platz. Ausser man kann das so stricken, dass die eigentliche Arbeit (Parallelisierung inklusive) in numpy oder sowas passiert, bei dem dann aber am Ende nur C/FORTRAN dahinter stehen.

Ja, wenn man mit großen Datenmengen arbeitet, dann sind Multiprozess-Lösungen (auf einer Maschine) nichts, da die Prozesse die Daten hin und her kopieren müssen. Und ein Prozess braucht am Besten die komplette Daten, um performant zu sein. Bei großen Listen etc. (kontinuierlichen Speicherbereichen) spielt einen da auch dann bei Python das Memory Management einen Streich, Python beschäftigt sich mit sich selbst, um den Speicher aufzuräumen (GC usw.). Man kann dann nur dafür sorgen, dass kleinere Chunks verarbeitet werden und der Speicher so sauber bleibt. Aber das gibt mit jedem Prozess auch wieder eine Performanceeinbusse wegen des Overheads, es müssen auch öfter Daten kopiert werden. Die Lösung ist da eigentlich (auf einer Maschine) Multithreading, aber das kann Python mit "PyObjects" nicht, wegen des GILs (Globaler Interpreter Lock).
So eine Semi-Lösung wären da Libs wie Numpy, die aussserhalb der "Pyobjects" agieren und selber thread-safe Konstrukte mitbringen. Die nutzen dann nur die Hooks, um sich ins Python zu integrieren.
Im allgemeinen nutzt man bei diesen Problemen da wohl mit Python eher ein scale-out (die Python-Fachleute mögen mich hier aber auch korrigieren), um sowas auf mehreren Maschinen zu erledigen. Glaube "Dask" kann das, aber habe da mit Python zu wenig Erfahrung..

[Sirius3]

Solche simplen Probleme löst man heutzutage mit GPU da hast du dann gleich ein paar tausend Cores.
Mit numba lässt sich das ganze dann auch noch in Python-Syntax programmieren.

Generell versucht man große Probleme in kleinere unabhängige aufzuspalten. Es macht keinen Sinn, jedem Prozess ein Minihäppchen zu geben und alle Ergebnisse zu sammeln.
Rucksackprobleme löst man z.B. mit Simulated Annealing, da hat man dann nach einer festgelegten Zeit ein fast optimales Ergebnis, was normalerweise völlig ausreichend ist, wenn nun als Alternative das perfekte Ergebnis erst in 10^x Jahren hat.