Устранение неожиданного отсутствия ParList в scala.collections.parallel

Итак, scala 2.9 недавно появился в тестировании Debian, принеся с собой новомодные параллельные коллекции.

Предположим, у меня есть код, эквивалентный

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

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

Теперь, когда я немного узнал о параллельных коллекциях до того, как документы действительно появились на моей машине, я ожидал распараллелить это, просто переключив список на ParList... но, к моему удивлению, его нет! (Просто ParVector, ParMap, ParSet...).

В качестве обходного пути это (или однострочный эквивалент), похоже, работает достаточно хорошо:

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

что привело к увеличению производительности примерно в 3 раза в моем тестовом коде и значительному увеличению использования ЦП (четырехъядерный процессор плюс гиперпоточность i7). Но выглядит как-то коряво.

Мой вопрос является своего рода агрегированным:

  • Почему нет ParList ?
  • Учитывая, что ParList нет, есть ли лучший шаблон/идиома, который я должен принять, чтобы я не чувствовал, что они отсутствуют?
  • Я просто «отстал от времени», часто используя списки в своих программах Scala (как и все книги Scala, которые я купил за 2,7 дня, научили меня), и мне действительно следует больше использовать Vectors ? (Я имею в виду, что в стране С++ мне обычно нужна довольно веская причина, чтобы использовать std::list вместо std::vector).

list scala parallel-processing map scala-collections
person timday    schedule 10.07.2011    source источник

Ответы (3)


arrow_upward
8
arrow_downward

Во-первых, позвольте мне показать вам, как сделать параллельную версию этого кода:

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

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

Это заставит Scala разобраться за вас — и, кстати, он использует ParVector. Если вы действительно хотите List, позвоните .toList вместо .seq.

Что касается вопросов:

  • ParList не существует, потому что List по своей сути является непараллельной структурой данных, поскольку любая операция с ней требует обхода.

  • Вы должны кодировать черты вместо классов — например, Seq, ParSeq и GenSeq. Даже рабочие характеристики List гарантируются LinearSeq.

  • Все книги до Scala 2.8 не имели в виду новую библиотеку коллекций. В частности, у коллекций действительно не было согласованного и полного API. Теперь они есть, и вы много выиграете, воспользовавшись этим.

    Более того, в Scala 2.7 не было такой коллекции, как Vector, — неизменяемой коллекции с (почти) постоянным индексированным доступом.

person Daniel C. Sobral    schedule 10.07.2011

arrow_upward
15
arrow_downward

List отлично подходят, когда вам нужно сопоставление с образцом (например, case x :: xs) и для эффективного добавления/итерации. Однако они не так хороши, когда вам нужен быстрый доступ по индексу, разделение на куски или объединение (например, xs ::: ys).

Следовательно, не имеет большого смысла (иметь параллельный List), если вы думаете, что такого рода вещи (разделение и объединение) именно необходимы для эффективного параллелизма. Использовать:

xs.toIndexedSeq.par
person oxbow_lakes    schedule 10.07.2011

arrow_upward
7
arrow_downward

List нельзя легко разделить на различные подсписки, что затрудняет распараллеливание. Во-первых, он имеет доступ O(n); также List не может обрезать свой хвост, поэтому необходимо включить параметр длины.

Думаю, Vector будет лучшим решением.

Обратите внимание, что Vector в Scala отличается от std::vector. Последний в основном представляет собой оболочку стандартного массива, непрерывный блок в памяти, который необходимо время от времени копировать при добавлении или удалении данных. Scala Vector — это специализированная структура данных, которая позволяет эффективно копировать и разбивать данные, сохраняя при этом неизменными сами данные.

person Debilski    schedule 10.07.2011