Ordenar 20 millones partiendo en dos: cuántos hilos y cuál mezcla corre sola
La recursión de ordenar_par dibujada por niveles. Elija hasta
qué profundidad se lanzan hilos, prediga cuántos nacen y después recorra los pasos en
el orden en que el código los ejecuta.
1. El árbol según la profundidad de corte
ahora 2
hilo nuevoel hilo que ya veníahoja: se ordena de corrido
Cada división lanza un hilo para la mitad izquierda; la derecha la
resuelve el hilo que ya estaba ahí. Una llamada deja de partir cuando se acaba el
presupuesto de profundidad o cuando el trozo baja de 10.000 elementos.
2. Antes de mover la perilla
¿Cuántos hilos se crean con profundidad 3?
3. Paso a paso, en el orden del código
La traza sigue al hilo principal. Cada hilo lanzado repite el mismo
recorrido por su cuenta; aquí se ve cuándo se lanza y cuándo el principal lo espera.
Verde: rangos que ya quedaron ordenados.
4. Qué sucede al medirlo
Profundidad
Hilos
Tiempo
Aceleración
Medido con taskset -c 0-3, cuatro núcleos. La versión
secuencial tarda 2.227 ms y std::sort 1.469 ms sobre los mismos datos.
La mezcla del nivel 0, medida aparte, 83 ms.
Con cuatro núcleos, ¿por qué ocho hilos (profundidad 3)
aún ganan sobre cuatro (profundidad 2)?