Параллельный Массив
Последовательность 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):
head | tail | apply | update | prepend | append | insert | |
---|---|---|---|---|---|---|---|
ParArray |
C | L | C | C | L | L | L |
ParVector |
eC | eC | eC | eC | eC | eC | - |
ParRange |
C | C | C | - | - | - | - |
Характеристики производительности множеств (set) и ассоциативных массивов (map):
lookup | add | remove | |
---|---|---|---|
неизменяемые | |||
ParHashSet /ParHashMap |
eC | eC | eC |
изменяемые | |||
ParHashSet /ParHashMap |
C | C | C |
ParTrieMap |
eC | eC | eC |
Расшифровка
Обозначения в двух представленных выше таблицах означают следующее:
C | Операция (быстрая) выполняется за постоянное время. |
eC | Операция выполняется за фактически постоянное время, но только при соблюдении некоторых предположений, например о максимальной длине вектора или распределении хэш-кодов. |
aC | Операция выполняется за амортизированное постоянное время. Некоторые вызовы операции могут выполняться медленнее, но при подсчете времени выполнения большого количества операций выходит, что в среднем на операцию требуется постоянное время. |
Log | Операция занимает время, пропорциональное логарифму размера коллекции. |
L | Операция линейна, то есть занимает время, пропорциональное размеру коллекции. |
- | Операция не поддерживается. |
Первая таблица трактует последовательные типы– изменяемые и неизменяемые– в контексте выполнения следующих операций:
head | Получение первого элемента последовательности. |
tail | Получение новой последовательности, состоящей из всех элементов исходной, кроме первого. |
apply | Индексирование. |
update | Функциональное обновление (с помощью updated ) для неизменяемых последовательностей, обновление с побочными действиями (с помощью update ) для изменяемых. |
prepend | Добавление элемента в начало последовательности. Для неизменяемых последовательностей создается новая последовательность, для изменяемых– модифицируется существующая. |
append | Добавление элемента в конец последовательности. Для неизменяемых последовательностей создается новая последовательность, для изменяемых– модифицируется существующая. |
insert | Вставка элемента в выбранную позицию последовательности. Поддерживается только изменяемыми последовательностями. |
Вторая таблица рассматривает изменяемые и неизменяемые множества и ассоциативные массивы в контексте следующих операций:
lookup | Проверка принадлежности элемента множеству, или получение значения, ассоциированного с ключом. |
add | Добавление нового элемента во множество или новой пары ключ/значение в ассоциативный массив. |
remove | Удаление элемента из множества или ключа из ассоциативного массива. |
min | Минимальный элемент множества или минимальный ключ ассоциативного массива. |