[Visual C++] Besseres _malloca()

[Krishty]

Wenn ich funktionslokal einen Block dynamischer Größe brauche, habe ich lange die Maximalgröße ausgerechnet und ein entsprechend großes lokales Array angelegt. Ich HASSE manuelle Speicherverwaltung.

Jedenfalls kommt der Ansatz, natürlich, schnell an Grenzen wenn man Probleme exponentieller Größe verarbeitet. Wenn ich z.B. die Schnitte aus n Linien berechnen möchte, könnte ich theoretisch in die Nähe von (n/2)² Schnittpunkten kommen. Da explodiert der Stack.

Eine Lösungsmöglichkeit ist _alloca(), aber das bringt mehr Nachteile als Vorteile. Der Schlimmste ist, dass man schlecht auf Erfolg prüfen kann.

Praktischer ist ein schneller Pfad mit lokalem Array, das groß genug für 99 % der Fälle ist. Das letzte Prozent der Fälle kann auf manuelle Speicherverwaltung zurückfallen (da sind die Datenmengen dann eh so groß, dass Allokation nicht mehr der Flaschenhals ist).

Tatsächlich ist das, was Microsofts _malloca-Makro macht. Das ist aber sehr halbgar (hat mit fast den gleichen Nachteilen zu kämpfen wie _alloca()) und erfordert – was es für mich ruiniert – _freea().

Ich habe mir ein eigenes Visual-C++-Makro geschrieben, das mit der Allokation hilft:

  #include <Windows.h>

  static auto const heap = GetProcessHeap();

  template <
    typename T
  > __declspec(noinline) T * slowReserve(
    size_t const length
  ) {
    // Pitfall 1: Allocation size overflow. This is a severe security issue, and it causes Visual C++ to generate inefficient
    // code for size computation (relying on the overflow flag). Data type limits are known here (since this is a template), so
    // use a jump instead.
    if(length > SIZE_T_MAX / sizeof(T)) {
      throw "allocation size overflow";
    }
    // Pitfall 2: Out-of-memory conditions.
    auto const result = HeapAlloc(heap, 0, length * sizeof(T));
    if(nullptr == result) {
      throw "out of memory";
    }
    __assume(nullptr != result);
    return reinterpret_cast<T *>(result);
  }

  void __declspec(noinline) slowRelease(
    void * const memory
  ) {
    HeapFree(heap, 0, memory);
  }

  template <
    typename T,
    size_t  stackLength
  > class LocalAllocation {
  public:

    ~LocalAllocation() throw() {
      if(nullptr != onHeap) {
        slowRelease(onHeap);
      }
    }

    T   onStack[stackLength];
    T * onHeap;
  };


  #define QUICK_LOCAL_ALLOC(NAME, TYPE, QUICK_LENGTH, ACTUAL_LENGTH) \
    LocalAllocation<TYPE, QUICK_LENGTH> NAME##Allocator; \
    TYPE * NAME; \
    if(ACTUAL_LENGTH > QUICK_LENGTH) { \
      NAME##Allocator.onHeap = NAME = slowReserve<TYPE>(ACTUAL_LENGTH); \
    } else { \
      NAME##Allocator.onHeap = nullptr; \
      NAME = NAME##Allocator.onStack; \
    }

Mein Augenmerk lag darauf, das Programm möglichst wenig mehr aufzublähen als wenn da ein statisches Array wäre. Darum kein _alloca() (das erst endlos den Stack ausrichtet, abtastet, verifiziert, usw.) und die hässliche Form (Visual C++ kriegt sonst nichts richtig optimiert).

Eine Funktion, die das benutzt, dürfte rund 30–40 B größer werden (32-Bit-x86). Der Test benötigt eine Handvoll Takte bei der Konstruktion und ebenso beim Zerstören. Natürlich könnt ihr andere Allokatoren als HeapAlloc() benutzen, aber lasst die bloß noinline, sonst bläht sich die Hölle unter euch auf.

[Helmut]

Das gefällt mir wesentlich besser als _alloca(). Die Funktion sollte meiner Meinung nach verboten werden.

Man sollte vielleicht noch erwähnen, dass dein Code nicht mehr funktioniert, sobald TYPE einen Konstruktor hat. Außerdem würde mich ein wenig stören, dass dann auf dem Stack Platz für 2 Pointer gemacht werden muss, obwohl nur einer benötigt wird. Wenn du den operator* und -> benutzt dürfte sich das doch beheben lassen.

[Krishty]

Man sollte vielleicht noch erwähnen, dass dein Code nicht mehr funktioniert, sobald TYPE einen Konstruktor hat.

Wer legt denn bitte Arrays von Klassen an ó_Ô vector_ctor_iterator() und dieser Müll …

Außerdem würde mich ein wenig stören, dass dann auf dem Stack Platz für 2 Pointer gemacht werden muss, obwohl nur einer benötigt wird. Wenn du den operator* und -> benutzt dürfte sich das doch beheben lassen.

Dummerweise baut Visual C++ dann bei jeder Dereferenzierung ein if in den Maschinentext (es erkennt nicht, dass sich Attribute über Methoden hinweg nicht ändern) … der endgültige Zeiger landet in meinen Testfällen sowieso im Register, also drauf gepfiffen.

[dawit]

Ich versteh gerade irgendwie nicht, warum das ein Makro sein muss. Würde nicht auch einfach eine Klasse gehen?

Code: Alles auswählen

template<size_t Size, typename T>
struct quick_vector
{
    quick_vector(size_t size) :
        heap{nullptr}
    {
        if(size > Size)
        {
            heap = new T[size];
            data = heap;
        }
        else
            data = stack;
    }

    ~quick_vector()
    {
        if(heap)
            delete[] heap;
    }

    T *data;
    T *heap;
    T stack[Size];
};

[Krishty]

Wenn du data in ein Attribut ablegst, allokiert Visual C++ tatsächlich Stapelspeicher für die Variable. Ist sie jedoch außerhalb der Klasse (via Makro), wandert sie in ein Register. (Ist jedenfalls bei meinem 2012er so.)

Du kannst ja mal den Maschinentext der beiden Versionen vergleichen, dann solltest du es sehen können.

[dawit]

Yupp, bin zwar unter Linux, aber GCC reserviert auch extra Speicher auf dem Stack wenn man das ganze in eine Klasse packt.

[Krishty]

Kleine Korrektur für Visual C++: In der 64-Bit-Version den Zeiger *vor* das Array schieben. Falls er hinter dem Array liegt und das Array größer als rund 240 B ist, muss auf 32-Bit-Adressierung zurückgegriffen werden. Konkret werden


  48 89 84 24 20 02 00 00             mov qword ptr [rsp+220h],rax
  48 C7 84 24 20 02 00 00 00 00 00 00 mov qword ptr [rsp+220h],0
  48 8B 8C 24 20 02 00 00             mov rcx,qword ptr [rsp+220h]

zu

  48 89 44 24 20             mov qword ptr [rsp+20h],rax
  48 C7 44 24 20 00 00 00 00 mov qword ptr [rsp+20h],0
  48 8B 4C 24 20             mov rcx,qword ptr [rsp+20h]

und damit zu 9 B weniger. In der 32-Bit-Version ist leider genau das Gegenteil der Fall weil er mit ebp adressiert (dort werden die zuletzt definierten Variablen kürzer adressierbar).

Perfekt wäre natürlich, die Variable erst garnicht auf den Stack zu schieben damit die movs ganz überflüssig sind. Aber offenbar traut Visual C++ fremden Funktionen (hier printf()) nicht, die Register wiederherzustellen.

Nebenbei: Weiß jemand, warum x86-64 die zuerst definierten Variablen kürzer adressiert? Das erscheint mir irrational, weil z.B. in verschachtelten Schleifen die zuletzt definierten Variablen (innere Schleife) deutlich öfter benutzt werden als die zuerst definierten (äußere Schleife). Nur um Stack Walking zu vereinfachen?