Datei-Sortierung

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.

FrEEzE2046

Ich lasse euch mal daran teilhaben, wie ich es nun umsetzen werde:

Aufgabenstellung:

Es ist ein Integer-Key mit n >= 4 Byte zu sortieren!

1. Laden der Datei in einer Puffer mit konstanter Page Ausrichtung. D.h.:
Größe der Page orientiert sich an einem Page Alignment,
Größe der Puffer hängt von Dateigröße ab:
z.B. Page Alignment = 1 MeBiByte, RecSize = 20 Byte
dann: Page Size = (Alignment / RecSize) * RecSize = 1048560 Byte

2. Radix-Sort von jedem Puffer:
Begonnen wird beim most significant Byte. D.h.:
Speicher-Position (z.B.) Buf[0=Puffer][0=PageElement] += (Vergleichslänge -1)
Es wird überprüft:
Selektiertes Byte & 0x80 wenn true, dann store in vector,
ansonsten 0x80 >> 1 (bis 0)
Soll heißen:
Ex existiert für jedes Bit ein Vector, d.h.:
Die ganze Datei wird zunächst in 8 vectoren aufgeteilt, welche die Adresse eines Schlüssels enthalten.
? Jetzt ist die Frage wie viele Bytes man weiter nach unten geht, da man im worst case immer das höchste Byte auf 0 hat ?
? Lösung wäre folgende: Wenn eine "unzureichende" Menge (oder gar 0) Elemente in den Vektoren liegen, wird das nächste Byte überpüft ?
? Großer Nachteil dabei: Dass darf erst am Ende festgestellt werden und kostet damit viel Zeit ?
? Generell alle Bytes durchzuzählen halte ich für kritisch: worst-case bei 16 Byte würde bedeuten, dass 128 Vektoren existiert ?
Lösung: Treshold einstellbar, ab welcher Grenze (bzw. Mindestgröße) Vektoren zusammengefasst werden
Dadurch ist die maximale Anzahl der Vektoren regulierbar

3. Übergabe der Vektoren an einen Thread Pool:
Es wird eine maximal Anzahl gleichzeitig parallel laufender Threads festgelegt. Jeder Thread sortiert einen Vektor (wieder nur die Adressen) mit dem QuickSort Algorithmus
Sobald ein Thread fertig ist, kann ein neuer Thread gestartet werden.
Die Vektoren sind aufsteigend sortiert. Es ist danach also kein Merging mehr nötig. Prinzipiell können die Daten nun rausgeschrieben
werden. Der Offset in der Datei ergibt sich aus Summe aller Elemente in den "niedrigeren" Vektoren * RecSize.

Fertig!

knivil

Da ich annehme, dass der begrenzende Faktor sowieso das Lesen und Schreiben der Daten ist, hier mein Vorschlag: 2 Threads. Der erste liest die Daten blockweise und uebergibt den Record an einen zweiten Thread. Dieser fuegt den Record in eine Map bei geeignetem Vergleichskriterium ein. Das sollte wesentlich weniger Zeit beanspruchen, als Daten von der Platte gelesen werden. Nach dem Einlesen wird einfach ueber die Map iteriert (sind dann sortiert) und herausgeschrieben. Damit nicht staendig new aufgerufen wird, kann man sich noch was ausdenken, aber das ist erstmal nebensaechlich ... Im Prinzip ein Producer-Consumer-Problem.

FrEEzE2046

Ich habe da nun noch ein Problem. Ich würde gerne den Radix-Sort für jeden Puffer durchführen,
direkt nachdem er gelesen wurde. D.h.:

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

  RadixSort(*(buf + i));
}

Dieser RadixSort stellt einen eigenen Thread da. Als Resultat speichere ich die Adresse
eines Records in Vektoren; es wird nach Bitmuster einsortiert.

Nun die Frage: Ist std::vector thread-safe? Es könnte sonst dazu kommen, dass auf ein und
den selben Vektor ein push_back zur gleichen Zeit ausgeführt wird ... muss ich mir da
Gedanken machen (eigene thead-sichere Variante von push_back) oder geht das?