Datei-Sortierung

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.

FrEEzE2046

Also zumindest das sort aus der STL hat mehrere Probleme:

1. Ich kenne den Typ nicht (ist im Endeffekt ein byte array für mich)
2. Ich habe puffer + pages und keinen linearen speicher

volkard

FrEEzE2046 schrieb:

Was ist deine Meinung? Auf ein Intro mit Radix,

Ja, radix. Sofern die führenden Bytes einigermaßen gleichverteilt sind. Das mußt Du wissen. Weiß ich nicht.
Wenn Du nichts weißt, dann gleich 3WQS.

FrEEzE2046 schrieb:

dann QuickSort setzen?

Für int vielleicht bis hinten hin radix. Quicksort eher nicht nativ nehmen, immer aufpeppen, daß der worst case nicht zuschlagen kann. Und Quicksort nicht bis hinten hin.

FrEEzE2046 schrieb:

Multi-Threaded fahren?

Logo! Multi-Threading ist das einzige, was hier viel rausholt. Alles andere sind nur Randüberlegungen, die nur ein paar Prozent bringen.

FrEEzE2046 schrieb:

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.

Wie kannste die anderen drei Kerne auslasten?
a) Array in 4 Teile teilen, jeden Kern eins machen lassen, danach einen Kern das Zeug mergen lassen. Klingt unlecker.
b) Radixintro kopiert in 256 Unterarrays, Threadpool. Am Schluß nichtmal zurückkopieren, einfach schon die Datendinge machen. Radixintro und Laden ist eins. Oh, es existiert gar kein großes Array. Klingt lecker.

Also mal b) nehmen.
Was passiert, wenn man pechhabenderweise in der Radixintro nicht spaltet, weil alle gleich anfangen? Zum Beispiel lauter ints zwischen 0 und 16777000. Ich würde sagen, das macht nichts, einfach weiter radixen, denn nach vier radixebenen ist man fertig, das ist ja viel netter als 24 quicksortebenen. radix inplace oder kopierend machen? ka. mini-array natürlich nicht mit radix. Wenn das Array nur noch 100 Elemete hat, per quicksort (randomisiert?) spalten lassen und mini-arrays mit weniger als 20 Elemeten per insertion sort. Ja, mit dem threadpool klingt das recht harmonisch und eichfach zu implementieren.

Für den Fall daß die keys so mini sind, sie vielleicht doch in die Sortierdinger kopieren?

Kann man die Zeit, die unparallel läuft, noch senken? Man kann parallel die Datei auslesen, aber dann nur in ein Array und kann nicht zugleich spalten.
Am Ende kann man parallel schreiben! Also nach dem ersten Spalten ist man parallel bis ganz hinten hin. Vielleicht würde ich erstmal die Datei ganz einlesen und firstbytes zählen lassen (parallel). Schnell die firstbytes addieren. Dann unparallel spalten. Ab dann alles parallel.

FrEEzE2046

Ist keineswegs böse gemeint, aber du schreibst manchmal ein wenig in Rätseln.

Hier mal das was ich mitgenommen habe:
"Denn nach vier readixebenen ist man fertig" ... ich soll also das erste DWORD nehmen und in radixebenen aufteilen.
"Wenn das array nur noch 100 Elemente hat per quicksort spalten lassen" ... wieso sollte das array kleiner werden? ("nur noch") | wie soll ich das per quicksort "spalten"

Wichtige Frage: Wie genau sieht bei dir dieser Threadpool aus?

"Am Ende parallel rausschreiben" ... was soll das bringen? Die Festplatte hat nur einen Schreib-/Lesekopf.