Datei-Sortierung

FrEEzE2046

Ich hab Dateien die 50 - maximal 150 MB groß sind. Die Sortierung läuft auf PCs mit lediglich 512 MB RAM, aber auch auf Servern mit deutlich mehr (spielt bei der Dateigröße nicht die große Rolle).

Grundsätzlich binäre Dateien, enthalten zum Teil aber auch Strings. Es handelt sich um Index-Dateien einer Datenbank. D.h. sie enthalten den Index und die Position in der Datenbank (4 Byte + n).

Mein bisheriges Verfahren (was ich nicht offen legen kann) benötigt für eine 70 MB Datei mit einer 20 Byte Struktur (nur Integer-Werte) 8 Sekunden mit nur einem Thread.

Ich muss aber bei der gleichen Struktur auf ca. 2 Sekunden runterkommen. Ich verwende einen normalen quick sort um das schon mal zu sagen. Ich würde die Datei jetzt in Abschnitte (im Speicher) unterteilen und mit 4 Threads sortieren lassen. Im Anschluss wäre dann noch ein Merge fällig.

Ich erwarte hier keine vollständige Lösung. Mir reicht die Nennung einer schnellen Möglichkeit oder eines schnellen Verfahrens.

FrEEzE2046

Was mich interessieren würde:

Wofür sollte ich einen eigenen Allocator brauchen?
Bisher bin ich so verfahren, dass ich eine 2D Matrix erstellt habe, welche die Datei für mich hält.

Also so ungefähr:

unsigned char** buf = new unsigned char*[n1]();
for( int i = 0; i < n1; i++ )
     *(buf + i) = new unsigned char[n2]();

Das gebe ich am Ende wieder frei ... mehr nicht.

Ich versuch mal wieder zu geben, was du meinst:
Eigenen Memory Pool zu beginn schaffen. Eine Allocator funktion benutzen, um Speicher aus diesem Pool zu allokieren.
Das ganze dient der beschleunigten SPeicher Allokierung und verminderter Heap-Fragmentierung.

Das bringt aber doch auch nur was, wenn ich ständig Speicher allokieren, "freigeben" würde.

volkard

FrEEzE2046 schrieb:

Eigenen Memory Pool zu beginn schaffen. Eine Allocator funktion benutzen, um Speicher aus diesem Pool zu allokieren.
Das ganze dient der beschleunigten SPeicher Allokierung und verminderter Heap-Fragmentierung.

Und ist unendlich einfach

void* DatenDing::operator new(size_t size){
   void* old=thePointer;
   thePointer+=size;
   return old;
}
void DatenDing::delete(){
   assert(false);
}

und auch bei einer Verwendung endlos schnell.

FrEEzE2046 schrieb:

Das bringt aber doch auch nur was, wenn ich ständig Speicher allokieren, "freigeben" würde.

Ich hatte Befürchtungen, das könnte immer wieder vorkommen, wenn ein Teil der Datei gelesen wird.
Aber die gesamten Daten passen ja ins RAM. Da dürfte das normale new kaum meßbar teurer sein. Macht nichts, ich wollte das bestellte Optimum suchen.

[cpp]
unsigned char** buf = new unsigned char*[n1]();
for( int i = 0; i < n1; i++ )
     *(buf + i) = new unsigned char[n2]();
[/cpp]

Ist n2 etwa fest?

volkard

FrEEzE2046 schrieb:

Grundsätzlich binäre Dateien, enthalten zum Teil aber auch Strings. Es handelt sich um Index-Dateien einer Datenbank. D.h. sie enthalten den Index und die Position in der Datenbank (4 Byte + n).

also

struct{
   char schluessel[n];
   char daten[4];
}

und die schluessel sind eindeutig, also keiner kommt in einer Datei zweimal vor?

FrEEzE2046

n1 ist die Anzahl der Puffer und n2 die Page größe. Also demnach fest.
Ich habe schon überlegt, die Datei komplett in den Speicher zu laden und dann lediglich eine linked list umzusortieren, die auf die Speicherbereiche zeigt. Dann schreib ich die Datei einfach anhand der Angaben in der liste heraus.

Geht doch schneller als die kompletten Structs umkopieren zu müssen.

volkard schrieb:

Und ist unendlich einfach
void* DatenDing::operator new(size_t size){
   void* old=thePointer;
   thePointer+=size;
   return old;
}
void DatenDing::delete(){
   assert(false);
}
und auch bei einer Verwendung endlos schnell.

Kannst du das mal näher erläutern? Ich muss doch am Anfang zwingend mit "new" den memory pool allokieren ... wie kann das schneller sein?

Zudem verstehe ich deinen Code nicht. Sry, wenn ich mich doof anstelle.

volkard schrieb:

und die schluessel sind eindeutig, also keiner kommt in einer Datei zweimal vor?

Die Schlüssel können eindeutig sein (Primary Key) müssen aber nicht (Sekundär)

FrEEzE2046

Ich verfahre jetzt wie folgt:

1. Speicher für gesamte Datei allokieren und in den Arbeitsspeicher laden.
2. array mit Adressen auf die einzelnen Records erstellen und sortieren (verglichen werden dann natürlich weiterhin die referenzierten Werte, aber ich muss lediglich 4 Byte umkopieren)
3. Nach der Sortierung der Adressliste werden nacheinander die Werte in einen AUsgabepuffer kopiert und letztendlich in die Datei geschrieben.

Es würde mich noch freuen, wenn du die Sache mit dem Memory Pool näher erklären könntest; denn ich verstehe den Vorteil weiterhin nicht.

Besten Dank schon mal.

volkard

FrEEzE2046 schrieb:

Es würde mich noch freuen, wenn du die Sache mit dem Memory Pool näher erklären könntest; denn ich verstehe den Vorteil weiterhin nicht.

Der wäre nett gewesen, wenn Du innerhalb einer Schleife new gebraucht hättest. Damit legt man mit vielen pseudo-news Speicher an, undem man ihn vom einmal vorher gesaugten großen Speicher abzwackt. Und man gibt ihn nicht durch kerrespendierende viele deletes frei, sondern am ende durch ein großes delete.
Ist aber hier Unfug, weil Du durch festes n2 spätestens anhand der Dateigröße ja die Anzahl der Arrayelemente vorher recht genau kennst.

volkard

FrEEzE2046 schrieb:

1. Speicher für gesamte Datei allokieren und in den Arbeitsspeicher laden.
2. array mit Adressen auf die einzelnen Records erstellen und sortieren (verglichen werden dann natürlich weiterhin die referenzierten Werte, aber ich muss lediglich 4 Byte umkopieren)
3. Nach der Sortierung der Adressliste werden nacheinander die Werte in einen AUsgabepuffer kopiert und letztendlich in die Datei geschrieben.

Klingt sehr schnell.
Aber warum werden nur die Referenzierten Werte verglichen?
Ich dachte, die Schlüssel seien int. Dann isses vermutlich besser, du baust ´

struct Sortierding{
   int key;
   int dateiindex;
   friend bool operator<(Sortierding const& a,Sortierding const& b){
      return a.key<b.key;
   }
};

und sortierst die. Da muß zwar mehr kopiert werden, aber es dürfte viel häufiger Cache-Treffer geben, also Du triffst mächtig oft Daten, die bereits im Prozessorcache liegen, und muß nicht so oft aufs zehnmal langsamer RAM zugreifen.

knivil

Ich habe das Sortierkriterium noch nicht ganz mitbekommen.

Geht doch schneller als die kompletten Structs umkopieren zu müssen.

Hast du das schon umgesetzt und es dauert trotzdem 8 sec oder ist es nur ein Gedanke von dir? Klar ist es schneller, Zeiger zu sortieren. Wobei man abwaegen muss, wie teuer eine Zeigerdereferenzierung im Vergleich zu einem Kopiervorgang ist. Falls es immer noch nicht reicht, gibt es spezielle Sortierverfahren wie radixsort. Aber da must du schauen, ob die Voraussetzungen in deinem Fall erfuellt sind.

volkard

FrEEzE2046 schrieb:

3. Nach der Sortierung der Adressliste werden nacheinander die Werte in einen AUsgabepuffer kopiert und letztendlich in die Datei geschrieben.

Kann nach Deinen Angaben knapp werden, wenn Du für zweimal Daten zweimal 150M brauchst und nur 512M hast und auf dem Server noch so ein dämlicher Virenscanner läuft. Wollte nur sagen, daß der Schritt 3 auch inplace in O(n) geht. Das wäre nicht so schnell wie mit Zusatzspeicher, aber vieel schneller als ins Thrashing zu geraten oder n durcheinanderene Dateilesezugriffe zu machen.

FrEEzE2046

Bin am hin und her überlegen:

Ich fahre ja einen QuickSort. Diesen zu beschleunigen gelingt eigentlich nur durch eine Vorsortierung. Diese habe ich mir folgendermaßen vorgestellt:

void* presort(
	char*  source,
	char*  dest,
	size_t elSize,
	size_t beg,
	size_t end,
	size_t mask = 0xFF
)
{
	std::vector<char*>* idx = new std::vector<char*>[mask+1]();
	source += (end * elSize) - 1;
	end -= beg;

	do
	{

		(idx + (*source & mask))->push_back(source);
		source -= elSize;
	}
	while( --end );

	for( unsigned i = 0; i <= mask; i++ )
	{
		if(	!(idx + (*source & mask))->empty() )
		{
			for( unsigned j = 0; j < (idx + (*source & mask))->size(); j++ )
			{
				memcpy(
					reinterpret_cast<char*>(dest) += (i * elSize),
					(idx + (*source & mask))->at(j),
					elSize
				);
			}				
		}
	}

	return dest;
	delete[] idx;
}

Es wird also nach dem most significant byte ein index erzeugt, der die Speicheradressen der Sortiermenge hält.
Danach werden die referenzierten Speicherstellen in dest kopiert.

Diesen Vorgang würde ich an folgender Stelle einsetzen:

unsigned char *tmp = new unsigned char[n2](), *paddr;
unsigned char** buf = new unsigned char*[n1]();
for( int i = 0; i < n1; i++ ) {
     *(buf + i) = new unsigned char[n2]();
}

DWORD dwBytesRead = 0;
for( UINT i = 0; i < n2; i++ )
{
	ReadFile(
		hFile,
		*(buf + i),
		n1,
		&dwBytesRead,
		NULL
	);

	tmp = presort(
		*(buf + i),
		tmp,
		-1,
		-1
	);

	paddr = tmp;
	tmp = *(buf + i); 
	*(buf + i) = paddr;
}

So ungefähr jedenfalls. Nachteilig ist wohl die Verwendung vom STL-Container vector oder?

knivil

QuickSort

Schon mal die Sortierroutine der STL benutzt? QuickSort hat quadratische Laufzeit im worst case.

Nachteilig ist wohl die Verwendung vom STL-Container vector oder?

Nein, warum?

reinterpret_cast<char*>(dest)

Verstehe ich nicht, dest ist doch schon vom Typ char*.

FrEEzE2046

knivil schrieb:

Verstehe ich nicht, dest ist doch schon vom Typ char*.

Ist ja auch quatsch. Hab ich mal eben so dahin geschrieben.
Die STL-Routinen sind etwas langsamer ... ich will aber schneller werden

Verwendung von STL-Containern nachteilig? Ich denke mal, dass das im Vergleich ziemlich langsam sein könnte.
Ohne nach zu schauen behaupte ich mal, dass vector immer wieder neuen speicher vom heap allokiert.

FrEEzE2046

volkard schrieb:

struct Sortierding{
   int key;
   int dateiindex;
   friend bool operator<(Sortierding const& a,Sortierding const& b){
      return a.key<b.key;
   }
};

Der Schlüssel ist kein einfacher Integer, sondern kann ein bis zu 100 Byte langer Composite Key sein. Ich unterscheide ansonsten nur zwischen Integer und String (wegen litte- und bigendian). Zum Vergleich benutze ich z.B. folgende Funktion:

push	edi
		push	esi
		push	ebx

		xor		ebx, ebx

		test	ecx, 0xFFFFFFFC
		lea		esi, DWORD PTR [eax+ecx-1]
		lea		edi, DWORD PTR [edx+ecx-1]
		jz		__Bytes

		sub		esi, 3
		sub		edi, 3

__DWORDs:
		mov		eax, DWORD PTR [esi]
		mov		edx, DWORD PTR [edi]

		cmp		eax, edx
		jnz		__Final

		sub		esi, 4
		sub		edi, 4
		sub		ecx, 4

		test	ecx, 0xFFFFFFFC
		jnz		__DWORDs
		test	ecx, ecx
		jz		__Final

		add		esi, 3
		add		edi, 3

__Bytes:
		movzx	eax, BYTE PTR [esi]
		movzx	edx, BYTE PTR [edi]

		dec		esi
		dec		edi

		cmp		eax, edx
		jnz		__Final

		dec		ecx
		jnz		__Bytes

__Final:
		seta	bl
		sbb		ebx, 0
		mov		eax, ebx

		pop		ebx
		pop		esi
		pop		edi

Das wäre für den Integer Vergleich gedacht. Die Vergleichsfunktion übergebe ich per Template-Argument um dem Compiler die Chance zu geben die Funktion an die Aufrufstelle zu kopieren (inlinen); das fällt bei einem Funktionsobjekt weg.

Damit war ich dann noch mal 1 Sekunde schneller als vorher^^.
Der Vergleich macht ziemlich viel aus (= ich war schon bei 24 Sekunden, was nur am Vergleich hängt).

volkard

std::vector kann im Zugriff nicht unterboten werden. Kannst sogar auch noch vorher so viel Speicher anlegen, wie Du brauchst.
Und für zufällige ints kannste std::sort auch vermutlich nicht unterbieten, wenn Du bei einem vergleichenden Sortieren bleibst. Insbesondere reißt keine Quicksort-Implemetierung. Ich habs mit etlichen probiert.
Aber zum Glück darfst Du radix sort und Co ausprobieren.

FrEEzE2046

volkard schrieb:

Klingt sehr schnell.
Aber warum werden nur die Referenzierten Werte verglichen?
Ich dachte, die Schlüssel seien int. Dann isses vermutlich besser, du baust

Wenn die Schlüssel int (4 Byte) wären, wäre es nicht gerade sinnvoll einen (4 Byte) Pointer zu nehmen, der dann auch noch dereferenziert werden muss
So leicht ist es leider nicht.

Was willst du sonst noch vergleichen? Evtl. verstehen wir uns gerade falsch.

FrEEzE2046

volkard schrieb:

std::vector kann im Zugriff nicht unterboten werden. Kannst sogar auch noch vorher so viel Speicher anlegen, wie Du brauchst.
Und für zufällige ints kannste std::sort auch vermutlich nicht unterbieten, wenn Du bei einem vergleichenden Sortieren bleibst. Insbesondere reißt keine Quicksort-Implemetierung. Ich habs mit etlichen probiert.
Aber zum Glück darfst Du radix sort und Co ausprobieren.

Meinst du jetzt, dass std::sort so unfassbar schnell ist oder, dass allgemein ein QuickSort nicht der schnellste ist?

Radix-Sort wäre doch ein gutes Intro für den QuickSort oder?
Die ganze Datei mit Radix sortieren ... dafür sind manche Keys zu lang würde ich sagen oder?

Das "presort" wie ich's vorgestellt habe, ist ja eine light variante von radix (im weitesten Sinne).

volkard

FrEEzE2046 schrieb:

Ich unterscheide ansonsten nur zwischen Integer und String (wegen litte- und bigendian).

Vielleicht besser, Du drehst die Schlüsselbytes beim Laden um, um optimal schnell vergleichen zu können.
Strings riechen stark nach Drei-Wege-Quicksort. Für wenn der Schlüssel doch nur ein int ist, radix.

volkard

FrEEzE2046 schrieb:

Meinst du jetzt, dass std::sort so unfassbar schnell ist oder, dass allgemein ein QuickSort nicht der schnellste ist?

Für zufällige ints meine ich beides, wobei mir klar ist, daß introsort im Kern ein quicksort ist.

FrEEzE2046

volkard schrieb:

FrEEzE2046 schrieb:

Ich unterscheide ansonsten nur zwischen Integer und String (wegen litte- und bigendian).

Vielleicht besser, Du drehst die Schlüsselbytes beim Laden um, um optimal schnell vergleichen zu können.
Strings riechen stark nach Drei-Wege-Quicksort. Für wenn der Schlüssel doch nur ein int ist, radix.

Ich kann auch so optimal schnell vergleichen (siehe ASM-Code). Das nimmt sich da nichts.

Was ist deine Meinung? Auf ein Intro mit Radix, dann QuickSort setzen? Multi-Threaded fahren? Würde gerne mal deine Meinung hören. Gehen wir aber mal davon aus, dass wir nur Integer (aber eben bis zu 32 Byte lange) haben.