Effinzienteste Art eine Map voller Vektoren zu transformieren



  • Habe das Problem, dass ich über eine Map von Laserpunkten (Kartesische Koordinaten) laufen muss und jeden dieser Punkte der gleichen Transformation unterziehen muss (nur x und y Koordinate). Die Map besteht aus 5 Einträgen und jeder mapped-type hat dann ein paar tausend Einträge, von denen jeder aus x-, y-, und z-Koordinaten besteht. Ich habe das wie folge gelöst, allerdings ist das Ganze inakzeptabel langsam. Habt ihr vielleicht eine Idee, wie man das Ganze effizienter machen kann? Habe kein C++17 zur Verfügung um das zu parallelisieren

    std::map<std::string, std::vector<std::vector<float>>> pointCloudsTransformed;
    
    float Xvalue = 5;
    float yValue = 10;
    float Phi = 0.5f;
    
    // 5 mapped types, jeder davon ein paar tausend Einträge mit jeweils 3 Koordinaten
    std::map<std::string, std::vector<std::vector<float>>> pointClouds; 
    
      for (auto const& cloud : pointClouds) {
    
          pointCloudsTransformed_[cloud.first].resize(cloud.second.size());
    
          for (auto const& point : cloud.second)
            std::transform(cloud.second.cbegin(), cloud.second.cend(),
                           pointCloudsTransformed[cloud.first].begin(),
                           [&](std::vector<float> point) -> std::vector<float> {
                             auto xyPair = transformCoordSystem(point.at(0), point.at(1), Phi, Xvalue, YValue);
                             return {xyPair.first, xyPair.second, point.at(2)};
                           });
    
          // copy funktioniert schnell
          //      std::copy(cloud.second.cbegin(), cloud.second.cend(),
          //                pointClouds_[cloud.first].begin());
        }
    

    Die Transformationsfunktion sieht so aus

    std::pair<float, float> transformCoordSystem(float x,
                                                 float y,
                                                 float rot,
                                                 float transX,
                                                 float transY) {
      double c{cos(rot)}, s{sin(rot)};
        return {(c * x + s * y) - transX, (-s * x + c * y) - transY};
    


  • Am besten benutzt du einen Profiler um herauszufinden, wo die meiste CPU Zeit verbraten wird. Auf den ersten Blick fällt mir nur auf, dass du dem Lambda den vector per value übergibst und die at Methode benutzt statt den Indexoperator. Und ist es richtig, dass dein Lambda immer einen 1-elementigen vector zurückgibt?
    Man kann auch ohne C++17 parallelisieren, dann musste das halt von Hand (zB mit std::async ) machen.



  • Ganz offensichtlich kannst du zumindest mal einen map-Lookup wegoptimieren.

    auto &newCloud = pointCloudsTransformed_[cloud.first];
    newCloud.resize(cloud.second.size());
    ...
    newCloud.begin()
    

    Dann frage ich mich natürlich: brauchst du wirklich einen vector<vector<>>? Ist denn deine Dimension variabel groß oder könnte man auch ein festes Array oder gar eine struct Point{float x,y,z(,t);}; nehmen?

    Dann: sin und cos sind langsame Operationen. Warum berechnest du sie jedes Mal neu? Phi scheint doch konstant zu sein?

    Und Standardfrage: sind Optimierungen an?



  • Danke Euch, ich werde den Code dahingehend optimieren.

    was meinst du mit "sind optimierungen an" ?



  • Übersetzt du im Release-Modus und hast in den Projektoptionen alle Optimierungen aktiviert?



  • Benutzte QtCreator und baue im Release, bei den anderen Optimierungen bin ich mir nicht sicher.

    Gibt es denn nicht vielleicht einen effizienteren Weg um die Transformation durchzuführen?



  • DocShoe schrieb:

    Am besten benutzt du einen Profiler um herauszufinden, wo die meiste CPU Zeit verbraten wird. Auf den ersten Blick fällt mir nur auf, dass du dem Lambda den vector per value übergibst und die at Methode benutzt statt den Indexoperator. Und ist es richtig, dass dein Lambda immer einen 1-elementigen vector zurückgibt?
    Man kann auch ohne C++17 parallelisieren, dann musste das halt von Hand (zB mit std::async ) machen.

    Wieso ein-elementig? Ich brace-initialize doch nen std::vector<float> mit drei floats im return?



  • Ah, ok. Ich benutze wenig bis kein C++11 und habe das wohl übersehen.

    Mir fällt auf dass du keinen Point3D Datentyp hast und die Koordinaten offensichtlich in einem vector<float> speicherst. Das wäre zuerst mal mein Ansatz, nämlich vernünftige Datenstrukturen zu entwerfen. Oder wenigstens std::tuple<float,float,float> für einen Punkt im Koordinatensystem zu benutzen. std::tuple hat den Vorteil, seine Daten auf dem Stack zu erzeugen, während vector seine Elemente auf dem Heap anlegt, was deutlich langsamer ist.



  • Ist das der gleiche Grund warum std::array schneller ist als std::vector? vorausgesetzt man kennt die container größe im Vorhinein

    Und wie verhält es sich mit dem Unterschied er Geschwindigkeit bei [] vs. at()?
    Der boundary check bei at() muss doch was kosten oder?



  • Ja und ja. Der Indexoperator ist schneller, weil er keine Gültigkeitsüberprüfung macht.


  • Mod

    Dinge die mir auffallen:

    • Du implementierst ein Tupel (von Koordinaten) mittels eines vector s!?
    • Du verwendest eine map . Da Du sie aber quasi ausschließlich für Zugriffe bereitstellst, wäre eine Hashmap ( unordered_map ) effizienter. Spielt hier aber vermutlich keine Rolle.
    • In jedem Schleifendurchlauf wird der Sinus und Kosinus von Phi berechnet. Ich gehe davon aus, dass ein Compiler so etwas i.d.R. hoisten kann (siehe den nächsten Punkt), aber Du solltest es trotzdem selbst optimieren.
    • Macht den vorigen Punkt umso gewichtiger: Deine "Konstanten" sind nicht const ! Das heißt, dass sie vom Closure tatsächlich per reference gecaptured werden, und im schlimmsten Fall noch eine Indirektion dazukommt. Der Compiler kann weder constant propagation noch folding durchführen, weil die Variablen external linkage haben, und daher die Möglichkeit besteht, dass sie von anderen TUs aus verändert werden. Bspw. könnte innerhalb des Lambdas der Sinus schon zur Compilezeit einfach durch eine Konstante ersetzt werden.
    • Ich verstehe Deinen Code nicht;
    for (auto const& point : cloud.second)
            std::transform(cloud.second.cbegin(), cloud.second.cend(),
                           pointCloudsTransformed[cloud.first].begin(),
                           [&](std::vector<float> point) -> std::vector<float> {
                             auto xyPair = transformCoordSystem(point.at(0), point.at(1), Phi, Xvalue, YValue);
                             return {xyPair.first, xyPair.second, point.at(2)};
                           });
    

    Hier iterierst du über alle Koordinaten-Tripel in einem Eintrag der Map, und fügst für jedes Tripel tausende Einträge in die Zielmap ein, die alle identisch sind. Die Schleife ist ein Tippfehler? 😕 Warum nicht einfach eine for Schleife?

    auto& vec = pointCloudsTransformed[cloud.first];
    for (auto point : cloud.second) {
      auto xyPair = transformCoordSystem(point.x, point.y, phiSin, phiCos, Xvalue, YValue);
      vec.emplace_back(xyPair.first, xyPair.second, point.z);
    }
    

    DocShoe schrieb:

    std::tuple hat den Vorteil, seine Daten auf dem Stack zu erzeugen, während vector seine Elemente auf dem Heap anlegt, was deutlich langsamer ist.

    Das ist ziemlich leicht misszuverstehen, IMO. tuple hält Elemente in-place, i.e. in dem Speicher, der für das tuple selbst alloziert wurde. Damit vermeidet man den Overhead einer zusätzlichen Indirektion.

    Edit: Und, wie bereits erwähnt, ist auch C++14 in der Lage, deinen Code zu parallelisieren. Da die Transformation keine Interdependenzen aufweist, könntest Du sie einfach in zwei Hälften durchführen, von denen eine mittels async in einen anderen Thread verlagert wird. Du kannst auch probieren, SSE einzubringen.



  • DocShoe schrieb:

    Ja und ja. Der Indexoperator ist schneller, weil er keine Gültigkeitsüberprüfung macht.

    Wobei das .at() bei mir bislang noch nie messbar war. Aber wenn du stattdessen einen Point-Struct nimmst, ist das eh überflüssig.


  • Mod

    wob schrieb:

    DocShoe schrieb:

    Ja und ja. Der Indexoperator ist schneller, weil er keine Gültigkeitsüberprüfung macht.

    Wobei das .at() bei mir bislang noch nie messbar war.

    Sicher, dass der Compiler das nicht einfach optimiert hat? Wäre nicht ungeheuer schwer festzustellen, dass eine Laufvariable ihr Interval nicht verlässt. Oder eben doch, aber nicht in deinem Test.



  • Danke vielmals für eure Hilfe!

    Ja das war nen Typ und hauptursache warum es so langsam war -.-

    gibt es eine richtlinie, wann man custom structs und wann stl container verwenden soll?

    Ist die for loop von dir schneller alas std::transform hier?

    Deinen vierten punkt verstehe ich nicht ganz. Könntest du den erläutern bitte?

    Ich hab jetzt ne struct Point3D gemacht.

    struct Point3D {
        float x;
        float y;
        float z;
    };
    

    Hab jetzt das Ganze modifiziert, das ganze wird für verschiedene Datensätze hintereinander aufgerufen (dh. die data methode), wobei nicht immer alle map Einträge vorhanden sind, weßhalb ich clear() aufrufe (ist das effizinet))

    Welcher der folgenden Snippets ist besser?

    void data(size_t index, double const& egoPosEast, double const& egoPosNorth,
                double const& UTMPhi)
      {
        pointClouts_.clear()
        float rotSin = sin(UTMPhi);
        float rotCos = cos(UTMPhi);
    
        for (auto const& cloud : data_->sequence_.at(index).pointClouds) {
    
          auto& vec = pointClouds_[cloud.first];
          for (auto point : cloud.second) {
            auto xyPair = transformCoordSystem(
              point.x, point.y, rotSin, rotCos, egoPosEast, egoPosNorth);
            vec.emplace_back(Point3D{ xyPair.first, xyPair.second, point.z,
                                           point.intensity, point.label });
          }
        }
      }
      std::map<std::string, std::vector<Point3D>> pointClouds_;
    };
    
    void data(size_t index, double const& egoPosEast, double const& egoPosNorth,
                double const& Phi)
      {
        pointClouds_.clear();
        float rotSin = sin(Phi);
        float rotCos = cos(Phi);
    
        for (auto const& cloud : data_->sequence_.at(index).pointClouds) {
    
          auto& vec = pointClouds_[cloud.first];
          pointClouds_[cloud.first].resize(cloud.second.size());
          for (size_t point = 0; point < cloud.second.size(); ++point) {
            auto xyPair = transformCoordSystem(
              cloud.second[point].x, cloud.second[point].y, rotSin, rotCos,
              egoPosEast, egoPosNorth);
            vec[point] = Point3D{ xyPair.first, xyPair.second, cloud.second[point].z};
          }
        }
      }
      std::map<std::string, std::vector<Point3D>> pointClouds_;
    


  • Sewing schrieb:

    gibt es eine richtlinie, wann man custom structs und wann stl container verwenden soll?

    Nur zu dieser Frage: Nein, die gibt es nicht, aber es wichtig zu wissen, wie die Container der Standardbibliothek implementiert sind
    (Allgemeine Grundlagen zu Algorithmen und Datenstrukturen) und dass es heutige CPUs gar nicht mögen, wenn man in einer Schliefe
    wild im Speicher herumspringt anstatt linear auf das jeweils benachbarte Element im Speicher zuzugreifen (CPU-Cache).

    std::vector<std::vector<T>> ist allerdings schon ein Alarmsignal das man sich merken kann, besonders wenn der äußere Vektor
    deutlich mehr Elemente enthält als die inneren. Ein std::vector ist am Ende ein struct { T* elements; }; , erfordert also eine
    Indirektion über den Pointer um auf die Elemente zuzugreifen. Ein struct { T x, y, z; }; erfordert das nicht - das ist im Endeffekt
    das was du mit einem Tupel, einem std::array oder einer selbstgebauten Point3D bekommst. Hierbei liegen die float s deiner Punkte
    dann alle schön hintereinander im Speicher.

    Zu Optimierungen und den von Arcoth erwähnten SSE-Instruktionen:
    Irgendwann könnte es sich auch lohnen, dem Compiler speziellen Code für deine CPU generieren zu lassen, wenn man die
    SIMD-Instruktionen (SSE und Konsorten) nicht explizit einbauen möchte (bei GCC/Clang mit -march=... ):
    https://gcc.gnu.org/onlinedocs/gcc-7.2.0/gcc/x86-Options.html#x86-Options
    Das wird aber erst dann einen messbaren Unterschied machen, wenn die Performance nicht durch den Datenzugriff gedeckelt
    wird ( Point3D geht schonmal in die richtige Richtung).

    Edit:

    Sewing schrieb:

    Welcher der folgenden Snippets ist besser?

    Erste Regel: Messen!
    Mein Bauchgefühl: Nach Compiler-Optimierungen werden sich beide Varianten wohl nicht viel nehmen, ABER:

    vec.emplace_back(Point3D{ xyPair.first, xyPair.second, point.z,
                                           point.intensity, point.label });
    

    Hier wird das .emplace() mit dem Copy-Konstruktor von einem temporär erzeugten Objekt aufgerufen.
    Das läuft letztendlich auf dasselbe wie in Variante 2 hinaus. Möglicherweise ist der Compiler pfiffig genug den Point3D
    dennoch direkt im std::vector zu konstruieren ohne den Umweg über das temporäre Objekt zu gehen. Dennoch hätte
    ich ein besseres Gefühl wenn es so aussähe:

    vec.emplace_back(xyPair.first, xyPair.second, point.z, point.intensity, point.label);
    

    ...dafür ist allerdings ein Konstruktor in Point3D erforderlich, der die entsprechenden Argumente entgegennimmt.

    Ansonsten:
    Der Point3D den du gepostet hast, hat zwar keine .intensity und .label Attribute, die Konstruktoren in deinem geposteten Code
    legen allerdings nahe, dass das dennoch der Fall sein könnte. Soweit ich sehe werden diese Attribute für die eigentliche Berechnung
    nicht benötigt, daher könnte es der Performance zuträglich sein, diese aus der Point3D -Struktur herauszuhalten und diese Attribute
    in einer getrennten Datenstruktur zu speichern. Andernfalls würden diese Attribute in deiner "heißen" Transformationsschleife jedes
    mal mit in den CPU-Cache geladen, wo sie Platz (und letztendlich Perfomance) wegnehmen, der besser in Daten investert wäre, mit
    denen auch tatsächlich gerechnet wird (Der Vorschlag geht in Richtung Data-orented design).



  • Oh man vielen Dank für deine ausführliche Hilfe und die Zeit, die du aufgewendet hast!

    vec.emplace_back(xyPair.first, xyPair.second, point.z, point.intensity, point.label);
    

    hatte ich als

    vec.emplace_back({xyPair.first, xyPair.second, point.z, point.intensity, point.label});
    

    versucht, also aggregate initialization, aber das hat nicht funktioniert. Würde die struct ungern zu ner Klasse mit Konstruktoren aufblähen.

    Zu dem anderen Punkt, heißt das, man sollte geschachtelte stl-container in der Regel vermeiden?

    bei stl::vector<Point3D> sind die einzelenen elemente nebeneinander auf dem Heap abgelegt. Bei std::vector<std::vector<float>> sind das in diesem Fall Pointer auf weitere Hep Speicherbereiche, die aber nicht notwendigerweise nebeneinander liegen müssen und daher der overhead. Hab ich das richtig verstanden?

    Wie kann ich am besten die Zeit messen?



  • Und wir verhält es sich mit so einer schachtelung?

    std::array<std::array<std::pair<float, float>, 4>, 3366> myArray;
    

    std::arraywird ja aufem stack angelegt, ist das also unproblematisch?



  • Sewing schrieb:

    Würde die struct ungern zu ner Klasse mit Konstruktoren aufblähen

    Das macht hier nach Compiler-Optimierungen wahrscheinlich eh keinen Unterschied für so ein simples struct .
    Aber nicht immer: Bei schwergewichtigeren Klassen könnte das emplace() mit der temporären Instanz durchaus zu einer überflüssigen Kopie führen.

    Sewing schrieb:

    Zu dem anderen Punkt, heißt das, man sollte geschachtelte stl-container in der Regel vermeiden?

    Wie gesagt, es macht Sinn zu wissen wie die Container funktionieren, bevor man das sagen kann. Bei map<> und vector<> würde ich allzu viel Schachtelung
    vermeiden - kommt aber auch drauf an wo die meisten Elemente liegen: Bei deiner 5-Element- map<> und tausenden Punkten im vector<> ist das weniger ein
    Problem. Allerdings gibt es auch Container, die anders aufgebaut sind - ein std::array<std::tuple<std::pair<int, char>, std::array<float>>> sieht z.B.
    böse aus, ist aber dennoch eine ziemlich flache Datenstruktur: alles liegt direkt hintereinander im automatischen Speicher (Stack, wenn man das Ding nicht
    gerade mit make_unique o.ä. erzeugt hat). Also: Faustregeln gibts nicht, Container kennen und selbst entscheiden.

    Sewing schrieb:

    bei stl::vector<Point3D> sind die einzelenen elemente nebeneinander auf dem Heap abgelegt. Bei std::vector<std::vector<float>> sind das in diesem Fall Pointer auf weitere Hep Speicherbereiche, die aber nicht notwendigerweise nebeneinander liegen müssen und daher der overhead. Hab ich das richtig verstanden?

    So ist es.

    Sewing schrieb:

    Wie kann ich am besten die Zeit messen?

    Simpel:

    • std::chrono
      - Externes Tool wie z.B. time(1) unter Linux oder unter Windows mit Cygwin/MSYS2.

    Detaillierter:
    - perf
    - Profiler (gprof, Visual Studio Profiler)

    Wenn du sowas öfter machst, oder generell während der Entwicklung die Perfomance im Auge behalten möchtest, bietet sich auch ein Benchmark-Framework
    wie z.B. Google Benchmark an. Interessant und informativ sind auch immer die Vorträge von Chandler Carruth zu dem Thema:
    Hier kann man sich z.B. eine Menge nützlicher Informationen mitnehmen, besonders was Methoden und Tools zur Performance-Messung angeht.


  • Mod

    Als Ergaenzung zu Finnegan's Kommentar zu verschachtelten Containern: Wenn die Groesse nicht eindeutig ist, kann man auch Boost's static_vector einsetzen, welcher nur eine statische Maximalgroesse kennen muss. Koennte sich performance-technisch definitiv auszahlen, und die Groesse ist bei kleinen static_vectors auch gar kein Thema, da ein vector sowieso schon 24 Byte Overhead mitbringt (+was man der runtime library durch Speichermanagement abverlangt).



  • aber ist denn ein

    std::array<std::array<float,4>,10> myArray
    

    notwendigerweise immer komplett sequentiell angelegt?

    die einzelnen unter-arrays können doch irgendwo auf dem Stack alloziert sein oder nicht?


Log in to reply