Effinzienteste Art eine Map voller Vektoren zu transformieren

Sewing

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_;

Finnegan

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

Sewing

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?

Sewing

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?

Finnegan

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.

Columbo

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

Sewing

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?

wob

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.

SeppJ

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.

Th69

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.

RHBaum

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