Почему использование репликации намного медленнее, чем последовательное выполнение? - PullRequest
Новая
       21

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

4 голосов
/ 23 октября 2010

У меня есть небольшая проблема. Я хотел использовать 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. Так что на самом деле должно быть быстрее:)

Edit2: Из-за ответа Кевина Райта я немного изменил программы, чтобы увеличить время их работы.

Ответы [ 2 ]

3 голосов
/ 24 октября 2010

Взгляните на источник для BigInteger.isProbablePrime (делегаты BigInt для библиотеки Java). Он выполняет большое количество новых BigInteger (), поскольку это неизменный класс.

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

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

2 голосов
/ 23 октября 2010

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

Сначала вы должны запустить тест несколько раз (в пределах одного и того же вызова виртуальной машины), по крайней мере, настолько, чтобы JVM правильно прогревался и работал в течение добрых 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)
  }
}

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

...