Datei-Sortierung

[FrEEzE2046]

Guten Morgen,

ich suche nach der - wirklich - schnellsten Möglichkeit eine Datei zu sortieren.
Welche möglichkeiten habe ich da mit STANDARD MITTELN. Wie man eine Datei selbst sortiert, weiß ich auch

[volkard]

FrEEzE2046 schrieb:

Guten Morgen,
ich suche nach der - wirklich - schnellsten Möglichkeit eine Datei zu sortieren.
Welche möglichkeiten habe ich da mit STANDARD MITTELN. Wie man eine Datei selbst sortiert, weiß ich auch

Ohne alles: introsort oder mergesort
Nach was sortieren? Zeilenweise lexikographisch? Oder Byteweise? Oder Records fester Länge? Paßt die Datei locker ins RAM? Ist eine Vorsortierung zu erwarten? Wieviele Kerne hast Du zur Verfügung? Welches BS?

[FrEEzE2046]

Favorisiere quick sort. Vergleich erfolgt byteweise. Records unterschiedlicher Länge werden erwartet.

Kernanzahl ist nicht fixierbar; bis zu 4 sind aber möglich, sollte daher auch multi-threaded (mit anschließendem merge) laufen.
BS: Windows XP - Windows 7; Windows Server 2003 - 2008

Propriertäre Lösung wollte ich mal gegen eine Variante mit Standard Klassen halten.

[volkard]

FrEEzE2046 schrieb:

Propriertäre Lösung wollte ich mal gegen eine Variante mit Standard Klassen halten.

Immer noch nicht genug Daten. Da Du nicht alle Tricks kennst, aber alle passenden Tricks empfohlen haben möchstest, kannst Du nicht auswählen, welche Daten für uns wichtig sind. Also leg das Format und die zu erwartenden Datenverteilung der Meßdatei offen.
So kann ich noch nichtmal zwischen hauptsächlich quicksort(also introsort, du Nase) und hauptsächlich mergesort abschätzen.
Also mal ein paar Allgemeinplätze: Nach Möglichkeit malloc/free bzw. new/delete sparen oder beschleunigen. Das macht splitten und mergen auch bei kleineren Größen so interessant, insbesondere den 256-Splitter. Eigener small object allocator ist nett. Bei Multithreading jedem Thread einen eigenen Speicherbereich geben. Freigabe dem memory pool überlassen. Vielleicht non-copy-strings verwenden, also Ranges auf fremden Speicher, zur Not auf die vorher komplett eingelesene Datei oder einen teil davon. Wir wollen ka kein filemapping nehmen *heul*. Wenns zu viel für's RAM ist, mergesort. Kleine Happen quicksort, aufpassen, RAM ist lahm, vielleicht nur Happen bis zur Größe des Prozessorcaches per quicksort. Kleine Reste per insertion sort, also quicksort einfach nicht bis unten absteigen lassen. Immer ein radix sort im Ärmel haben und Gegentesten. Warum nicht erstmal in einem Rutsch in 256 Dateien spalten (und gleichzeitig für jede Datei ein Histogramm der Verteilung der zweiten Bytes erstellen (256 integers wiegen ja nichts) und bei guter Datenlage und wenn groß genug, rekursiv runtergehen). Drei-Wege-Quicksort. Wie weit bringen einen die klassischen Künste wie natürliches mergesort und mehrere merge-Dateien (also ein Mini-Heap im RAM)? Sollte eigentlich BS-Aufrufe und String-Ende-Suchen sparen.
Alles hängt von der Verteilung ab.

[TheTester]

volkard schrieb:

[...]
Alles hängt von der Verteilung ab.

Würde es dir etwas ausmachen, dass in diesem Kontext näher auszuführen?

[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.