3. Alignment/Architektur herausfinden

Alignment/Architektur herausfinden

  • ?

    Hallo,

    ich habe hier in Code eine std::map<MeinTyp*, Foo> , auf die recht häufig zugegriffen wird.

    Nun ist die Reihenfolge irrelevant, weswegen ich die std::map durch eine std::unordered_map<MeinTyp*, Foo> ersetzt habe. Damit ist das Programm schon einmal schneller geworden (je nachdem, wie viel so in der Map drin ist, in einem Beispiel ca. 4%).

    Nun habe ich festgestellt, dass die niedrigsten 3 Bits der Pointer immer 0 sind und habe eine eigene Hash-Funktion genommen:

    namespace std {
  template <>
  struct hash<MeinTyp*> {
    size_t operator()(const MeinTyp* x) const {
      return hash<uintptr_t>()(reinterpret_cast<uintptr_t>(x) >> 3);
    }
  };
}

    Das wirkt Wunder und spart nochmal doppelt so viel wie der Schritt auf die unordered_map. Nun ist das aber ja hier wohl meiner 64-Bit-Architektur geschuldet (oder dem Compiler, der die Pointer so ausrichtet). Gibt es irgendeine Möglichkeit herauszufinden, obige Hash-Funktion nur dann einzuführen, wenn wirklich immer pointer & 0b111 == 0 ist? Bzw. kann man ermitteln, wie viele Bits rechts immer 0 sind? Gut, char* könnte sicher auch anders sein, sonst könnte man ja keine Strings durchlaufen. Hier sind die Objekte alle >100 Byte groß und alle mit new erzeugt. Oder sollte ich sowas wie (x >> 3) | (x << (numeric_limits<uintptr_t>::digits-3)) machen?

    Wie bekomme ich die obige Info am standardkonformsten 😉 heraus?

    Wobei: eigentlich fällt mir gerade ein: es ist >>3 doch auf jeden Fall unproblematisch, weil sizeof(MeinTyp) > 100 ist und sich die Pointer ja nicht überlappen können, d.h. ich könnte ich auch reinterpret_cast<uintptr_t>(x)/sizeof(MeinTyp)) rechnen und das Ergebnis wäre danach immer noch eindeutig zuordenbar -> spannend, gerade getestet: das ist aber wieder genauso schnell wie ohne das >>3.

    0

  • Mit alignof(T) bekommst du portabel das Alignment von jedem Typen. Auf einer 64 Bit Architektur wundert es mich nicht, dass Zeiger ein Alignment von 8 haben 😉

    0
  • ?

    Cool, dann kann ich das >>3 am besten durch /alignof(MeinTyp*) ersetzen!

    0

  • Wenn dann eher /alignof(MeinTyp) . Wie der Zeiger selbst aligned wäre ist ja egal - hashen willst du ja nicht die Adresse des Zeigers sondern die des MeinTyp Objekts. Und dabei ist natürlich nur das Alignment des MeinTyp Objekts interessant. Und das ist alignof(MeinTyp) .

    Aber ganz anderer Vorschlag, probier mal das:

    template <>
  struct hash<MeinTyp*> {
    size_t operator()(const MeinTyp* p) const {
      static size_t const m0 = sizeof(MeinTyp) - 1;
      static size_t const m1 = m0 | (m0 >> 1);
      static size_t const m2 = m1 | (m1 >> 2);
      static size_t const m3 = m2 | (m2 >> 4);
      static size_t const d = (m3 <= 255) ? (m3 + 1) : 256;

      uintptr_t const n = reinterpret_cast<uintptr_t>(p);
      return static_cast<size_t>(n ^ (n / d)); // KEIN hash<uintptr_t>()(...)!
    }
  };
    0
  • ?

    Danke hustbaer für deinen Vorschlag. Habs mal ausprobiert. Macht ungefähr gar keinen Unterschied. Ich hatte bislang immer mit einer Einstellung getestet, die ca. 3 Minuten läuft und konnte dabei keinen Unterschied feststellen.

    Jetzt habe ich die Einstellungen geändert, sodass die Berechnung genauer wird und länger dauert - und jetzt habe ich folgendes gemessen (Stichprobe = 1, da ich nicht so viel Zeit habe...):

    Hustbaer  wob/alignof(MeinTyp)  std::unordered_map    std::map
-----------------------------------------------------------------
688 s          680 s                  721 s             760 s
696 s          705 s           (nicht gemessen, da eh schlechter)

    (Zeilen 1 und 2 unterscheiden sich noch durch das inline-Machen einer anderen, unabhängigen Funktion -> ohne inline (Zeile 1) ists schneller)

    Und 680/688 Sekunden ist jetzt so nah beieinander, dass ich da nichts draus schließen möchte, da ich auch noch nebenbei in Impress herumwerkele. Dennoch ist 680 versus 760 schon ganz gut, das sind insgesamt 0.95x gegenüber dem originalen Code mit der map. Mit den Einstellungen, die ich eigentlich benötige, dauert die Berechnung aktuell ca. 10 Stunden, daher machen 5% dann schon ne halbe Stunde aus. Wobei es dann wohl auch eh in der Map anders aussieht. Hoffe aber, dass das Ergebnis irgendwie übertragbar ist.

    Ich schau mir erstmal andere Code-Teile an, die "verdächtig" aussehen. Ich habe dazu mit gperftools herumgespielt, aber die längste Zeit wird in einem getter einer float-Variablen verbracht, die sich hinter einem pointer auf einen vector mit float-pointern versteckt ( vector<float*> *v ). Meine Vermutung ist aktuell, dass da zu viele Pointer im Spiel sind und ich da weiter vereinfachen müsste bzw. dass ich die Daten besser hintereinander im Speicher einreihen können müsste.

    Habe ihr Empfehlungen für Profiler? Außer perf und gperftools habe ich bislang noch keine Erfahrungen. Vor allem habe ich irgendwie das Gefühl, dass Funktionen, die nicht mehr einfacher gehen (so 1-3 Zeiler) erschreckend viel Zeit brauchen.

    0
  • ?

    wob schrieb:

    Meine Vermutung ist aktuell, dass da zu viele Pointer im Spiel sind und ich da weiter vereinfachen müsste bzw. dass ich die Daten besser hintereinander im Speicher einreihen können müsste.

    hatte ich mal ähnlich bei einem neuronalen netzwerk, ein schlichtes umordnen der floats für die gewichtungen (nacheinander im speicher) brachte da ca. 50% mehr an geschwindigkeit. cache misses sind auch ein hund...
    was du auch probieren könntest, wäre ein mehr an daten in kleinere felder zu packen. evtl. (wenn du unter linux bist und unter gewissen voraussetzungen) https://en.wikipedia.org/wiki/X32_ABI - dann hast du z.b. kleinere zeiger (=meist auch schneller); oder du packst sachen in bitfields (wobei das wohl nicht geht, wenn du auf floats angewiesen bist).

    abgesehen natürlich davon, dass du auch immer einen besseren algorithmus auf der übergeordneten ebene finden kannst.

    0
Anmelden zum Antworten