Головоломка Scala параллельной коллекции во время исполнения

Question

Редактировать: размер моей выборки был слишком мал. Когда я проверил его на реальных данных 8 процессоров, я увидел увеличение скорости в 7,2 раза. Не так уж плохо для добавления 4 символов в мой код;)

В настоящее время я пытаюсь «продать» управление преимуществами использования Scala, особенно когда речь идет о масштабировании с использованием процессоров. С этой целью я создал простое тестовое приложение, которое выполняет кучу векторной математики, и был немного удивлен, обнаружив, что время выполнения на моей четырехъядерной машине заметно не улучшилось. Интересно, что я обнаружил, что время выполнения является худшим в первый раз, когда вы проходите сбор, и становится лучше с последующими вызовами. Есть ли какие-то ленивые вещи в параллельной коллекции, которые вызывают это, или я просто делаю это неправильно? Следует отметить, что я из мира C ++ / C #, поэтому вполне возможно, что я как-то испортил свою конфигурацию. В любом случае, вот мои настройки:

Плагин InteliJ Scala

Scala 2.9.1. Финал

64-разрядная версия Windows 7, четырехъядерный процессор (без гиперпоточности)

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")
    }
  }
}

Вывод этой программы:

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

Так что здесь происходит? Первые 2 раза мы делаем фильтр, он работает медленнее, а потом все ускоряется? Я понимаю, что изначально при запуске параллелизма будут возникать издержки, я просто пытаюсь выяснить, где имеет смысл выражать параллелизм в моем приложении, и, в частности, я хочу показать Management, что программа запускается 3-4 раза. быстрее на Quad Core Box. Разве это не хорошая проблема?

Идеи

Answer 1

У вас микробиктограмма.Скорее всего, вы тестируете этап компиляции JIT.Сначала вам нужно согреть свой JIT с помощью предварительного прогона.

Вероятно, лучшая идея состоит в том, чтобы использовать инфраструктуру микро-бенчмаркинга, такую ​​как http://code.google.com/p/caliper/, которая обрабатывает все это для вас.

Редактировать : Есть хороший SBT шаблон для бенчмаркинга Caliper для проектов Scala, на который ссылается из этого поста в блоге

Answer 2

Вещи ускоряются, но это не имеет ничего общего с параллельным или последовательным, вы не сравниваете яблоки с яблоками. В JVM есть JIT (как раз вовремя) компилятор, который скомпилирует некоторый байт-код только после того, как код будет использован определенное количество раз. Итак, что вы видите в первых итерациях, это медленное выполнение кода, который еще не является JIT, а также время для самой продолжающейся JIT-компиляции. Удаление .par так, чтобы оно было последовательным , вот что я вижу на своей машине (итерация в 10 раз меньше, потому что я использую более старую машину):

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

Но это все последовательно! Вы можете увидеть, что JVM делает с точки зрения JIT, используя JVM -XX:+PrintCompilation (установите в JAVA_OPTS или используйте опцию -J-XX:+PrintCompilation scala. На первых итерациях вы увидите большое количество операторов печати JVM, показывающих, что такое JIT затем стабилизируется.

Итак, чтобы сравнить яблоки с яблоками, вы сначала запускаете без пар, затем добавляете пар и запускаете ту же программу. На моем двухъядерном процессоре при использовании .par получаю:

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

Так что примерно в два раза ускорение, когда оно станет стабильным.

В связанной заметке другая вещь, с которой вы должны быть осторожны, это бокс и распаковка, особенно если вы сравниваете только с Java. Функции высокого порядка в библиотеке scala, такие как filter, выполняют упаковку и распаковку примитивных типов, и это обычно является источником первоначального разочарования для тех, кто конвертирует код из Java в Scala.

Хотя это и не применяется в этом случае, поскольку for выходит за пределы времени, есть также некоторые затраты на использование for вместо while, но компилятор 2.9.1 должен делать достойную работу, когда используя -optimize скалярный флаг.

Answer 3

Помимо упомянутых выше оптимизаций JIT, ключевая концепция, которую вам необходимо оценить, заключается в том, склоняется ли ваша проблема к распараллеливанию: присущи затраты на разделение, координацию потоков и объединение, которые отягощают преимущество параллельных операций.Scala скрывает от вас эту сложность, но вам нужно знать, когда применять ее для достижения хороших результатов.

В вашем случае, несмотря на то, что вы выполняете огромное количество операций, каждая отдельная операция является почти ЦПтривиальный.Чтобы увидеть параллельные коллекции в действии, попробуйте операцию, которая является тяжелой на единичной основе.

Для аналогичной презентации Scala я использовал простой (неэффективный) алгоритм, чтобы вычислить, является ли число простым числом: def isPrime(x:Int) = (2 to x/2).forall(y=>x%y!=0)

Затем используйте ту же логику, которую вы представили, чтобы определить числа в коллекции, которые являются простыми:

val col = 1 to 1000000
col.filter(isPrime(_))  // sequential
col.par.filter(isPrime(_)) // parallel

Поведение процессора действительно показало разницу между ними:

Время было в 3,5 раза лучше для параллельных сборок в 4-ядерном процессоре.

Answer 4

как насчет

val numTargetsInRange_sequential = parTargets.filter(within50)

Кроме того, вы, вероятно, получите более впечатляющие результаты с картой, а не с фильтром.