In mathematischen Algorithmus einarbeiten

[ZuseZ3]

Hallo erstmal,

ich arbeite gerade nebenbei daran, zwei mathematische Programme A und B zusammenzuführen.
Dabei verfolgt A einen neuen, effizienten Ansatz gewisse Zahlen zu berechnen, B ist genereller und zeigt allgemein einen neuen Weg für gewisse Algorithmen, um den Speicher effizienter zu nutzen.
A wurde bereits von mir effizient mit openMP parallelisiert, von 2-12 Kernen skaliert es linear, ebenso von 13-48 Kerne (4x12 core System).
Mathematisch spricht nichts dagegen, A und B zu vereinigen, beide liegen als C Code vor.
Praktisch ist B von einem Mathematiker geschrieben worden, anscheinend ohne auf entsprechende Programmierrichtlinien zu achten.
Ergo beinhaltet B eine größere Zahl von globalen Variablen, kryptische Bitmasks, Pointermagie,...
Dessen Dokumentation beschreibt das Ziel und das generelle Verfahren, leider nicht die konkrete Implementierung, welche zugegebenermaßen allerdings auch nur ein PoC Code ist.
Es handelt sich um grob 1k Zeilen.

Da ich mir ja einrede lernfähig/willig zu sein, wollte ich euch mal nach eurer Meinung fragen.
Wie geht man am besten damit um, gibt es gute Werkzeuge, um das ganze zu visualisieren/nen guten überblick zu bekommen?
Oder soll ich mich weiterhin oldschool mit Papier, Bleistift, Zahnstochern und Mate hinsetzen?
So, oder so, mein Ansatz wäre den Code erstmal umzustrukturieren vorm zusammenführen, aber bisher habe ich mich mit Refactoring nie beschäftigt.

 

[RalphS]

Mh... wenn ich das richtig herauslese, dann ist das Kernproblem jenes:

- Hast Du das Programm B verstanden? Weißt Du, was es tut und wie es das tut, mit Augenmerk auf den dokumentierten Ansprüchen?

Wenn ja, dann implementierst Du B ganz einfach neu. Bei maximal 1000 Codezeilen ist das auch nicht das ganz große Problem. Wie B das Problem ursprünglich angegangen ist, ist egal: was wichtig ist, ist daß bei Deiner Reimplementierung für jede Eingabe auch dieselbe Ausgabe herauskommt.

Was mich bei der ganzen Sache aber zögern läßt, ist genau der Anspruch von B, auf effiziente Speichernutzung optimiert sein zu sollen. Denn zB die Verwendung von globalen Variablen ist auf dem Speicher effizienter, ebenso wie die Übergabe byReference speicherfreundlicher ist als byValue. Aktuelle Software ist nicht speichereffizient und daran sind nicht zuletzt aktuelle Programmierparadigmen schuld - "macht aber nix", da Speicherplatz nicht annähernd eine so beschränkte Ressource ist wie früher. Außerdem gibt es durchaus andere Vorteile: Copy-on-write erfordert zB sehr viel mehr Speicher als in-place zu überschreiben, aber dafür kann copy-on-write den Schreibvorgang als Transaktion abbilden und im Zweifel den Ursprungszustand wiederherstellen.

Und Du hältst etwas hinter dem Berg in bezug darauf, was das (die) Programm(e) konkret tun oder tun sollen.

Ergo kannst Du B natürlich umschreiben, wie Du willst, läufst aber Gefahr, eben jenen Anspruch der effizienten Speichernutzung zu unterwandern einfach deswegen, weil Du B nach aktuellen Paradigmen umbaust.


Nur für den Fall, daß meine Grundannahme auch unzutreffend ist und Dir nicht ganz klar ist, was B überhaupt tun soll (und ggfs. wie): dazu befragst Du am Besten den Autoren von B.


Wenn Du allerdings auf der Suche nach Hinweisen sein solltest, wie B auf andere Eigenschaften zu optimieren sei - zB auf multicore --- dann müßtest Du ein paar mehr Infos rausrücken und konkreter werden: wie sieht B aus, wie ist es implementiert, und was exakt ist das angestrebte Ziel.

 

[new Account()]

Außerdem gibt es durchaus andere Vorteile: Copy-on-write erfordert zB sehr viel mehr Speicher als in-place zu überschreiben, aber dafür kann copy-on-write den Schreibvorgang als Transaktion abbilden und im Zweifel den Ursprungszustand wiederherstellen.

Man Kann auch ohne komplette Kopien anzufertigen Historie bauen.
Letztendlich eine Speicher/Geschwindigkeitsfrage.

Von konkret welchen Paradigmen redest du?
Objektorientierung als auch Funktionale Programmierung kostet passed eingesetzt in C++ 0.

Ergänzung (28. März 2019)

Wie geht man am besten damit um, gibt es gute Werkzeuge, um das ganze zu visualisieren/nen guten überblick zu bekommen?

Nimm ein Whiteboard, den Code und den Algorithmus und versuch die Funktionen und Datentypen top down zu matchen.
Wenns nicht klappt, Weil du es nicht überblicken kannst: refactoring bottom up
Ansonsten wenn Alle Stricken reißen, Oder es zu aufwensig wird, Wie gesagt Neuimplementieren geht immer.

 

[RalphS]

Man Kann auch ohne komplette Kopien anzufertigen Historie bauen.
Letztendlich eine Speicher/Geschwindigkeitsfrage.

Das ist mir schon klar, es war ein simples Beispiel zur Veranschaulichung. Gemäß TO ist sein "Programm B" bereits optimiert und ich wollte einfach herausstellen, daß er eben jenen Existenzzweck, nämlich die ursprünglich genannte "effiziente Speichernutzung", nicht ad absurdum führen soll. Dann wäre die Umsetzung von B nämlich wertlos.

 

[ZuseZ3]

Hi @RalphS , erstmal vielen Dank für die ausführliche Antwort.
Zuerst ein paar mehr Informationen zum Algorithmus, was sie genau tun.
Der Algorithmus A lässt sich unter anderem zur Primzahlenberechnung in gewissen Intervallen nutzen und arbeitet dazu selbst erstellte Subintervalle in unterschiedlichen größen ab.
Beschränken wir uns der einfachkeit halber mal darauf.
Algorithmus B zeigt, wie man Berechnungen innerhalb dieser Subintervalle so umstrukturieren kann, das der Cache dabei sinnvoll genutzt werden kann.

1. Mir ist leider nicht komplett bekannt, wie das Programm arbeitet.
Was es macht ist mir klar. Es ändert die Art und damit Reihenfolge, in der SubIntervalle bearbeitet werden.
Wie es das macht theoretisch auch. Allerdings nicht bei der konkreten Implementierung.
Beim verstehen verlangsamen mich da sachen wie interessant mehrfach verschachtelte Defines, Variablennamen wie oo und ooo und die oben genannten Punkte.
Die Mathematik dahinter ist für mich schon spannend genug, da hatte ich gehofft es gäbe entsprechende Programme, welche mir eine hübsche übersicht generieren.

2. Der große Punkt mit der Performance. An sich sind mir in vielen fällen die Vorteile von entsprechender herangehensweise bekannt. Auf einige Optimierungen kann man natürlich nicht verzichten, da dann selbst kleinere Testläufe den RAM sprengen/Tage dauern würden.
Umgekehrt glaube ich jedoch, dass einige Optimierungen die Berechnungen nur um einen kleinen Faktor, unabhängig von der Intervallgröße optimieren. Auf diese könnte ich vorrübergehend verzichten, um den vereinfachten Code dann in Ruhe zu verstehen, Memory dependencies zu entfernen, ihn mittels OpenMP zu parallelisieren, ihn mit dem anderen Algorithmus zusammenzuführen und zuletzt ggf GPUs einzubinden.
Am Ende kann ich dann ja ggf. die Rückwärtsersetzung durchführen um entsprechende Benchmarks zu machen.
Dabei ist der Algorithmus B auch im Sinne der O Notation vergleichsweise effizient. Ändert man den startpunkt von einem kleinen Testintervall bei gleicher Intervalllänge von 10^12 auf 10^18 steigt die Laufzeit um den Faktor 4 von 2.5 auf 10 Sekunden. Bei einer Version ohne entsprechende Umstrukturierung springt die Laufzeit um den Faktor 20 von 10 auf 200 Sekunden. Selbst wenn ich also Algorithmus B durchs vereinfachen um z.B. den Faktor 10 langsamer mache, dürfte das zusammenführen mit Algorithmus A diesen immer noch deutlich beschleunigen.

3. Author fragen. Der Kontakt zu ihm wurde mir tatsächlich hergestellt, allerdings weniger für so generelle Fragen.

An sich habe ich auch kein Problem damit, das weiterhin alles per Hand zu machen.
Allerdings habe ich mal am Rande mitbekommen, was die Softwaretechnik Abteilung an meiner Uni aus vermurcksten Vererbungshirarchien noch automatisiert an übersichten generieren kann.
Daher dachte ich, dass für einen vereinfachten Fall wie meinen schon genug Programme bereit stünden, die mir beim Verständnis helfen können. Um mich entsprechend vortzubilden hatte ich dh. einfach mal nachgefragt.

 

[Kanibal]

Ein Debugger hilft da möglicherweise. Programm laufen lassen für eine bestimmte Eingabe und step-by-step nachvollziehen, wo was passiert.

 

[Overprime]

Stell dem Autor doch kurz die Frage, ob er dir einen Programmablaufdiagramm bereitstellen kann. Eine grafische Aufarbeitung der Vorgänge kann eventuell einen Anteil der Magie entwirren und logische Zusammenhänge besser darstellen.

 

[Piak]

@ZuseZ3 : schreib mir doch mal ne pn, würde gerne mit dir ein wenig philosophieren.

Ich hab nen eigenen primzahlgenerator, biete derzeit 0,08s für 1 -1Mrd. auf nem doch recht unterdurchschnittlichen i5-6500. Na neugierig ?

Reden wir von "Tomás Oliveira e Silva's" bit bucket ? Den hab ich auch nicht überblickt, aber vielleicht ja zusammen.

@RalphS : ein paar der Grundsätze sind mir klar bezüglich Optimierung, gibts da ne kleine Liste, was heutzutage zwar als schick gilt, aber performance kostet, würde gerne mein programm gegenchecken.

 

[_killy_]

@Piak

Du möchtest philosophieren ... dann lies dir 1+1=10 Mathematik für Höhlenmenschen durch.1+1=10 Mathematik für Höhlenmenschen

 

[BeBur]

Würde einfach mal Dinge wie "C data flow analysis" in Google eingeben.
Da stößt man zumindest auf die Ansätze die intermediate Repräsentationen von gcc evtl. mal anzuschauen: GIMPLE und GENERIC.
Compiler sind ja smarte Dinger heute und machen viele Optimierungen und dafür müssen sie ja logischerweise entsprechend auch recht umfassende Analysen machen was datenfluss und Programmablauf angeht.

Oder das selbe Spielchen für LLVM.

 

[Ichthys]

Ich habemal so etwas ähnliches gehabt. Der erste Schritt zum Verständnis solcher Projekte ist tatsächlich, Schritt für Schritt mit einem Debugger durchgehen. Dann versteht man schjon eher, was da passiert. Außerdem würde ich während des Debuggens gleich mal den Variablen sprechendere Namen geben.

 

[Piak]

@_killy_ : nett gemeint, sicherlich kein schlechtes buch. Meine Anfrage war in diesem Fall fachlicher ausgerichtet.

ps. "fermats letzter satz" ist ein mega spannendes buch

 

[ZuseZ3]

Also, ums mal kurz zusammenzufassen.
Ich habe zugriff auf ein HPC Cluster, wo sehr viele Programme wie intel inspector/advisor/amplifier, ddt,... installiert sind und mal die beiden performancekritischten Teile analysiert sowie nach Datenabhähngigkeiten untersuchen lassen. Ich ersetze jetzt noch die ganzen mehrzeiligen Defines durch Funktionen, damit debugger und co besser damit zurecht kommen und versuche mich dann ganz praktisch an der parallelisierung.
Vlt. kommt das Verständnis ja durchs modifizieren.

 

[kuddlmuddl]

Schreib dir vorher automatisierte tests! Wenigstens ums komplette einmal drumrum
Besser noch um teilmengen (funktionen/module)