Конкретные классы параллельных коллекций

Параллельный Массив

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

scala> val pa = scala.collection.parallel.mutable.ParArray.tabulate(1000)(x => 2 * x + 1)
pa: scala.collection.parallel.mutable.ParArray[Int] = ParArray(1, 3, 5, 7, 9, 11, 13,...

scala> pa reduce (_ + _)
res0: Int = 1000000

scala> pa map (x => (x - 1) / 2)
res1: scala.collection.parallel.mutable.ParArray[Int] = ParArray(0, 1, 2, 3, 4, 5, 6, 7,...

Реализация разбивки параллельного массива разделителями сводится к созданию двух новых разделителей с последующим обновлением их итерационных индексов. Компоновщики играют более заметную роль. Так как мы не знаем заранее количество элементов (и следовательно, размер массива) при выполнении большинства методов трансформации (например, flatMap, filter, takeWhile, и т.д.), каждый компоновщик, в сущности, является массивом-буфером, у которого операция += требует для выполнения амортизированное постоянное время. Разные процессоры добавляют элементы к отдельным компоновщикам параллельного массива, которые потом по цепочке объединяют свои внутренние массивы. Лежащий в основе массив размещается и параллельно заполняется только после того, как становится известным общее число элементов. По этой причине методы трансформации требуют больше ресурсов, чем методы получения доступа. Также стоит заметить, что финальное размещение массива выполняется JVM последовательно, поэтому этот момент может стать узким местом, если даже сама операция отображения весьма нересурсоемкая.

Вызов метода seq приводит к преобразованию параллельного массива в коллекцию ArraySeq, которая является его последовательным аналогом. Такое преобразование эффективно, и в основе ArraySeq остается тот же массив, что и был у исходного параллельного.

Параллельный вектор

ParVector является неизменяемой последовательностью, временная сложность доступа и обновления которой является логарифмической с низкой константой-множителем.

scala> val pv = scala.collection.parallel.immutable.ParVector.tabulate(1000)(x => x)
pv: scala.collection.parallel.immutable.ParVector[Int] = ParVector(0, 1, 2, 3, 4, 5, 6, 7, 8, 9,...

scala> pv filter (_ % 2 == 0)
res0: scala.collection.parallel.immutable.ParVector[Int] = ParVector(0, 2, 4, 6, 8, 10, 12, 14, 16, 18,...

Неизменяемые векторы представлены 32-ичными деревьями (32-way trees), поэтому разделители разбивают их, назначая по поддереву каждому новому разделителю. Компоновщики в настоящий момент хранят вектор из элементов и компонуют путем отложенного копирования. По этой причине методы трансформации менее масштабируемы по сравнению с теми же методами параллельного массива. Как только в будущем релизе Scala станет доступной операция конкатенации векторов, компоновщики станут образовываться путем конкатенации, и от этого методы трансформации станут гораздо более эффективными.

Параллельный вектор является параллельным аналогом последовательной коллекции Vector, и преобразования одного в другое занимают постоянное время.

Параллельный диапазон

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

scala> (1 to 3).par
res0: scala.collection.parallel.immutable.ParRange = ParRange(1, 2, 3)

scala> (15 to 5 by -2).par
res1: scala.collection.parallel.immutable.ParRange = ParRange(15, 13, 11, 9, 7, 5)

Подобно тому, как последовательные диапазоны не имеют строителей, параллельные диапазоны не имеют компоновщиков. При создании отображения (mapping) элементов параллельного диапазона получается параллельный вектор. Последовательные и параллельные диапазоны могут эффективно преобразовываться друг в друга вызовами методов seq и par.

Параллельные хэш-таблицы

В основе параллельной хэш-таблицы лежит массив, причем место элемента таблицы в этом массиве определяется хэш-кодом элемента. На хэш-таблицах основаны параллельные изменяемые хэш-множества (mutable.ParHashSet) и параллельные изменяемые ассоциативные хэш-массивы (хэш-отображения) (mutable.ParHashMap).

scala> val phs = scala.collection.parallel.mutable.ParHashSet(1 until 2000: _*)
phs: scala.collection.parallel.mutable.ParHashSet[Int] = ParHashSet(18, 327, 736, 1045, 773, 1082,...

scala> phs map (x => x * x)
res0: scala.collection.parallel.mutable.ParHashSet[Int] = ParHashSet(2181529, 2446096, 99225, 2585664,...

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

Последовательные хэш-отображения и хэш-множества могут преобразовываться в свои параллельные аналоги с помощью метода par. Внутри параллельной хэш-таблицы требуется поддерживать карту размеров, которая отслеживает количество элементов в различных ее частях. Это значит, что при первом преобразовании последовательной хэш-таблицы в параллельную, вся она просматривается с целью создания карты размеров - по этой причине первый вызов метода par требует линейного по отношению к числу элементов времени выполнения. При дальнейших изменениях хэш-таблицы ее карта размеров поддерживается в актуальном состоянии, поэтому последующие преобразования вызовами par и seq имеют постоянную сложность. Впрочем, поддержку карты размеров можно и отключить, используя метод useSizeMap хэш-таблицы. Важный момент: изменения, сделанные в последовательной хэш-таблице, видны в параллельной, и наоборот.

Параллельные префиксные хэш-деревья (Hash Tries)

Параллельные префиксные хэш-деревья являются параллельным аналогом неизменяемых префиксных хэш-деревьев, которые используются для эффективного представления неизменяемых множеств и ассоциативных массивов. Последние представлены классами immutable.ParHashSet и immutable.ParHashMap.

scala> val phs = scala.collection.parallel.immutable.ParHashSet(1 until 1000: _*)
phs: scala.collection.parallel.immutable.ParHashSet[Int] = ParSet(645, 892, 69, 809, 629, 365, 138, 760, 101, 479,...

scala> phs.map(x => x * x).sum
res0: Int = 332833500

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

Параллельные хэш-деревья могут за постоянное время преобразовываться вызовами методов seq и par в последовательные хэш-деревья и обратно.

Параллельные многопоточные префиксные деревья (Concurrent Tries)

Параллельным аналогом коллекции concurrent.TrieMap, представляющей собой многопоточный и потокозащищеный ассоциативный массив, является коллекция mutable.ParTrieMap. В то время, как большинство многопоточных структур данных не гарантируют правильного перебора элементов в случае, если эта структура данных была изменена во время ее прохождения, многопоточные деревья Ctries гарантируют, что обновленные данные станут видны только при следующем прохождении. Это означает, что можно изменять многопоточное дерево прямо во время прохождения, как в следующем примере, в котором выводятся квадратные корни от 1 до 99:

scala> val numbers = scala.collection.parallel.mutable.ParTrieMap((1 until 100) zip (1 until 100): _*) map { case (k, v) => (k.toDouble, v.toDouble) }
numbers: scala.collection.parallel.mutable.ParTrieMap[Double,Double] = ParTrieMap(0.0 -> 0.0, 42.0 -> 42.0, 70.0 -> 70.0, 2.0 -> 2.0,...

scala> while (numbers.nonEmpty) {
     |   numbers foreach { case (num, sqrt) =>
	 |     val nsqrt = 0.5 * (sqrt + num / sqrt)
	 |     numbers(num) = nsqrt
	 |     if (math.abs(nsqrt - sqrt) < 0.01) {
	 |       println(num, nsqrt)
	 |		 numbers.remove(num)
	 |	   }
	 |   }
	 | }
(1.0,1.0)
(2.0,1.4142156862745097)
(7.0,2.64576704419029)
(4.0,2.0000000929222947)
...

Компоновщики реализованы как TrieMap– так как эта структура является многопоточной, при вызове метода трансформации создается только один компоновщик, разделяемый всеми процессорами.

Как и в случае с другими параллельными изменяемыми коллекциями, экземпляры TrieMap и параллельных ParTrieMap, полученные вызовом методов seq или par, хранят данные в одном и том же хранилище, поэтому модификации одной коллекции видны в другой. Такие преобразования занимают постоянное время.

Характеристики производительности

Характеристики производительности последовательных типов (sequence types):

Характеристики производительности множеств (set) и ассоциативных массивов (map):

Расшифровка

Обозначения в двух представленных выше таблицах означают следующее:

Первая таблица трактует последовательные типы– изменяемые и неизменяемые– в контексте выполнения следующих операций:

Вторая таблица рассматривает изменяемые и неизменяемые множества и ассоциативные массивы в контексте следующих операций: