Scala parallel collection tiempo de ejecución desconcertante
runtime scalability (4)
Editar: Mi tamaño de muestra fue demasiado pequeño. Cuando lo ejecuté contra los datos reales en 8 CPUs, vi un aumento de velocidad de 7.2x. No está nada mal para agregar 4 caracteres a mi código;)
Actualmente estoy en el proceso de tratar de "vender" a la administración los beneficios de usar Scala, especialmente cuando se trata de escalar con CPU. Con ese fin, creé una aplicación de prueba simple que hace un montón de matemáticas vectoriales y me sorprendió un poco descubrir que el tiempo de ejecución no era notablemente mejor en mi máquina de cuatro núcleos. Curiosamente, descubrí que el tiempo de ejecución es el peor la primera vez que revisas la colección y mejora con las llamadas posteriores. ¿Hay algunas cosas perezosas en la colección paralela que están causando esto, o lo estoy haciendo mal? Cabe señalar que vengo del mundo C ++ / C #, por lo que es muy posible que haya estropeado mi configuración de alguna manera. De todos modos, aquí está mi configuración:
Complemento InteliJ Scala
Scala 2.9.1.final
Procesador de cuatro núcleos Windows 7 de 64 bits (sin hyperthreading)
import util.Random
// simple Vector3D class that has final x,y,z components a length, and a ''-'' function
class Vector3D(val x:Double, val y:Double, val z:Double)
{
def length = math.sqrt(x*x+y*y+z*z)
def -(rhs : Vector3D ) = new Vector3D(x - rhs.x, y - rhs.y, z - rhs.z)
}
object MainClass {
def main(args : Array[String]) =
{
println("Available CPU''s: " + Runtime.getRuntime.availableProcessors())
println("Parallelism Degree set to: " + collection.parallel.ForkJoinTasks.defaultForkJoinPool.getParallelism);
// my position
val myPos = new Vector3D(0,0,0);
val r = new Random(0);
// define a function nextRand that gets us a random between 0 and 100
def nextRand = r.nextDouble() * 100;
// make 10 million random targets
val targets = (0 until 10000000).map(_ => new Vector3D(nextRand, nextRand, nextRand)).toArray
// take the .par hit before we start profiling
val parTargets = targets.par
println("Created " + targets.length + " vectors")
// define a range function
val rangeFunc : (Vector3D => Double) = (targetPos) => (targetPos - myPos).length
// we''ll select ones that are <50
val within50 : (Vector3D => Boolean) = (targetPos) => rangeFunc(targetPos) < 50
// time it sequentially
val startTime_sequential = System.currentTimeMillis()
val numTargetsInRange_sequential = targets.filter(within50)
val endTime_sequential = System.currentTimeMillis()
println("Sequential (ms): " + (endTime_sequential - startTime_sequential))
// do the parallel version 10 times
for(i <- 1 to 10)
{
val startTime_par = System.currentTimeMillis()
val numTargetsInRange_parallel = parTargets.filter(within50)
val endTime_par = System.currentTimeMillis()
val ms = endTime_par - startTime_par;
println("Iteration[" + i + "] Executed in " + ms + " ms")
}
}
}
El resultado de este programa es:
Available CPU''s: 4
Parallelism Degree set to: 4
Created 10000000 vectors
Sequential (ms): 216
Iteration[1] Executed in 227 ms
Iteration[2] Executed in 253 ms
Iteration[3] Executed in 76 ms
Iteration[4] Executed in 78 ms
Iteration[5] Executed in 77 ms
Iteration[6] Executed in 80 ms
Iteration[7] Executed in 78 ms
Iteration[8] Executed in 78 ms
Iteration[9] Executed in 79 ms
Iteration[10] Executed in 82 ms
Entonces, ¿qué está pasando aquí? Las primeras 2 veces que hacemos el filtro, es más lento, y luego las cosas se aceleran? Entiendo que habrá un costo de inicio de paralelismo intrínsecamente, solo estoy tratando de descubrir dónde tiene sentido expresar el paralelismo en mi aplicación, y específicamente quiero poder mostrar a la Administración un programa que se ejecuta 3-4 veces más rápido en una caja de cuatro núcleos. ¿Esto no es un buen problema?
Ideas?
Junto a las optimizaciones JIT mencionadas anteriormente, un concepto clave que debe evaluar es si su problema se basa en la paralelización: hay un costo inherente de división, coordinación de subprocesos y unión que pesa sobre la ventaja de hacer las cosas en paralelo. Scala oculta esta complejidad, pero necesita saber cuándo aplicarla para obtener buenos resultados.
En su caso, aunque está realizando una gran cantidad de operaciones, cada operación en sí misma es casi trivial en la CPU. Para ver las colecciones paralelas en acción, intente una operación que sea pesada en una unidad.
Para una presentación similar de Scala, utilicé un algoritmo simple (ineficaz) para calcular si un número es primo: def isPrime(x:Int) = (2 to x/2).forall(y=>x%y!=0)
Luego use la misma lógica que presentó para determinar los números en una colección que son primos:
val col = 1 to 1000000
col.filter(isPrime(_)) // sequential
col.par.filter(isPrime(_)) // parallel
El comportamiento de la CPU realmente mostró la diferencia entre ambos:
El tiempo fue aproximadamente 3,5 veces mejor para las colecciones paralelas en una CPU de 4 núcleos.
Las cosas se aceleran, pero eso no tiene nada que ver con paralelo versus secuencia, no estás comparando manzanas con manzanas. La JVM tiene un compilador JIT (justo a tiempo) que compilará un código de bytes solo después de usar el código una cierta cantidad de veces. Entonces, lo que se ve en las primeras iteraciones es una ejecución más lenta para el código que aún no está JIT-ed, así como el tiempo para la compilación de JIT en curso. Quitar el .par para que todo sea secuencial aquí es lo que veo en mi máquina (10 veces menos iteración porque estoy usando una máquina más antigua):
Sequential (ms): 312
Iteration[1] Executed in 117 ms
Iteration[2] Executed in 112 ms
Iteration[3] Executed in 112 ms
Iteration[4] Executed in 112 ms
Iteration[5] Executed in 114 ms
Iteration[6] Executed in 113 ms
Iteration[7] Executed in 113 ms
Iteration[8] Executed in 117 ms
Iteration[9] Executed in 113 ms
Iteration[10] Executed in 111 ms
¡Pero todo es secuencial! Puede ver lo que hace JVM en términos de JIT utilizando JVM -XX:+PrintCompilation (establecido en JAVA_OPTS o use -J-XX:+PrintCompilation opción de -J-XX:+PrintCompilation . En las primeras iteraciones verá un gran número de instrucciones de impresión de JVM mostrando lo que está siendo JIT-ed, luego se estabiliza más adelante.
Entonces, para comparar manzanas con manzanas, primero se ejecuta sin el par, luego se agrega el par y se ejecuta el mismo programa. En mi doble núcleo, cuando uso .par obtengo:
Sequential (ms): 329
Iteration[1] Executed in 197 ms
Iteration[2] Executed in 60 ms
Iteration[3] Executed in 57 ms
Iteration[4] Executed in 58 ms
Iteration[5] Executed in 59 ms
Iteration[6] Executed in 73 ms
Iteration[7] Executed in 56 ms
Iteration[8] Executed in 60 ms
Iteration[9] Executed in 58 ms
Iteration[10] Executed in 57 ms
Así que más o menos una aceleración de 2x una vez que es estable.
En una nota relacionada, la otra cosa con la que debes tener cuidado es boxear y des-boxear, especialmente si estás comparando con solo Java. Las funciones de alto orden de la biblioteca scala como filtro están haciendo boxeo y desacoplando tipos primitivos, y esto suele ser una fuente de decepción inicial para aquellos que convierten código de Java a Scala.
Aunque no se aplica en este caso, ya que la for está fuera del tiempo, también hay algún costo por usar for lugar de while , pero el compilador 2.9.1 debería estar haciendo un trabajo decente al usar el -optimize -optimize scalac.
qué tal si
val numTargetsInRange_sequential = parTargets.filter(within50)
?
Además, es probable que obtenga resultados más impresionantes con un mapa en lugar de una operación de filtro.
Usted tiene la enfermedad micro-benchmark. Lo más probable es que compares la fase de compilación JIT. Necesitarás calentar primero tu JIT con una prueba previa.
Probablemente la mejor idea es utilizar un marco de micro-benchmarking como http://code.google.com/p/caliper/ que maneje todo eso por usted.
Editar : Hay una buena plantilla de SBT para los proyectos de Scala de referencia de Caliper, como se menciona en esta publicación de blog