Allokator auf Windows programmieren - Denkanstöße und Korrekturen

[dachschaden]

Jodocus schrieb:

RAII ist doch nicht das Selbe wie RTTI...

Ugh, da hab' ich mich verlesen. Ja, stimmt. RAII != RTTI. Ich bin blöd.

[volkard]

dachschaden schrieb:

volkard schrieb:

Jupp, aber RAII ist auch hier supi praktisch: Türlich ziehen wir hier nur Sprachmittel, die Nullkosten oder weniger gegenüber C haben. C ist halt an sich lahm, weil der Compiler weniger weiß.

Brauch ich nicht. Habe ich mal in ein paar Testprogrammen verwendet, als ich mir C++ angeschaut habe, und danach nie wieder. Irgendwie verursacht es mir Magenschmerzen, wenn man nachgucken muss, was genau für ein Typ hinter einem Objekt steht.

(kleine RTTI/RAII-Verwechslung)
Da sind wir einer Meinung. Ich verwende in C++ auch nie RTTI. RTTI ist nur ein Notnagel, falls man eine total verbuggte und fehlgeplante Fremdlib benutzen muss.
RAII ist kostenlos im Vergleich zu C oder im Zusammenhang mit Exceptions sogar schneller als C. Das wollen wir schon nehmen. Es ist auch angenehm zu benutzen und vermeidet viele Fehler.

[hustbaer]

dachschaden schrieb:

Wobei ich sagen muss, dass meine Implementierung über SSE/AVX gegenüber der glibc-Implementierung rund 16.000 Cycles langsamer ist, gegenüber der Windows-Version aber 1.600 Cycles schneller (beides Durchschnittswerte mehrerer tausend Durchläufe). Da ich das Kopieren aber eh nur für Windows brauche, verbuche ich diesen Aspekt bereits als Erfolg.

Hast du bei Windows/MSVC gegen memcpy verglichen oder gegen memmove ?
Ich frag' nur weil memmove bei mir (deutlich) schneller ist (ca. ~9 GB/s vs. ~6.1 bei memcpy ).
(Oder gegen eine WinAPI-Funktion?)

dachschaden schrieb:

Ugh, da hab' ich mich verlesen. Ja, stimmt. RAII != RTTI.

OK. Jetzt verstehe ich was du geschrieben hast Kam mir halt komisch vor, aber bin nicht auf die Idee gekommen dass du RTTI meinen könntest.

[dachschaden]

volkard schrieb:

RAII ist kostenlos im Vergleich zu C oder im Zusammenhang mit Exceptions sogar schneller als C. Das wollen wir schon nehmen. Es ist auch angenehm zu benutzen und vermeidet viele Fehler.

Sehe ich nicht so. Gerade bei dem Topic - dem Halten der Mappings, die mir der Kernel zurückgibt - muss ich diese ja irgendwo speichern. Dafür hole ich mir einmal unbürokratisch 64 KiB Speicher. Aber das muss ich ja nur dann machen, wenn ich das Mapping auch wirklich haben will. Jetzt gibt es aber Codepfade innerhalb von Funktionen, wo ein Mapping gar nicht gebraucht wird. Sprich, ich habe das Objekt auf dem Stack, muss es aber in einem Codepfad gar nicht verwenden. Ich will den Code aber dennoch in einer Funktion halten, sonst schreibe ich eventuell anderen Code wieder und wieder.

Wenn die Funktion bei RAII aufgerufen wird, habe ich bei C++ direkt zwei Kernel-Calls sitzen, selbst, wenn ich das Objekt gar nicht brauche (allozieren + freigeben). Ja, kannst du sagen, dann pack die Tabelleninitialisierung doch in eine eigene Funktion deiner Klasse/Stuktur. Dafür brauche ich aber nicht RAII - das kann ich auch über eine <Strukturname>_init -Funktion regeln (und <Strukturname>_free für's freigeben). Nur in diesen Funktionen muss ich mich dann um Ressourcenmanagement kümmern.

Das sind alles so Automatismen, die gut gemeint sind, aber dann häufig doch nur im Weg liegen. Ja, Programmierer vergessen die manchmal. Aber deswegen jetzt die Programme langsamer werden zu lassen ist auch blöd.

hustbaer schrieb:

Hast du bei Windows/MSVC gegen memcpy verglichen oder gegen memmove ?

Zuerst gegen memcpy , jetzt auch mal gegen memmove . MSVC's memmove und mein memcpy brauchen beide so ungefähr 380K Cycles zum Kopieren von 2 MiB.

Habe außerdem gemerkt: prefetching hilft, aber nur, wenn man den Schreibzugriff cached, und dann am Besten 2 oder 3 Iterationen vorher laden. Sonst wird's mit den Stalls echt lächerlich.
Nichttemporär (zu schreiben) ist übrigens so ziemlich das langsamste im Universum, hat den Durchsatz verdoppelt, das nicht zu verwenden.

hustbaer schrieb:

Ich frag' nur weil memmove bei mir (deutlich) schneller ist (ca. ~9 GB/s vs. ~6.1 bei memcpy ).
(Oder gegen eine WinAPI-Funktion?)

CopyMemory ist auf meiner Hardware nochmal durchschnittlich 0.5K Cycles schneller als meine Implementierung. Hat mich erstaunt, weil ich vor gar nicht langer Zeit gelesen habe, dass auf Windows memcpy intern CopyMemory aufrufen würde.

Ich glaub' inzwischen, der Speicher hat sowas wie eine Tageslaune, und gibt mir mal schnelleren, mal weniger schnellen Zugriff. Oder die Ausführungen fielen manchmal unglücklich mit dem DRAM-Refresh zusammen.
Der Grund, warum dein memmove so viel schneller ist, könnte mit dem Prefetching zusammenhängen - soweit ich weiß sind CPUs da höllisch eigen. Hm ... vielleicht sollte ich mal schauen, ob das ebenfalls Ausschlag auf den Durchsatz hat. EDIT: "sind CPUs mit der Kopierrichtung höllisch eigen", wollte ich schreiben.

EDIT2: Nein, die Kopierrichtung zu ändern bringt nichts.

[hustbaer]

Achja, nur kleiner Tip: Vergleich auch mal gegen rep movsb .
Ist bei mir gleich schnell wir memmove (also auch 9 GB/s).

[dachschaden]

hustbaer schrieb:

Achja, nur kleiner Tip: Vergleich auch mal gegen rep movsb .
Ist bei mir gleich schnell wir memmove (also auch 9 GB/s).

Mit rep movsb komme ich beinahe auf glibc's Durchsatz - ist zwar immer noch ein wenig langsamer, aber da werde ich von mir aus nichts mehr dran machen. Vielleicht noch mal Prefetching, mehr aber nicht.

Für Windows musste ich mir erst anschauen, wie ich MASM-Support da reingepfriemelt bekomme (MS hat für die 64-Bit-Version Inline-Assembly rausgekommen). Habe dennoch diesen Code hier ans Laufen bekommen:

_text SEGMENT

.code

memcpy_page_4KiB PROC
	push RDI
	push RSI

	cld

	;Windows verwendet für x64 folgende Convention:
	;1. Parameter in RCX
	;2. Parameter in RDX
	mov RDI,RCX
	mov RSI,RDX
	mov RCX,1000h
	rep movsb

	pop RSI
	pop RDI

	ret

memcpy_page_4KiB ENDP

END

Ich bin mir sicher, dass man das noch optimieren könnte - aber ich war noch nie der große Assembly-Held.

Jedenfalls benötige ich damit nur noch 310K Cycles anstelle von 370-380K Cycles. Kann man das mit Memory-Stalls erklären, oder benötigt das Ausführen der AVX-Instuktionen so lange, dass ich damit kaum mithalten kann?

Ich hätte auch erwartet, dass es zumindest einen messbaren Unterschied zwischen

mov RCX,1000h
	rep movsb

und:

mov RCX,200h
	rep movsq

gibt, aber die halten sich eigentlich die Waage.

[hustbaer]

MASM muss man im Projekt einfach nur aktivieren:
http://stackoverflow.com/questions/20078021/how-to-enable-assembly-language-support-in-visual-studio-2013

Wenn du danach .asm Files im Projekt anlegst sollten die automatisch mit MASM verknüpft werden. (Wenn du davor .asm Files anlegst musst du es nachträglich mit Hand machen, also in den File-Properties als Build-Tool MASM einstellen.)

Was die verwunderliche Geschwindigkeit von rep movsb angeht: soweit ich weiss hat Intel das speziell optimiert. Quasi nen fast perfektes memcpy in Microcode. Möglicherweise haben manche CPUs sogar ne spezielle "Copy-Engine"?

Auf jeden Fall ist rep movsb vermutlich der Befehl der bei weitem am häufigsten in exakt der Form zum kopieren von Speicherblöcken verwendet wird (also auch häufiger als kompliziertere Schleifen). Daher zahlt es sich aus rep movsb so schnell wie möglich zu machen. Und daher halte ich es auch für halbwegs "zukunftssicher".

Allerdings gibt es auch Nachteile, auf einigen CPUs ist es wohl deutlich langsamer. Weiss leider nimmer welche es waren, aber wenn du maximale Geschwindigkeit auf allen möglichen CPUs willst/brauchst, dann solltest du ausgiebig testen.

ps: Misst du mit Workloads die in den Cache passen, oder mit grossen? Ich hab meine Tests mit 1 GiB grossen Blöcken (mit 4K Alignment) gemacht, weil ich die "RAM-to-RAM" Copy-Speed messen wollte. Aber sollte klar sein, 9 GB/s für Cache-to-Cache wären schon sehr mickrig.

[Bonita.M]

dachschaden schrieb:

Für Windows musste ich mir erst anschauen, wie ich MASM-Support da reingepfriemelt bekomme (MS hat für die 64-Bit-Version Inline-Assembly rausgekommen). Habe dennoch diesen Code hier ans Laufen bekommen:

Für fast alle x86-Instruktionen die man nicht indirekt durch Standard-C(++) ausdrücken kann gibt es Intrinsics, so auch für MOVSB:
https://msdn.microsoft.com/de-de/library/hhta9830.aspx
Da man eben für fast alles was sonst nur in Assembler ging Intrinsics hat, ist Assembler fast nie nötig.

[dachschaden]

hustbaer schrieb:

MASM muss man im Projekt einfach nur aktivieren:
http://stackoverflow.com/questions/20078021/how-to-enable-assembly-language-support-in-visual-studio-2013

Nein, eben nicht. Die Datei war noch vom Build ausgeschlossen (frag' mich nicht, warum, gesetzt habe ich es nicht - die ASM-Datei war ja komplett neu).

hustbaer schrieb:

Auf jeden Fall ist rep movsb vermutlich der Befehl der bei weitem am häufigsten in exakt der Form zum kopieren von Speicherblöcken verwendet wird (also auch häufiger als kompliziertere Schleifen). Daher zahlt es sich aus rep movsb so schnell wie möglich zu machen. Und daher halte ich es auch für halbwegs "zukunftssicher".

Allerdings gibt es auch Nachteile, auf einigen CPUs ist es wohl deutlich langsamer. Weiss leider nimmer welche es waren, aber wenn du maximale Geschwindigkeit auf allen möglichen CPUs willst/brauchst, dann solltest du ausgiebig testen.

Hm. Notfalls kann man immer noch auf den Prozessor prüfen (CPUID-Interface habe ich hier).

hustbaer schrieb:

ps: Misst du mit Workloads die in den Cache passen, oder mit grossen? Ich hab meine Tests mit 1 GiB grossen Blöcken (mit 4K Alignment) gemacht, weil ich die "RAM-to-RAM" Copy-Speed messen wollte. Aber sollte klar sein, 9 GB/s für Cache-to-Cache wären schon sehr mickrig.

Workloads, die in den Cache passen.

Ich habe allerdings auch mal versuchsweise das Kopieren von einem GiB gemessen, 560M Cycles. Allerdings werde ich da auch ein paar TLB-Misses gehabt haben, einfach, weil ich gerade nicht mit 1-GiB-Pages gebootet habe (Bei 1-GiB werden die Pages schon beim Booten reserviert, und man kann sie danach nicht mehr freigeben, deswegen sind die standardmässig aktiviert - den Platz möcht ich noch für andere Sachen haben). Wenn ich dann mit 1024 2-MiB-Pages arbeite (1 GiB-Source, 1 GiB-Destination), habe ich ungefähr einen Durchsatz von 6 GiB/s. Auf Linux jetzt.

@Bonita.M: damit bin ich nochmal um 10K-20K Cycles schneller. Vielen Dank!

[hustbaer]

@Bonita.M
Sehr cool. Danke auch von mir, kannte ich noch nicht.

[hustbaer]

@dachschaden
Du solltest auf jeden Fall immer alle Varianten mit der selben Programmausführung ausführen und vergleichen, und immer mehrere Versuche machen. Und mit den selben Pufferadressen. Und dann den schnellsten raussuchen. Und so lange versuchen bis z.B. 100 Ausführungen zu keiner Verbesserung mehr geführt haben. Damit bekommt man zumindest halbwegs reproduzierbare Resultate die kaum noch von Sonnenflecken beeinflusst werden.

Ca so.

#include <intrin.h>
#include <windows.h>
#include <immintrin.h>

// candidates

typedef void __stdcall RtlCopyMemoryType(void*, const void*, size_t Length);

RtlCopyMemoryType* MyRtlCopyMemory;
RtlCopyMemoryType* MyRtlMoveMemory;

void char_copy(unsigned char const* s, unsigned char* d, size_t n)
{
	while (n--)
		*d++ = *s++;
}

void int_copy(unsigned char const* s, unsigned char* d, size_t n)
{
	size_t n4 = n / 4;
	int const* s4 = reinterpret_cast<int const*>(s); // strict aliasing, yes, I know
	int* d4 = reinterpret_cast<int*>(d);

	s += n4 * 4;
	d += n4 * 4;
	n = n % 4;

	while (n4--)
		*d4++ = *s4++;

	while (n--)
		*d++ = *s++;
}

void avx_copy(unsigned char const* s, unsigned char* d, size_t n)
{
	size_t n128 = n / 128;
	__m256i const* s32 = reinterpret_cast<__m256i const*>(s); // strict aliasing, yes, I know
	__m256i* d32 = reinterpret_cast<__m256i*>(d);

	s += n128 * 128;
	d += n128 * 128;
	n = n % 128;

	while (n128--)
	{
		auto r1 = _mm256_loadu_si256(s32);
		auto r2 = _mm256_loadu_si256(s32 + 1);
		auto r3 = _mm256_loadu_si256(s32 + 2);
		auto r4 = _mm256_loadu_si256(s32 + 3);
		_mm256_storeu_si256(d32, r1);
		_mm256_storeu_si256(d32 + 1, r2);
		_mm256_storeu_si256(d32 + 2, r3);
		_mm256_storeu_si256(d32 + 3, r4);
		s32 += 4;
		d32 += 4;
	}

	while (n--)
		*d++ = *s++;
}

extern "C" void repmovsb(unsigned char const* s, unsigned char* d, size_t n); // implemented in the .asm file

// timing

#include <chrono>
#include <iostream>
#include <cassert>

using namespace std;
using namespace std::chrono;

extern "C" __declspec(dllexport) volatile void* g_dummy1 = 0;
extern "C" __declspec(dllexport) volatile void* g_dummy2 = 0;
extern "C" __declspec(dllexport) volatile int g_dummy3 = 0;

nanoseconds baseline = nanoseconds(0);

unsigned char* buffer0;
unsigned char* buffer1;
//size_t const buffer_size = 1024 * 1024 * 1024;
//size_t const repeat = 1;
//size_t const buffer_size = 2048 * 1024;
//size_t const repeat = 10;
//size_t const buffer_size = 64 * 1024;
//size_t const repeat = 100;
size_t const buffer_size = 4 * 1024;
size_t const repeat = 1000;

void optimization_barrier()
{
	_ReadWriteBarrier();
	g_dummy1 = buffer0;
	g_dummy2 = buffer1;
	g_dummy3++;
}

template <class F>
nanoseconds measure_once(F fun)
{
	auto const t0 = high_resolution_clock::now();

	for (size_t i = 0; i < repeat; i++)
	{
		optimization_barrier();
		fun();
		optimization_barrier();
	}

	auto const t1 = high_resolution_clock::now();
	return duration_cast<nanoseconds>(t1 - t0);
}

template <class F>
nanoseconds measure(F fun)
{
	nanoseconds best_duration;

	for (size_t i = 0; i < 100; i++)
	{
		nanoseconds duration = measure_once(fun);
		if (duration < best_duration || i == 0)
		{
			best_duration = duration;
			i = 0;
		}
	}

	return best_duration;
}

template <class F>
void measure(char const* name, F fun)
{
	nanoseconds best_duration = measure(fun) - baseline;

	auto gbps = 1.0 * buffer_size * repeat / best_duration.count();
	cout << name << ": " << best_duration.count() << " ns (" << gbps << " GB/s)\n";
}

unsigned char* aligned_alloc(size_t size)
{
	auto buf = new unsigned char[size + 4096];
	uintptr_t offset = reinterpret_cast<uintptr_t>(buf) % 4096;
	buf += 4096 - offset;
	offset = reinterpret_cast<uintptr_t>(buf) % 4096;
	assert(offset == 0);
	return buf;
}

int main(int argc, char *argv[])
{
	auto ntdll = ::LoadLibraryW(L"ntdll.dll");
	MyRtlCopyMemory = reinterpret_cast<RtlCopyMemoryType*>(GetProcAddress(ntdll, "RtlCopyMemory"));
	MyRtlMoveMemory = reinterpret_cast<RtlCopyMemoryType*>(GetProcAddress(ntdll, "RtlMoveMemory"));

	buffer0 = aligned_alloc(buffer_size);
	buffer1 = aligned_alloc(buffer_size);

	baseline = measure([]() {});
	cout << "baseline: " << baseline.count() << " ns\n";

	measure("nothing", []() { });
	measure("memcpy", []() { memcpy(buffer0, buffer1, buffer_size); });
	measure("memmove", []() { memmove(buffer0, buffer1, buffer_size); });
	measure("char_copy", []() { char_copy(buffer0, buffer1, buffer_size); });
	measure("int_copy", []() { int_copy(buffer0, buffer1, buffer_size); });
	measure("avx_copy", []() { avx_copy(buffer0, buffer1, buffer_size); });
	measure("repmovsb", []() { repmovsb(buffer0, buffer1, buffer_size); });
	measure("__movsb", []() { __movsb(buffer0, buffer1, buffer_size); });
	measure("RtlCopyMemory", []() { MyRtlCopyMemory(buffer0, buffer1, buffer_size); });
	measure("RtlMoveMemory", []() { MyRtlMoveMemory(buffer0, buffer1, buffer_size); });

	return 0;
}

Damit bekomme ich (Haswell Xeon E3-1245 v3 @ 3.4 GHz)

// 1 GiB (x1)
memcpy: 173110767 ns (6.20263 GB/s)
memmove: 120273184 ns (8.92752 GB/s)
char_copy: 374367046 ns (2.86815 GB/s)
int_copy: 179932513 ns (5.96747 GB/s)
avx_copy: 173484789 ns (6.18926 GB/s)       <----------- ???
repmovsb: 121840513 ns (8.81268 GB/s)
__movsb: 121446265 ns (8.84129 GB/s)
RtlCopyMemory: 111961087 ns (9.59031 GB/s)  <----------- ???
RtlMoveMemory: 111988860 ns (9.58793 GB/s)  <----------- ???

// 2 MiB (x10)
memcpy: 1159800 ns (18.082 GB/s)
memmove: 943356 ns (22.2308 GB/s)
char_copy: 6663866 ns (3.14705 GB/s)
int_copy: 1953426 ns (10.7358 GB/s)
avx_copy: 1156177 ns (18.1387 GB/s)         <----------- ???
repmovsb: 943054 ns (22.2379 GB/s)
__movsb: 930677 ns (22.5336 GB/s)
RtlCopyMemory: 1125687 ns (18.63 GB/s)
RtlMoveMemory: 1130216 ns (18.5553 GB/s)

// 64 KiB (x100)
memcpy: 219161 ns (29.9031 GB/s)
memmove: 213425 ns (30.7068 GB/s)
char_copy: 2021047 ns (3.24268 GB/s)
int_copy: 535525 ns (12.2377 GB/s)
avx_copy: 217652 ns (30.1105 GB/s)
repmovsb: 215840 ns (30.3632 GB/s)
__movsb: 215538 ns (30.4058 GB/s)
RtlCopyMemory: 218859 ns (29.9444 GB/s)
RtlMoveMemory: 219161 ns (29.9031 GB/s)

// 4 KiB (x1000)
memcpy: 66412 ns (61.6756 GB/s)
memmove: 42866 ns (95.5536 GB/s)
char_copy: 1154064 ns (3.5492 GB/s)
int_copy: 324515 ns (12.6219 GB/s)
avx_copy: 31999 ns (128.004 GB/s)           <----------- ???
repmovsb: 42564 ns (96.2316 GB/s)
__movsb: 40753 ns (100.508 GB/s)
RtlCopyMemory: 69733 ns (58.7383 GB/s)
RtlMoveMemory: 69431 ns (58.9938 GB/s)

Also durchaus eigenartige Resultate

ps:
Falls du die Seite noch nicht kennst, SEHR COOLE Übersicht über die ganzen Intel Intrinsics:
https://software.intel.com/sites/landingpage/IntrinsicsGuide/#

pps: Beim avx_copy fehlen vermutlich noch irgendwelche Fences.

[dachschaden]

Bin gerade erst dazu gekommen, den Code mal nach C für Linux zu portieren.

Dein Code prüft ein paar Fälle, die wir in der Realität nicht supporten:
- die Kopierfunktion soll nur das Kopieren von Pages unterstützen. Das heißt: dest und src sind immer korrekt aligned (selbst AVX benötigt nur 32 Byte), ebenso wie die Länge. Sprich, wir haben nie kleinere Reste, die noch mitkopiert werden müssen.
- bei meinen AVX-Tests habe ich festgestellt, dass das non-temporal Schreiben (nicht Lesen) doppelt so lange dauert wie die Daten aus dem Cache zu senden. Daher habe ich in meiner AVX-Implementierung einfache Reads und Writes verwendet:

while(plength--)
{
        r1 = psrc[0];
        r2 = psrc[1];
        r3 = psrc[2];
        r4 = psrc[3];

        pdest[0] = r1;
        pdest[1] = r2;
        pdest[2] = r3;
        pdest[3] = r4;

        pdest += iterations;
        psrc  += iterations;
}

Um Optimierungen durch den Compiler vorzubeugen, habe ich die eigentlichen Kopierfunktionen in eine eigene Library gepackt, ohne LTO. Meines Wissens sollte das genug sein - schaue ich in das Kompilat, sehe ich dort auch den Funktionsaufruf von measure und die Funktionspointer in %esi geschoben.

Die Rtl-Funktionen habe ich auf Linux nicht, ein repmovsb war aber schnell gehackt:

void repmovsb
(
        type_dest dest,
        type_src src,
        size_t length
)
{
        __asm__
        (
                "rep movsd\n\t"
                :
                :"S"(src),"D"(dest),"c"(length / 4)
                :"memory"
        );
}

Iterations: 1000|Buffer size: 65536
memcpy    : 2407023 ns (27.226994 GiB/s)
memmove   : 2407597 ns (27.220502 GiB/s)
char_copy : 2419531 ns (27.086241 GiB/s) <---Wieso ...?
int_copy  : 2420056 ns (27.080365 GiB/s)
avx_copy  : 2449989 ns (26.749508 GiB/s)
repmovsb  : 2407616 ns (27.220288 GiB/s)

Iterations: 3|Buffer size: 1073741824
memcpy    : 803536257 ns (4.008812 GiB/s)
memmove   : 797947852 ns (4.036887 GiB/s)
char_copy : 1139965098 ns (2.825723 GiB/s)
int_copy  : 1142812474 ns (2.818682 GiB/s)
avx_copy  : 1146694691 ns (2.809140 GiB/s)
repmovsb  : 909587241 ns (3.541415 GiB/s)

Weitere Tests stehen noch aus - und so ganz vertraue ich den Berechnungen noch nicht, das werde ich mir noch mal anschauen, wenn mir nicht die Augen fast zufallen. Wobei ich eine Sache unbesehen glaube - dass memcpy bzw. memmove auf Linux so hochgezüchtet sind, dass sie repmovsb ohne Probleme schlagen.

Ach, und noch eine Sache: in diesem Thread ging es primär nicht um schnelles Kopieren von Daten, obwohl dieses im schlimmsten Fall notwendig wird, sondern um die Mapping-Verwaltung, die ich vorgeschlagen hatte. Ich habe diese nun implementiert und mit einem Produktivprogramm, was auf Linux bereits funktionierte, jetzt auf Windows getestet.

Stellt sich heraus, dass die Leute bei Microsoft die Vorteile von 64 Bit mal so gar nicht nutzen. Linux wie Windows haben im Userspace (der 47-Bit-Adressraum, der einem derzeit zur Verfügung steht) am Anfang einen Block Mappings, am Ende einen Block Mappings, und dazwischen gähnende Leere. Man sollte annehmen, dass für VirtualAlloc versucht wird, in dieser gähnenden Leere Speicher zu finden - aber anscheinend versucht das System eher, das Mapping so niedrig wie möglich anzulegen. Das ist natürlich kompletter Unsinn, denn wenn man nun versucht, ein weiteres Mapping danach anzulegen, um fortwährend Speicher zu reservieren, klappt das meist nicht, weil direkt nach dem eigenen Mapping ein reservierter/commiteter Block existiert. Und dann müssen wir Daten kopieren.

Ich habe bereits für beide Betriebssysteme Funktionen, mit der ich mir eine Mapping-Table ins Userspace ziehen kann. Unter Windows ist das allerdings der reine Overkill, da ich pro Region einmal einen Kernel-Call habe, um dann die Regioninformation aus den geschriebenen Daten zu ziehen.

Mein Plan war daher, dass ich mir die Speicherverwaltung unter 32-Bit- und 64-Bit-Prozessen ansehen und dann statisch den Beginn des leeren Blocks hinterlegen werde. Anstatt nun von Anfang an die Mappings durchzugehen, beginne ich am Anfang des Blocks zu suchen. Gleiches mache ich, wenn Mappings erfragt werden, die von oben nach unten wachsen sollen (Linux und Windows supporten das nativ, allerdings soll die Windows-Implementierung so ziemlich das langsamste im Universum sein), da fange ich dann halt von oben nach unten an zu suchen.

Irgendwelche Einwände?

EDIT: Für Linux habe ich bereits ein paar Änderungen eingefügt, die mir ein maps_binary für einen Prozess in procfs anlegen. Ich kann mir vorstellen, dass Leute jetzt vorschlagen werden, doch einen Treiber für Windows zu schreiben, der das Suchen nach freiem virtuellen Arbeitsspeicher durchführen soll.

Problem ist: bei Linux hatte ich ein bisschen Ahnung, was ich tat - bei Windows überhaupt keine. Deswegen stelle ich ja diese ganzen bescheuerten Fragen. Und einen Kerneltreiber zu schreiben wäre meines Erachtens eh Overkill, wobei ich noch nicht mal wüsste, wo da anfangen ...

EDIT2: Ach, das auch noch: Fences wären meines Wissens nur dann nötig, wenn das Schreiben non-temorary wäre. Da ich das aber nicht mache, wären diese nicht notwendig.

@hustbaer: Die Intrinsics-Seite kannte ich schon.