C++Guns – RoboBlog blogging the bot

Betrachte ein unstruturiertes Gitternetz bestehend aus Punkte und Dreiecken. Jeder Punkt kann durchnummeriert werden. Für jeden Punkt IP bezeichnet die Variable NCONN die Anzahl der angeschlossenen Punkte pro Punkt. Und die Variable NCONE bezeichnet die angeschlossene Dreiecke pro Punkt.
Es ist leicht zu sehen, dass Punkte am Rand eine unterschiedliche Anzahl von angeschlossenen Punkte und Dreiecke haben. Wärend Punkte im Mesh gleich viele angeschlossene Punkte und Dreiecke haben.

Folgender C++ könnte grob so ein Gitternetz beschreiben:

#include <vector>

struct Mesh {
  std::vector<int> NCONN, NCONE;

  void update_NCONN_NCONE() {
     // Genaue Impl. nicht relevant für das Rätsel
  }

  bool istRandpunkt(int IP) const {
    return NCONN[IP] != NCONE[IP];
  }
}

Vor der ersten Benutzung der Funktion isRandpunkt müssen die Variablen NCONN und NCONE gefüllt werden. Dies übernimmt die Funktion update_NCONN_NCONE. Die genaue Implementierung dieser Funktion ist für das Rätsel nicht relevant, und wird daher nicht angegeben.

Nun muss der Programmierer darauf achten, dass diese Funktion auch immer aufgerufen wird. Programmierer sind aber auch nur Menschen und machen Fehler. Sollte der Aufruf von update_NCONN_NCONE einmal vergessen werden, stürzt das Programm im besten Fall ab. Im schlechtesten Fall werden falsche Ergebnisse produziert.

Wie kann dem Programmierer geholfen werden?
Es muss auf eine Art sichergestellt werden, dass die Variablen NCONN und NCONE immer mit den aktuellen Daten gefüllt sind. Allerdings darf die Funktion update_NCONN_NCONE nicht unnötig oft aufgerufen werden, da sie unter Umständen eine lange Laufzeit zur Folge hat.

Beachtet auch, dass dieser Code zur Laufzeit in ein Programm geladen werden könnte (Library/Plugin).

Es gibt für jedes Problem viele Lösungen und auch wenige gute.

Beispiel
In der Funktion istRandpunkt bei jedem Aufruf zu testen, ob die Funktion update_NCONN_NCONE aufgerufen werden muss würde zwar sicherstellen, dass die Variablen immer aktuell sind. Allerdings ist das so keine gute Idee, da dies die Laufzeit negativ beeinflusst.

struct Mesh {
  mutable std::vector<int> NCONN, NCONE;
  mutable bool needUpdate = true;

  void update_NCONN_NCONE() {
     if(not needUpdate) return;
     needUpdate = false;
     // Genaue Impl. nicht relevant für das Rätsel
  }

  bool istRandpunkt(int IP) const {
    update_NCONN_NCONE();
    return NCONN[IP] != NCONE[IP];
  }
}

In der Implementierung zeigen sich noch weitere Hässlichkeiten. Die Funktion istRandpunkt sollte als const attributiert sein, da sie keine Daten ändert. Allerdings widerspricht das der Idee, die Variablen on-the-fly zu aktualisieren. Daher müssen sie als mutable deklariert werden.
Damit werden aber Dinge im Hintergrund getriggert, welcher der Programmierer nicht erwartet. Die Funktion istRandpunkt sagt vom Funktionsnamen nicht aus, dass noch ein Update passiert.

Lösung 1: Tags
Die Idee ist, dass die Funktion istRandPunkt nur dann aufgerufen/compiliert werden kann, wenn als Argument irgendetwas mitgegeben werden kann, was vorher nur von der Funktion update_NCONN_NCONE erstellt wurde. Beispielsweise mittels einer Tag Variable. Diese kann nur von update_NCONN_NCONE erstellt werden.

struct Mesh {
    private:
    struct Tag { };

public:
  std::vector<int> NCONN, NCONE;

  Tag update_NCONN_NCONE() {
     // Genaue Impl. nicht relevant für das Rätsel
     return Tag();
  }

  bool istRandpunkt(int IP, Tag) const {
    return NCONN[IP] != NCONE[IP];
  }
};

auto func() {
    Mesh mesh;    
    auto tag = mesh.update_NCONN_NCONE();
    return mesh.istRandpunkt(1, tag);
}

Der Nachteil ist schnell erkannt. Sobald mehr als ein Mesh existiert, kann die tag Variable mehrfach genutzt werden. Es existiert keine Bindung zu einer speziellen Instanz eines Mesh Types.

Lösung 1: Enums

Die Performance ist ein Opfer von Level of Indirection. Jetzt auch bei mir. Ich will keinen langweiligen Code zeigen wie so etwas aussieht, oder wie man es verhindern kann. Viel interessanter ist es doch, wie das aus Assembler Ebene aussieht.
Dazu zwei Assembler Auszüge. Der erste mit zwei zusätzlichen Indirektionen. Es wird auf das i-th Element eines std::vector zugegriffen und zurück gegeben.

func(std::vector<T> const&, int):
        movq    %rdi, %rax       }
        movslq  %edx, %rdx       |
        salq    $4, %rdx         | Addressberechnung
        addq    (%rsi), %rdx     }
        movq    (%rdx), %rdx     * Indirektion 
        movq    (%rdx), %rdx     * Indirektion
        movdqu  (%rdx), %xmm0    }
        movups  %xmm0, (%rdi)    |
        movdqu  16(%rdx), %xmm1  | Kopieren der 4 double Variablen
        movups  %xmm1, 16(%rdi)  }
        ret

Ohne zweimalige Indirektion:

func2(std::vector<T> const&, int):
        movq    %rdi, %rax        }
        movslq  %edx, %rdx        |
        salq    $5, %rdx          | Addressberechnung
        addq    (%rsi), %rdx      }
        movdqu  (%rdx), %xmm0     }
        movups  %xmm0, (%rdi)     |
        movdqu  16(%rdx), %xmm1   | Kopieren der 4 double Variablen
        movups  %xmm1, 16(%rdi)   }
        ret

Es sind zwei Dinge zu erkennen.
Erstens gibt es zwei zusätzliche mov Anweisungen, welche eine Dereferenzierung eines Pointers bewirken. Die zusätzliche Arbeit den Befehl zu bearbeiten ist nicht das Problem. Vielmehr, dass die Daten nicht mehr hintereinander im RAM stehen. Es wird im RAM umher gesprungen. Dies geht bekanntlich auf die Performance, Cache misses u.s.w.

Bei dem konkreten Problem, aus dem dieses Beispiel hervorgegangen ist, lief das Programm nach dem Entfernen der zwei Indirektionen 10 mal schneller!

Zweitens ist zu erkennen, dass die zurück gegebenen Variablen aus 4 double Werten besteht, aber nur zwei Kopieraktionen zu erkennen sind. Von dem Register rdx, nach xmm0, nach rdi. Und noch einmal mit einem Offset von 16Byte (2 double Werte). Der Compiler hat erkannt, dass SIMD angewendet werden kann. Das Kopieren von zwei Werten mit einer Instruktion. Und das ohne zusätzlichen Bemühungen meinerseits C++ Code extra SIMD tauglich zu schreiben!