Datei-Sortierung

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

[FrEEzE2046]

So,

ich wollte mir zur erleichterten Errechnung des Offsets in meiner Sort-Funktion (egal welche) einen kleinen Iterator schreiben.
Dies habe ich auch gemacht. Mit einem Interator-Interface und der entsprechenden Ableitung für meine Puffer-Variante.

Ist natürlich denkbar blöd, da der Compiler - zur Sicherheit - nicht inlinen wird und über die vtable geht. Ich will dass ganze nur aus Bequemlichkeit verwenden; aber nur dann, wenn es keine Performancenachteile mitsich bringt. Dass ist in dem Fall aber so. Daher dachte ich mich, dasss ich mich dafür CRTP bediene und habe das jetzt mal ganz abgespeckt so gemacht:

template<
	class Derived
>
class iterator_interface 
{
	typedef typename Derived::TYPE T;

public:
	inline T* operator++ () {
		return reinterpret_cast<Derived*>(this)->PreInc();
	}

	inline T* operator++ (
		int 
	) {
		return reinterpret_cast<Derived*>(this)->PostInc();
	}

	inline operator T*() {
		return reinterpret_cast<Derived*>(this)->Convert();
	}
};

template<
	typename T
>
class buffer_iterator : public iterator_interface<buffer_iterator<T>>
{
private:
	T**	   base;
	size_t buf_count,
	       page_elem,
		   idx;

	inline T* get() {
		return *(base + static_cast<int>(idx / page_elem)) + (idx % page_elem);
	}	

public:
	typedef T TYPE;

	buffer_iterator(
		T**    pbase,
		size_t bufcnt,
		size_t pageelem
	) : base(pbase), buf_count(bufcnt), page_elem(pageelem), idx(0) {}	

	inline T* PreInc() 
	{
		idx++;
		return get();		
	}

	inline T* PostInc() 
	{
		T* retval = get();
		idx++;
		return retval;
	}	

	inline T* Convert()  {
		return get();
	}
};

Ich erhalte aber den Fehler:

'TYPE' : is not a member of 'buffer_iterator<T>'

Warum?

[volkard]

FrEEzE2046 schrieb:

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

Du wechselt öfters den Kontext. Mal mit Standard, mal mit multithreading, mal int als Schlüssel, mal ohne. Da gehe ich netterweise mit. Und die Postings sind dann wie die Suren des Nostradamus. Und "thread pool" und "3-wege-quicksort" und ganz viel steht in google.

FrEEzE2046 schrieb:

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

Schreib halt shattered und hoff aufs NCQ. Verschiedene Sub-Arrays werden zu verschiedenen Zeiten fertig, da wäre es unlecker aufs Rausschreiben warten zu müssen, bis der letzte fertig ist.

[FrEEzE2046]

volkard schrieb:

Du wechselt öfters den Kontext. Mal mit Standard, mal mit multithreading, mal int als Schlüssel, mal ohne. Da gehe ich netterweise mit. Und die Postings sind dann wie die Suren des Nostradamus. Und "thread pool" und "3-wege-quicksort" und ganz viel steht in google.

Nein,

da hast du mich falsch verstanden. Ich favorisiere weiterhin eien multi threaded Lösung.

Das mit "mal int als Schlüssel, mal ohne" ... da reden wir aneinander vorbei.

Also:
Ich habe keine EINFACHEN INTEGER als Schlüssel; damit meine ich 4 Byte Ganzzahl-Typen. Ich habe aber durchaus ganzzahlige Typen mit mehr als 4 Byte (bis zu 32).

Das heißt, dass ich prinzipiell Integer vergleichen tue, aber eben nicht nur einen (beginnend mit dem signifikantesten DWORD).

Bzgl der CRTP Geschichte:
Ja, ich weiß, dass der Compiler zur Kompilier-Zeit die Ableitung noch nicht kennt und daher der Error kommt. Ich suche eine Möglichkeit das zu umgehen.