Existen ciertos algoritmos cuyo tiempo de ejecución puede disminuir significativamente cuando se divide una tarea y se hace cada parte en paralelo. Uno de estos algoritmos es el tipo de fusión, donde una lista se divide en partes infinitesimalmente más pequeñas y luego se recombinan en un orden ordenado. Decidí hacer un experimento para probar si podía o no aumentar la velocidad de este tipo mediante el uso de varios hilos. Estoy ejecutando las siguientes funciones en Java en un Dell de cuatro núcleos con Windows Vista.¿Por qué mi algoritmo de ordenación multihilo no es más rápido que mi mergesort de un solo hilo?
Una función (el caso de control) es simplemente recursiva:
// x is an array of N elements in random order
public int[] mergeSort(int[] x) {
if (x.length == 1)
return x;
// Dividing the array in half
int[] a = new int[x.length/2];
int[] b = new int[x.length/2+((x.length%2 == 1)?1:0)];
for(int i = 0; i < x.length/2; i++)
a[i] = x[i];
for(int i = 0; i < x.length/2+((x.length%2 == 1)?1:0); i++)
b[i] = x[i+x.length/2];
// Sending them off to continue being divided
mergeSort(a);
mergeSort(b);
// Recombining the two arrays
int ia = 0, ib = 0, i = 0;
while(ia != a.length || ib != b.length) {
if (ia == a.length) {
x[i] = b[ib];
ib++;
}
else if (ib == b.length) {
x[i] = a[ia];
ia++;
}
else if (a[ia] < b[ib]) {
x[i] = a[ia];
ia++;
}
else {
x[i] = b[ib];
ib++;
}
i++;
}
return x;
}
El otro está en la función 'run' de una clase que se extiende hilo de rosca, y de forma recursiva crea dos nuevos temas cada vez que se llama:
public class Merger extends Thread
{
int[] x;
boolean finished;
public Merger(int[] x)
{
this.x = x;
}
public void run()
{
if (x.length == 1) {
finished = true;
return;
}
// Divide the array in half
int[] a = new int[x.length/2];
int[] b = new int[x.length/2+((x.length%2 == 1)?1:0)];
for(int i = 0; i < x.length/2; i++)
a[i] = x[i];
for(int i = 0; i < x.length/2+((x.length%2 == 1)?1:0); i++)
b[i] = x[i+x.length/2];
// Begin two threads to continue to divide the array
Merger ma = new Merger(a);
ma.run();
Merger mb = new Merger(b);
mb.run();
// Wait for the two other threads to finish
while(!ma.finished || !mb.finished) ;
// Recombine the two arrays
int ia = 0, ib = 0, i = 0;
while(ia != a.length || ib != b.length) {
if (ia == a.length) {
x[i] = b[ib];
ib++;
}
else if (ib == b.length) {
x[i] = a[ia];
ia++;
}
else if (a[ia] < b[ib]) {
x[i] = a[ia];
ia++;
}
else {
x[i] = b[ib];
ib++;
}
i++;
}
finished = true;
}
}
Resulta que la función que no usa multithreading en realidad funciona más rápido. ¿Por qué? ¿El sistema operativo y la máquina virtual Java no se "comunican" con la suficiente eficacia como para colocar los diferentes hilos en diferentes núcleos? ¿O me estoy perdiendo algo obvio?
Cuando tiene un hilo, tiene todos sus datos en el caché. Si divide los datos entre subprocesos, algunos de los datos deben copiarse en la memoria caché del segundo subproceso y luego copiarse nuevamente para la fusión final. Si el costo de la comparación es pequeño, el costo de la copia podría ser mayor. Es posible que descubras que cuantos más hilos uses, mayor será la sobrecarga. –
No veo que llames a Thread.start() en ningún lado. Su fusión se ve rota ya que solo está llamando al método run() todo en un hilo. – Justin
Los programadores realmente necesitan salir de la mentalidad de "un solo hilo": es como si los años ochenta llamaran y quisieran recuperar su CPU 80386 de un solo núcleo. Nos estamos moviendo a un mundo con múltiples núcleos y las mejoras más grandes que se producirán en el futuro se deberán a la ampliación horizontal de varios núcleos. Las personas que se nieguen a aprender los beneficios de múltiples subprocesos producirán API/software de bajo rendimiento. El OP puede verificar mi respuesta: los algoritmos de subprocesos correctos (incluidos los de ordenación) tienen ** propios ** algos de subprocesos múltiples. Superar esto, nos estamos moviendo a un mundo de múltiples núcleos. – SyntaxT3rr0r