Boost Histogram sehr langsam - was mache ich falsch?


  • Gesperrt

    Hallo,

    Ich bin daran eine Histogramm-Plotter-Feature zu implementieren und versuche bisher dazu Boost.Histogram zu verwenden.

    Der erste Fehler den ich bemerkte war, dass die Flächen ausgegeben werden und nicht die Höhe der Balken. Da die Flächen der Balken immer < 1 sind, brauchte ich eine Weile es zu bemerken, da dann die Flächen immer kleiner als die Seitenlängen sind (z.B. 0.50.5=0.250.5 \cdot 0.5 = 0.25).

    Minimales Beispiel zur eigentlichen Frage:

    void CalcHistogram(std::vector<float>& data, unsigned int number_bins, float lower_limit, float upper_limit)
    {
    	const auto axis = histogram::axis::regular<>(number_bins, lower_limit, upper_limit);
    	auto histogram = histogram::make_histogram(axis);
    	const float weight_value = static_cast<float>(1) / static_cast<float>(data.size());
    	histogram.fill(data, histogram::weight(weight_value));
    }
    

    Also ohne den Aufruf von histogram.fill() läuft das Programm stabil bei 240 FPS, mit diesem Aufruf fällt es nach ein paar Sekunden auf 34 FPS ab. Das ganze Programm ist viel grösser, aber der Perfomance Profiler (für CPU-Usage) gibt bei der erwähnten Zeile 6: 6541 (83.20%) aus.

    Also ich denke so langsam sollte eigentlich nicht sein, siehe Boost.Histogram Benchmark.

    Ich wollte fragen ob jemand weiss woran es liegen könnte ❔ ❔ ❔

    Edit: Inzwischen glaube ich, dass der Grund an der Grösse des vector liegt. Als ich const size_t sample_size = 100000; zu const size_t sample_size = 1000; änderte, beanspruchte eine andere Funktion mit einer Schleife im Render-Loop mit ebenfalls 1000 Iterationen am meisten CPU-(i7-9750H)-Usage.



  • Naja, 100.000 Fill-Operationen sind schon eine Menge.
    Nur mal als Vergleich: mit ROOT und einem TH1D mit 100 Bins von 0 bis 100 brauche ich sowas wie 900us (i7-4790K).

    Testcode:

    TH1D h("h", "h", 100, 0, 100);
    for (int j=1; j < 100; ++j) {
       auto s = high_resolution_clock::now();
       for (int i = 0; i < 100000; ++i) h.Fill(i & 63);
       auto e=high_resolution_clock::now();
       cout << duration_cast<microseconds>(e-s).count() << '\n';
    }
    

    Wie schnell muss es denn bei dir sein? Wie viele Bins hast du? Kannst du das Weight nachträglich reinrechnen, sodass man nur am Ende 1x multiplizieren muss (oder ist das fill mit dem weight-Argument da klug genug?).


  • Gesperrt

    @wob sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    900us

    sind das all 0.9 ms (Millisekunden), das wären dann glaube ich 1111 FPS oder Hz.

    @wob sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    Kannst du das Weight nachträglich reinrechnen, sodass man nur am Ende 1x multiplizieren muss (oder ist das fill mit dem weight-Argument da klug genug?).

    Also am Ende ergeben die Flächen (was den relativen Häufigkeiten entspricht) aller Balken/bins 1 (was der Fläche unter einer Dichtekurve einer Wahrscheinlichkeitsverteilung entspricht), ohne weight-Argument zählt es die absoluten Häufigkeiten. Um die Balkenhöhe zu berechnen, kann die Fläche durch die Balkenbreite dividiert werden.

    @wob sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    Naja, 100.000 Fill-Operationen sind schon eine Menge.

    https://math.stackexchange.com/... (Below is a histogram of the one million sample means) der Plot zeigt eine Dichtekurve und ein Histogramm (und eine Mittellinie 😀 ). Ich habe vor mit Zufallszahlen Ergebnisse von Stichprobenfunktionen visuell zu überprüfen. Aber soweit ich mich erinnere, braucht es sehr eine sehr grosse Stichprobenanzahl, damit die Balken dann so genau der Dichtekurve entsprechen.

    @wob sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    Wie schnell muss es denn bei dir sein?

    Also im Moment befindet es sich im Render-Loop. Da die Achsen eingestellt werden können und der Plot auch verschoben (und auch gezoomt) werden können soll.

    @wob sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    Wie viele Bins hast du?

    Falls ich irgendwann dann fertig werde, kann die Anzahl per ImGui gewählt werden (screenshot).



  • Ich glaube dass du hier für Flexibilität bezahlst die du nicht brauchst. Unterstützung mehrerer Dimensionen, automatischers Upgrade von 1 Byte pro Bin zu 2 zu 4 etc.

    Kannst du statt dessen nicht einfach einen vector verwenden und die Bin-Nummer selbst berechnen?


  • Gesperrt

    @hustbaer sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    Ich glaube dass du hier für Flexibilität bezahlst die du nicht brauchst.

    Ich denke auch dass es qualitativ gut ist und bereits fertig.

    Also im Beispiel oben wird zuerst die Achse berechnet und diese Berechnung ist eigentlich die einzige die im Render-Loop dynamisch bleiben soll. Die Fill-Operation muss eigentlich nicht im Render-Loop sein, wenn die Achsen nach der Fill-Operation neu berechnet werden könnten.

    @hustbaer sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    Kannst du statt dessen nicht einfach einen vector verwenden und die Bin-Nummer selbst berechnen?

    Daran dachte ich auch schon und habe auch schon vor dazu zu wechseln. std::sort(data.begin(), data.end()); Sortiert habe ich es schon und dachte dann, dass wenn eine bin Grenze erreicht wird, der Vergleichswert zum nächsten bin inkrementiert, anstatt jeden Wert auf jeweils alle bin-Grenzen zu testen.



  • Warum wird denn überhaupt ständig neu berechnet und gezeichnet? Malt man das einmal auf ne Textur und zeigt die an, gibts ja sicher kein Problem. Man hat ja sicher nicht 240 mal pro Sekunden 100000 neue Messwerte und falls doch kann die niemand so schnell ablesen und eine Echtzeitanzeige is ehh unnuetz.


  • Gesperrt

    @TGGC sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    Malt man das einmal auf ne Textur und zeigt die an, gibts ja sicher kein Problem.

    @titan99_ sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    Da die Achsen eingestellt werden können und der Plot auch verschoben (und auch gezoomt) werden können soll.

    @TGGC sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    Man hat ja sicher nicht 240 mal pro Sekunden 100000 neue Messwerte

    @titan99_ sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    Also im Beispiel oben wird zuerst die Achse berechnet und diese Berechnung ist eigentlich die einzige die im Render-Loop dynamisch bleiben soll. Die Fill-Operation muss eigentlich nicht im Render-Loop sein, wenn die Achsen nach der Fill-Operation neu berechnet werden könnten.

    @TGGC sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    eine Echtzeitanzeige is ehh unnuetz.

    Ich finde für diesen Zweck ist es nicht unbedingt nötig. Aber ich finde es hat auch Vorteile. Sollen Eingabewerte geändert werden, wird das Ergebnis umgehend angezeigt. Wenn z.B. ein R-Script geändert wird, dauert es länger, bis das Ergebnis als Plot angezeigt wird.

    Zudem habe ich zuvor schon ein paar C++-Plot-Libraries angeschaut, z.B.

    Ich bin am überlegen nur jeweils Funktionen aufzurufen, wenn sich Funktionsargumente geändert haben. Gibt es dazu Konzepte?



  • @titan99_

    Daran dachte ich auch schon und habe auch schon vor dazu zu wechseln. std::sort(data.begin(), data.end()); Sortiert habe ich es schon und dachte dann, dass wenn eine bin Grenze erreicht wird, der Vergleichswert zum nächsten bin inkrementiert, anstatt jeden Wert auf jeweils alle bin-Grenzen zu testen.

    Ähm. Dividieren? Bzw. bei Gleitkomma: Multiplizieren und dann in nen Integer konvertieren?


  • Gesperrt

    @hustbaer Wo? Also 1 durch die vector-Grösse (einmal von size_t in float casten) dividieren, um die relativen Häufigkeiten zu berechnen und nicht die absoluten Häufigkeiten.

    Dann sortieren und in aufsteigender Reihenfolge die bins mit dem errechneten Wert inkrementieren. Die Werte der bins entsprechen dann ihrer Fläche und müssen nur noch durch die bin-Breite dividiert werden um auch die bin-Höhe zu haben, um die bins rendern zu können.

    Aber ich habe mich trotzdem dazu entschieden mit Boost.Histogram weiterzumachen. Es gibt noch Optimierungsmöglichkeiten (z.B. Multithreading), die Programmbibliothek wird weiterentwickelt, als Release erstellt ist der FPS-Verlust geringer. Und ich denke der Grund für die CPU-Beanspruchung beim Fill lag an der Grösse der Daten.

    Mir helfen die Antworten, da auf die Frage eingegangen wurde 🙂 Danke für die Antworten.

    @titan99_ sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    Ich bin am überlegen nur jeweils Funktionen aufzurufen, wenn sich Funktionsargumente geändert haben. Gibt es dazu Konzepte?

    Ist wohl OT.



  • @titan99_ sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    @hustbaer Wo? (...)
    Dann sortieren und in aufsteigender Reihenfolge die bins mit dem errechneten Wert inkrementieren.

    Dort. Um zu berechnen in welchen Bin ein Wert gehen soll musst du nichts sortieren. Einfach den Min-Wert des ersten Bins abziehen, dann mit der Bin-Breite multiplizieren und in einen Integer verwandeln. Clamp auf max. Bin-Nummer und dan vec[bin]++ und total++.



  • @hustbaer Bist du sicher, dass das nicht in boost::histogram genauso gehandhabt wird? Ich meine, das ist ja eine regular_axis, was soll man da anders machen? Sicher, vielleicht gibts irgendeinen kleinen Einmal-Overhead. Aber im Wesentlichen wird das fill doch auch nicht anders sein. Wieso sollte man für Unterstützung mehrerer Dimentsionen etc. zahlen? Laut Doku gibt es beste Performance, wenn man histogram::make_histogram(axis); macht, weil dann schon zur Compilezeit feststeht, dass es genau eine (bzw. n) Achse(n) gibt. Ich kann mir nicht vorstellen, dass man da händisch viel einsparen kann (selbst wenn es 10% sein sollten, hilft das weiter?).
    Ich frage mich ernsthaft viel mehr, was hier genau gemacht wird, dass man so häufig so ein Histogram berechnen muss. Ja, Histogram füllen sollte so schnell wie möglich sein, aber ich frage mich auch andere Dinge. Wie zum Beispiel: ist der Daten-vector wirklich nötig? Wenn die Daten doch eh x-mal pro Sekunden neu erzeugt und weggeschmissen werden, könnte man sie ggf. auch direkt in ein Histogram füllen. Und dann noch der Punkt: kann man ggf. gezielt Daten an den Stellen erzeugen, wo die Änderung am größten ist? (dann muss man natürlich mit den Gewichten aufpassen, aber ggf. reichen viel weniger als 100k Events aus).



  • @wob
    Vermutlich macht Boost.Histogram das so, ja. Würde ich zumindest hoffen. Mein Beitrag war die Antwort auf den von @titan99_ wo er was vonwegen sortieren geschrieben hat -- was halt nicht nötig ist. Wenn die Daten von sich aus schon sortiert sind ist das natürlich Cache-freundlich und alles. Aber wenn man sie dazu erstmal sortieren muss, dann zahlt man dort halt die Cache-Misses -- macht IMO also keinen Sinn zu sortieren.

    Wie zum Beispiel: ist der Daten-vector wirklich nötig? Wenn die Daten doch eh x-mal pro Sekunden neu erzeugt und weggeschmissen werden, könnte man sie ggf. auch direkt in ein Histogram füllen.

    Wenn du oft fill aufrufst, dann zahlst du bei Boost.Histogram mit dem "Default Storage" auf jeden Fall auch oft für die Fallunterscheidung welcher Storage aktuell gerade verwendet wird (1 Byte pro Zelle, 2 Bytes etc.).

    Und egal wie oft man fill aufruft zahlt man mit "Default Storage" für den Overflow-Check.

    In Summe beides vermutlich immer noch nicht viel das stimmt schon.

    Mein ursprünglicher Punkt war einfach: Wenn ein mächtiges Teil wie Boost.Histogram schlechte Performance liefert, man aber bloss einen vector<int> + ein paar Zeilen eigenen Code braucht, wieso dann lange auf die Suche gehen was das Problem mit Boost.Histogram ist? Da schreib ich persönlich lieber die paar Zeilen eigenen Code.


  • Gesperrt

    @wob sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    Wenn die Daten doch eh x-mal pro Sekunden neu erzeugt und weggeschmissen werden, könnte man sie ggf. auch direkt in ein Histogram füllen.

    Die Daten werden nicht im Render-Loop erzeugt, aber die Achse wird durch Verschieben oder durch Änderungen der Achsengrenzen im Render-Loop neu berechnet. Und soweit ich es bisher verstehe, muss die Achse vor dem Fill definiert werden.

    @hustbaer sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    Und egal wie oft man fill aufruft zahlt man mit "Default Storage" für den Overflow-Check.

    Ich habe auch schon versucht anstelle von "Default Storage" einen vector zu verwenden, bemerkte aber keinen wesentlichen Unterschied.



  • @hustbaer sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    Wenn du oft fill aufrufst, dann zahlst du bei Boost.Histogram mit dem "Default Storage" auf jeden Fall auch oft für die Fallunterscheidung welcher Storage aktuell gerade verwendet wird (1 Byte pro Zelle, 2 Bytes etc.).

    Machst du halt auto hist = make_histogram_with(std::vector<double>(), axis);

    Und egal wie oft man fill aufruft zahlt man mit "Default Storage" für den Overflow-Check.

    In ROOT war (ist?) lange der Default ein TH1F (1d Hist mit Float_t), wenn man im TBrowser doppelklickt. Irgendwann habe ich mich gewundert, warum die Daten an einer Stelle so glatt aussehen. Stellte sich heraus, dass es an float lag, den f += 1 ergibt eher als man denkt wieder f / (Hist.Precision.1D: double in der .rootrc ist die Abhilfe, falls hier jemand ROOT nutzt). Daher: Overflow-Checks sind schon nett 🙂

    Außerdem tracken Histogramm-Klassen normalerweise noch die Over- und Underflows und auch die quadratischen Gewichtssummen pro Bin (Sumw2 in ROOT), um später Unsicherheiten bestimmen zu können. Gut, ist ggf. hier unnötig.

    In Summe beides vermutlich immer noch nicht viel das stimmt schon.

    Mein ursprünglicher Punkt war einfach: Wenn ein mächtiges Teil wie Boost.Histogram schlechte Performance liefert, man aber bloss einen vector<int> + ein paar Zeilen eigenen Code braucht, wieso dann lange auf die Suche gehen was das Problem mit Boost.Histogram ist? Da schreib ich persönlich lieber die paar Zeilen eigenen Code.

    Wenn eine 3rd-Pary Library aus Boost behauptet, sehr schnell zu sein und das auch im Vergleich zu anderen Libraries einhält, gehe ich nicht als erstes davon aus, dass diese mein Geschwindigkeitshauptproblem ist. Zumal du dir bei einer eigenen Lösung ja auch Gedanken um Daten im Under- und Overflowbin machen solltest... Häufig muss du dann noch hier oder dort einen Spezialfall einbauen etc.



  • @titan99_ sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    Die Daten werden nicht im Render-Loop erzeugt, aber die Achse wird durch Verschieben oder durch Änderungen der Achsengrenzen im Render-Loop neu berechnet. Und soweit ich es bisher verstehe, muss die Achse vor dem Fill definiert werden.

    Jein (also technisch schon)! Mach einfach ein sehr feines Binning und mach dann innerhalb der Loop einfach ein Rebinning je nach Anforderung!


  • Gesperrt

    @hustbaer sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    vec[bin]++ und total++.

    Prefer ++i to i++

    Also ++vec[bin] und ++total, finde ich auch angenehmer zum lesen.

    Edit: Quick C++ Benchmark, ich weiss nicht mehr was stimmt.



  • @titan99_
    Wenn du erstmal die 100.000 Pixel auf eine Textur gezeichnet hast, dann kannst du die danach beliebig zoomen und verschieben, das kostet nichts mehr zur Laufzeit. Und nachdem sich die Eingabewerte ändern (was sehr langsam passiert, weil jemand muss da was eingeben), setzt du ein Dirty Flag und aktualisierst bei nächstes Gelegenheit. Da braucht man immer noch keine 240fps, niemand gibt so schnell was ein.



  • @titan99_ Mir ist die x++ vs. ++x Geschichte bekannt, danke. Ich denke auch dass ich sie besser verstehe als du, denn mich wundert das Ergebnis deines Benchmarks gar nicht.
    x++ vs. ++x ist völlig uninteressant bei eingebauten Typen, speziell wenn man den Wert des Ausdrucks nicht verwendet.

    Bei sowas wie BigInt Klassen ist es dagegen gar nicht egal - selbst wenn man den Wert des Ausdrucks nicht verwendet. Bei manchen Iteratoren ebenso, wobei hier auch viel übertrieben wird. Wenn man "checked iterators" hat ist i++ merklich teurer, ja. Ansonsten mit den meisten Iterator-Klassen eher nicht.



  • @wob sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    Wenn eine 3rd-Pary Library aus Boost behauptet, sehr schnell zu sein und das auch im Vergleich zu anderen Libraries einhält, gehe ich nicht als erstes davon aus, dass diese mein Geschwindigkeitshauptproblem ist.

    Es kommt auch immer drauf an was man braucht/erreichen will. Wenn ich bloss ein einfaches 1D Histrogramm brauche wo alle Gewichte gleich sind etc., dann nehm ich einen vector<int> bevor ich mich mit Libraries rumschlage. Ganz egal was jetzt das Problem ist - also ob die Library langsam ist oder ich sie nur falsch verwende. Zeit geht auf jeden Fall dabei drauf.

    Aber ihr dürft das alle machen wie ihr wollt.



  • @hustbaer sagte in Boost Histogram sehr langsam - was mache ich falsch?:

    Aber ihr dürft das alle machen wie ihr wollt.

    Natürlich. Vielleicht bin ich auch geschädigt, weil ich jahrelang Histogramme gefüllt, gemalt, skaliert, gefittet etc. habe. Da ist mir nie in den Sinn gekommen, statt TH1D einen std::vector<double> zu nehmen. Aber klar, hängt sicher erheblich vom Problem ab. Ich habe in der Zeit auch tatsächlich nie ein Histogramm mit int-Bins benutzt. Ich habe sicher viel mehr 1d-Histogramm-Objekte erzeugt als std::vector-Objekte (sogar möglicherweise std::vector<TH1*> - viele Histos, 1 vector). Und irgendwann überlegt man auch gar nicht mehr, ob ein anderer Datentyp als der bekannte Histogramm-Typ überhaupt in Frage kommt.

    dann nehm ich einen vector<int> bevor ich mich mit Libraries rumschlage

    Daher war es für mich bei dem Begriff "Histogramm" andersrum klar: Standard-Histogramm-Datentyp nehmen, bevor ich mich mit std::vector rumschlage und überlegen muss.


Anmelden zum Antworten