Почему использование репликации происходит гораздо медленнее, чем серийное исполнение?

Question

У меня проблема. Я хотел использовать scala.concurrent.ops.replicate для распараллеливания моей программы. Но я узнал, что алгоритм фактически становится намного медленнее. Итак, я написал небольшой тест и получил тот же результат. Итак, вот они.

Серийный код: занимает около 63 секунд, чтобы закончить

object SerTest { 
    def main(args: Array[String]) { 
     for(x <- 1 to 10){ 
     for(i <- 1 to 4) { 
      for(j <- 1 to 100000) { 
      val a = BigInt(j).isProbablePrime(1000) 
      if(!a && j == 100000) println(i + " is ready")}}}}} 

Параллельное Код: занимает около 161 секунд, чтобы закончить

object ParTest { 
    def main(args: Array[String]) { 
     for(x <- 1 to 10){ 
     replicate(1,5) { i => 
      for(j <- 1 to 100000) { 
      val a = BigInt(j).isProbablePrime(1000) 
      if(!a && j == 100000) println(i + " is ready")}}}}} 

Итак, где совершенно очевидно, и неловко ошибок я сделал? :)

Редактировать: Ой, и я запускаю это на Quadcore-CPU. Так что на самом деле это должно быть быстрее :)

Редактировать 2: Из-за ответа Кевина Райт я немного изменил программы, чтобы иметь больше времени для запуска.

Answer 1

Если вы посмотрите на свой пример кода, я бы предположил, что вы прыгаете прямо в основной метод из командной строки. Это самый худший способ, которым вы можете заниматься микропрофилированием в Java!

Вы должны сначала запустить тест для горстки раз (в пределах одной и тот же VM вызова), по крайней мере настолько, что виртуальная машина была должным образом разогревается и работают в течение хороших 30 секунд, прежде чем вы даже думать о запуске для измерения чего-либо. Это обеспечит выполнение компилируемого (и не интерпретируемого) кода и что он полностью оптимизирован.

Вы также должны знать стоимость запуска потоков. Для коротких циклов это будет чрезмерно накладными расходами и будет потреблять больше времени, чем сам цикл!

обновление

следующие определения заимствованы из ops.scala:

val defaultRunner: FutureTaskRunner = TaskRunners.threadRunner 
def spawn(p: => Unit)(implicit runner: TaskRunner = defaultRunner): Unit = {...} 
def replicate(start: Int, end: Int)(p: Int => Unit) {...} 

Таким образом, фактический бегун используется впрыскивается в качестве неявных, или по умолчанию для TaskRunners.threadRunner

Вы можете попробовать изменив это, чтобы использовать пул потоков, префикс вашего кода:

implicit val runner = TaskRunners.threadPoolRunner 

Или я верю следующие будут работать:

import concurrent.TaskRunners.threadPoolRunner 

Смотрите, если это делает никакой разницы

---

На второй мысли ...

Я не думаю, этот параметр на самом деле будет проходить через вложенный вызов до spawn, вероятно, лучше, если вы просто продублируете метод, который вы (в настоящее время у меня есть запрос об этом, опубликованном в списках рассылки).

Для вашего удобства здесь метод в полной, ужасающей, слава:

def replicate(start: Int, end: Int)(p: Int => Unit) { 
    if (start == end) 
    () 
    else if (start + 1 == end) 
    p(start) 
    else { 
    val mid = (start + end)/2 
    spawn { replicate(start, mid)(p) } 
    replicate(mid, end)(p) 
    } 
} 

(вы все еще нужно определить неявную бегун ...)

Answer 2

Посмотрите на источник BigInteger.isProbablePrime (делегаты BigInt в java-библиотеке). Это делает серьезную сумму нового BigInteger(), поскольку это неизменный класс.

Я предполагаю, что выделение памяти вызывает слишком много конфликтов, чтобы извлечь выгоду из распараллеливания. Вероятно, вы можете подтвердить, заменив простой расчет (например, умножив число 100MM вместе) для вашего основного теста. Или переписывайте первичный тест, используя var longs вместо BigInt.

Кроме того, ops.replicate запускает операции в новые потоки, а не использует какой-то пул потоков. Создание темы имеет определенный объем накладных расходов, но недостаточно, чтобы быть проблемой в этом случае. Я лично предпочитаю придерживаться более надежных библиотек java.util.concurrent.