[Visual C++] Besseres _malloca()
Verfasst: 21.08.2014, 13:51
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.
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.