3. Effinzienteste Art eine Map voller Vektoren zu transformieren

Effinzienteste Art eine Map voller Vektoren zu transformieren

  • 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.

    0
  • W

    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.

    0
  • 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.

    0
  • S

    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_;
    0
  • F

    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).

    0
  • S

    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?

    0
  • S

    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?

    0
  • F

    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.

    0
  • 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).

    0
  • S

    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?

    0
  • W

    Sewing schrieb:

    aber ist denn ein

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

    notwendigerweise immer komplett sequentiell angelegt?

    Ja.

    Ebenso auch bei std::vector<std::array<float,4>> myArray . Nur dass du einmal vorne im Vector einen Pointer auf den gesamten Speicherbereich hast.

    Bei std::array<std::vector<float>,10> myArray dagegen sind die Vector-Objekte (d.h. vector-Länge, vector-Kapazität und vector-Datenpointer) sequentiell im Speicher. Die Vector-Daten sind dagegen nur einzeln sequentiell im Speicher. D.h. die Daten von myArray[0][0] bis myArray[0][size-1] liegen sequentiell im Speicher, die von myArray[1][0] bis myArray[1][size-1] ebenfalls, aber die einzelnen Datenbereiche der Vectoren haben nichts miteinenander zu tun.

    Sewing schrieb:

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

    Nein.

    0
  • Mod

    Sewing schrieb:

    aber ist denn ein

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

    notwendigerweise immer komplett sequentiell angelegt?

    Ja.

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

    Nein, wieso sollten sie? Arrays sind kein magisches Gebilde. Das sind ganz normale Objekte, wie alle andere auch. Bei einem array<float, 4> sind die vier floats auf jeden Fall sequentiell. Das wundert dich nicht, oder? Wieso wundert dich dann, dass bei einem Array von Arrays die inneren Arrays sequentiell liegen?

    Der entscheidende Unterschied zwischen array<vector<float>> (mehrere Sequenzen verteilt im Speicher) und array<array<float>> (mehrere Sequenzen sequentiell im Speicher): Das Array ist sein Inhalt. Da wo das Array ist, ist auch sein Inhalt, die beiden sind ein und dasselbe. Der Vector ist nur ein Verweis auf seinen Inhalt. Der Inhalt kann und wird ganz woanders sein als die Verwaltungsdaten des Vectors.

    0

  • Du mißverstehst etwas mit dem Stack.
    Daher wiederhole ich mal die Aussage:

    Arcoth schrieb:

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

    Aber die Elemente liegen dann alle am Stück im Speicher.

    0
  • R

    Die Map besteht aus 5 Einträgen und jeder mapped-type hat dann ein paar tausend Einträge

    Du hasst nen dyn. Array aus fixen tuples von floats
    Dein Ergebnis ist wiederum ach nen dyn. Array mit selber grösse vom Ausgangs-Array aus fixen tuples aus floats.

    Das schreit formlich nach GPU, wenn die Arrays groß genug sind und die Berechnung komplex genug(Daten-Übertragung vs. compute zeit)
    Schon mal über ne Lösung auf OpenCL/Cuda/OpenGL/Vulkan Basis nachgedacht?
    Bei idealen GPU Bedingungen kann sogar der integrierte Intel HD chip gegenüber der CPU was bringen.

    Ciao ..

    0
Anmelden zum Antworten