Эффективность / масштабируемость параллельных коллекций в Scala (графики) - PullRequest
Новая
       25

Эффективность / масштабируемость параллельных коллекций в Scala (графики)

2 голосов
/ 16 марта 2012

Итак, я работал с параллельными коллекциями в Scala для графического проекта, над которым я работаю, у меня определены основы класса графа, в настоящее время он использует scala.collection.mutable.HashMap, где ключом является * 1002.* и значение ListBuffer[Int] (список смежности).(РЕДАКТИРОВАТЬ: с тех пор это было изменено на ArrayBuffer[Int]

Я сделал то же самое несколько месяцев назад в C ++, с std::vector<int, std::vector<int> >.

Что я пытаюсь сделатьтеперь выполняется метрика между всеми парами вершин в графе, поэтому в C ++ я сделал что-то вроде этого: 

// myVec = std::vector<int> of vertices
for (std::vector<int>::iterator iter = myVec.begin(); iter != myVec.end(); ++iter) {
    for (std::vector<int>::iterator iter2 = myVec.begin(); 
        iter2 != myVec.end(); ++iter2) {
        /* Run algorithm between *iter and *iter2 */
    }
}

Я сделал то же самое в Scala, распараллелив (или попытался), выполнив это: 

// vertexList is a List[Int] (NOW CHANGED TO Array[Int] - see below)
vertexList.par.foreach(u =>
  vertexList.foreach(v =>
    /* Run algorithm between u and v */
  )
)

Версия C ++ явно однопоточная, версия Scala имеет .par, поэтому она использует параллельные коллекции и многопоточна на 8 ядрах (на одной машине). Однако версия C ++ обработана305 570 пар за промежуток времени, равный примерно 3 дням, в то время как версия Scala обработала только 23 573 за 17 часов.

При условии, что я правильно выполнил math , однопоточная версия C ++примерно в 3 раза быстрее, чем версия Scala. Действительно ли Scala намного медленнее, чем C ++, или я совершенно неправильно использую Scala (я только недавно начал - у меня около 300 страниц по программированию в Scala)?

Спасибо! -kstruct

РЕДАКТИРОВАТЬ Чтобы использовать цикл while, могу ли я сделать что-то вроде .. 

// Where vertexList is an Array[Int]
vertexList.par.foreach(u =>
  while (i <- 0 until vertexList.length) {
    /* Run algorithm between u and vertexList(i) */
  }
}

Если вы, ребята, хотите использовать цикл while для всего, есть ли эквивалент.par.foreach какое-то время?

РЕДАКТИРОВАТЬ2 Подождите секунду, этот код даже не прав - мой плохой.Как бы я распараллелить это, используя циклы while?Если у меня есть var i, который отслеживает итерацию, то не все ли потоки будут делиться этим i?

Ответы [ 3 ]

4 голосов
/ 17 марта 2012

Из ваших комментариев я вижу, что вы обновляете общий изменяемый файл HashMap в конце каждого алгоритма.И если вы рандомизируете свои прогулки, общий Random также является предметом спора.

Я рекомендую два изменения:

  1. Используйте .map и .flatMap для возвратанеизменяемая коллекция вместо изменения общей коллекции.
  2. Используйте ThreadLocalRandom (из Akka или Java 7 ), чтобы уменьшить конкуренцию в генераторе случайных чисел
  3. Проверьте остальную часть вашего алгоритма на предмет возможных возможных противоречий.
  4. Вы также можете попробовать запустить внутренний цикл параллельно.Но не зная вашего алгоритма, трудно понять, поможет ли это или навредит.К счастью, запустить все комбинации параллельных и последовательных коллекций очень просто;просто отключите pVertexList и vertexList в приведенном ниже коде.

Примерно так: 

val pVertexList = vertexList.par
val allResult = for {
  u <- pVertexList
  v <- pVertexList
} yield {
  /* Run algorithm between u and v */
  ((u -> v) -> result)
}

Значение allResult будет ParVector[((Int, Int), Int)].Вы можете позвонить .toMap, чтобы преобразовать это в Map.

2 голосов
/ 17 марта 2012

Почему изменчиво?Я не думаю, что есть хорошая параллельная изменяемая карта в Scala 2.9.x - особенно потому, что именно такая структура данных была добавлена ​​в предстоящем Scala 2.10.

С другой стороны ... у вас есть List[Int]?Не используйте это, используйте Vector[Int].Кроме того, вы уверены, что не тратите время в другом месте, делая преобразования из изменяемых карт и буферов в неизменяемые списки?Структуры данных Scala отличаются от структур C ++, поэтому вы, возможно, столкнетесь с проблемами сложности в других частях кода.

Наконец, я думаю, что dave может быть чем-то, когда он спрашивает о конфликте.Если у вас есть разногласия, параллелизм вполне может замедлить ситуацию.Как быстрее / медленнее он будет работать, если вы сделаете не параллельным?Если сделать его не параллельным, это сделает его быстрее, то, скорее всего, у вас возникнут проблемы конкуренции.

0 голосов
/ 16 марта 2012

Я не совсем уверен в этом, но я думаю, что циклы foreach в циклах foreach довольно медленные, потому что создается много объектов. См .: http://scala -programming-language.1934581.n4.nabble.com / for-loop-vs-while-loop-performance-td1935856.html

Попробуйте переписать его, используя цикл while.

Также списки эффективны только для доступа к голове, массивы, вероятно, быстрее.

...