Tratando con la sorprendente falta de ParList en scala.collections.parallel

Question

Así que Scala 2.9 recientemente apareció en las pruebas de Debian, trayendo consigo las colecciones en paralelo novedosas.

Supongamos que tengo un código equivalente a

def expensiveFunction(x:Int):Int = {...} 

    def process(s:List[Int]):List[Int} = s.map(expensiveFunction) 

ahora de la pequeñísima poco que había espigué sobre las colecciones paralelas antes de que los documentos en realidad se convirtió en mi máquina, que estaba esperando para paralelizar esta simplemente cambiando la Lista a un ParList ... pero para mi sorpresa, ¡no hay ninguno! (Solo ParVector, ParMap, ParSet ...).

Como workround, este (o una sola línea equivalente) parece que funciona bastante bien:

def process(s:List[Int]):List[Int} = { 
    val ps=scala.collection.parallel.immutable.ParVector()++s 
    val pr=ps.map(expensiveFunction) 
    List()++pr 
    } 

produciendo una mejora del rendimiento x3 aproximadamente en mi código de prueba y alcanzar masivamente mayor uso de la CPU (de cuatro núcleos más hyperthreading i7). Pero parece un poco torpe.

Mi pregunta es una especie de agregado:

• Por qué no hay un ParList?
• Dado que no hay un ParList, ¿hay un mejor patrón/modismo de que deba adoptar para que no me parezca que se están perdiendo?
• solo estoy "detrás de los tiempos" Utilizar listas mucho en mis programas Scala (como todos los libros Scala I comprado de nuevo en los 2,7 días me enseñó) y que realmente debería hacer un mayor uso de Vectors? (Quiero decir, en C++ tierra generalmente necesitaría una muy buena razón para usar std::list sobre std::vector).

Answer 1

En primer lugar, permítame mostrarle cómo hacer una versión paralela de ese código:

def expensiveFunction(x:Int):Int = {...} 

def process(s:List[Int]):Seq[Int] = s.par.map(expensiveFunction).seq 

que tendrán figura Scala cosas para usted - y, por cierto, se utiliza ParVector. Si realmente desea List, llame al .toList en lugar de .seq.

En cuanto a las preguntas:

• No hay una ParList porque un List es una estructura de datos intrínsecamente no paralela, ya que cualquier intervención directa, requiere de recorrido.

• Debe codificar los rasgos en lugar de las clases - Seq, ParSeq y GenSeq, por ejemplo. Incluso las características de rendimiento de List están garantizadas por LinearSeq.

• Todos los libros anteriores a Scala 2.8 no tenían la nueva biblioteca de colecciones en mente. En particular, las colecciones realmente no compartían una API consistente y completa. Ahora lo hacen, y ganarás mucho al aprovecharlo.

  Además, no había una colección como Vector en Scala 2.7 - una colección inmutable con (casi) acceso indexado constante.

Answer 2

List s son grandes cuando se desea la coincidencia de patrones (es decir case x :: xs) y para una eficiente prepending/iteración. Sin embargo, no son tan geniales cuando desea un acceso rápido por índice, o dividir en fragmentos, o unirse (es decir, xs ::: ys).

Por lo tanto, no tiene mucho sentido (para tener un paralelo List) cuando se piensa que este tipo de cosas (la división y unión) es exactamente lo que se necesita para el paralelismo eficiente. Uso:

xs.toIndexedSeq.par 

Answer 3

Un List no se puede dividir fácilmente en varias sub-listas que hace que sea difícil de paralelizar. Por un lado, tiene acceso O (n); también un List no puede despojar a su cola, por lo que es necesario incluir un parámetro de longitud.

Supongo que tomar una Vector será la mejor solución.

Tenga en cuenta que Vector de Scala es diferente de std::vector. Este último es básicamente un envoltorio alrededor de la matriz estándar, un bloque contiguo en la memoria que debe ser copiado de vez en cuando al agregar o eliminar datos. El Vector de Scala es una estructura de datos especializada que permite copiar y dividir de forma eficiente, al tiempo que mantiene los datos inmutables.