Haskell-Forum| vorherige Seite | 1 2 |
Gepostet: |
|||||||||||
Das ist beim Profiling rausgekommen....Mon Jul 02 13:57 2007 Time and Allocation Profiling Report (Final) Gruß, Rome |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
Hab dein Programm mal laufen lassen. Das Resultat war wie von dir beschrieben. Ein Blick in die Prozessliste brachte dann etwas Erleuchtung: Das Programm hatte eine Speicherauslastung von über 600MB.  Auf den ersten Blick in das Profiling-Protokoll liegt der Speicherverbraucht bei der Funktion Algorithm.resultOfMult. Aber ich werd mir den Code heute abend mal etwas genauer zu Gemüte führen. Viele Grüße, Siracusa |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| Hallo nochmal, zwei Stellen zum Optimieren hab ich gefunden, die laut Profiling sehr häufig durchlaufen werden: * In der Funktion Algorithmus.resultOfMult erzeugst du eine Teilliste nach folgendem Muster: [genericIndex p (i-1) | i<-[a..b] ]. Das ist bei langen Listen p und großen Abständen a..b sehr uneffizient. genericIndex geht nämlich für jeden Index von Anfang an die ganze Liste durch, bis die entsprechende Position gefunden ist, hat also linearen Aufwand. Hier würde ich mich nicht auf eine Optimierung vom Compiler zu einem konstanen Aufwand verlassen. Zusätzlich wird durch die list comprehension eine zusätzliche Liste der Indizes erzeugt, was überflüssig ist. Da du dir ja nur eine Teilliste aus der originalen Liste "herausschneidest", kannst du mittels take und drop direkt auf die zusammenhängende Originalliste zugreifen. Obiger Ausdruck läßt sich dann zum effizienteren genericTake (b-a) (genericDrop a p) umformen. * In der Funktion SignedDigit.shift werden u.U. große Links-/Rechts-Shifts in Einzelschritten ausgeführt. Hier könnte ich mir vorstellen, wäre ein ganzer Block-Shift mit nur einem Rekursionsaufruf ebenfalls effizienter. Beim Links-Shift ist das besonders einfach, da du nur die Kommastelle entsprechend ändern mußt. Beim Rechsshift müßte dann evtl. ein ganzer Block von 'Z'-Werten vorangestellt werden. Das Problem mit dem Speicherallokieren lösen diese Änderungen m.E. aber nicht. Ich hab mir das Speicherverhalten des Programms noch einmal angesehen. Der benötigte Speicher bleibt bis zum unerwarteten Ende des Programms relativ gering, bei mir unter 10MB. Dann, kurz nach dem Halten, explodiert der Speicherverbrauch plötzlich ins Extreme. Daher mag ich nicht so recht an die Schuld des Garbage Collectors glauben. Die letzte berechnete Stelle liegt kurz hinter 2^15. Vielleicht wird intern irgendein Maximalwert (für Listenlängen?) überschritten, der das Programm in eine Endlosschleife stürzt, was dann die rasante Speicherallokierung zur Folge hat. Überhaupt rechnet das Programm sehr ruckelig, hält immer wieder mal für mehrere Sekunden an, bevor es weiterrechnet. Kann ich mir auch nicht wirklich erklären, woran das liegt. Tritt das Problem eigentlich bei allen 3 Multiplikations-Algorithmen auf? Ich hab es nur mit der letzten versucht. Und versuch mal einen Durchlauf ohne die Compiler-Optimierung anzuschalten. Mehr Ideen hab ich dazu momentan leider auch nicht. Du könntest nur versuchen, den Kern des Problems durch sukzessives Rauswerfen von Quellcode zu lokalisieren. Viele Grüße, Siracusa |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| Servus, hab deine beiden Tipps ma umgesetzt, er scheint ein wenig schneller zu sein, hört aber genau an der gleichen Stelle auf 8/ . Ich, bzw mein Kumpel hatte noch die Idee, dass es vielleicht an der Rekursionstiefe liegen könnte, da er ja eigentlich den Speicher ne freigeben dürfte, solange er im rekursiven Aufruf steckt. Werde jetzt mal versuchen die Rekursion mittels /iterate/ aufzulösen. Habe grade was Interessantes festgestellt: Das Problem tritt beim naiven Algorithmus bereits an der Stelle 16392 bzw 16395 auf, genau dort, wo er bei den beiden anderen mittendrin auch kurz hängt, aber dann weiterrechnet. Ich poste mal die beiden Subroutinen für /Naive/ und /Karatsuba/ , den Schönhage-Strassen wird er denke noch ne verwenden, da ich den Turnoverpoint auf 8192 gesetzt habe, vorher wird dort auch /karatsuba/ benutzt. Weiter habe ich mal mit der Funktion /Algorithm.mult/ mal die Zahl /p = genericReplicate 40000 O/ , also 0.1111...., im Interpreter quadriert, er hat mir am Anfang auch brav nur Einsen ausgegeben, aber später dann Nullen, was eigentlich nicht sein darf. Die können eigentlich nur auftreten, wenn er in der Funktion /Algortihm.resultOfMult/ nicht mehr entsprechend auf die beiden Eingabeparamter zugreifen kann und daher diese mit Nullen auffüllt.... -- Dieses Modul dient der Multiplikation zweier Binärzahlen in SD-Darstellung. module Karatsuba( Also auch ohne Optimierungsoption hängt er an genau der gleichen Stelle... Gruß, Rome |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| Also, mein Kumpel hats mal unter Linux compiliert und folgendes festgestellt: 32779 : 1 1 ---32776--> 0 32780 : 1 0 ---32777--> -1 Main: Ix{Integer}.index: Index (32766) out of range ((0,32765)) Werde das morgen dann mal genauer unter die Lupe nehmen, hab trotzdem vielen dank für deine Mühe... Gruß, Rome |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| So, hab mal wieder was neues herausgefunden: Habe sämtliche Typen /Integer/ ind /Int/ umgeschrieben und nutze nun die normalen /Prelude/ Listenfuktionen anstelle der /generics/ . Bisher ist er bei über 36000.... mittlerweile bei über 100K.... Gruß Rome |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
Offensichtlich sind die generic-Funktionen für größere Datenmengen ungeeignet:Prelude> length [1..1000000] Mich würde mal die Speicherauslastung des Programms bei Stelle 100.000 interessieren, ist die durch die Ersetzung gesunken oder allokiert er immer noch gigantische Speichermengen? Viele Grüße, Siracusa |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| Soeben hat mein Programm die 200.000 Marike geknackt und die Speicherauslastung sieht wie am Anfang aus, es sind vielleicht nur sehr sehr wenige MB dazu gekommen, aber diese Explosion, wie zuvor, ist definitiv nicht eingetreten. Meine Windows-Auslagerungsdatei ist bei 368MB, mit sowas um den Dreh hat er heute Vormittag angefangen und rechnet immer noch brav weiter.... Gruß, Rome |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| Hab den Rechner über Nacht laufen lassen und er rechent immer noch, ist nu bei stelle 279500 und Auslagerungsdatei bei 408MB. Weiter hab ich das rausgefunden: Prelude> Data.List.foldl (+) 0 $ map (const 1) [1..1000000] :: Int *** Exception: stack overflow Prelude> Data.List.foldl' (+) 0 $ map (const 1) [1..1000000] :: Integer 1000000 Scheint wohl an dem fold zu liegen..... |
|||||||||||
| Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
| Ich hab glaube den Übeltäter: Weil i zu dumm zum testen war, hab ich anscheinend doch nur den Karatsuba getestet, weil ich heute nochmal alles von vorne quasi aufgebaut habe und beim karatsuba läufts auch mit integer durch..... Den Speicher verbraucht die FFT beim SchönhageStrassen, muss jetzt nur noch dort drin den Fehler finden.... Sry..... |
|||||||||||
| Zum Seitenanfang | |||||||||||
| vorherige Seite | 1 2 |