✔ [C] Liste sortieren. Threads verwenden?

KeDaiv · 30. Oktober 2008

Hallo, ich bin gerade dabei eine Liste in C zu implementieren. Hier mal kurz die Dateien, damit ihr mal ein Bild davon bekommt.

klist.h
mem_check.h
klist.c

Das sind zur Zeit meine 3 Dateien. Die eine nutze ich, um Speciherlecks zu vermeiden. Wenn ich die Liste dann fertig habe, wird diese natürlich entfernt.
Nun aber zu meinem kleinen aber feinen Problem. Wie ihr seht, möchte ich die Liste ja sortieren. Und das klappt auch schon recht gut mit mergesort. Aber um es speziell für manny Core CPU's zu beschleunigen, habe ich mir überlegt, den "Teile" - Schritt in Threads auszulagern. Das wäre so meine Idee. Jedoch weiß ich nicht so genau, ob das Punkte bringen würde und wie ich das genau realisieren soll, weiß ich auch noch nicht. Das nächste Problem besteht in der Rekursionstiefe. Ich habe ja eine unbestimmte Anzahl von Elementen in der Liste und da kann es auch passieren, dass der Stack durch die Rekursion irgendwann voll ist und dann habe ich ja ein Problem. Wie könnte man dieses Problem umgehen, oder behandeln geschweige denn bemerken? Und ebend hatte ich noch eine Frage im Kopf rum schwirren... Aber vlt fällt mir die ja noch wieder ein! ^^

Ich danke euch schon mal für eure Hilfe.
KeDaiv

KeDaiv · 31. Oktober 2008

Hmm... das mit den threads hab ich nun mal ausprobiert. Aber irgendwie mag das alles nicht so funktionieren, wie ich das gerne haben würde. Kompilieren tut er die threads. Aber er "bricht" im Programmlauf dann nacher einfach ab. Schaut einfach mal, bitte....
Noch mal gleich zu meiner Verteidigung, ich hab noch nie mit threads in C und unter Linux programmiert...

C:

void *klist_mergesort_threads( void *vptr_args ) {

	KList *list = ( KList * ) vptr_args;
	if( 1 == list->capacity ) {
		return NULL;
	}

	KList *right = klist_initList( list->type, list->resizeable,
			list->destroyElementUserFunction, list->compareUserFunction );
	klist_splitAt( list, right, ( list->capacity / 2 ) );

	pthread_t t1, t2;
	pthread_create(&t1, NULL, klist_mergesort_threads, (void *) list);
	pthread_create(&t2, NULL, klist_mergesort_threads, (void *) right);

	pthread_join(t1, NULL);
	pthread_join(t2, NULL);

	pthread_detach(t1);
	pthread_detach(t2);

	klist_merge(list, right);

	klist_removeList(right);
	free(right);

	return NULL;

}

/**
 * Sortiert eine Liste anhand des mergesort -
 * Sortieralgorythmus. Der comparor befindet
 * sich in der Liste
 */
void klist_mergesort( KList * const list ) {

	klist_mergesort_threads((void *) list);

	/**if( 1 == list->capacity ) {
		return;
	}

	KList *right = klist_initList( list->type, list->resizeable,
			list->destroyElementUserFunction, list->compareUserFunction );
	klist_splitAt( list, right, ( list->capacity / 2 ) );

	//Hier vlt threads starten
	klist_mergesort( list );
	klist_mergesort( right );

	//Listen werden gemerged
	klist_merge( list, right );

	//Tmp Listenkopf muss wieder freigegeben werden.
	klist_removeList( right );
	free(right);*/
}

deepthroat · 31. Oktober 2008

Hi.

Ich denke für jedes Element in der Liste zwei Threads zu starten ist nicht sehr sinnvoll. Erstens kann man nur relativ wenige Threads starten da diese Resource limitiert ist und außerdem ist dann der Aufwand der Verwaltung der Threads so hoch, das die Geschwindigkeit sicherlich drunter leidet.

Du solltest die Listen einfach in n Teile teilen (evtl. n == Anzahl an Prozessoren), dann die Teile parallel sortieren und danach zusammenführen.

Um ein überlaufen des Stacks zu vermeiden, würde es sinnvoll sein, statt eines rekursiven Algorithmus einen iterativen Algorithmus zu verwenden.

Gruß

PS: Ich hab das grad mal ausprobiert. Ich habe allerdings OpenMP und nicht direkt Pthreads verwendet. Kompilieren mit "gcc -fopenmp ...".

C:

#include <omp.h>

void klist_dosort(KList * list) { 
  if (list->capacity == 1) return;
  
  int splits = omp_get_max_threads();

  printf("nr of threads: %d\n", splits);

  int size = list->capacity / splits;

  if (size > 10) {
    KList** parts = calloc(splits, sizeof(KList*));
    int i;
    parts[0] = list;
    for (i = 0; i < splits; ++i) {
      KList* right =  klist_initList( list->type, list->resizeable,
			list->destroyElementUserFunction, list->compareUserFunction );
      klist_splitAt(list, right, size);
      
      parts[i] = list = right;
    }

#pragma omp parallel for shared(parts) private(i) schedule(static, 1)
    for (i = 0; i < splits; ++i) {
      klist_mergesort(parts[i]);
    }
    
    for (int i = 1; i < splits; ++i) {
      klist_merge(parts[0], parts[i]);
      klist_removeList(parts[i]);
      free(parts[i]);
    }
  } else {
    klist_mergesort(list);
  }
}

Gruß

KeDaiv · 31. Oktober 2008

Das mit openmp mag mein Compiler irgendwie nicht... Vlt habe ich das Packet nciht installiert...
Kanst du mir vlt sagen, welches Packet das unter linux ist?
Ansonnsten habe ich das nochmal mit pthreads probiert.
Das sieht dann so aus:

C:

void *klist_mergesort_threads( void *vptr_args ) {

	KList *list = ( KList * ) vptr_args;
	if( 1 == list->capacity ) {
		return NULL;
	}

	KList *right = klist_initList( list->type, list->resizeable,
			list->destroyElementUserFunction, list->compareUserFunction );
	klist_splitAt( list, right, ( list->capacity / 2 ) );

	static int count;

	if( count < 2 ) {
		count += 2;
		pthread_t t1, t2;

		pthread_create( &t1, NULL, klist_mergesort_threads, ( void * ) list );
		pthread_create( &t2, NULL, klist_mergesort_threads, ( void * ) right );

		pthread_join( t1, NULL);
		pthread_join( t2, NULL);

		count -= 2;
		pthread_detach( t1 );
		pthread_detach( t2 );
	}
	else {
		klist_mergesort_threads( ( void * ) list );
		klist_mergesort_threads( ( void * ) right );
	}

	klist_merge( list, right );

	klist_removeList( right );
	free(right);

	return NULL;

}

/**
 * Sortiert eine Liste anhand des mergesort -
 * Sortieralgorythmus. Der comparor befindet
 * sich in der Liste
 */
void klist_mergesort( KList * const list ) {

	static int count = 0;

	klist_mergesort_threads( ( void * ) list );

	/**if( 1 == list->capacity ) {
	 return;
	 }

	 KList *right = klist_initList( list->type, list->resizeable,
	 list->destroyElementUserFunction, list->compareUserFunction );
	 klist_splitAt( list, right, ( list->capacity / 2 ) );

	 //Hier vlt threads starten
	 klist_mergesort( list );
	 klist_mergesort( right );

	 //Listen werden gemerged
	 klist_merge( list, right );

	 //Tmp Listenkopf muss wieder freigegeben werden.
	 klist_removeList( right );
	 free(right);*/
}

Problem dabei ist nur, damit geh ich nun sicher, dass er nur noch 2 Threads startet.
Jedoch gibt es dabei noch ein Problem, nämlich, dass er nun nicht die aufrufe malloc und free überein stimmen...
Aber ansonsten muss ich sagen, zieht er nun dabei ziemlich viel ab.

Wenn ich nun noch weiß, wie das mit openmp ist, dann probier ich das auch nochmal aus...

deepthroat · 31. Oktober 2008

Hi.

Der GCC kann OpenMP ab Version 4.2 (vorher als Zusatzbibliothek libgomp).

Gruß

KeDaiv · 1. November 2008

hmm....
ich hab nur den gcc-4.1 drauf. Und werd auch in der nächsten Zeit nicht updaten. Das dauert mir immer zu lange... ^^
Die libgomp konnte ich nicht finden... -.-

Aber noch mal zu meinem kleinen code... ^^
Wie kommt es denn, dass nun nicht mehr die malloc und die free aufrufe stimmen?
Also, wenn ich das so sagen kann, Action ist auf meinen beiden CPU's. Nur kann ich bei ca 10Mio Daten nciht mehr wiklich prüfen, ob denn nun dort alles richtig sortiert ist, bzw ob auch wirklich noch alle Daten da sind.

deepthroat · 1. November 2008

KeDaiv hat gesagt.:
Aber noch mal zu meinem kleinen code... ^^
Wie kommt es denn, dass nun nicht mehr die malloc und die free aufrufe stimmen?

Weil du die Zugriffe auf die Zählvariable nicht gegen zeitgleiche Zugriffe schützt. Thread 1 will den Wert der Variable um 10 erhöhen und holt sich den Wert. Thread 2 will den Wert der Variablen auch erhöhen und holt sich den Wert. Jetzt speichern beide Threads den veränderten Wert ab - wobei der Wert sich allerdings nur um 10 und nicht um 20 erhöht hat. Da mußt du explizit synchronisieren mit einer Mutexvariablen.

KeDaiv hat gesagt.:
Also, wenn ich das so sagen kann, Action ist auf meinen beiden CPU's. Nur kann ich bei ca 10Mio Daten nciht mehr wiklich prüfen, ob denn nun dort alles richtig sortiert ist, bzw ob auch wirklich noch alle Daten da sind.

Warum nicht? 10 Mio ist doch gar nichts. Das solltest du eigentlich tun.

Gruß

KeDaiv · 1. November 2008

Ich werde mir das mal mit dieser Mutex Variablen anschaun.

Wegen dem prüfe... Das muss ich ja manuell machen. oder ich lass mir die alle ausgeben... ^^
Muss ich mal schaun!

deepthroat · 1. November 2008

KeDaiv hat gesagt.:
Ich werde mir das mal mit dieser Mutex Variablen anschaun.

Wegen dem prüfe... Das muss ich ja manuell machen. oder ich lass mir die alle ausgeben... ^^
Muss ich mal schaun!

Ja, am besten ausdrucken und drauf hoffen das es keine Endlosliste ist... ^^

Ich sprach natürlich von einem Check im Programm welches die Nachbedingung der mergesort Funktion kontrolliert.

Gruß

KeDaiv · 2. November 2008

thx... ^^
mit mutex das klappt doch alles!
Musste nur die Variable blocken, welche für das zählen der free und malloc aufrufe zuständig ist!

Also, danke nochmal...
Hatte nun eine Zeitersparnis beim sortieren von vorher ca 25sec und nu nachdem ich das auf den beiden CPU's laufen lasse von 17sec... also, 32% schneller! ^^
(Gemessen mit der Handur...

)
Thx dafür!

✔ [C] Liste sortieren. Threads verwenden?

KeDaiv

KeDaiv

deepthroat

Erfahrenes Mitglied

KeDaiv

deepthroat

Erfahrenes Mitglied

KeDaiv

deepthroat

Erfahrenes Mitglied

KeDaiv

deepthroat

Erfahrenes Mitglied

KeDaiv

Neue Beiträge