[Risolto] Problema QuickSort in C

Se avete dubbi o domande sulla programmazione in generale, fatele qui
Rispondi
nierro
Little John
Messaggi: 1019
Iscritto il: 19 novembre 2009, 17:51
Architettura: x86_64 (64bit)

[Risolto] Problema QuickSort in C

Messaggio da nierro » 10 aprile 2014, 14:02

Ciao a tutti!
C'è qualche anima pia in grado di spiegarmi dove sbaglia l'algoritmo per il QuickSort scritto in C (utilizzando le liste perché sono masochista) e, in teoria, multithreaded?
https://github.com/FedeDP/Sorting/blob/ ... uicksort.c

Non capisco perché sia cosi dannatamente lento...e se gli do 1000 interi va in segfault. Se diminuisco il numero di thread (a 5), almeno i 1000 interi me li fa...ma è lentissimo.
Idee su dove sbaglio? (ovviamente tutto sarà sbagliato già lo so :D )
Ovviamente non multithreaded è comunque lentissimo. (https://github.com/FedeDP/Sorting/blob/ ... oubleptr.c )

Grazie!

ps: non sono esercizi di uni o chissà che, ovviamente. Sto solo giochicchiando un po' ;)
Ultima modifica di nierro il 10 aprile 2014, 23:19, modificato 1 volta in totale.

nierro
Little John
Messaggi: 1019
Iscritto il: 19 novembre 2009, 17:51
Architettura: x86_64 (64bit)

Re: Problema QuickSort in C

Messaggio da nierro » 10 aprile 2014, 23:19

Ok, trovata la soluzione.
Riporto pari pari la risposta di un mio cerchiato su g+:

Pointer aliasing. Ogni volta che devi passare da un elemento della lista al successivo il processore deve caricare il valore del puntatore in un registro, chiedere il valore della locazione di memoria indirizzata da quel puntatore, caricare la struttura in cache e poi accedervi.

Siccome fai una malloc per ogni elemento della lista non hai la certezza che questi siano inseriti in memoria in locazioni contigue e quindi fai continuamente cache trashing spostando avanti e indietro dati da e per la memoria centrale.

Se usi gli array sfrutti meglio la cache e quindi hai prestazioni migliori.

Se sei preoccupato per l'eventualità di avere un numero arbitrario di oggetti da ordinare sappi che la chiamata realloc ti consente di avere comunque il più grande vantaggio che ti danno le liste: poter gestire un numero di elementi variabile a runtime.

Rispondi